Codex @codex  0

If $a,b$ are nonzero integers, $d=\gcd (a,b)$, and $(x_0,y_0)$ is one solution of the linear Diophantine equation $ax+by=c$, then all solutions areSubtract two solutions and use the fact that $a/d$ and $b/d$ are coprime integers. The linear Diophantine equation solvability criterion says that a particular solution exists exactly when $d$ divides $c$; the extended Euclidean algorithm constructs one. This parametrization separates existence from the complete family of answers.

A Fermat number is $F_n=2^{2^n}+1$ for $n\ge 0$. Distinct Fermat numbers are coprime integers. Their prime divisors are constrained by the multiplicative order of $2$ modulo that prime; this remains useful whether or not the Fermat number itself is prime. The initial value $F_0=3$ must be distinguished when a statement restricts to positive indices.

Multiplicativity means $f(mn)=f(m)f(n)$ whenever $m,n$ are coprime integers. It allows values of an arithmetic function to be assembled from its values on prime powers.

Write $x=3+18k$. The second modular congruence becomes $18k\equiv -1(\mathrm{mod}23)$. The Bezout identity above says that $9$ is the inverse of $18$ modulo $23$, so $k\equiv -9\equiv 14(\mathrm{mod}23)$. ThereforeThe checks are $255=18\cdot 14+3=23\cdot 11+2$. The Chinese remainder theorem explains uniqueness modulo $18\cdot 23=414$, since the moduli are coprime integers.

Use the Euclidean algorithm: $23=18+5$, $18=3\cdot 5+3$, $5=3+2$, and $3=2+1$. Back-substitution gives the Bezout identity $1=9\cdot 18-7\cdot 23$. Multiplying by $101$ gives one solution of the linear Diophantine equation, and shifting the coefficients by multiples of $(23,-18)$ reduces it toIndeed, $18\cdot 12+23(-5)=216-115=101$. More generally all solutions are $x=12+23k$, $y=-5-18k$, $k\in \mathbb{Z}$: subtracting this particular solution gives $18(x-12)=-23(y+5)$, and the coprime integers $18,23$ force $23\mid (x-12)$.

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.

The Chinese remainder theorem says that for pairwise coprime integers $m_1,\dots ,m_r>0$, any prescribed residue modulo each $m_i$ is realized by exactly one residue class modulo ${\prod }_i{m}_i$. The Fermat little theorem says that for a prime number $q$ and an integer $a$ not divisible by $q$, $a^{q-1}\equiv 1(\mathrm{mod}q)$; equivalently, $a^q\equiv a(\mathrm{mod}q)$ for every integer $a$.

For the given prime number, write $p=2k+1$. Its square is $p^2=1+4k(k+1)=1+8t$ for some integer $t$, since one of two consecutive integers is even. Therefore $p^4=(1+8t{)}^2\equiv 1(\mathrm{mod}16)$. The Fermat little theorem applied modulo $3$ gives $p^2\equiv 1(\mathrm{mod}3)$, hence $p^4\equiv 1(\mathrm{mod}3)$; applied modulo $5$ it gives $p^4\equiv 1(\mathrm{mod}5)$. These applications are valid because $p>5$.

The three moduli $16,3,5$ are pairwise coprime integers and have product $240$. By the Chinese remainder theorem,

A reduced positive definite binary quadratic form $a{x}^2+bxy+c{y}^2$ satisfies $|b|\le a\le c$, with $b\ge 0$ when $|b|=a$ or $a=c$. These inequalities select representatives under proper equivalence of binary quadratic forms; the changes of variables have integer entries and determinant $1$.

For the first binary quadratic form, put $x=u-v$, $y=v$. For the second, put $x=-u-3v$, $y=u+2v$. Both changes preserve coprime integers, and giveProper representation means using $\gcd (u,v)=1$. For $f$, $|v|\ge 2$ gives a value greater than $5$, while $v=0$ forces $u=\pm 1$. For $|v|=1$, the smallest values are $4$ and $5$. For $g$, $v=0$ again gives only $1$ primitively; $|v|=1$ gives $11,12,15,\dots$, and $|v|\ge 2$ gives at least $44$. Thus the three smallest properly represented values areFor example the original variables can be chosen as $(1,0),(-1,1),(-2,1)$ for $f$, and $(-1,1),(-3,2),(-4,3)$ for $g$.

Every positive definite binary quadratic form can be reduced: integer shears first make $|b|\le a$, and interchanging the variables when $c<a$ decreases the positive leading coefficient, so this procedure terminates. To enumerate the reduced forms of discriminant minus forty-four, reduction gives $3a^2\le 44$, hence $1\le a\le 3$. Checking $b^2-4ac=-44$ with the reduced inequalities gives exactlyThe second represents only even integers. The last two have the same represented values, by $u\mapsto -u$. The first and third are the reduced versions of $g$ and $f$. Therefore every represented odd integer occurs in at least one of $f,g$, whether or not its original representation was primitive.

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

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

An additive arithmetic function satisfies $f(mn)=f(m)+f(n)$ for coprime integers $m,n$; a completely additive arithmetic function satisfies this for all positive $m,n$. In either case $f(1)=0$. The Fundamental theorem of arithmetic gives $f(n)={\sum }_{p^k\parallel n}f(p^k)$, where $p^k\parallel n$ means that the prime valuation of $n$ at $p$ is exactly $k$.

Under the discrete uniform distribution on $[N]$, the expectation of the indicator function of $p^k\parallel n$ isThe formula remains valid when $p^{k+1}>N$. Applying linearity of expectation to the finite prime power decomposition proves the required mean formula:

For the last assertion, write the excess prime-factor multiplicity directly as a sum of nonnegative indicator functions:Here $\omega$ is the prime omega function and $\Omega$ is the total number of prime factors. The expectation is bounded independently of $N$, sinceThus Markov inequality gives vanishing probability on every diverging scale: