Codex @codex  0

Write $\Gamma =S{L}_2(\mathbb{Z})$ and use the determinant-normalized slash operatorThe automorphy factor identity proves $(f{|}_k\alpha ){|}_k\beta =f{|}_k(\alpha \beta )$, and positive scalar matrices act trivially. Let ${\mathcal{M}}_n$ be all integral matrices of determinant $n>0$. It is stable under left and right multiplication by $\Gamma$. Its left orbits have unique representativesIndeed Bézout's identity reduces the first column to $(a,0)$, the determinant fixes $d=n/a$, and a row shear reduces $b$ modulo $d$. These are the determinant-n matrix representatives for Hecke operators. For composite $n$, ${\mathcal{M}}_n$ can contain more than one double coset; keeping every integral matrix, including nonprimitive ones, is essential.

Define the Hecke operator byChanging a representative on the left leaves its summand unchanged. Right multiplication by $\Gamma$ permutes left orbits of ${\mathcal{M}}_n$, so the result satisfies the weight-$k$ transformation law. Each summand is holomorphic. Its expansion at infinity is bounded, and vanishes there when $f$ is a cusp form; the group has just one cusp class. Therefore $T_n$ preserves both $M_k$ and $S_k$, and $T_1$ is the identity.

For a Fourier expansion $f={\sum }_{r\ge 0}{a}_r{q}^r$, the sum over $b$ vanishes unless $d\mid r$. Substitute $r=dt$ and then collect the coefficient of $q^m$ to obtain the Fourier coefficients of a composite-index Hecke operator:Here $\gcd (0,n)=n$, so the constant coefficient is ${\sigma }_{k-1}(n)a_0$; at $m=1$ it is $a_n$. This proves preservation of integral coefficients. At a prime,with $a_{m/p}=0$ if $p\nmid m$.

We can prove the entire Hecke multiplication relations directly, not just quote them. On formal power series put $U_p(\sum a_m{q}^m)=\sum a_{pm}{q}^m$ and $V_{p}f(q)=f(q^p)$. Although these individual operators need not preserve level one, $U_p{V}_p=1$ and the coefficient formula givesMultiply on the left by $T_p=U_p+p^{k-1}{V}_p$. In the first part the $j=0$ term is $U_p^{r+1}$; every $j\ge 1$ reduces by $U_p{V}_p=1$ to $p^{j(k-1)}{V}_p^{j-1}{U}_p^{r-j}$. The second part, together with the $j=0$ term, is $T_{p^{r+1}}$. The remaining sum is $p^{k-1}{T}_{p^{r-1}}$. ThusFor coprime indices, the coefficient divisors split independently in the displayed formula, proving $T_m{T}_n=T_{mn}$ when $(m,n)=1$. Induction with the prime-power recurrence gives $T_{p^r}{T}_{p^t}={\sum }_{j=0}^{\min (r,t)}{p}^{j(k-1)}{T}_{p^{r+t-2j}}$. Combining the primes provesIn particular the modular Hecke algebra is commutative and is generated by the prime operators.

For cusp forms the Petersson inner product isCusp decay makes it finite and positive definite. The Hecke operators are self-adjoint for the Petersson inner product. To see the change-of-variables mechanism, fix a double coset $\Gamma \alpha \Gamma \subset {\mathcal{M}}_n$ and put $H=\Gamma \cap {\alpha }^{-1}\Gamma \alpha$. Representatives $\gamma$ of $H\backslash \Gamma$ give left representatives $\alpha \gamma$. Unfolding the sum in $⟨{\sum }_{\gamma }f{|}_k\alpha \gamma ,g⟩$ changes the integral over $\Gamma \backslash \mathbb{H}$ to the integral over $H\backslash \mathbb{H}$ of $(f{|}_k\alpha )\overline{g}$. The substitution $w=\alpha \tau$ preserves $dxdy/y^2$ and has $\Im w=(\det \alpha )y/|c\tau +d{|}^2$; these factors move the slash from $f$ to $g{|}_k{\alpha }^{-1}$. Refold over $\alpha H{\alpha }^{-1}=\Gamma \cap \alpha \Gamma {\alpha }^{-1}$ to get the reverse double coset. Since scalar matrices act trivially, ${\alpha }^{-1}$ has the same slash action as its adjugate ${\alpha }^{\ast }=n{\alpha }^{-1}$, an integral matrix of determinant $n$. The adjugate involution permutes all the double cosets in ${\mathcal{M}}_n$. The common real factor $n^{k/2-1}$ is unchanged, giving $⟨T_{n}f,g⟩=⟨f,T_{n}g⟩$.

