Codex @codex  0

The Euclidean algorithm givesThus the greatest common divisor is $d=7$. The extended Euclidean algorithm reverses these divisions:This supplies the Bezout identity with $x=8$, $y=-11$.

To obtain all solutions of a linear Diophantine equation, subtract this particular solution from any other and divide by $7$. The result is $29(x-8)+21(y+11)=0$. Since $29$ and $21$ are coprime integers, $21$ divides $x-8$, givingEvery displayed pair satisfies the original linear Diophantine equation, so the parametrization is exhaustive.

For the modular arithmetic calculation, $21\cdot 18=378\equiv 1(\mathrm{mod}29)$, so $18$ is the modular inverse of $21$. Multiplication gives $n\equiv 25\cdot 18\equiv 15(\mathrm{mod}29)$. The admissible integers are $15+29t$ for $0\le t\le 68$, ending at $1987$; the next is $2016$. There are $\boxed{69}$ such integers.

An absolute value on a field is a map $|\cdot |:K\to {\mathbb{R}}_{\ge 0}$ satisfyingA Non-Archimedean absolute value satisfies the stronger ultrametric inequality $|x+y|\le \max (|x|,|y|)$. Two equivalent absolute values induce the same topology, or equivalently differ by a positive real power. The trivial absolute value on a field takes value one on every nonzero element. The rational classification and the compactness criterion below concern nontrivial absolute values on a field; the trivial exceptions are given explicitly.

Here the additive valuation has real values. For any $c>1$, the mutually inverse constructions areMultiplicativity becomes $v(xy)=v(x)+v(y)$, and the ultrametric inequality becomes $v(x+y)\ge \min (v(x),v(y))$. Equivalent real-valued valuations differ by positive scaling, so these constructions give the required bijection on equivalence classes. Changing $c$ merely rescales the valuation.

To justify the topology formulation, $|a|<1$ is equivalent to $a^n\to 0$. Thus two nontrivial absolute values on a field with the same topology give the same strict positivity relation on their additive valuations. Fix $t$ with $v_1(t)>0$. Comparing the signs of $m{v}_j(t)-n{v}_j(x)=v_j(t^m{x}^{-n})$, for integers $m$ and positive integers $n$, shows that $v_1(x)/v_1(t)$ and $v_2(x)/v_2(t)$ have identical rational cuts. They are equal, proving $v_2=c{v}_1$ for $c>0$. If one allows valuations in arbitrary ordered groups, the nontrivial classes arising this way are precisely rank-one valuations: higher-rank ordered value groups do not embed order-preservingly in $\mathbb{R}$.

For a nontrivial Non-Archimedean absolute value on $\mathbb{Q}$, $|n|\le 1$ for every integer $n$, by repeatedly applying the ultrametric inequality to sums of ones. Some prime $p$ must have $|p|<1$, otherwise prime factorization and multiplicativity would make every nonzero rational have value one. There is at most one such prime: if both $|p|,|q|<1$, a Bezout identity $ap+bq=1$ contradicts the ultrametric inequality. If $p\nmid m$, another Bezout identity gives $|m|=1$. HenceThis proves the non-Archimedean part of the Ostrowski theorem. If the trivial absolute value on a field is admitted, it supplies one additional class and is not equivalent to any p-adic absolute value.

The valuation ring, its maximal ideal, and its residue field areSuppose the absolute value on a field is nontrivial and $R$ is compact. The ideal $\mathfrak{m}$ is an open additive subgroup of $R$, so $k$ is discrete; as a continuous image of a compact space it is finite. The subgroup $\mathfrak{m}$ is also closed, since all its cosets are open, and is therefore compact. The continuous function $|\cdot |$ attains a maximum $\rho$ on $\mathfrak{m}$, with $0<\rho <1$. Choose $\pi$ with $|\pi |=\rho$. Then the positive values of $v=-\log |\cdot |$ have least element $-\log \rho$. Division with remainder in this additive subgroup of $\mathbb{R}$ proves $v(K^{\times })=v(\pi )\mathbb{Z}$. Thus $K$ is a discretely valued field and $\pi$ is a uniformizer.

