Codex @codex  0

True. First suppose $p^e\mid N$ with $e\ge 2$ maximal. By the Chinese remainder theorem, choose $a\equiv 1+p^{e-1}(\mathrm{mod}{p}^e)$ and $a\equiv 1$ modulo all other prime-power factors. This is a unit, with Jacobi symbol one, because it is one modulo every prime. For $m=(N-1)/2$, the binomial theorem givesbecause $p\nmid m$ and all higher terms contain $p^e$. It is therefore a witness to the desired failure.

If $N$ is square-free and composite, it has at least two prime factors. Choose $a$ to be a quadratic nonresidue at one prime $p$ and one at every other prime, again using the Chinese remainder theorem. Then $(a/N)=-1$. At a different odd prime $q\mid N$, however, $a^m\equiv 1\not\equiv -1(\mathrm{mod}q)$. These two cases prove that every odd composite has an Euler-Jacobi witness, unlike the situation for the ordinary Fermat primality test.

Multiplying the desired representation by $b_1{b}_2$ turns it into the integer equationSince $b_1$ and $b_2$ are coprime integers, the necessary modular multiplicative inverses exist. Choose the unique representativesThen $a-a_1{b}_2-a_2{b}_1$ is divisible by both $b_1$ and $b_2$, hence by their product, because they are coprime. Definingtherefore gives an integer and proves existence. Any other representation, reduced modulo $b_1$ and $b_2$, must have the same $a_1$ and $a_2$, since their allowed ranges contain exactly one representative of each residue. The integer equation then forces the same $n$. This proves uniqueness.

For the prime-power fraction decomposition, put $d_i=p_i^{n_i}$ and $B_i=b/d_i$. The distinct prime-power factors $d_i$ are pairwise coprime, and $B_i$ has a modular multiplicative inverse modulo $d_i$. DefineEvery term $q_j{B}_j$ with $j\ne i$ is divisible by $d_i$, while $q_i{B}_i\equiv a(\mathrm{mod}{d}_i)$. Thus $a-{\sum }_i{q}_i{B}_i$ is divisible by all the pairwise coprime $d_i$ and therefore by $b$. With $n=(a-{\sum }_i{q}_i{B}_i)/b$, division by $b$ yields the required representation. Reducing any such representation modulo each $d_i$ proves uniqueness exactly as above. This is the residue-solving mechanism of the Chinese remainder theorem.

For $315=9\cdot 5\cdot 7$, the complementary factors are $35,63,45$. The required modular inverses givebecause $35\cdot 8\equiv 1(\mathrm{mod}9)$, $63\cdot 2\equiv 1(\mathrm{mod}5)$, and $45\cdot 5\equiv 1(\mathrm{mod}7)$. Their numerator sum is $280+126+225=631=1+2\cdot 315$. Thus the unique decomposition is

A fibre product of schemes $Z=X{\times }_{S}Y$ has projection morphisms to $X$ and $Y$ with equal composites to $S$, and for every scheme $T$ the induced map is a bijectionThis universal property determines $Z$ uniquely up to unique isomorphism. On affine charts over $\mathrm{Spec}R$, takeThe tensor product of commutative algebras has the required universal property for ring maps. Localization identifies these constructions on principal-open overlaps. Cover the base and its two inverse images by affine charts and glue the resulting affine products along those overlaps; their local universal properties give the global one.

For a counterexample to preservation of irreducibility, take $X=Y=\mathrm{Spec}\mathbb{C}$ and $S=\mathrm{Spec}\mathbb{R}$ with their usual structure morphisms. All three are integral schemes, but the Chinese remainder theorem givesThe product scheme is the disjoint union of two points, so it is not irreducible.

For $p\nmid 2k$, the displayed integral equation has nonzero elliptic-curve discriminant modulo $p$, so it has good reduction. Let $\chi$ be the Legendre symbol, with $\chi (0)=0$. Counting the two, one, or zero possible ordinates over each $x$ givesIf $p\equiv 3(\mathrm{mod}4)$, then $\chi (-1)=-1$ and the terms for $x$ and $-x$ cancel. The term at zero vanishes. Thus the count is $p+1$.