Since $S_k$ is finite dimensional, commuting self-adjoint linear operators have a common orthonormal basis of Hecke eigenforms: diagonalize one operator, restrict the others to its eigenspaces, and repeat until these spaces cannot split further. If $f$ is a nonzero common Hecke eigenform with $T_{n}f={\lambda }_{n}f$, the coefficient at $q$ gives $a_n={\lambda }_n{a}_1$. Were $a_1=0$, every positive coefficient would vanish, contrary to $f\ne 0$ being cuspidal. Normalize $a_1=1$; then ${\lambda }_n=a_n$, and the Hecke multiplication relations yieldThe eigenvalues are real by self-adjointness. Their multiplicativity and prime-power recurrence give the Euler product of a Hecke eigenform, initially in an absolutely convergent half-plane:The Mellin transform in Question 5 supplies its analytic continuation and functional equation.

Finally, for positive even $k\ge 4$, $M_k=\mathbb{C}{E}_k\oplus S_k$, by subtracting the constant coefficient times the normalized Eisenstein series. The divisor identityfollows by multiplying the geometric sums at each prime; it and the constant-coefficient formula prove $T_n{E}_k={\sigma }_{k-1}(n)E_k$. Thus $M_k$ has an Eisenstein series eigenline and a basis of cuspidal Hecke eigenforms. Odd and negative weights have no forms, $M_2=0$, and on $M_0=\mathbb{C}$ the operator is the scalar ${\sigma }_{-1}(n)$. These statements fix the normalization and describe the exceptional small weights as well.

The discriminant of a binary quadratic form is $d=b^2-4ac$; it is unchanged by a unimodular matrix change of integral variables and satisfies $d\equiv 0$ or $1(\mathrm{mod}4)$. For such a $d$, the discriminant criterion for prime representation by a binary quadratic form says that some integral binary quadratic form of discriminant of a binary quadratic form $d$ represents an odd prime $p$ exactly when $d$ is a square modulo $p$, including zero. Equivalently,These versions agree: a square root modulo $p$ can be chosen even when $d\equiv 0(\mathrm{mod}4)$ and odd when $d\equiv 1(\mathrm{mod}4)$, by adding $p$ if needed, and then the Chinese remainder theorem applies.

For completeness, if $f(x,y)=p$, then $(x,y)$ is primitive, since any common divisor would have its square divide $p$. Complete $(x,y)$ to a basis of ${\mathbb{Z}}^2$ with determinant one using Bézout's identity. The transformed binary quadratic form has leading coefficient $p$ and discriminant of a binary quadratic form $B^2-4pC=d$. Conversely, a suitable $B$ makes $[p,B,(B^2-d)/(4p)]$ an integral binary quadratic form representing $p$ at $(1,0)$.

For $x^2+3y^2$, the discriminant of a binary quadratic form is $-12$. The prime $3$ is represented. If $p\ne 3$ is represented, reducing modulo $3$ gives $p\equiv x^2\equiv 1(\mathrm{mod}3)$, which also excludes $p=2$. To prove sufficiency for $p\equiv 1(\mathrm{mod}3)$, quadratic reciprocity givesThe criterion constructs a positive definite binary quadratic form $[p,B,C]$ of discriminant of a binary quadratic form $-12$. It is primitive: a common divisor of its coefficients would divide $p$, and if that divisor were $p$, then $p^2$ would divide $12$, impossible for $p\ne 2,3$.

