Codex @codex  0

Write $x=3+18k$. The second modular congruence becomes $18k\equiv -1(\mathrm{mod}23)$. The Bezout identity above says that $9$ is the inverse of $18$ modulo $23$, so $k\equiv -9\equiv 14(\mathrm{mod}23)$. ThereforeThe checks are $255=18\cdot 14+3=23\cdot 11+2$. The Chinese remainder theorem explains uniqueness modulo $18\cdot 23=414$, since the moduli are coprime integers.

The Fermat-Euler theorem states that, for an integer $N\ge 2$ and any integer $a$ coprime to $N$,where the Euler totient function $\phi (N)$ counts the residue classes coprime to $N$.

Let $r_1,\dots ,r_{\phi (N)}$ be representatives of these residue classes. Multiplication by $a$ gives a permutation of them: each $a{r}_i$ remains coprime to $N$, and $a{r}_i\equiv a{r}_j$ implies $r_i\equiv r_j$ by cancellation using the modular inverse of $a$. Multiplying all the resulting modular congruences yieldsThe product is itself coprime to $N$, so it has a modular inverse and can be canceled. This proves the Fermat-Euler theorem. For $N=1$, the congruence is trivial; no separate argument is needed.

For $1\le j\le p-1$, the identity for binomial coefficientsshows that $p$ divides $j\left(\genfrac{}{}{0ex}{}{p}{j}\right)$. Since $p$ is a prime number and $j$ is not divisible by $p$, cancellation modulo $p$ givesThe binomial theorem consequently gives $(1+x{)}^p\equiv 1+x^p$ as a coefficientwise polynomial modular congruence. Apply the same identity with $x$ replaced by $x^{p^r}$ and use mathematical induction to obtainThis is an iteration of the Frobenius endomorphism in characteristic $p$. Comparing the intermediate coefficients gives the prime-power binomial divisibility result

Reduce $z$ using modular congruence: its residue class modulo $3$ is $0$, $1$, or $-1$. A square number therefore has residue class $0$ or $1$, and raising either residue to the positive integer power $n$ leaves it unchanged. ConsequentlyThe exponent in the original PDF is $2n$; the polynomial identities in the converted TeX are a transcription error. The argument uses $n\ge 1$; it does not assign $0^0$ a value.

For a Pythagorean triple, each square number is $0$ or $1$ modulo $3$. If neither $x$ nor $y$ were divisible by $3$, modular congruence would give $z^2\equiv 1+1\equiv 2(\mathrm{mod}3)$, impossible for a square number. Thus at least one of $x,y$ is divisible by $3$; both can be divisible, as in $(9,12,15)$.

An odd number has square number congruent to $1$ modulo $4$, whereas an even number has square number congruent to $0$. If both $x$ and $y$ were odd numbers, their sum of square numbers would again be $2$ modulo $4$, which no square number can be. Hence $x$ and $y$ cannot both be odd. They can both be even; the conclusion does not require the Pythagorean triple to be primitive.

The Fermat-Euler theorem states that for an integer $a$ and a positive integer $n$ with $\gcd (a,n)=1$,where the Euler totient function $\phi (n)$ counts the residue classes coprime to $n$. For $n\ge 2$, choose a reduced residue system $r_1,\dots ,r_{\phi (n)}$. Multiplication by the unit modulo n $a$ preserves coprimality and is injective on these residue classes: $a{r}_i\equiv a{r}_j(\mathrm{mod}n)$ implies $r_i\equiv r_j(\mathrm{mod}n)$, because $a$ has a multiplicative inverse modulo $n$. It therefore permutes the reduced residue system, givingThe product is also a unit modulo n, so it can be cancelled. This proves the Fermat-Euler theorem. For $n=1$ every modular congruence is automatic; one may use $\phi (1)=1$.

For a prime number $p$, the Euler totient function has value $\phi (p)=p-1$. Thus $a^{p-1}\equiv 1(\mathrm{mod}p)$ whenever $p\nmid a$. Multiplying by $a$, and treating $p\mid a$ separately, gives the all-integer version of Fermat's little theorem:Finally, Wilson theorem states that for every prime number $p$, $\boxed{(p-1)!\equiv -1(\mathrm{mod}p)}$. Its converse is also true: an integer $n>1$ is prime exactly when $(n-1)!\equiv -1(\mathrm{mod}n)$. For the converse, any proper divisor $1<d<n$ would divide both $(n-1)!$ and $n$, contradicting that congruence.

A reduced positive definite binary quadratic form $f=[a,b,c]=a{x}^2+bxy+c{y}^2$ satisfieswith $b\ge 0$ when $|b|=a$ or $a=c$. Its discriminant of a binary quadratic form is $d=b^2-4ac<0$. The first displayed inequality already gives $|b|\le a$, while $c\ge a$ givesTaking the positive square root yieldsMoreover, $d=b^2-4ac\equiv b^2\equiv b(\mathrm{mod}2)$, so $b\equiv d(\mathrm{mod}2)$. For fixed negative $d$, the displayed bounds leave only finitely many possible integers $a$ and $b$, and then $c=(b^2-d)/(4a)$ is uniquely determined. Hence only finitely many reduced forms have discriminant $d$.

For $d=-15$, the bound gives $a\le \sqrt{5}$, so $a\in \{1,2\}$. The modular congruence condition makes $b$ odd. If $a=1$, then $b=\pm 1$ and $c=4$; the boundary convention $|b|=a\Rightarrow b\ge 0$ retains $[1,1,4]$. If $a=2$, then $b=\pm 1$ and $c=2$; the boundary convention $a=c\Rightarrow b\ge 0$ retains $[2,1,2]$. Thus the complete list is

The Lagrange root bound over a field says that a nonzero polynomial of degree $r$ over a field has at most $r$ roots. In particular, a polynomial modular congruence of degree $r$ modulo a prime number has at most $r$ incongruent solutions unless all its coefficients vanish modulo that prime.

Suppose that $d$ is good and that the positive integer divisor $e$ divides $d$. The $d$ roots of $X^d-1$ form a finite multiplicative subgroup $H$ of ${\mathbb{F}}_p^{\times }$. By the fact that every finite multiplicative subgroup of a field is cyclic, $H=⟨g⟩$ is a cyclic group of order $d$. The solutions in $H$ of $x^e=1$ areso there are at least $e$ of them. The Lagrange root bound over a field gives at most $e$ roots in all of ${\mathbb{F}}_p$, hence exactly $e$. Thus every divisor of a good number is good.

Now put $n=pq$. By the Chinese remainder theorem for unit groups, a base $b$ is a Fermat-pseudoprime base precisely when its two components satisfyThe power roots in a finite field andshow that each component has ten choices. Therefore there areFermat-pseudoprime bases.

To impose the strong pseudoprime condition, write $n-1=2^{s}m$ with $m$ odd. Since $10\mid n-1$, we have $5\mid m$. In each cyclic group of ten Fermat components, raising to the $m$th power sends five elements to $1$ and five elements to $-1$. A pair of components passes the strong test exactly when their signs agree: the pair $(1,1)$ satisfies the first alternative, and $(-1,-1)$ satisfies the second at $j=0$. Components of opposite sign become $(1,1)$ after squaring and can never jointly equal $-1$. Hence the number of strong-pseudoprime bases is