For the converse, suppose $p\equiv 1(\mathrm{mod}4)$, and put $h=(p-1)/2$. The Euler criterion and the sum of powers over a finite field show that the Trace of Frobenius satisfiesIndeed, among the positive exponents in this polynomial, of degree $3(p-1)/2<2(p-1)$, only $p-1$ has a nonzero sum over ${\mathbb{F}}_p$, and that sum is $-1$. Since $(x^3+kx{)}^h=x^h(x^2+k{)}^h$, the coefficient formula for trace of Frobenius modulo p yieldsNeither $k$ nor the binomial coefficient vanishes modulo $p$. Hence $a_p\ne 0$, proving the point-count criterion for y squared equals x cubed plus k x:

We use the following formal logarithm fact, also useful for the next part. For a formal group law over ${\mathbb{Z}}_p$, its logarithm has coefficients $c_j/j$ with $c_j\in {\mathbb{Z}}_p$, obtained by integrating its integral invariant differential. If $p$ is odd and $t\in p{\mathbb{Z}}_p\setminus \{0\}$, every term of degree $j\ge 2$ has valuation strictly greater than $v_p(t)$, since $j{v}_p(t)-v_p(j)>v_p(t)$. Thus the logarithm converges and is nonzero at $t$. Its homomorphism into the additive characteristic-zero group proves torsion-freeness of the formal group over Qp for odd p. Consequently reduction injects the entire rational torsion subgroup at any odd prime of good reduction, including its $p$-primary torsion. In particular the torsion subgroup is finite, and its order divides $p+1$ at every good $p\equiv 3(\mathrm{mod}4)$.

By the Dirichlet theorem on primes in arithmetic progressions, choose a good prime $p\equiv 3(\mathrm{mod}8)$. Then $v_2(p+1)=2$, bounding the two-primary part by four. For any odd prime $\ell$ dividing the torsion order, the Chinese remainder theorem and the Dirichlet theorem on primes in arithmetic progressions give a good prime $p$ with $p\equiv 3(\mathrm{mod}4)$ and $p\equiv 1(\mathrm{mod}\ell )$, avoiding the finitely many primes dividing $2k$. But then $\ell \nmid p+1$, a contradiction. Therefore

The order four does occur. For $k=4$, the elliptic-curve addition formula gives $2(2,4)=(0,0)$, so $(2,4)$ has order four. More precisely, the only nonzero rational 2-torsion point when $k>0$ is $(0,0)$, so order four means a cyclic group with a rational half of this point. The duplication formula isSuch a half must have $x(P{)}^2=k$. Writing $k=s^2$, positivity of $y(P{)}^2=2kx(P)$ forces $x(P)=s>0$. Then $y(P{)}^2=2s^3$, so $2s$ is a rational square, equivalently $s=2t^2$ for an integer $t\ge 1$. Conversely $(2t^2,4t^3)$ is a half of $(0,0)$ when $k=4t^4$. The rational torsion on y squared equals x cubed plus positive k x is therefore cyclic of order four exactly for these $k$, and otherwise cyclic of order two.

First establish rational conjugation of finite-index modular subgroups without assuming that $\Gamma$ is a congruence subgroup. Multiply $\gamma$ by a positive integer to obtain an integral matrix $A$, and let $D=\det A>0$. Conjugation is unchanged by this scalar. If $h=I+DB\in \Gamma (D)$, thenThus the principal congruence subgroup $\Gamma (D)$ is contained in $H=S{L}_2(\mathbb{Z})\cap {\gamma }^{-1}S{L}_2(\mathbb{Z})\gamma$. It has finite index because reduction modulo $D$ has finite image. Inside $H$, pullback under conjugation of $\Gamma$ has relative index at most $[S{L}_2(\mathbb{Z}):\Gamma ]$. ConsequentlyThis argument does not assert that an arbitrary finite-index subgroup contains a principal congruence subgroup.