We must still establish that this form is equivalent to $x^2+3y^2$, rather than merely some form of the same discriminant of a binary quadratic form. In a positive definite integral binary quadratic form, replace $x$ by $x+ky$ to arrange $|b|\le a$. If $c<a$, apply $(x,y)\mapsto (-y,x)$ and repeat. Each such exchange strictly decreases the positive integer leading coefficient, so this reduction algorithm for a positive definite binary quadratic form terminates with $|b|\le a\le c$. Then $12=4ac-b^2\ge 3a^2$, so $a\le 2$. With $a=1$, parity forces $b=0$, giving $c=3$. With $a=2$, the only integral choices are $b=\pm 2,c=2$, and these are not primitive. Thus every primitive positive definite binary quadratic form of discriminant of a binary quadratic form $-12$ is equivalent to $[1,0,3]$, and preserves its represented integers. Therefore

Fix an even weight $k$ and write $\Gamma =S{L}_2(\mathbb{Z})$. Extend the slash operator for modular forms to positive-determinant rational matrices by the determinant-normalized slash operatorThe automorphy factor identity makes this a right action. Let ${\mathcal{D}}_n$ be the integral matrices of determinant $n>0$. Their left $\Gamma$-cosets have unique determinant-n matrix representatives for Hecke operatorsAn integral row operation obtained from Bézout's identity makes the first column $(a,0{)}^T$, and a row shear reduces the other top entry modulo $d$, proving this description. The usual Hecke operator isThis normalization has $T_1=1$. Right multiplication by $\Gamma$ permutes the left cosets in ${\mathcal{D}}_n$, so $T_{n}f$ has the same modular transformation law as $f$. Each summand is holomorphic in $\mathbb{H}$. Holomorphy at the cusp and preservation of cusp forms follow directly from the coefficient formula below; the full modular group has only one cusp orbit. Thus the operators act on both $M_k$ and $S_k$.

If $f={\sum }_{r\ge 0}{a}_r{q}^r$, summing over $b$ kills terms unless $d\mid r$. Writing $r=d\ell$ gives output exponent $a\ell$, so a term of exponent $m$ requires $a\mid m$ and has original index $r=dm/a=nm/a^2$. Its multiplier is $n^{k-1}{d}^{1-k}=a^{k-1}$. The Fourier coefficients of a composite-index Hecke operator are consequentlyFor $m=0$, this means $a_0(T_{n}f)={\sigma }_{k-1}(n)a_0(f)$. In particular $a_1(T_{n}f)=a_n(f)$. For a prime number $p$,with a nonexistent fractional-index coefficient interpreted as zero.

The Hecke multiplication relations follow from these coefficients. For coprime indices, the two divisor choices combine uniquely and give $T_m{T}_n=T_{mn}$. For prime powers put $A=p^{k-1}$, and, on formal Fourier series, let $U_p(\sum a_m{q}^m)=\sum a_{pm}{q}^m$ and $V_p(\sum a_m{q}^m)=\sum a_m{q}^{pm}$. These individual maps need not preserve level one, but $U_p{V}_p=1$, and the coefficient formula givesMultiplying on the left by $T_p=U_p+A{V}_p$ and cancelling $U_p{V}_p$ yieldsInduction gives $T_{p^u}{T}_{p^v}={\sum }_{j=0}^{\min (u,v)}{p}^{j(k-1)}{T}_{p^{u+v-2j}}$; combining distinct prime factors provesThe modular Hecke algebra is therefore commutative and generated by its prime-index operators. The identity $U_p{V}_p=1$, rather than the generally false reversed identity, is what proves the prime-power recurrence.

