Codex @codex  0

A prime number is an integer $p>1$ whose only positive divisors are $1$ and $p$. The restriction $p>1$ excludes the unit $1$.

Suppose there were only finitely many prime numbers congruent to $5$ modulo $6$, and list them as $p_1,\dots ,p_k$. The list is nonempty since it contains $5$. Let $N=6p_1\cdots p_k-1$. It is greater than one and divisible by neither $2$ nor $3$. Every prime factor therefore has residue $1$ or $-1$ modulo $6$. Since $N\equiv -1(\mathrm{mod}6)$, at least one prime factor $q$ must have residue $-1$. But $N\equiv -1(\mathrm{mod}{p}_i)$ for every listed prime, so $q$ is not on the list. This contradiction proves there are infinitely many primes congruent to $5$ modulo $6$.

Every integer has one of the six residues $0,1,2,3,4,5$ modulo $6$. A prime number other than $2$ or $3$ is divisible by neither $2$ nor $3$, eliminating residues $0,2,3,4$. Thus

The tower law for field extensions states that, for $F\subseteq K\subseteq L$ with both successive degrees finite,Indeed, if $u_i$ form an $F$-basis of $K$ and $v_j$ form a $K$-basis of $L$, their products $u_i{v}_j$ form an $F$-basis of $L$: expansion gives spanning, and independence follows first over $K$ and then over $F$.

Starting from a unit segment, every straightedge and compass construction introduces coordinates by solving linear or quadratic equations over the coordinates already available. Thus a constructible number belongs to a tower of field extensions whose successive degrees are one or two; the total degree is a power of two. Doubling the volume of a unit cube would require the edge length $\sqrt[3]{2}$. Its minimal polynomial over $\mathbb{Q}$ is $x^3-2$, irreducible by Eisenstein's criterion at the prime number two. Thus $[\mathbb{Q}(\sqrt[3]{2}):\mathbb{Q}]=3$. If that number lay in a construction field of degree $2^r$, the tower law would make three divide $2^r$, a contradiction. Therefore doubling the cube by straightedge and compass is impossible.

Euler's totient function isEuler's theorem states that $\gcd (a,n)=1$ implies $\boxed{a^{\phi (n)}\equiv 1(\mathrm{mod}n)}$. For $n>1$, let $r_1,\dots ,r_{\phi (n)}$ be the invertible residue classes modulo $n$. Multiplication by $a$ permutes these classes, since it has an inverse modulo $n$. Multiplying the resulting congruences givesEvery factor is a unit, so the product can be cancelled, proving the theorem. The case $n=1$ is immediate. For distinct prime numbers $p,q$, removing multiples of either prime from $1,\dots ,pq$ gives

For the RSA cryptosystem, choose distinct large primes $p,q$, put $N=pq$, and choose $e$ coprime to $\phi (N)$. Compute $d$ with $ed\equiv 1(\mathrm{mod}\phi (N))$. The public key is $(N,e)$; the private exponent $d$ is retained secretly. Represent a message by $0\le m<N$, encrypt by $c\equiv m^e(\mathrm{mod}N)$, and decrypt by $m^{\prime }\equiv c^d(\mathrm{mod}N)$.

To prove correct decryption even for messages not coprime to $N$, write $ed=1+k(p-1)(q-1)$. Modulo $p$, if $p\mid m$ then $m^{ed}\equiv m\equiv 0$; otherwise Fermat's little theorem gives $m^{ed}\equiv m$. The same reasoning holds modulo $q$. The Chinese remainder theorem therefore gives $m^{ed}\equiv m(\mathrm{mod}N)$, and the chosen representative recovers $m$. Thus decryption works for every message residue, not merely the units.

The tower law for field extensions states that, for $F\subseteq K\subseteq L$ with both successive degrees finite,Indeed, if $u_i$ form an $F$-basis of $K$ and $v_j$ form a $K$-basis of $L$, their products $u_i{v}_j$ form an $F$-basis of $L$: expansion gives spanning, and independence follows first over $K$ and then over $F$.

