A matching from $X$ to $Y$ is a set of pairwise vertex-disjoint edges that covers every vertex of $X$. Equivalently, it chooses for each $x\in X$ a distinct neighbour in $Y$.

Hall marriage theorem says that such a matching exists if and only ifNecessity is immediate: the distinct partners of the vertices in $S$ all belong to $N(S)$.

For sufficiency, induct on $|X|$. The claim is clear when $|X|=1$. First suppose every nonempty proper $S\subset X$ satisfies the strict inequality $|N(S)|\ge |S|+1$. Choose an edge $xy$ and delete $x$ and $y$. For $S\subseteq X\setminus \{x\}$, deletion removes at most one neighbour, soInduction gives a matching of $X\setminus \{x\}$, and adding $xy$ completes it.

Otherwise there is a nonempty proper $S\subset X$ with $|N(S)|=|S|$. Hall's condition holds in the bipartite graph induced by $S\cup N(S)$, so induction matches $S$ onto $N(S)$. For $A\subseteq X\setminus S$,and hence $A$ has at least $|A|$ neighbours outside $N(S)$. Induction therefore matches $X\setminus S$ into $Y\setminus N(S)$. The two matchings are disjoint and together cover $X$.

We describe a collection of finite multiplication patterns. For finite setswriteCall $(E,D)$ $T$-forbidden if the following theory, in $L$ expanded by unary symbols $f_1,\dots ,f_n$, is inconsistent:

Let $T^{\ast }$ contain the group axioms and, for every $T$-forbidden finite pattern, the sentenceThis is a first-order theory in the language of groups.

Suppose $G$ is $T$-good. Choose $M\models T$ and an embedding $\rho :G\hookrightarrow \mathrm{Aut}(M)$. If a tuple $(g_1,\dots ,g_n)$ in $G$ realized a forbidden pattern, interpreting $f_i$ as $\rho (g_i)$ would give a model of its supposedly inconsistent automorphism theory. Thus no such tuple exists, and $G\models T^{\ast }$.

Conversely, suppose $G$ is $T$-bad. By part (e), there is a finite set $X=\{g_1,\dots ,g_n\}\subseteq G$ for which $T_G\cap L_X$ is inconsistent. LetThe associated automorphism theory is precisely $T_G\cap L_X$, up to renaming its function symbols, so $(E,D)$ is $T$-forbidden. But $(g_1,\dots ,g_n)$ realizes $P_{E,D}$ in $G$, and therefore $G$ violates the corresponding forbidding axiom. Hence $G/\models T^{\ast }$.

We have proved

Take $T_f$ to consist of $T$ together with the following sentences.

This includes $f(c)=c$ for each constant symbol $c$.

The first pair of axioms makes the interpretation $\vartheta$ a bijection. The remaining schemes say exactly that it preserves every operation and relation, so $(M,\vartheta )\models T_f$ exactly when $M\models T$ and $\vartheta \in \mathrm{Aut}(M)$.

Finally, $T$ is consistent and hence has a model $M$ by part (b). Expanding $M$ by interpreting $f$ as the identity automorphism gives a model of $T_f$, so $T_f$ is consistent.

The compactness theorem states that a set $T$ of first-order sentences has a model if and only if every finite subset of $T$ has a model.

The forward implication follows by using the same model for every finite subset. Conversely, suppose every finite subset of $T$ has a model. If $T$ were inconsistent, a formal derivation of $\perp$ from $T$ would use only finitely many assumptions, say those in $T_0\subseteq T$. Then $T_0$ would be inconsistent. By part (b), $T_0$ would have no model, contrary to the hypothesis. Thus $T$ is consistent, and part (b) gives a model of $T$.

Suppose first that $M\models T$. By the soundness theorem for first-order logic, every theorem of $T$ is true in $M$. A contradiction cannot be true in a structure, so $T$ is consistent.

Conversely, the Godel completeness theorem says that every semantically valid consequence is derivable. Its equivalent model-existence form says directly that every consistent first-order theory has a model. Hence

Since $r$ is even,The first factor is not divisible by $N$, since that would contradict minimality of $r$, and the second is not divisible by $N$ by hypothesis. Nevertheless their product is divisible by $N$. Thereforeand Euclid's algorithm computes a nontrivial factor. One can also compute $\gcd (a^{r/2}+1,N)$; together the two gcds expose factors lying on opposite sides of the congruence $a^{r/2}\equiv \pm 1$ modulo the prime-power divisors of $N$.

Defineusing the inverse of $a$ for negative $x$. Since $a^r\equiv 1$, $f(x+r)=f(x)$. Conversely, if $f(x)=f(y)$ then $a^{x-y}\equiv 1$, so the definition of order gives $r\mid x-y$. Two integers in the same block of $r$ consecutive integers cannot differ by a nonzero multiple of $r$. Hence $f$ is one-to-one within each period.

The order of $a$ modulo $N$ is the least positive integer $r$ such thatIt exists because $a$ is a unit in the finite group $(\mathbb{Z}/N\mathbb{Z}{)}^{\times }$.