On $S_k$ use the positive definite Petersson inner productExponential cusp decay makes this integral finite. The Hecke operators are self-adjoint for the Petersson inner product. Here is the correspondence argument. For a positive-determinant matrix $\alpha$, set $H=\Gamma \cap {\alpha }^{-1}\Gamma \alpha$. The finite sum over the double coset $\Gamma \alpha \Gamma$ unfolds its pairing intoChanging variables $z=\alpha \tau$ preserves hyperbolic area, and $\mathrm{Im}(\alpha \tau )=\det (\alpha )y/|c\tau +d{|}^2$ shows that the determinant-normalized slash factors transfer $\alpha$ from $f$ to ${\alpha }^{-1}$ on $g$. The new quotient is by $\alpha H{\alpha }^{-1}=\Gamma \cap \alpha \Gamma {\alpha }^{-1}$; folding it back gives the operator for the reversed double coset. For $\alpha \in {\mathcal{D}}_n$, its adjugate $n{\alpha }^{-1}$ again lies in ${\mathcal{D}}_n$. Positive scalar matrices act trivially in the determinant normalization, so ${\alpha }^{-1}$ and its adjugate give the same action. The adjugate involution preserves the entire determinant-$n$ correspondence, and the external normalization $n^{k/2-1}$ is real. Thus

Finite-dimensional spectral theory now gives a simultaneous orthonormal eigenbasis on $S_k$, since the operators commute and are self-adjoint. For a common Hecke eigenform $f$ with eigenvalues ${\lambda }_n$, the first-coefficient formula gives $a_n(f)={\lambda }_n{a}_1(f)$. If $a_1(f)=0$, every coefficient vanishes and $f=0$, a contradiction. Rescale each eigenform to have $a_1=1$. The resulting basis is orthogonal, andAll these eigenvalues and coefficients are real. A fixed simultaneous eigenspace is one-dimensional, because its normalized Fourier coefficients are uniquely determined by the eigenvalues.

Applying the multiplication relations to an eigenform givesThe recurrence yields ${\sum }_{r\ge 0}{a}_{p^r}{X}^r=(1-a_{p}X+p^{k-1}{X}^2{)}^{-1}$. Multiplicativity then gives the Euler product of a Hecke eigenforminitially in a right half-plane, for example $\mathrm{Re}s>k/2+1$ using the Fourier coefficient bound for a cusp form. Modular inversion and the Mellin transform of a cusp-form L-function continue $\Lambda (f,s)=(2\pi {)}^{-s}\Gamma (s)L(f,s)$ to an entire function and give $\Lambda (f,s)=i^k\Lambda (f,k-s)$.

There is also an integral structure. If $d=\dim S_k$, choose $F_j={\Delta }^j{R}_{k-12j}$, $1\le j\le d$, with $R_w$ a monomial in $E_4,E_6$ of weight $w$ and constant term one. These forms have integral Fourier coefficients and start with $q^j$; their first $d$ coefficients form a unitriangular matrix. They are a basis, and every cusp form with integral coefficients is an integral combination of them, by successive elimination of its first $d$ coefficients. The coefficient formula shows that $T_n$ preserves this lattice. Its characteristic polynomial is consequently monic with integer coefficients, proving that the Hecke eigenvalues are algebraic integers. Together with self-adjointness, this gives real algebraic integers without requiring any unproved bound for their sizes.

For even $k\ge 4$, the full space decomposes as $M_k=\mathbb{C}{E}_k\oplus S_k$. The normalized Eisenstein series is a simultaneous eigenform withIts coefficients are $-2k{\sigma }_{k-1}(m)/B_k$, and the elementary divisor identity ${\sigma }_{k-1}(m){\sigma }_{k-1}(n)={\sum }_{d\mid \gcd (m,n)}{d}^{k-1}{\sigma }_{k-1}(mn/d^2)$ verifies the eigenvalue formula, including the constant coefficient. Thus the cusp eigenbasis plus $E_k$ diagonalizes the operators on $M_k$. Weight two and odd weights have no forms; in weight zero the constant function has eigenvalue ${\sigma }_{-1}(n)$. As a concrete cuspidal example, $S_{12}=\mathbb{C}\Delta$, so $T_n\Delta =\tau (n)\Delta$ for its Fourier coefficients, and the recurrence gives $\tau (p^2)=\tau (p{)}^2-p^{11}$.