Use the determinant-normalized slash operatorThe positive real power of the determinant is used; on $S{L}_2(\mathbb{Z})$ this reduces to the usual slash operator for modular forms. The automorphy factor identity gives the right-action rule $(f{|}_k\gamma ){|}_k\eta =f{|}_k(\gamma \eta )$.

A modular form on a finite-index subgroup of integer weight $k$ is a holomorphic function on the complex upper half-plane, invariant under this weight-$k$ action of $\Gamma$, and holomorphic at a cusp at each of its cusps. A cusp of a modular group is a $\Gamma$ orbit in ${\mathbb{P}}^1(\mathbb{Q})$. If $\sigma \in S{L}_2(\mathbb{Z})$ carries infinity to its representative, choose a positive integer $h$ with $\sigma T^h{\sigma }^{-1}\in \Gamma$. Such $h$ exists by finite index. Then $f{|}_k\sigma$ is periodic and has a convergent expansion in $q_h=e^{2\pi iz/h}$ near zero; holomorphy means no negative exponents, and being a cusp form means zero constant term. Using an actual translation period avoids possible signs if a smaller width of a cusp is defined only modulo the center, particularly in odd weights.

For cusp holomorphy under rational slash operators, choose $\sigma \in S{L}_2(\mathbb{Z})$ with $\sigma \infty =\gamma \infty$, possible by completing a primitive integer pair to a determinant-one matrix. Then ${\sigma }^{-1}\gamma =\left(\begin{array}{cc}a& b\\ 0& d\end{array}\right)$, with $a/d>0$. Up to a nonzero constant factor,The imaginary part of the argument tends to infinity with that of $z$, so this remains bounded by the cusp expansion of $f{|}_k\sigma$. It tends to zero if $f$ is a cusp form. Moreover $f{|}_k\gamma$ is invariant under ${\Gamma }^{\prime }$: for $\eta \in {\Gamma }^{\prime }$, $\gamma \eta {\gamma }^{-1}\in \Gamma$ and the right-action rule applies. Finite index gives a translation period for ${\Gamma }^{\prime }$, so boundedness is a removable singularity at zero in that periodic parameter. This proves holomorphy at infinity. For every other cusp, apply the same argument to the rational matrix $\gamma \rho$, with $\rho \in S{L}_2(\mathbb{Z})$. Thus all cusp conditions hold, and

For the character twist by rational translations of a cusp form, put $B_j=\left(\begin{array}{cc}1& j/N\\ 0& 1\end{array}\right)$ and $K={\Gamma }_1(N)\cap {\Gamma }_0(N^2)$. For $\eta =\left(\begin{array}{cc}a& b\\ c& d\end{array}\right)\in K$, direct conjugation givesIndeed $N^2\mid c$ and $a\equiv d\equiv 1(\mathrm{mod}N)$. Every $f{|}_k{B}_j=f(z+j/N)$ is therefore $K$-invariant and vanishes at all its cusps by the preceding rational-translate argument. Their finite weighted sum is a cusp form, for every Dirichlet character:

There is, however, a missing primitivity hypothesis in the printed final expansion claim. The exact Fourier expansion of a modular form is alwaysValues of a Dirichlet character on units have modulus one, so $\chi (j{)}^{-1}=\overline{\chi (j)}$. For unit $n$, substitution gives $S_{\overline{\chi }}(n)=\chi (n)g(\overline{\chi })$, where $g$ is the Gauss sum of a Dirichlet character. For nonunit $n$, this vanishing formula requires a primitive Dirichlet character.

