Codex @codex  0

The Fermat test looks for a coprime base $a$ with $a^{N-1}\not\equiv 1(\mathrm{mod}N)$. Such a witness proves compositeness by the Fermat little theorem, but Carmichael numbers pass for every coprime base.

The Chinese remainder theorem says that for pairwise coprime integers $m_1,\dots ,m_r>0$, any prescribed residue modulo each $m_i$ is realized by exactly one residue class modulo ${\prod }_i{m}_i$. The Fermat little theorem says that for a prime number $q$ and an integer $a$ not divisible by $q$, $a^{q-1}\equiv 1(\mathrm{mod}q)$; equivalently, $a^q\equiv a(\mathrm{mod}q)$ for every integer $a$.

For the given prime number, write $p=2k+1$. Its square is $p^2=1+4k(k+1)=1+8t$ for some integer $t$, since one of two consecutive integers is even. Therefore $p^4=(1+8t{)}^2\equiv 1(\mathrm{mod}16)$. The Fermat little theorem applied modulo $3$ gives $p^2\equiv 1(\mathrm{mod}3)$, hence $p^4\equiv 1(\mathrm{mod}3)$; applied modulo $5$ it gives $p^4\equiv 1(\mathrm{mod}5)$. These applications are valid because $p>5$.

The three moduli $16,3,5$ are pairwise coprime integers and have product $240$. By the Chinese remainder theorem,

False. The Carmichael number $561=3\cdot 11\cdot 17$ supplies a counterexample. For every $a$ coprime to $561$, the Fermat little theorem gives $a^{560}\equiv 1$ modulo each of these primes, since $2,10,16$ all divide $560$. The Chinese remainder theorem then gives $a^{560}\equiv 1(\mathrm{mod}561)$. Thus the proposed Fermat primality test can fail to detect a composite for every coprime base.

The extended Euclidean algorithm givesBack-substituting in these equations produces the Bezout identityThus one integer solution is $\boxed{x=12,y=-7}$. In fact, subtracting this Bezout identity from any other solution and using that $17$ and $29$ are coprime integers gives all solutions: $x=12+29t$, $y=-7-17t$, where $t\in \mathbb{Z}$.

For the modular arithmetic calculation, $29$ is a prime number and $17$ is coprime to it, so Fermat little theorem gives $17^{28}\equiv 1(\mathrm{mod}29)$. Since $138=5\cdot 28-2$, and the preceding Bezout identity identifies $12$ as the modular multiplicative inverse of $17$, we obtainConsequently the least positive representative is $\boxed{28}$.

The auxiliary Higman group $Q$ has no nontrivial finite quotients of a group. One can use this permitted property directly, but there is a short verification. In any finite quotient, let $n_i$ be the order of the image of $a_i$. Since conjugation sends $a_{i+1}$ to its square, $n_{i+1}$ must be odd. If some $n_i>1$, choose the least prime number $p$ dividing any $n_i$. It is odd. Conjugation by the preceding generator givesThe multiplicative order of $2$ modulo $p$ is therefore a divisor of $n_{i-1}$. It is greater than one and divides $p-1$ by the Fermat little theorem, so it has a prime divisor smaller than $p$. That prime also divides $n_{i-1}$, contradicting the choice of $p$. Hence every $n_i=1$ and the quotient is trivial.

Given any finitely presented group $P$, form $\hat{P}=P\ast ⟨v⟩$, and apply part (a) to the word $w=v$. This word is nontrivial by the normal form theorem for a free product, so the output $J=\hat{P}(v)$ contains $P$ by the embedding already proved.

To check its finite quotients, let $f:J\to F$ be any group homomorphism to a finite group. The image of the copy of $Q$ is trivial by the preceding property. The identifications $u_j=a_3^{j+1}{a}_1{a}_3^{-(j+1)}$ make all $f(u_j)$ trivial. Thus the equations $u_j^{-1}c{u}_j=g_j$ give, in the image,Since $f(c)=f(z)$, this forces $f(x_i)=1$ for all generators of $\hat{P}$, including $v$. The defining word $c=[v,z]$ then has trivial image, so $f(z)=f(d)=1$ as well. Every generator of $J$ has trivial image. ThereforeThis uses the concrete construction of part (a), not an assumption that arbitrary quotients preserve an embedding of $P$.

The Fermat-Euler theorem states thatIndeed, if $r_1,\dots ,r_{\phi (n)}$ are the reduced residue classes modulo $n$, multiplication by $a$ permutes them. ThereforeThe product ${\prod }_i{r}_i$ is invertible modulo $n$, so cancellation gives the theorem.

Now let $p$ be prime. If $k\equiv 1(\mathrm{mod}p-1)$, then for $p\nmid b$, Fermat little theorem gives $b^{k-1}\equiv 1(\mathrm{mod}p)$, while $p\mid b$ makes $b^k\equiv b\equiv 0$. Thus $b^k\equiv b$ for every integer $b$.

Conversely, assume this congruence holds for every $b$. Choose a primitive root $g$ modulo $p$. Then $g^{k-1}\equiv 1(\mathrm{mod}p)$. Since $g$ has order $p-1$, one has $p-1\mid k-1$. Hence

An odd composite $N$ coprime to $b$ is a Fermat pseudoprime to base $b$ when $b^{N-1}\equiv 1(\mathrm{mod}N)$. It is a Carmichael number when this congruence holds for every $b$ coprime to $N$.

Suppose a Carmichael number has $p^a\Vert N$ with $a\ge 2$. The group $(\mathbb{Z}/p^a\mathbb{Z}{)}^{\ast }$ is cyclic, so choose a residue of orderBy the Chinese remainder theorem, extend it to an integer $b$ that is congruent to $1$ modulo every other prime-power factor of $N$. Then $\gcd (b,N)=1$, and the Carmichael congruence forces the order of $b$ modulo $p^a$ to divide $N-1$. In particular $p\mid N-1$, contradicting $p\mid N$. Therefore every Carmichael number is square-free.

Now assume $N$ is square-free. If $p-1\mid N-1$ for every $p\mid N$, then for every $b$ coprime to $N$, Fermat little theorem givesfor each $p\mid N$. The Chinese remainder theorem then gives the congruence modulo $N$, so $N$ is Carmichael.

Conversely, if $N$ is Carmichael, fix $p\mid N$. Choose a primitive root $g$ modulo $p$ and use the Chinese remainder theorem to choose $b\equiv g(\mathrm{mod}p)$ and $b\equiv 1(\mathrm{mod}N/p)$. Then $b^{N-1}\equiv 1(\mathrm{mod}p)$, so the order $p-1$ of $g$ divides $N-1$. This proves the Korselt criterion in the required form:

A Carmichael number cannot have one prime factor because it is composite. If $N=pq$ with distinct primes $p<q$, the condition $q-1\mid pq-1$ implies $q-1\mid p-1$, which is impossible. Hence every Carmichael number has at least three prime factors.

The Wilson theorem states that for a prime $p$,Indeed, every nonzero residue modulo $p$ has a unique multiplicative inverse. The only residues equal to their own inverses solve $x^2\equiv 1(\mathrm{mod}p)$, hence are $1$ and $-1$. Pairing every other residue with its distinct inverse leaves

The Fermat little theorem states that for prime $p$,equivalently, if $p\nmid a$, then $a^{p-1}\equiv 1(\mathrm{mod}p)$.

Wilson's theorem at $p=31$ givesso $28!\equiv 15(\mathrm{mod}31)$. Also $729\equiv 16(\mathrm{mod}31)$, and therefore