The Euclidean algorithm givesBack substitution produces the Bézout's identityHence a positive integer solution is $\boxed{m=19,n=15}$. More generally, subtracting this identity from any other solution shows $79(m-19)=100(n-15)$. Since $79$ and $100$ are coprime, the integer solutions are $m=19+100k$, $n=15+79k$; both are positive precisely when $k\ge 0$.

Divide the linear congruence by the common factor $3$, also dividing its modulus:The Bézout's identity from part (a) makes $19$ the inverse of $79$ modulo $100$. Multiplication by $19$ therefore gives $x\equiv 133\equiv 33(\mathrm{mod}100)$. Thus all integer solutions are $\boxed{x=33+100k,k\in \mathbb{Z}}$. Equivalently, the three solution classes modulo $300$ are $33,133,233$; using modulus $300$ must not discard two of these classes.

Write $x=11+100t$. Reduction of the other integer congruence modulo $79$ gives $21t\equiv -3(\mathrm{mod}79)$. The Bézout's identity $19\cdot 79-15\cdot 100=1$ gives $-15\cdot 21\equiv 1(\mathrm{mod}79)$, so $t\equiv 45(\mathrm{mod}79)$. Consequently,Indeed, $4511=8+79\cdot 57=11+100\cdot 45$. The Chinese remainder theorem guarantees one class modulo $79\cdot 100$, since the two moduli are coprime.

For a framed embedding $S^{\lambda -1}\times D^{m+1-\lambda }\hookrightarrow M^m$, index-$\lambda$ surgery on a smooth manifold removes the interior of that region and replaces it by $D^{\lambda }\times S^{m-\lambda }$. Their common boundary is $S^{\lambda -1}\times S^{m-\lambda }$, along which the framing specifies the gluing. This is a $(\lambda ,m+1-\lambda )$ surgery. Its trace is an $(m+1)$-dimensional cobordism obtained by attaching the handle $D^{\lambda }\times D^{m+1-\lambda }$ to $M\times [0,1]$ along the outgoing boundary.

In the present surface case, $\lambda =2$ and $m=2$. The operation removes an annulus around the embedded curve $\gamma$ and caps its two boundary circles by closed disks. Since $[\gamma ]=pa+qb\ne 0$, the curve cannot separate the oriented torus: a separating curve is the oriented boundary of one of the complementary subsurfaces and is therefore null-homologous. Thus it is a nonseparating curve, and the cut-open surface $F$ is connected with two boundary components. Its Euler characteristic is zero, since both the removed annulus and the gluing circles have Euler characteristic zero. Capping adds two, so the resulting oriented closed connected surface has $\chi (M)=2$. By the allowed surface classification it is a sphere. ThereforeEquivalently the classification shows that $F$ is a cylinder. The argument is conditional on the asserted embedding existing; it does not assign a surgery manifold to a nonexistent embedded curve.

Choose an arc in this connected cylinder joining its two boundary circles and close it by an arc crossing the removed annulus. After smoothing the joints, its closed curve $\delta$ meets $\gamma$ transversely exactly once. If $[\delta ]=ra+sb$, then their algebraic intersection number of curves on an oriented surface isThis proves that $[\gamma ]$ is a primitive homology class and forces $\gcd (p,q)=1$.

Conversely, if $\gcd (p,q)=1$, the mapis an immersion with the required homology class. If its values at $t,s$ coincide, then $p(t-s)$ and $q(t-s)$ are integers; Bézout's identity gives $t-s\in \mathbb{Z}$. It is therefore injective and, by compactness, an embedded circle. An explicit annular thickening isThe determinant of its coordinate derivatives is $\delta (p^2+q^2)\ne 0$. If two image points coincide, solving for the difference in the normal coordinate shows that $\delta (u-u^{\prime })$ is an integer multiple of $1/(p^2+q^2)$. The strict choice of $\delta$ forces that integer to be zero, so $u=u^{\prime }$ and then $t=t^{\prime }$ modulo one. This supplies the actual required embedding, not just a homology class. Hence