Conversely, normalize the discrete valuation by $v(\pi )=1$. If $k$ has $q$ elements, $R/{\pi }^{N}R$ has $q^N$ elements. Each quotient therefore supplies a finite cover by balls of radius tending to zero. The ring $R$ is a closed subset of the complete metric field $K$, hence complete and totally bounded, so it is compact. Equivalently,This is the local compactness criterion for a complete non-Archimedean field, with nontriviality understood. For the trivial absolute value on a field, $R=K$ has the discrete topology and is compact exactly when $K$ is a finite field; its value group is zero rather than a nonzero discrete cyclic group.

The extended Euclidean algorithm givesBack-substituting in these equations produces the Bezout identityThus one integer solution is $\boxed{x=12,y=-7}$. In fact, subtracting this Bezout identity from any other solution and using that $17$ and $29$ are coprime integers gives all solutions: $x=12+29t$, $y=-7-17t$, where $t\in \mathbb{Z}$.

For the modular arithmetic calculation, $29$ is a prime number and $17$ is coprime to it, so Fermat little theorem gives $17^{28}\equiv 1(\mathrm{mod}29)$. Since $138=5\cdot 28-2$, and the preceding Bezout identity identifies $12$ as the modular multiplicative inverse of $17$, we obtainConsequently the least positive representative is $\boxed{28}$.

We prove the conjugate product of a quadratic ideal identity $\mathfrak{a}\overline{\mathfrak{a}}=(N(\mathfrak{a}))$, which applies to the given two-generator ideal without assuming its displayed generators form an integral basis.

The quadratic ring of integers of a number field has a basis $1,\omega$ over $\mathbb{Z}$: the vector 1 is primitive, since a rational algebraic integer must be an integer, and extends to an integral basis. Write ${\omega }^2-T\omega +U=0$, with $T,U\in \mathbb{Z}$. Let $B$ be the least positive integer in $\mathfrak{a}$ and let $s>0$ generate the set of coefficients of $\omega$ in elements of $\mathfrak{a}$. Its lattice basis can be chosen as $B,r+s\omega$, with $r\in \mathbb{Z}$. Since $B\omega \in \mathfrak{a}$, comparison of coefficients shows $s\mid B$ and $s\mid r$. Write $B=sd$, $r=se$ and $\theta =e+\omega$. ThenThe scaled ideal $\mathfrak{j}=s^{-1}\mathfrak{a}$ remains an ${\mathcal{O}}_L$-ideal. From ${\theta }^2-T^{\prime }\theta +U^{\prime }=0$ we get $U^{\prime }\in \mathfrak{j}\cap \mathbb{Z}=d\mathbb{Z}$, so $d\mid U^{\prime }$. The product $\mathfrak{j}\bar{\mathfrak{j}}$ is generated as an ideal by $d^2,d\theta ,d\bar{\theta },U^{\prime }$ and is contained in $(d)$.

Moreover $\gcd (d,T^{\prime },U^{\prime }/d)=1$. If a prime $\ell$ divided all three, then $\ell \mid T^{\prime }$ and ${\ell }^2\mid U^{\prime }$, so $\theta /\ell$ would satisfy the monic integer polynomial $z^2-(T^{\prime }/\ell )z+U^{\prime }/{\ell }^2$. It would lie in ${\mathcal{O}}_L$, impossible because its $\omega$ coefficient in the integral basis is $1/\ell$. Bezout identity now expresses one as an integer combination of $d,T^{\prime },U^{\prime }/d$. Multiplying by $d$, the terms are $d^2$, $d{T}^{\prime }=d\theta +d\bar{\theta }$, and $U^{\prime }$, all in the product. Hence $d$ belongs to it, proving $\mathfrak{j}\bar{\mathfrak{j}}=(d)$.

