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 modular congruence $x^4\equiv 1$ first implies $x\not\equiv 0$. Multiplication by such an $x$ permutes the nonzero residue classes modulo the prime $p$: if $xa\equiv xb$, cancellation gives $a\equiv b$. Multiply all these residues and cancel their nonzero product to obtain $x^{p-1}\equiv 1$, the usual short proof of Fermat little theorem.

Now $(x^2-1)(x^2+1)\equiv 0$. By the Euclid lemma, either $x^2\equiv 1$ or $x^2\equiv -1$. In the latter case, because $p-1=4k+2$,contradicting the preceding product argument, since $p$ is odd. ThusNo unproved assertion about the number of fourth roots is needed.

For a prime number $p$ and an integer $x$ coprime to $p$, multiplication by $x$ permutes the nonzero residue classes modulo $p$. Indeed, $ax\equiv bx(\mathrm{mod}p)$ implies $a\equiv b(\mathrm{mod}p)$, and none of the products is zero. Taking the product over the $p-1$ classes givesThe factorial is coprime to $p$ and can be cancelled, proving Fermat little theorem: $\boxed{x^{p-1}\equiv 1(\mathrm{mod}p)}$.

Now $n=mp$ and $x$ is coprime to $n$, so it is coprime to $p$. Since $(n-1)-(m-1)=m(p-1)$, the proved theorem givesThus the two specified integer congruences modulo $p$ are equivalent. In this particular step the additional hypothesis $(m,p)=1$ is not needed; it will hold for the squarefree factorization used next.

If $n$ is a squarefree integer, its distinct prime factors are pairwise coprime. Consequently $n$ divides $x^{n-1}-1$ exactly when every prime factor does. Applying the preceding equivalence with $m=n/p$ provesFinally retain this squarefree hypothesis. If $p-1$ divides $n-1$, write $n-1=k_p(p-1)$. Fermat little theorem gives $x^{n-1}=(x^{p-1}{)}^{k_p}\equiv 1(\mathrm{mod}p)$ for every prime factor. Their pairwise coprimality then gives $\boxed{x^{n-1}\equiv 1(\mathrm{mod}n)}$. For composite $n$ this is the sufficient direction of the Korselt criterion for a Carmichael number; primality is not excluded by the requested implication.

The Wilson theorem says that $(p-1)!\equiv -1(\mathrm{mod}p)$ for a prime number $p$. Thus $18\cdot 17!\equiv -1(\mathrm{mod}19)$, and since $18\equiv -1$, we get $17!\equiv 1$. The Fermat little theorem says $b^{p-1}\equiv 1(\mathrm{mod}p)$ when $p$ does not divide $b$. Applying it to $3$ gives $3^{18}\equiv 1$, so $3^{16}$ is the inverse of $9$ modulo $19$. Since $9\cdot 17=153\equiv 1$, the required residue isThis is the unique representative in $\{1,\dots ,19\}$.

For the simultaneous integer congruences, the modulus-$2$ condition is already implied by $x\equiv 3(\mathrm{mod}4)$. Write $x=3+4k$; the modulus-$3$ condition becomes $k\equiv 1(\mathrm{mod}3)$, hence $x=7+12t$. The modulus-$5$ condition then gives $2+2t\equiv 4$, or $t\equiv 1(\mathrm{mod}5)$. ThereforeEvery such integer satisfies all four integer congruences; reversing the substitutions shows that there are no others. The uniqueness modulo $60$ also follows from the Chinese remainder theorem applied to the coprime moduli $3,4,5$.

Since $31$ is a prime number, the Wilson theorem states that $30!\equiv -1(\mathrm{mod}31)$. But $30!\equiv (-1)(-2)28!=2\cdot 28!$, so the modular inverse of $2$, which is $16$, givesThe Fermat little theorem states that $a^{p-1}\equiv 1(\mathrm{mod}p)$ when $p$ is prime and $p\nmid a$. Therefore $13^{30}\equiv 1(\mathrm{mod}31)$, andsince $14\cdot 20=280=9\cdot 31+1$. Combining these modular congruences,This representative lies between $0$ and $30$, so it is the least nonnegative residue.

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

To prove it when $p\nmid a$, multiplication by $a$ permutes the nonzero residues $1,\dots ,p-1$. Indeed, $ai\equiv aj(\mathrm{mod}p)$ implies $p\mid a(i-j)$, and the Euclid lemma implies $i=j$ in this range. Multiplying all these residues givesNone of the factors of $(p-1)!$ is divisible by $p$, so the factorial has a modular inverse. Cancelling it proves $a^{p-1}\equiv 1$, hence $a^p\equiv a$. When $p\mid a$, the latter identity has both sides zero, completing the proof.

For an odd prime number $p\ne 5$, the numbers $10,p$ are coprime. The Fermat little theorem gives $10^{p-1}\equiv 1(\mathrm{mod}p)$, and consequentlyThese exponents are distinct, so infinitely many are obtained.

Write the repdigit with $n$ copies of $5$ asIf $p\ne 3,5$, choose $n$ to be any positive multiple of $p-1$. Then $9$ has a modular inverse modulo $p$, so $p\mid R_n$. Division by $9$ cannot be used modulo $3$; instead $10\equiv 1(\mathrm{mod}3)$ gives $R_n\equiv 5n(\mathrm{mod}3)$, so $3\mid R_{3j}$ for every $j\ge 1$. If $p=5$, every $R_n$ is divisible by $5$. ThusThe separate treatment of $3$ accounts for the prime factor of the geometric-sum denominator.

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

A repdigit is a positive integer whose base-$b$ expansion repeats one nonzero digit $d$. For $b\ge 2$, $1\le d<b$ and $n\ge 1$, the finite geometric series gives $R_n=d(1+b+\cdots +b^{n-1})=d(b^n-1)/(b-1)$. For example, $5(10^n-1)/9$ has $n$ decimal digits, all equal to five.

Every prime number not dividing $b$ divides infinitely many such repdigits. If it divides $d$, every length works. Otherwise, if it does not divide $b-1$, the Fermat little theorem gives divisibility for lengths that are multiples of $p-1$, and division by $b-1$ is justified by its modular inverse. If $p\mid b-1$, the sum is congruent to $dn$ modulo $p$, so lengths divisible by $p$ work instead. A prime dividing $b$ but not $d$ divides none, since $R_n\equiv d(\mathrm{mod}p)$. This distinction prevents invalid cancellation of the geometric-sum denominator.