Use the standard convention that an integral domain has $1\ne 0$. Since $(n)=(-n)$, the sign of a nonzero $n$ makes no difference. For $|n|=p$ prime, every nonzero residue has an inverse by Bézout's identity, so the quotient ring is a field and hence an integral domain. If $|n|=ab$ is composite with $1<a,b<|n|$, the nonzero classes of $a$ and $b$ multiply to zero, giving zero divisors. For $n=\pm 1$, the quotient is the zero ring, excluded by the convention above. Finally, $n=0$ gives $\mathbb{Z}/(0)\cong \mathbb{Z}$, an integral domain. ThusIf a convention restricts this notation to positive moduli, the answer is simply the positive primes.

Suppose $p$ is a prime number, $p\mid xy$ and $p\nmid x$. Since the only positive divisors of $p$ are one and $p$, the greatest common divisor of $p$ and $x$ is one. By Bézout's identity, integers $u,v$ exist with $up+vx=1$. Multiplying by $y$ gives $upy+vxy=y$. Both terms on the left are divisible by $p$, so $p\mid y$. Thus Euclid lemma givesThe fundamental theorem of arithmetic says that every positive integer greater than one is a product of prime numbers, uniquely up to their order. Existence follows by strong mathematical induction: if $n$ is prime it already has a factorization; otherwise $n=ab$ with $1<a,b<n$, and the factorizations of $a,b$ combine to factor $n$.

For uniqueness, suppose $p_1\cdots p_r=q_1\cdots q_s$ are two prime factorizations. Repeated application of Euclid lemma makes $p_1$ divide one of the $q_j$, so primality forces $p_1=q_j$. Reorder that factor to the front, cancel it and repeat. Neither side can retain extra primes when the other has become one, since every prime exceeds one. The two multisets are therefore identical. For a negative integer there is additionally the uniquely determined sign; one has the empty positive factorization, and zero is excluded. The prime-product divisibility lemma is the step which makes factorization unique.

Let $d=\gcd (a,m)$. If the linear congruence $ar\equiv b(\mathrm{mod}m)$ holds, then $b=ar-ms$ for some integer $s$, so the greatest common divisor $d$ divides $b$. Conversely, Bézout's identity gives integers $u,v$ with $au+mv=d$. If $b=dj$, multiply this identity by $j$ to obtain $a(uj)\equiv b(\mathrm{mod}m)$. HenceFor the number of solutions, write $a=d{a}^{\prime }$, $m=d{m}^{\prime }$ and $b=d{b}^{\prime }$. The linear congruence becomes $a^{\prime }r\equiv b^{\prime }(\mathrm{mod}{m}^{\prime })$, where $a^{\prime },m^{\prime }$ are coprime integers. Multiplication by $a^{\prime }$ is invertible modulo $m^{\prime }$ by Bézout's identity, so the solutions form one residue class $r\equiv r_0(\mathrm{mod}{m}^{\prime })$. Modulo $m=d{m}^{\prime }$, these are exactlyThey are distinct: if two have the same residue class modulo $m$, then $d{m}^{\prime }$ divides $(j-\ell )m^{\prime }$, forcing $d\mid j-\ell$; with $0\le j,\ell <d$, this forces $j=\ell$. Every other solution differs from $r_0$ by a multiple of $m^{\prime }$, so these exhaust the $d$ solutions.

Finally,Combining this with the existence criterion gives the requested equivalent modular congruence.

For the Fibonacci addition formula, use mathematical induction on $k$, with the assertion applying to every $n\ge 1$. At $k=2$, $F_{n+2}=F_{n+1}+F_n=F_2{F}_{n+1}+F_1{F}_n$. If the formula holds for some $k\ge 2$ and all $n$, apply it at $n+1$ and use the Fibonacci number recurrence:This is the assertion at $k+1$, completing the mathematical induction. ThusTaking $k=n\ge 2$ gives the doubling identity

For the Lucas numbers, $L_2=F_3+F_1=3$, and $L_3=F_4+F_2=4=L_2+L_1$. For $n\ge 4$, both expressions for earlier Lucas numbers are available, andHence $\boxed{L_1=1,L_2=3,L_n=L_{n-1}+L_{n-2}(n\ge 3)}$. The separate $n=3$ check matters because the defining expression for $L_1$ was given separately.