The determinant of the lattice basis $sd,s(e+\omega )$ gives the ideal norm $N(\mathfrak{a})=s^{2}d$. ConsequentlyIn particular $⟨b,\alpha ⟩⟨b,\bar{\alpha }⟩$ is principal. This does not require the original $b$ to be nonzero or the ideal itself to be principal.

Write an integral binary quadratic form as $Q(u,v)=A{u}^2+Buv+C{v}^2$, with discriminant of a binary quadratic form $d=B^2-4AC$. If $Q(u,v)=p$ is prime, then $\gcd (u,v)=1$: any common divisor would have its square dividing $p$. Complete $(u,v)$ to a matrix in ${\mathrm{SL}}_2(\mathbb{Z})$ using Bezout identity. After the associated integral change of variables, the properly equivalent form has leading coefficient $p$, say $[p,b,c]$. Its discriminant of a binary quadratic form gives $d=b^2-4pc$, hence $b^2\equiv d(\mathrm{mod}p)$.

Conversely suppose $b_0^2\equiv d(\mathrm{mod}p)$. Since $d$ is an integral-form discriminant of a binary quadratic form, $d\equiv 0$ or $1(\mathrm{mod}4)$. Choose $b\equiv b_0(\mathrm{mod}p)$ with even integer parity for $d\equiv 0(\mathrm{mod}4)$ and odd integer parity for $d\equiv 1(\mathrm{mod}4)$. This is possible because $p$ is odd. Then $b^2-d$ is divisible by $4p$, andis an integral form of discriminant of a binary quadratic form $d$ representing $p=Q(1,0)$. This proves the discriminant criterion for prime representation by a binary quadratic form, including the case $p\mid d$; no assumption that $d$ is a fundamental discriminant was used.

Bezout identity gives integers $b,c$ with $ab+nc=1$ whenever $\gcd (a,n)=1$, so $ab\equiv 1(\mathrm{mod}n)$. If $b,b^{\prime }$ are inverses, multiplying $a(b-b^{\prime })\equiv 0$ by an inverse gives $b\equiv b^{\prime }(\mathrm{mod}n)$. Multiplying Bezout identities for $a$ and $b$ shows that $\gcd (ab,n)=1$.

Wilson theorem states that $(p-1)!\equiv -1(\mathrm{mod}p)$ for prime $p$. Pair the nonzero residues with their unique multiplicative inverses. The only self-inverse residues are $1,-1$, whose product is $-1$, proving the theorem.

Counting one factor of $p$ for every multiple of $p$, another for every multiple of $p^2$, and so on proves Legendre formulaNow $22!\equiv 20!\cdot 21\cdot 22\equiv 2(20!)\equiv -1(\mathrm{mod}23)$, so $20!\equiv 11(\mathrm{mod}23)$. Also $v_5(1000!)=200+40+8+1=249$, while $v_2(1000!)>249$, so $1000!\equiv 0(\mathrm{mod}10^{249})$.

Finally,For $1\le j<p^m$, $v_p(p^m-j)=v_p(j)$, so the second factor is a $p$-adic unit. If $v_p(k)=\ell$, then

First, every nonzero nonunit in a principal ideal domain factors into irreducible elements. Otherwise repeatedly choose a proper nonunit factor $a_{j+1}$ of $a_j$; then the principal idealsform a strictly increasing chain, contradicting the ascending chain condition, since every principal ideal domain is a Noetherian ring.

Next every irreducible $p$ is a prime element. If $p\mid ab$ but $p\nmid a$, then $\gcd (p,a)=1$. The Bezout identity gives $up+va=1$, so multiplying by $b$ shows $p\mid b$. Thus irreducibles are prime.

Existence of an irreducible factorization and primality give uniqueness: an irreducible on one side divides the product on the other, hence is associate to one factor; cancel and continue. Therefore every principal ideal domain is a unique factorization domain.