Here is its proof in that case. Choose a prime $p\mid (n,N)$. Primitivity supplies a unit $u\equiv 1(\mathrm{mod}N/p)$ with $\chi (u)\ne 1$: otherwise the character would factor through the surjective reduction to units modulo $N/p$. Surjectivity follows by lifting a unit and, if needed, adjusting the lift to avoid the additional prime $p$, using the Chinese remainder theorem. Multiplication by $u$ fixes $e^{2\pi inj/N}$ because $p\mid n$, but multiplies the character factor by a nontrivial constant. Hence $S_{\overline{\chi }}(n)=0$. The finite Fourier transform of a primitive Dirichlet character now gives the corrected formulaThe constant is nonzero: finite exponential orthogonality gives ${\sum }_{n\mathrm{mod}N}|S_{\overline{\chi }}(n){|}^2=N\phi (N)$, whereas the proved formula makes this $\phi (N)|g(\overline{\chi }){|}^2$. Thus $|g(\overline{\chi })|=\sqrt{N}$.

For a concrete counterexample to the printed unrestricted claim, take $N=2$, the principal Dirichlet character, and $f=\Delta$. The translation sum is $\Delta (z+1/2)={\sum }_n(-1{)}^n\tau (n)q^n$, whose $q^2$ coefficient is $-24$. Any constant multiple of the proposed odd-index-only series has $q^2$ coefficient zero. Thus the general modularity conclusion is proved, while the claimed simplification is false without the stated extra hypothesis.

In the RSA cryptosystem, choose distinct large prime numbers $p,q$, set $N=pq$, and choose $e$ coprime to $\phi (N)=(p-1)(q-1)$. Choose $d$ with $ed\equiv 1(\mathrm{mod}\phi (N))$. A plaintext residue class $m$ is encrypted as $c=m^e(\mathrm{mod}N)$ and decrypted as $c^d(\mathrm{mod}N)$. Fermat's little theorem modulo $p$ and $q$, followed by the Chinese remainder theorem, proves correctness even when $m$ is not coprime to $N$.

Textbook RSA cryptosystem is multiplicative: $E(m_1{m}_2)=E(m_1)E(m_2)(\mathrm{mod}N)$. For a chosen-ciphertext attack, multiply an intercepted $c$ by $r^e$ for a known invertible $r$. A decryption oracle returns $mr$, from which multiplication by $r^{-1}$ recovers $m$. Likewise, multiplying two textbook RSA signatures produces a signature of their product. These are homomorphism attacks, exploiting algebra rather than factoring $N$.

For an ElGamal signature, choose a prime $p$, a primitive root $g$ modulo $p$, a private exponent $a$, and public $y=g^a$. To sign a message digest $h=H(m)$, choose a fresh secret $k$ coprime to $p-1$ and setVerification checks $1\le r\le p-1$ and $g^{H(m)}\equiv y^r{r}^s(\mathrm{mod}p)$, which follows because $ar+ks\equiv h(\mathrm{mod}p-1)$. Authenticating the ciphertext and its context with such a digital signature, before decryption, prevents the simple multiplicative modification from being accepted without a fresh valid signature. One needs an appropriate cryptographic hash function and fresh secret cryptographic nonces: this is not a claim that every algebraic attack is impossible. In particular, the unhashed historical ElGamal signature scheme admits existential forgeries of specially chosen message exponents; mere multiplication of encrypted messages is not an authentication mechanism.

Let $D$ be a Dedekind domain. The zero ideal is generated by $0$, and $D$ is generated by $1$, so consider a nonzero proper ideal $I$. Choose $0\ne a\in I$. We use these consequences of the unique factorization of ideals in a Dedekind domain: every nonzero ideal has finitely many nonzero prime-ideal valuations in a Dedekind domain; containment reverses the valuations as in part (b); andThe last formula follows from the containment rule: $J+K$ is the smallest ideal containing both $J$ and $K$, and the product with the indicated minimum exponents is exactly that ideal.