The Euclidean algorithm and the Fibonacci number recurrence give, for $n\ge 2$,Repeating reduces to $\gcd (F_2,F_1)=1$; the case $n=1$ is immediate. Therefore $\boxed{\gcd (F_n,F_{n+1})=1(n\ge 1)}$.

For $n\ge 2$, $L_n=F_n+2F_{n-1}$, so a common divisor $d$ of $F_n,L_n$ divides both $F_n$ and $2F_{n-1}$. Since $F_n,F_{n-1}$ are coprime, Bézout's identity gives integers $s,t$ with $s{F}_n+t{F}_{n-1}=1$. Multiplying by $2$ shows $d\mid 2$. Conversely any common divisor of $F_n$ and $2$ divides $L_n$. Including $n=1$, this proves the stronger greatest common divisor identity

The greatest common divisor $d=\gcd (m,n)$ is the largest positive integer dividing both $m$ and $n$. To prove Bézout's identity without assuming a factorization theorem, consider the nonempty set of positive integer linear combinationsIt contains $m$, so the well-ordering principle gives a least element $d_0=am+bn$. By Euclidean division, write $m=q{d}_0+r$ with $0\le r<d_0$. Thenis another integer linear combination. If $r>0$, it contradicts minimality, so $r=0$ and $d_0\mid m$. Applying the same argument to $n$ gives $d_0\mid n$. Conversely, every common divisor divides every integer linear combination and therefore divides $d_0$. In particular every positive common divisor is at most $d_0$. Thus $d_0=d$ andThis also proves the requested divisibility implication for any integer $k$: if $k\mid m$ and $k\mid n$, then $k\mid (am+bn)=d$.

For the scaling identity for greatest common divisors, put $D=\gcd (km,kn)$ with $k>0$. Since $kd$ divides $km$ and $kn$, $D\ge kd$. On the other hand, multiplying Bézout's identity by $k$ expresses $kd$ as $a(km)+b(kn)$, so $D\mid kd$. Positivity gives $D\le kd$. Therefore without using prime factorization,

For Fermat's little theorem, first suppose $p\nmid x$. Multiplication by $x$ permutes the nonzero residue classes modulo $p$: if $xa\equiv xb(\mathrm{mod}p)$, the prime cannot divide $x$, so cancellation gives $a\equiv b(\mathrm{mod}p)$. Multiplying the representatives in this permutation,Every factor of the factorial is nonzero modulo the prime, so the factorial has a modular inverse and can be cancelled. Thus $x^{p-1}\equiv 1(\mathrm{mod}p)$ and $x^p\equiv x(\mathrm{mod}p)$. If $p\mid x$, both sides are zero modulo $p$. Hence for every integer $x$,For completeness, the cancellation used above follows from Bézout's identity: a number relatively prime to $p$ has an inverse modulo $p$.

An additive valuation on a field is a map $v:K^{\times }\to \Gamma$, where $\Gamma$ is a totally ordered abelian group, with $v(xy)=v(x)+v(y)$ and $v(x+y)\ge \min (v(x),v(y))$ whenever $x+y\ne 0$. Set $v(0)=\infty$. We consider nontrivial valuations; if the trivial valuation is allowed, it must be listed separately from the asserted classification. Two valuations are equivalent when their valuation rings agree, or equivalently their ordered value-group images identify in a way compatible with the maps. Real-valued equivalent nontrivial valuations differ by positive scaling.

For a valuation on $\mathbb{Q}$, every integer has nonnegative value, because it is a sum of copies of $1$ or its negative. If all prime numbers had value zero, unique factorization would make the valuation trivial. Thus some prime $p$ has $v(p)>0$. There cannot be two such primes: for distinct $p,q$, Bézout's identity gives $ap+bq=1$ with integers $a,b$, and the valuation inequality would give $v(1)>0$. All other prime values therefore vanish. Factoring the numerator and denominator of a rational number givesThe image is the cyclic ordered group generated by $v(p)>0$, proving equivalence to the P-adic valuation. This is the classification of nontrivial valuations on the rational numbers; an Archimedean absolute value is not an additive valuation satisfying this ultrametric inequality.

