[proofplan] The proof splits on the squarefreeness of $N$. If $N$ has a square factor $p^2 \mid N$, we build a base $b$ near $1 + p$ modulo $p^2$; the binomial expansion shows $b^{N-1} \not\equiv 1 \pmod{p^2}$, which already defeats Fermat and a fortiori Euler. If $N$ is squarefree, we write $N = pm$ with $p$ an odd prime and $p \nmid m$, and combine a quadratic non-residue modulo $p$ with the residue $1 \pmod m$ via the Chinese Remainder Theorem; the resulting base $b$ has Jacobi symbol $-1$ but $b^{(N-1)/2} \equiv 1 \pmod m$, so the two sides of the Euler congruence cannot match modulo $N$. In both cases the constructed base certifies failure of the Euler test. [/proofplan] [step:Split on squarefreeness of $N$] Let $N$ be odd and composite. Write $N = \prod_p p^{e_p}$ for its prime factorisation. Exactly one of the following holds: - **(a)** $N$ is squarefree: $e_p \in \{0, 1\}$ for every prime $p$; - **(b)** there exists a prime $p$ with $e_p \geq 2$, equivalently $p^2 \mid N$. We treat the two cases separately and, in each, exhibit a base $b \in (\mathbb{Z}/N\mathbb{Z})^\times$ failing the Euler test. [/step] [step:Handle the squarefree case via a non-residue modulo $p$ and $1$ modulo $m$] Assume (a). Since $N$ is composite and squarefree, write $N = p m$ where $p$ is a prime divisor of $N$ and $m = N/p$, with $\gcd(p, m) = 1$ and $m \geq 3$ odd (the last because $N$ is odd and composite, so $m > 1$ and odd, and $m = 2$ is impossible). Since $p$ is odd, exactly half of the non-zero residues modulo $p$ are quadratic non-residues (see [Count of Quadratic Residues](/theorems/???)), so there exists $u \in \mathbb{Z}$ with $\gcd(u, p) = 1$ and \begin{align*} \left(\tfrac{u}{p}\right) &= -1, \end{align*} where $\left(\tfrac{\cdot}{p}\right)$ is the Legendre symbol. By the [Chinese Remainder Theorem](/theorems/???), since $\gcd(p, m) = 1$, the natural ring map $\mathbb{Z}/N\mathbb{Z} \to \mathbb{Z}/p\mathbb{Z} \times \mathbb{Z}/m\mathbb{Z}$ is an isomorphism. We choose $b \in \mathbb{Z}$ satisfying \begin{align*} b &\equiv u \pmod{p}, & b &\equiv 1 \pmod{m}. \end{align*} Then $\gcd(b, p) = 1$ (since $\gcd(u, p) = 1$) and $\gcd(b, m) = 1$ (since $b \equiv 1 \pmod m$), hence $\gcd(b, N) = 1$. We compute the Jacobi symbol $\left(\frac{b}{N}\right)$. By [Properties of the Jacobi Symbol](/theorems/???), since $N = pm$ with $p, m$ odd, \begin{align*} \left(\tfrac{b}{N}\right) &= \left(\tfrac{b}{p}\right)\left(\tfrac{b}{m}\right). \end{align*} Using $b \equiv u \pmod p$ we have $\left(\frac{b}{p}\right) = \left(\frac{u}{p}\right) = -1$. Using $b \equiv 1 \pmod m$ we have $\left(\frac{b}{m}\right) = \left(\frac{1}{m}\right) = 1$. Thus \begin{align*} \left(\tfrac{b}{N}\right) &= (-1) \cdot 1 = -1. \end{align*} On the other side of the Euler congruence, $b \equiv 1 \pmod m$ forces \begin{align*} b^{(N-1)/2} &\equiv 1^{(N-1)/2} = 1 \pmod{m}. \end{align*} If the Euler test succeeded, i.e. $b^{(N-1)/2} \equiv \left(\frac{b}{N}\right) = -1 \pmod{N}$, then reducing modulo $m$ would give $1 \equiv -1 \pmod{m}$, i.e. $m \mid 2$. This contradicts $m \geq 3$. Therefore \begin{align*} b^{(N-1)/2} &\not\equiv \left(\tfrac{b}{N}\right) \pmod{N}, \end{align*} and $N$ fails the Euler test to base $b$. [guided] The strategy in the squarefree case is engineered as follows. We want a base $b$ such that the two sides of the Euler congruence \begin{align*} b^{(N-1)/2} &\equiv \left(\tfrac{b}{N}\right) \pmod{N} \end{align*} disagree. The Jacobi symbol factors through the prime factors of $N$, so we can control its sign one prime at a time. We want $\left(\frac{b}{N}\right) = -1$ — this is achieved by making $b$ a non-residue modulo exactly one prime factor. Meanwhile we want $b^{(N-1)/2}$ to be forced to the value $+1$ modulo some factor — this is achieved by making $b \equiv 1$ modulo that factor. Write $N = pm$ with $p$ a prime factor, $m = N/p$, and $\gcd(p, m) = 1$. Because $N$ is squarefree and composite and odd, we have $m \geq 3$ and $m$ odd. Pick $u$ with $\left(\frac{u}{p}\right) = -1$; such $u$ exists by the [Count of Quadratic Residues](/theorems/???), which guarantees $(p-1)/2 \geq 1$ non-residues modulo any odd prime $p$. The [Chinese Remainder Theorem](/theorems/???) — whose hypothesis $\gcd(p, m) = 1$ is the squarefreeness of $N$ at the prime $p$ — gives us simultaneous congruences $b \equiv u \pmod p$, $b \equiv 1 \pmod m$. The coprimality $\gcd(b, N) = 1$ follows because $b \equiv u \pmod p$ with $\gcd(u, p) = 1$, and $b \equiv 1 \pmod m$. Computing $\left(\frac{b}{N}\right)$ via [Properties of the Jacobi Symbol](/theorems/???), \begin{align*} \left(\tfrac{b}{N}\right) &= \left(\tfrac{b}{p}\right)\left(\tfrac{b}{m}\right) = \left(\tfrac{u}{p}\right)\left(\tfrac{1}{m}\right) = (-1)(1) = -1. \end{align*} Meanwhile $b \equiv 1 \pmod m$ propagates: $b^{(N-1)/2} \equiv 1 \pmod m$. If the Euler congruence held, reducing to $m$ would give $-1 \equiv 1 \pmod m$, forcing $m \mid 2$ — impossible for odd $m \geq 3$. [/guided] [/step] [step:Handle the non-squarefree case via a binomial expansion modulo $p^2$] Assume (b): there is a prime $p$ with $p^2 \mid N$. Since $N$ is odd, $p$ is odd. Write $N = p^2 \cdot N'$ with $N' \geq 1$. We seek a unit $b$ modulo $N$ with $b \equiv 1 + p \pmod{p^2}$. By the [Chinese Remainder Theorem](/theorems/???), since $\gcd(p^2, N/p^2)$ need not be $1$ in general we work locally: the reduction $\mathbb{Z}/N\mathbb{Z} \to \mathbb{Z}/p^2\mathbb{Z}$ is surjective, and we choose any integer $b$ with $b \equiv 1 + p \pmod{p^2}$ and $\gcd(b, N) = 1$. Such $b$ exists because $1 + p$ is coprime to $p$ (and therefore to $p^2$), so the residue class $1 + p \pmod{p^2}$ contains infinitely many integers coprime to $N/p^2$ (by Dirichlet's theorem on primes in arithmetic progressions, or more elementarily by the Chinese Remainder Theorem applied to $p^2$ and the squarefree part of $N/p^2$); fix one. We expand $b^{N-1}$ modulo $p^2$ via the binomial theorem. Write \begin{align*} b^{N-1} &\equiv (1+p)^{N-1} \pmod{p^2}. \end{align*} By the binomial theorem, \begin{align*} (1+p)^{N-1} &= \sum_{k=0}^{N-1} \binom{N-1}{k} p^k = 1 + (N-1)p + \sum_{k=2}^{N-1} \binom{N-1}{k} p^k. \end{align*} Every term with $k \geq 2$ is divisible by $p^2$ and so vanishes modulo $p^2$. Hence \begin{align*} b^{N-1} &\equiv 1 + (N-1)p \pmod{p^2}. \end{align*} Since $p \mid N$, $N \equiv 0 \pmod p$, so $(N-1)p \equiv -p \pmod{p^2}$. Therefore \begin{align*} b^{N-1} &\equiv 1 - p \pmod{p^2}. \end{align*} Now $1 - p \not\equiv 1 \pmod{p^2}$ (the difference is $-p$, nonzero modulo $p^2$), so $b^{N-1} \not\equiv 1 \pmod{p^2}$, hence $b^{N-1} \not\equiv 1 \pmod{N}$. In particular $b^{(N-1)/2}$, whose square is $b^{N-1}$, cannot equal $\pm 1$ modulo $p^2$ either: if $b^{(N-1)/2} \equiv \pm 1 \pmod{p^2}$ then squaring would give $b^{N-1} \equiv 1 \pmod{p^2}$, a contradiction with $b^{N-1} \equiv 1 - p \pmod{p^2}$. Consequently $b^{(N-1)/2} \not\equiv \pm 1 \pmod{N}$. But $\left(\frac{b}{N}\right) \in \{\pm 1\}$ by definition of the Jacobi symbol. Therefore \begin{align*} b^{(N-1)/2} &\not\equiv \left(\tfrac{b}{N}\right) \pmod{N}, \end{align*} so $N$ fails the Euler test to base $b$. [guided] In the non-squarefree case our enemy is not the Jacobi symbol — it is the exponentiation side, which we will push off the set $\{\pm 1\}$ entirely. The Euler congruence demands $b^{(N-1)/2} \equiv \left(\frac{b}{N}\right) \pmod N$, and the right-hand side always lies in $\{\pm 1\}$. If we can make $b^{(N-1)/2}$ fail to be $\pm 1$ modulo $N$, the Euler test fails automatically. The classical trick is to exploit a prime power $p^2 \mid N$ and the element $1 + p$. Modulo $p^2$, the element $1 + p$ has order exactly $p$ in the multiplicative group: $(1+p)^p \equiv 1 \pmod{p^2}$ and no smaller power equals $1$. Since $p$ is odd, the order $p$ is coprime to $2$. Concretely, pick an integer $b$ with $b \equiv 1 + p \pmod{p^2}$ and $\gcd(b, N) = 1$; such $b$ exists because $1 + p$ is a unit modulo $p^2$, and we can perturb the representative by a multiple of $p^2$ to adjust coprimality with $N/p^2$. Then the binomial theorem gives \begin{align*} b^{N-1} &\equiv (1+p)^{N-1} = 1 + (N-1) p + \sum_{k \geq 2} \binom{N-1}{k} p^k \equiv 1 + (N-1)p \pmod{p^2}, \end{align*} because every $p^k$ with $k \geq 2$ vanishes modulo $p^2$. Substituting $N \equiv 0 \pmod p$ (which is how we use $p \mid N$), \begin{align*} b^{N-1} &\equiv 1 - p \pmod{p^2}. \end{align*} So $b^{N-1}$ is not even $1$ modulo $p^2$, hence not modulo $N$ — so $b^{(N-1)/2}$ cannot be $\pm 1$ modulo $p^2$ (if it were, its square $b^{N-1}$ would be $1$ modulo $p^2$, contradicting what we just computed). Since $\left(\frac{b}{N}\right) \in \{\pm 1\}$, the Euler congruence fails. Why this particular $b$? The choice $1 + p$ modulo $p^2$ isolates a single non-trivial direction in the kernel of the reduction $(\mathbb{Z}/p^2\mathbb{Z})^\times \to (\mathbb{Z}/p\mathbb{Z})^\times$; the kernel is cyclic of order $p$ and generated by $1 + p$. Any generator would do; we picked the simplest one. [/guided] [/step] [step:Combine the cases to conclude] In case (a) the base $b$ constructed in Step 2, and in case (b) the base $b$ constructed in Step 3, witnesses that $N$ is not an Euler pseudoprime to base $b$. Since every odd composite $N$ falls into exactly one of the two cases, in every case there exists a base $b$ with $\gcd(b, N) = 1$ for which $N$ fails the Euler test. This is the claim of the theorem. [/step]