Let $T$ be the finite set of prime ideals dividing $(a)$. For each $P\in T$, set $r_P=v_P(I)$. Since $(a)\subseteq I$, we have $r_P\le v_P((a))$. The containment rule also gives $I⊈P^{r_P+1}$, so chooseDistinct nonzero prime ideals of $D$ are distinct maximal ideals and hence comaximal ideals; their positive powers are also comaximal. Indeed, if $u+v=1$ with $u\in P$, $v\in Q$, for positive integers $m,n$ expanding $(u+v{)}^{m+n-1}$ shows $1\in P^m+Q^n$, since each term contains either at least $m$ factors of $u$ or at least $n$ factors of $v$. We use the Chinese remainder theorem in its ideal form: for pairwise comaximal ideals $J_1,\dots ,J_s$, the map $D\to {\prod }_{j}D/J_j$ is surjective. Apply it to the powers $P^{r_P+1}$ to choose $e_P\in D$ withThen $b={\sum }_{P\in T}{e}_P{b}_P$ belongs to $I$ and satisfies $b\equiv b_P(\mathrm{mod}{P}^{r_P+1})$ for every $P\in T$. Thus $b\notin P^{r_P+1}$, whereas $b\in I\subseteq P^{r_P}$, proving $v_P((b))=r_P$.

For $P\in T$, therefore,For $P\notin T$, $v_P((a))=0$, and $(a)\subseteq I$ forces $v_P(I)=0$ as well. Hence $(a,b)$ and $I$ have the same valuation at every nonzero prime ideal. Uniqueness of their factorizations givesThis proves two generators for an ideal in a Dedekind domain; in fact the first nonzero generator $a\in I$ can be chosen in advance.

For pairwise coprime integers $m_1,\dots ,m_r$, put $M={\prod }_i{m}_i$. The Chinese remainder theorem states that reduction gives an isomorphismEquivalently, every system $x\equiv a_i(\mathrm{mod}{m}_i)$ has one solution modulo $M$.

For existence, let $M_i=M/m_i$. Since $\gcd (M_i,m_i)=1$, choose $u_i$ with $u_i{M}_i\equiv 1(\mathrm{mod}{m}_i)$. Thenhas every required residue: modulo $m_j$, all terms except the $j$th vanish and the remaining term is $a_j$. For uniqueness, if $x$ and $y$ have the same residues, every $m_i$ divides $x-y$. Pairwise coprimality then makes $M$ divide $x-y$. Thus the simultaneous solution exists and is unique modulo $M$.

Choose distinct primes $p_1,\dots ,p_{1000}$. The moduli $p_k^2$ are pairwise coprime, so the Chinese remainder theorem supplies an integer $N$ satisfyingConsequentlyso $p_k\mid N+k$ but $p_k^2\nmid N+k$. By the definition of a squarefull number, $N+k$ is therefore not squarefull. Adding a sufficiently large multiple of ${\prod }_k{p}_k^2$ makes $N$ positive without changing any congruence. The integers $N+1,\dots ,N+1000$ are the required consecutive integers.

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.

Since $4^{-1}\equiv 16(\mathrm{mod}21)$ and $2^{-1}\equiv 23(\mathrm{mod}45)$, the two linear congruences reduce toWrite $x=16+21k$. The second congruence becomesor $7k\equiv 3(\mathrm{mod}15)$ after division by three. Since $7^{-1}\equiv 13(\mathrm{mod}15)$, $k\equiv 9(\mathrm{mod}15)$. The Chinese remainder theorem therefore gives the complete familyThe modulus is $\mathrm{lcm}(21,45)=315$ because the compatibility condition modulo their greatest common divisor is satisfied.

The prime ideal factorization of $pB$ iswhich defines the ramification index of a prime ideal $e_{q/p}=v_q(pB)$. The residue-field degree isLocalizing at $p$ makes $B_p$ a free $R_p$-module of rank $[L:K]$, so $B/pB$ has dimension $[L:K]$ over the residue field $R/p$. The Chinese remainder theorem and the filtration by powers of each $q$ decompose this vector space into $e_{q/p}$ successive quotients isomorphic to $B/q$, each of dimension $f_{q/p}$. Therefore the fundamental identity for prime decomposition gives