Let $S=\left(\begin{array}{cc}0& -1\\ 1& 0\end{array}\right)$ and $T=\left(\begin{array}{cc}1& 1\\ 0& 1\end{array}\right)$. The modular group acts on the complex upper half-plane by fractional linear transformations, andFor fixed $z=x+iy$, the values $|cz+d|$ with primitive integer pairs $(c,d)$ have a positive minimum: the conditions $|cz+d|\le R$ bound both $|c|\le R/y$ and $|d|\le R+|cx|$, leaving finitely many pairs. By Bezout identity, a minimizing pair is the bottom row of a matrix in $S{L}_2(\mathbb{Z})$. Applying that matrix gives a point of maximal imaginary part in its orbit.

Translate it by a power of $T$ into $-1/2<x\le 1/2$. It must have modulus at least one, since otherwise $S$ would increase its imaginary part. If it is on the unit circle with negative real part, apply $S$, which there changes $x$ to $-x$. This gives an element of the specified half-open standard fundamental domain of the modular group. It proves existence by reduction to the standard modular region.

For uniqueness, if $z$ lies in the closed standard region then $y\ge \sqrt{3}/2$ andfor every primitive pair. If $c=0$, this follows from $d=\pm 1$; if $|c|\ge 2$, it follows from $|c|y\ge \sqrt{3}$. If $|c|=1$, then $d=0$ uses $|z|\ge 1$, while $|d|\ge 1$ givesIf both $z$ and $z^{\prime }=\gamma z$ lie in the region, applying this inequality to $\gamma$ and ${\gamma }^{-1}$ forces their imaginary parts to agree, hence $|cz+d|=1$.

The equality cases describe every possible boundary identification. For $c=0$ the map is an integer translation; the half-open vertical strip retains one representative. For $|c|=1,d=0$, equality requires $|z|=1$, and the map is an inversion followed by an integer translation. Inversion exchanges the two halves of the circle, so retaining only the right half removes the duplication; the only translation that returns the exchanged endpoint is the one identifying the two corners. The remaining equality cases have $|c|=|d|=1$, $|z|=1$ and $x=\pm 1/2$, and give only those same corner identifications. Our region retains the right corner alone. Therefore $z^{\prime }=z$, proving

The equality analysis also gives the elliptic stabilizers of the modular group. The central matrices $\pm I$ fix every point. The point $i$ is fixed by $S$, with $S^2=-I$, and the retained corner ${\rho }_{+}=e^{i\pi /3}$ is fixed by $R=TS$, with $R^3=-I$. There are no other noncentral stabilizers, and the possible bottom rows in the equality cases give exactlyThe corresponding stabilizer orders in $PS{L}_2(\mathbb{Z})$ are two, three and one; the requested group is $S{L}_2(\mathbb{Z})$, so the center must be included.

We use left multiplication by $\Gamma =S{L}_2(\mathbb{Z})$. For an integral matrix $A$ of determinant $n>0$, the Bezout identity gives a determinant-one row operation sending its first column to $(a,0{)}^t$, where $a$ is the positive gcd of that column. The resulting matrix is $\left(\begin{array}{cc}a& b\\ 0& d\end{array}\right)$ with $d=n/a>0$. Adding a multiple of the second row to the first makes $0\le b<d$.

These representatives are unique. Left multiplication by a unimodular matrix preserves the gcd of the first column, so two representatives in one orbit have the same $a$ and hence $d$. A matrix taking $(a,0{)}^t$ to itself has the form $\left(\begin{array}{cc}1& t\\ 0& 1\end{array}\right)$, so it changes $b$ by $td$; the prescribed range makes $b$ unique. Thus the determinant-n matrix representatives for Hecke operators are exactly ${\Pi }_n$. In the printed set, $0\le b<d$ already forces $d>0$, and $ad=n>0$ forces $a>0$.