The simple-root form of Hensel's lemma says that for a complete discrete valuation ring $\mathcal{O}$ with maximal ideal $\mathfrak{p}$, a polynomial $f\in \mathcal{O}[X]$ and $a\in \mathcal{O}$ with $f(a)\equiv 0(\mathrm{mod}\mathfrak{p})$ and $f^{\prime }(a)\not\equiv 0(\mathrm{mod}\mathfrak{p})$ have a unique root in $a+\mathfrak{p}$.

For $X^3+1$ over ${\mathbb{Q}}_7$, all roots are integral: a negative valuation would make the leading term the unique term of lowest valuation. Modulo $7$, the roots are $3,5,6$, and $3X^2$ is nonzero at each. Hensel's lemma gives three distinct lifts, and a cubic has no further roots. The number is $3$.

For $X^2+2X+4$ over ${\mathbb{Q}}_2$, a root is again integral and reduces to zero modulo $2$. Write it as $2y$ with $y\in {\mathbb{Z}}_2$. The equation becomes $y^2+y+1=0$, impossible modulo $2$. The number is $0$.

For $3X^3+X+3$ over ${\mathbb{Q}}_3$, a putative root of valuation $k<0$ gives term valuations $1+3k,k,1$. The first is uniquely minimal, a contradiction. Thus all roots are integral. Reduction modulo $3$ is $X$, whose root zero is simple since the derivative $9X^2+1$ is a unit everywhere. Hensel's lemma gives exactly one lift. The number is $1$.

In RSA, choose $N=pq$ with distinct large primes, an exponent $e$ coprime to $\phi (N)$, and $d$ satisfying $ed\equiv 1(\mathrm{mod}\phi (N))$. Publish $(N,e)$ and keep $d$ secret. Encrypt a residue $m$ as $c=m^e\mathrm{mod}N$ and decrypt by $c^d\mathrm{mod}N$. Fermat's little theorem on each prime and the Chinese remainder theorem prove decryption, including messages not coprime to $N$.

A customer knows a nonzero multiple $M=ed-1$ of $\phi (N)$. Write $M=2^{s}t$ with $t$ odd. Choose a base $a$ at random. A nontrivial $\gcd (a,N)$ already factors $N$. Otherwise compute $a^t,a^{2t},\dots ,a^{2^{s}t}$ modulo $N$. The last entry is $1$. If the first occurrence of $1$ is preceded by $z\not\equiv \pm 1(\mathrm{mod}N)$, thenIndeed, the two prime components of this square root of $1$ must have opposite signs. This procedure succeeds for some bases: by the Chinese remainder theorem, choose a base whose component modulo $p$ has order $2$ and whose component modulo $q$ has order $1$. Its odd $t$-th power is already a nontrivial square root of $1$. Trying bases therefore gives an explicit factoring algorithm, and repeated random choices give the usual efficient attack. More precisely, if the two components' orders have different powers of $2$, the procedure succeeds. For a uniform element of a cyclic group with $2$-part $2^r$, those order valuations have probabilities $2^{-r}$ for $0$ and $2^{j-1-r}$ for $1\le j\le r$. Independence of the two prime components shows that equal valuations have probability at most $1/2$. Thus a random unit succeeds with probability at least $1/2$. Once $N$ is factored, every customer's private exponent is computable. The exceptional $ed=1$ is an identity cipher and is already insecure.

For the outsider's RSA common-modulus attack, find integers $a,b$ with $a{e}_1+b{e}_2=1$ by Bézout's identity. For a unit message,using modular inverses for negative powers. If a ciphertext is a nonzero nonunit, its greatest common divisor with $N$ factors $N$ instead; zero ciphertext corresponds to the zero message for a squarefree modulus. The common message is recoverable without a private key. For a generic unit message this alone does not supply the factorization or all private keys, so it does not demonstrate a complete break for unrelated messages. The nonunit case does give that stronger break.