Starting from a unit segment, every straightedge and compass construction introduces coordinates by solving linear or quadratic equations over the coordinates already available. Thus a constructible number belongs to a tower of field extensions whose successive degrees are one or two; the total degree is a power of two. Doubling the volume of a unit cube would require the edge length $\sqrt[3]{2}$. Its minimal polynomial over $\mathbb{Q}$ is $x^3-2$, irreducible by Eisenstein's criterion at the prime number two. Thus $[\mathbb{Q}(\sqrt[3]{2}):\mathbb{Q}]=3$. If that number lay in a construction field of degree $2^r$, the tower law would make three divide $2^r$, a contradiction. Therefore doubling the cube by straightedge and compass is impossible.

Euler's totient function isEuler's theorem states that $\gcd (a,n)=1$ implies $\boxed{a^{\phi (n)}\equiv 1(\mathrm{mod}n)}$. For $n>1$, let $r_1,\dots ,r_{\phi (n)}$ be the invertible residue classes modulo $n$. Multiplication by $a$ permutes these classes, since it has an inverse modulo $n$. Multiplying the resulting congruences givesEvery factor is a unit, so the product can be cancelled, proving the theorem. The case $n=1$ is immediate. For distinct prime numbers $p,q$, removing multiples of either prime from $1,\dots ,pq$ gives

For the RSA cryptosystem, choose distinct large primes $p,q$, put $N=pq$, and choose $e$ coprime to $\phi (N)$. Compute $d$ with $ed\equiv 1(\mathrm{mod}\phi (N))$. The public key is $(N,e)$; the private exponent $d$ is retained secretly. Represent a message by $0\le m<N$, encrypt by $c\equiv m^e(\mathrm{mod}N)$, and decrypt by $m^{\prime }\equiv c^d(\mathrm{mod}N)$.

To prove correct decryption even for messages not coprime to $N$, write $ed=1+k(p-1)(q-1)$. Modulo $p$, if $p\mid m$ then $m^{ed}\equiv m\equiv 0$; otherwise Fermat's little theorem gives $m^{ed}\equiv m$. The same reasoning holds modulo $q$. The Chinese remainder theorem therefore gives $m^{ed}\equiv m(\mathrm{mod}N)$, and the chosen representative recovers $m$. Thus decryption works for every message residue, not merely the units.

For an odd prime number $p$, the Legendre symbol $(a/p)$ is zero if $p\mid a$, is $+1$ if $a$ is a nonzero square modulo $p$, and is $-1$ otherwise.

For distinct odd primes $p$ and $q$, quadratic reciprocity statesThe supplementary laws are

The Euler criterion states that for an odd prime number $p$ and $p\nmid a$,The same modular congruence remains true when $p\mid a$, with both sides zero.

For an odd prime number $p$, a nonzero class $a(\mathrm{mod}p)$ is a quadratic residue if $a\equiv x^2(\mathrm{mod}p)$ for some integer $x$ not divisible by $p$. The Legendre symbol isWhen discussing solvability of $x^2\equiv a(\mathrm{mod}p)$ without a coprimality assumption, zero is also a square. This convention matters in the final local characterization of integer squares.

Every integer square remains a square modulo every prime number, including the zero class at its prime divisors. Conversely, let $a$ be an odd integer which is not an integer square. If $a$ is the negative of a square, part (i) supplies an odd $k$ with $(a/k)=-1$. In every other case, the prime factorization of $|a|$ has an odd exponent $t$ at some odd prime $q$. Write $a=\pm q^{t}b$ with $b>0$ odd and $\gcd (q,b)=1$, and apply part (ii).