For positive determinant extend the slash operator for modular forms byThe determinant factor makes this a right action: $(f{|}_{k}A){|}_{k}B=f{|}_k(AB)$. Right multiplication by $\delta \in \Gamma$ permutes the left cosets represented by ${\Pi }_n$, since it preserves the set of determinant-$n$ integral matrices. Hence $T_{n}f$ satisfies the modular transformation law. Its summands are holomorphic on the upper half-plane. For an upper-triangular representative,Substitute the Fourier expansion of a modular form. The sum over $b$ is zero unless the original index is divisible by $d$, in which case it equals $d$. Writing that index as $dr$ givesOnly nonnegative powers occur, so $T_{n}f$ is holomorphic at infinity, and all level-one cusps are equivalent to infinity. We have proved $T_{n}f\in M_k(\Gamma )$ and the Fourier coefficients of a composite-index Hecke operator formulaHere $\gcd (n,0)=n$, giving $a_0(T_{n}f)={\sum }_{a\mid n}{a}^{k-1}{a}_0(f)$. In particular cusp forms stay cusp forms. For nonzero level-one cusp forms the weight is an even integer at least twelve, so the powers $a^{k-1}$ are integers; the zero cusp space causes no exception. Thus every $T_n$ preserves integral Fourier coefficients, and closure under addition, multiplication and integer scalars provesThis is the integral Hecke algebra of level-one cusp forms.

We will also need commutativity. The coefficient formula directly givesFor the first identity, the divisors of $u$ and $v$ in the iterated coefficient sum combine uniquely into a divisor of $uv$. For the second, write a coefficient index as $p^t{r}_0$ with $p\nmid r_0$; the formula isApplying $T_p$ splits this into the two sums with shifts $t+1$ and $t-1$; their overlapping terms give exactly the stated recurrence. Since $T_1$ is the identity, induction expresses each $T_{p^r}$ as a polynomial in $T_p$, and coprime multiplicativity expresses every $T_n$ as a product of these polynomials. Distinct prime operators commute by the coprime identity. Hence all Hecke operators commute, and so do all elements of $\mathbb{T}$.

Let $\Lambda =S_k(\Gamma ,\mathbb{Z})$ and $m=\dim S_k(\Gamma )$. In the permitted basis $F_j={\Delta }^j{E}_4^{a_j}{E}_6^{b_j}$, the modular discriminant begins $q+O(q^2)$ and the normalized Eisenstein series begin $1+O(q)$, soThe matrix of $a_1,\dots ,a_m$ on this integral basis is unitriangular and has determinant one. Integer elimination therefore gives an integral basis $f_1,\dots ,f_m$ with $a_i(f_j)={\delta }_{ij}$ for $1\le i,j\le m$. Thus $a_1,\dots ,a_m$ are a $\mathbb{Z}$-basis of the dual module ${\mathrm{Hom}}_{\mathbb{Z}}(\Lambda ,\mathbb{Z})$.

The map $\alpha$ is well-defined by lattice preservation and is $\mathbb{Z}$-linear. Because $\alpha (T_j)=a_j$, it is surjective. For injectivity suppose $\alpha (T)=0$. For every $f\in \Lambda$ and every $n\ge 1$, commutativity givesThe constant term is also zero because $Tf$ is a cusp form. The identity theorem applied to its Fourier expansion of a modular form gives $Tf=0$. The integral basis spans the complex cusp space, so $T=0$ as an endomorphism. This proves the perfect integral Hecke pairing andIf $m=0$, both modules are zero and the asserted basis is empty.

The condition $\gcd (a,b,n)=1$ says that the ideal of $\mathbb{Z}$ generated by $a,b,n$ is all of $\mathbb{Z}$. The multi-integer Bezout identity therefore supplies integers $r,s,t$ such thatEquivalently, first apply Bézout's identity to $a,b$ and then to $\gcd (a,b),n$.

The class of $(1,1)$ isso its size is Euler's totient functionThe unit group acts freely on every pair in $Y$: if $\lambda a\equiv a$ and $\lambda b\equiv b$, multiplying the Bezout identity by $\lambda -1$ gives $\lambda \equiv 1(\mathrm{mod}n)$. Hence every equivalence class has size $\phi (n)$. Dividing the answer from part (a) by this size gives

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$.

Evaluation at $\alpha$ gives the ring isomorphismand reducing modulo $p$ givesFor each $i$,This quotient is a field because ${\overline{g}}_i$ is irreducible. Hence $P_i$ is a nonzero prime ideal; it is nonzero because it contains $p$. Its ideal norm is