If $P$ is a prime ideal of the commutative Artinian ring $R$, then $R/P$ is an Artinian domain. For $0\ne x\in R/P$, the descending chain $(x)\supseteq (x^2)\supseteq \cdots$ stabilizes, so $x^n=x^{n+1}a$ for some $n$; cancellation gives $xa=1$. Thus $R/P$ is a field and $P$ is maximal.

There are only finitely many maximal ideals. Otherwise, distinct maximal ideals $P_i$ are pairwise comaximal and their finite products give the strictly descending chaincontradicting the Artinian condition. This proves the statement about the prime ideals of a commutative Artinian ring.

The nilradical $N$ is the ideal of all nilpotent elements, equivalently the intersection of all prime ideals. Its powers stabilize, say $N^r=N^{r+1}=I$. If $I\ne 0$, choose an ideal $J$ minimal subject to $IJ\ne 0$, then choose $x\in J$ with $Ix\ne 0$. Since $I^2=I$, minimality gives $Rx=Ix$, so $x=ax$ for some $a\in I$. But $a$ is nilpotent, hence $1-a$ is a unit, contradicting $(1-a)x=0$. Therefore the nilradical of a commutative Artinian ring is nilpotent.

If the maximal ideals are $P_1,\dots ,P_s$, the Chinese remainder theorem givesa finite product of fields. Each layer $N^j/N^{j+1}$ is an Artinian module over this product and therefore finite-dimensional. Since $N$ is nilpotent, these finitely many layers show that every ideal of $R$ is finitely generated. This proves the Artinian commutative ring is Noetherian theorem.

Now assume $R$ is local with maximal ideal $P$ and ${\dim }_{R/P}P/P^2=1$. The Nakayama lemma gives $P=(x)$. Since $P$ is nilpotent, its powers form a finite chain ending in zero. For a nonzero ideal $J$, choose the largest $r$ with $J\subseteq (x^r)$ and take $y\in J\setminus (x^{r+1})$. Write $y=x^{r}u$; then $u\notin P$, so $u$ is a unit. Henceand every ideal of $R$ is principal.

Finally, the Artin–Wedderburn theorem says that a finite-dimensional semisimple $k$-algebra has the formwhere each $D_i$ is a finite-dimensional division ring over $k$; the factors are unique up to permutation and isomorphism. By the assumed complete reducibility, write the right regular module aswith pairwise nonisomorphic simple right modules $S_i$. The Schur lemma says that $D_i={\mathrm{End}}_T(S_i)$ is a division ring and that homomorphisms between distinct $S_i$ vanish. Left multiplication and the endomorphism ring of the displayed direct sum therefore giveConversely, the regular module of $M_n(D)$ is a direct sum of $n$ simple column modules, proving that every algebra on the right is semisimple. Uniqueness follows from uniqueness of the simple summands and their multiplicities.

Letand let $W$ be the product of the finitely many primes at most $r$ or dividing some nonzero difference $h_i-h_j$. Sieve with the primes $p\nmid W$. For such a prime, the congruence $F(n)\equiv 0(\mathrm{mod}p)$ has exactly $r$ distinct roots. By the Chinese remainder theorem, the root-counting function $\rho (d)$ is multiplicative on squarefree $d$ coprime to $W$, andThus the polynomial root density in a sieve applies with

Take $z=x^{1/4}$ and $D=z$. For squarefree $d$ coprime to $W$,The supplied mean-value estimate, partial summation, and removal of square factors using $r^{\omega (n)}{\ll }_{r,ϵ}{n}^{ϵ}$ giveThe error in the Selberg upper-bound sieve isConsequently

If every $n+h_i$ is prime and all of them exceed $z$, then $F(n)$ has no prime divisor $p<z$ with $p\nmid W$, apart from a fixed finite set of divisibility cases absorbed into the implied constant. The cases with some $n+h_i\le z$ contribute $O_r(z)$. Therefore