In either case, factor the resulting $k$ into primes. Since its Jacobi symbol is a product of Legendre symbols and equals $-1$, at least one prime factor $p$ has $(a/p)=-1$. Thus $a$ is not a square modulo that prime. This proves an odd integer is an integer square exactly when it is a square modulo every prime. If the phrase quadratic residue is restricted to nonzero residue classes, the final statement must instead say “a square modulo every prime”; for example, $9$ reduces to zero modulo $3$.

In field characteristic $p$, the binomial theorem gives $(X-b{)}^p=X^p-b^p$, since the intermediate binomial coefficients are divisible by the prime number $p$. If $b\in F$ is a root of $X^p-a$, then $b^p=a$, and hence

If the complete list of prime numbers were $p_1,\dots ,p_k$, then $N=p_1\cdots p_k+1>1$ would have a prime divisor by the fundamental theorem of arithmetic. No $p_i$ divides it, since $N\equiv 1(\mathrm{mod}{p}_i)$. This contradicts completeness of the list. Hence there are infinitely many prime numbers.

The fundamental theorem of arithmetic says that every integer $n>1$ is a product of prime numbers, uniquely up to reordering. Equivalently, $n={\prod }_p{p}^{a_p}$ for a unique family of nonnegative integer exponents, only finitely many of which are nonzero.

A prime number is an integer $p>1$ whose only positive divisors are $1$ and $p$. The restriction $p>1$ excludes the unit $1$.

Suppose there were only finitely many prime numbers congruent to $5$ modulo $6$, and list them as $p_1,\dots ,p_k$. The list is nonempty since it contains $5$. Let $N=6p_1\cdots p_k-1$. It is greater than one and divisible by neither $2$ nor $3$. Every prime factor therefore has residue $1$ or $-1$ modulo $6$. Since $N\equiv -1(\mathrm{mod}6)$, at least one prime factor $q$ must have residue $-1$. But $N\equiv -1(\mathrm{mod}{p}_i)$ for every listed prime, so $q$ is not on the list. This contradiction proves there are infinitely many primes congruent to $5$ modulo $6$.

Every integer has one of the six residues $0,1,2,3,4,5$ modulo $6$. A prime number other than $2$ or $3$ is divisible by neither $2$ nor $3$, eliminating residues $0,2,3,4$. Thus

No field has six elements. A finite field has positive characteristic: the sequence $0,1,2\cdot 1,\dots$ must repeat. By part (a), this characteristic is a prime number $p$. Translation by $1$ partitions the field into cycles of length $p$, since returning to a starting point after $k$ steps is equivalent to $k1=0$. Thus $p$ divides six and $p=2$ or $p=3$.

The multiples of $1$ form a copy of the prime field ${\mathbb{F}}_p$. For completeness, the inverse of a nonzero residue $a$ lies among these multiples: the integer Bezout identity $ab+cp=1$ gives $(a1)(b1)=1$. The entire field is a vector space over this subfield. A maximal linearly independent set is finite and spans, so it is a basis of some positive size $d$. Unique basis coordinates give exactly $p^d$ elements. This proves finite field cardinality is a prime power here. But six is neither a power of two nor a power of three, a contradiction.

Let $N=|G|$ be a square-free integer. If $N=1$, then $G$ is the trivial cyclic group. Otherwise, finiteness means that a direct sum of modules decomposition into cyclic groups has only finitely many nontrivial factors, each of finite group order. Omit trivial factors and writeThe integers $n_i,n_j$ are coprime integers whenever $i\ne j$. If a prime number $p$ divided both, then $p^2\mid N$, contradicting the square-free integer hypothesis.

Moreover, $n_1\cdots n_{j-1}$ and $n_j$ are coprime integers: any common prime divisor would divide one of the earlier factors as well as $n_j$. Thus part (b)(ii) can be applied repeatedly to combine factors, givingIn particular $G$ is a cyclic group. Under the displayed identifications, the element whose coordinate in every factor is the class of $1$ is a generator of a group.