The ideals are distinct. Indeed, if $P_i=P_j$ with $i\ne j$, then both ${\overline{g}}_i$ and ${\overline{g}}_j$ would vanish in the same quotient. Since distinct monic irreducibles are coprime, a Bezout identity between them would make $1$ vanish there, a contradiction.

Because the chosen lifts satisfyfor some $H\in \mathbb{Z}[X]$, evaluation at $\alpha$ givesEvery generator of the product ideal ${\prod }_i{P}_i^{e_i}$ either contains a factor $p$ or is the displayed product, soOn the other hand, multiplicativity of ideal norms and ${\sum }_i{e}_i\mathrm{deg}{\overline{g}}_i=\mathrm{deg}f=[L:\mathbb{Q}]$ giveTwo finite-index ideals with one contained in the other and equal index are equal. Thus the Dedekind factorization theorem is proved in this monogenic case:

Because $\mathrm{char}K=0$, the formal derivative $f^{\prime }$ is nonzero and has smaller degree than $f$. Since $f$ is irreducible, it cannot divide $f^{\prime }$, soBy the Bezout identity for polynomials, there are $a,b\in K[X]$ with $af+b{f}^{\prime }=1$. A repeated root of $f$ in $M$ would also be a root of $f^{\prime }$, contradicting this identity. Thus the result that an irreducible polynomial in characteristic zero is separable gives

Because $\gcd (m,n)=1$, choose $u,v\in \mathbb{Z}$ with $um+vn=1$ by Bézout's identity. Thensatisfies $c\equiv a(\mathrm{mod}m)$ and $c\equiv b(\mathrm{mod}n)$. Any two simultaneous solutions differ by a multiple of both coprime integers and hence by a multiple of $mn$. This proves the two-modulus Chinese remainder theorem.

The three congruences reduce toThe first two give $x\equiv 17(\mathrm{mod}35)$; imposing the last gives

The Euclidean algorithm repeatedly replaces a pair $(a,b)$ by $(b,a-qb)$ without changing its greatest common divisor. Reversing the divisions expresses $\gcd (a,b)$ as an integer linear combination $\alpha a+\beta b$, which is Bézout's identity.

Here $3=3(15)-2(21)$, and thereforeOne solution is $(x,y,z)=(36,-24,-1)$. It is not unique: for every $t\in \mathbb{Z}$, $(x,y,z)=(36+7t,-24-5t,-1)$ is another solution.

The non-Archimedean part of the Ostrowski theorem says that every nontrivial Non-Archimedean absolute value on $\mathbb{Q}$ is equivalent to the p-adic absolute value for a unique prime $p$.

Indeed, $|n|\le 1$ for every integer $n$. Nontriviality gives a prime $p$ with $|p|<1$, and there cannot be two such primes because the Bezout identity would make $1$ a sum of two terms of absolute value below one. If $a$ is coprime to $p$, another Bezout identity shows $|a|=1$. Consequentlyfor every $x\in {\mathbb{Q}}^{\times }$, which is a positive real power of $|x{|}_p$.

More generally, the Non-Archimedean absolute values on a number field $K$ are indexed, up to equivalence, by the nonzero prime ideals $\mathfrak{p}\subset {\mathcal{O}}_K$. The value attached to $\mathfrak{p}$ isTo prove completeness of the list, restrict an absolute value to $\mathbb{Q}$ and obtain a rational prime $p$. Its valuation ring contains ${\mathcal{O}}_K$ away from a unique prime above $p$; equivalently, its centeris a nonzero prime ideal. Since ${\mathcal{O}}_{K,\mathfrak{p}}$ is a discrete valuation ring, every $x\in K^{\times }$ is a unit times a power of a uniformizer, so the given value is equivalent to the displayed $\mathfrak{p}$-adic value. An absolute value trivial on $\mathbb{Q}$ is trivial on the algebraic extension $K$, so no further cases occur.