The Chinese remainder theorem says that if the positive integers $m_1,\dots ,m_r$ are pairwise coprime and $M={\prod }_i{m}_i$, then for arbitrary residue classes $a_i(\mathrm{mod}{m}_i)$ there is a unique residue class $x(\mathrm{mod}M)$ satisfyingEquivalently, reduction is a ring isomorphism

For existence, put $M_i=M/m_i$. Pairwise coprimality gives $\gcd (M_i,m_i)=1$, so Bézout's identity supplies an integer $u_i$ with $u_i{M}_i\equiv 1(\mathrm{mod}{m}_i)$. Thenhas the required residues, because every term except the $i$th is divisible by $m_i$. If $x$ and $y$ are two solutions, each $m_i$ divides $x-y$. Pairwise coprimality then implies that their product $M$ divides $x-y$, proving uniqueness modulo $M$.

The Euler totient function $\varphi (n)$ is the number of residue classes modulo $n$ that are coprime to $n$. The Chinese remainder theorem says that for pairwise coprime moduli $m_i$, reduction induces a bijectionIt restricts to a bijection of unit groups. If $n=p_1\cdots p_r$ is squarefree, thenEach of the primes $3,5,17,257$ is one more than a power of two, so every squarefree product of them has power-of-two totient. Ten odd examples are

An integral positive definite binary quadratic formis reduced whenwith $b\ge 0$ when $|b|=a$ or $a=c$. Its discriminant is $D=b^2-4ac$.

For $D=-20$, reduction gives $3a^2\le 20$, so $a=1$ or $2$. Since $b^2\equiv D(\mathrm{mod}4)$, $b$ is even. If $a=1$, then $|b|\le 1$ forces $b=0$, and $c=5$. If $a=2$, then $b\in \{-2,0,2\}$; integrality ofleaves $b=\pm 2$ and $c=3$, and the boundary convention retains only $b=2$. Hence the complete list is

Now suppose the prime $p\ne 5$ is represented by $x^2+5y^2$. If $p=2$, the equation is impossible modulo four, so $p$ is odd. The integers $x$ and $y$ then have opposite parity, and thereforeAlso $x\not\equiv 0(\mathrm{mod}5)$, since otherwise $5\mid p$; henceThe Chinese remainder theorem gives the stronger conclusionIn particular,as required.

Put $e=(N-1)/2$. The odd integer $N$ is an Euler pseudoprime to the coprime base $b$ whenwhere $(b/N)$ is the Jacobi symbol.

Let $G=(\mathbb{Z}/N\mathbb{Z}{)}^{\times }$ be the unit group of residue classes modulo $N$, and partition it into the set $E$ of bases satisfying the displayed congruence and the set $W$ of Euler witnesses that do not. If $b_0\in W$, multiplication by $b_0$ maps $E$ injectively into $W$: indeed, if $b\in E$ and $b{b}_0$ also lay in $E$, then the multiplicativity of the Jacobi symbol would giveCancelling the invertible congruence for $b$ would say that $b_0\in E$, a contradiction. Hence $|W|\ge |E|$, so at least half of the coprime bases are witnesses.

It remains to construct one witness for every odd composite number $N$. If $N$ is not squarefree, choose an odd prime number $p$ with $p^2\mid N$. The Chinese remainder theorem gives a unit $b$ such that $b\equiv 1+p(\mathrm{mod}{p}^a)$ for the full power $p^a\mid N$ and $b\equiv 1$ modulo every other prime-power factor. The binomial theorem givesSince $p\nmid e$, this is neither $1$ nor $-1$ modulo $p^2$, whereas the Jacobi symbol is always $1$ or $-1$. Thus $b$ is a witness.

If $N$ is squarefree and composite, choose distinct primes $p,q\mid N$. By the Chinese remainder theorem, choose $b$ to be a quadratic nonresidue modulo $p$ and to satisfy $b\equiv 1$ modulo every other prime divisor of $N$. Then $(b/N)=-1$, while $b^e\equiv 1(\mathrm{mod}q)$, so the Euler congruence again fails. This proves the existence of an Euler witness for every odd composite integer.