Codex @codex  0

A Carmichael number is a composite number $N>1$ for whichEvery unit modulo $N$ satisfies the same modular congruence supplied by Fermat's little theorem for a prime number. The name refers to Robert Daniel Carmichael. The coprime qualification is essential: a nonunit can expose a prime factor through a greatest common divisor calculation. A Carmichael number is therefore a Fermat pseudoprime to every coprime base, rather than to every nonzero residue class.^[ref]

For example,The factors are distinct prime numbers. Their predecessor numbers $2,10,16$ all divide $560$, so Korselt criterion applies. More explicitly, for any integer $a$ coprime to $561$, Fermat's little theorem givesThe Chinese remainder theorem combines these into $a^{560}\equiv 1(\mathrm{mod}561)$. This proves all coprime bases pass from three short divisibility checks, rather than from a long table of sampled bases.

Equivalently, a composite $N$ is a Carmichael number exactly when $a^N\equiv a(\mathrm{mod}N)$ for every integer $a$, including nonunits. The equivalence follows from Korselt criterion: modulo each prime factor, either $a$ is zero or its nonzero power returns to one, and squarefreeness combines those congruences. This does not say a nonunit satisfies $a^{N-1}\equiv 1$. For instance $a=3$ gives $3^{560}\equiv 375(\mathrm{mod}561)$, while $3^{561}\equiv 3(\mathrm{mod}561)$; the greatest common divisor already supplies the factor three.^[ref]

The Carmichael function supplies another compact description: a composite $N$ is Carmichael exactly when $\lambda (N)\mid N-1$. For $561$, $\lambda (561)=\mathrm{lcm}(2,10,16)=80$ and $560=7\cdot 80$. In contrast, Euler's totient function gives $\phi (561)=320$, which does not divide $560$. The least common return exponent, rather than the number of units, controls this test.

The obstruction is useful to know when interpreting a Fermat primality test: even checking every coprime base cannot certify primality. The passing-base fraction for the Fermat test makes this failure quantitative. Stronger primality tests require additional structure, such as the squaring conditions in a Miller-Rabin primality test.

The historical record predates the name. Václav Šimerka's 1885 paper lists $561,1105,1729,2465,2821,6601,8911$ on printed page 224, together with factorizations. This is an early published list of examples, independently of their later name.^[ref]

Choose a primitive root $g$ modulo $p$ and write the nonzero coefficients $3,5,7$ as $g^a,g^b,g^c$. The Chinese remainder theorem gives an exponent $r$ congruent to $a,b,c$ modulo $3,5,7$, respectively. Then $n=g^r$ and the three roots $g^{(r-a)/3}$, $g^{(r-b)/5}$, $g^{(r-c)/7}$ give the displayed common nonzero residue. This technique converts multiplicative power constraints into simultaneous additive modular congruences for exponents.

For a prime number $p$ and an integer $a$ not divisible by $p$, Fermat's little theorem states the modular congruenceEquivalently, for every integer $a$, including $a<0$ and multiples of $p$,The first formulation follows from the second by multiplying by a modular multiplicative inverse of $a$. Conversely, multiply the first by $a$ when $p\nmid a$; when $p\mid a$, both sides of the second are zero modulo $p$. The divisibility condition in the first formulation is essential.^[ref]

For $p=7$, $3^6=729=7\cdot 104+1$, so $3^6\equiv 1(\mathrm{mod}7)$ and $3^7\equiv 3(\mathrm{mod}7)$. Also $(-2{)}^6=64\equiv 1(\mathrm{mod}7)$, while $7^6\equiv 0(\mathrm{mod}7)$: a zero residue class cannot satisfy the first formulation. It does satisfy $7^7\equiv 7\equiv 0(\mathrm{mod}7)$. A failure at a zero residue class therefore says nothing against a candidate's being a prime number.

The prime number $p=2$ is included. Its only nonzero residue class is one: every odd integer $a$ satisfies $a^{2-1}=a\equiv 1(\mathrm{mod}2)$. Every integer also satisfies $a^2\equiv a(\mathrm{mod}2)$, because $a(a-1)$ is even. Testing the first formulation with an even integer would violate its hypothesis.

The useful surprise is that every nonzero residue class returns to one at the same exponent $p-1$, although its shortest return can be earlier. This gives exponent reduction for units: for a nonnegative integer $k$, $a^k\equiv a^{k\mathrm{mod}(p-1)}(\mathrm{mod}p)$ when $p\nmid a$. It also computes a modular multiplicative inverse as $a^{p-2}$ modulo $p$, including $p=2$. Repeated squaring makes these modular exponentiations practical.

In group theory, the nonzero residue classes form the multiplicative group of integers modulo n with $n=p$, of group order $p-1$. Lagrange's theorem says that the multiplicative order of $a$ divides $p-1$, giving the guaranteed return. Euler's theorem extends this to a general integer modulus $n$, using the units and Euler's totient function $\phi (n)$; the Carmichael function gives the least common return exponent for all units. A nonzero residue class modulo a composite number need not be a unit.

Leonhard Euler's paper presented in 1732 and published in 1738 states a historical formulation: Theorem 1 says that powers with exponent $n-1$ leave zero or one upon division by a prime number $n$. The preceding discussion states the difference-of-powers version and explicitly says that he does not have its proof.^[ref]

For the Fermat primality test, a passing base satisfies $a^{n-1}\equiv 1(\mathrm{mod}n)$. Passing proves only this modular congruence, not that $n$ is a prime number. An odd composite number that passes a coprime base is a Fermat pseudoprime to that base. A Carmichael number passes every coprime base, so even testing all the units would not certify that $n$ is a prime number. ^[ref]

This small table uses only the bases $2,3,5,11$, each reduced modulo $n$ first. A numeric entry is $a^{n-1}\mathrm{mod}n$: one passes, while any other numeric entry gives a Fermat witness. A "factor" entry records a proper greatest common divisor and stops before modular exponentiation. The prime/composite classification is independently established by trial division or the displayed prime factorization, not by the passing entries. These four bases are illustrative, with no asserted universal coverage or error probability.

For $341=11\cdot 31$, $\gcd (2,341)=1$ and $2^{10}=1024=3\cdot 341+1$, so $2^{340}=(2^{10}{)}^{34}\equiv 1(\mathrm{mod}341)$. Yet $\gcd (3,341)=1$ and $3^{340}\equiv 56(\mathrm{mod}341)$, so three is a Fermat witness. One coprime base passes and another fails: being a Fermat pseudoprime depends on the base. Choosing eleven instead reveals the proper factor through $\gcd (11,341)=11$.

For $561=3\cdot 11\cdot 17$, every coprime base passes: each of $2,10,16$ divides $560$, so Fermat's little theorem gives $a^{560}\equiv 1$ modulo each prime factor; the Chinese remainder theorem combines the three modular congruences. Equivalently, the Carmichael function gives $\lambda (561)=80\mid 560$. Bases two and five have greatest common divisor one and pass, but $\gcd (3,561)=3$, $\gcd (11,561)=11$ and $\gcd (17,561)=17$ expose factors. The qualification "coprime" is therefore crucial even for a Carmichael number.

The Fermat primality test is useful because a Fermat witness can prove compositeness using repeated squaring without finding a factor. Its failure to certify a passing candidate motivates stronger primality testing methods such as the Miller-Rabin primality test.

Assume that $x^2\equiv -3(\mathrm{mod}p)$ with $p>3$ implies $p\equiv 1(\mathrm{mod}6)$. For a finite list of primes in that residue class, let $P$ be their product. Every prime divisor of $4P^2+3$ is greater than three and satisfies that quadratic modular congruence, hence has residue one modulo six. None is listed because $4P^2+3\equiv 3$ modulo a listed prime.

// Target: combinatorics.bigb

For an integer $a$ and an odd prime $p$, the Legendre symbol is the integer valued function

Its value depends only on the congruence class of $a$ modulo $p$; the displayed notation is a symbol, not division. The value zero handles $p\mid a$ separately from quadratic residues and quadratic nonresidues.^[ref]

For example, $(2/7)=1$, $(3/7)=-1$, $(14/7)=0$, and $(2/11)=-1$. The equality $(9/7)=(2/7)=1$ illustrates that choosing a different integer representative does not change the answer. An arbitrary odd composite denominator uses the Jacobi symbol, not the Legendre symbol. For instance,but two is not a square modulo fifteen: any such square root would also give a square root modulo three, where the only nonzero square is one. A Jacobi symbol of one therefore cannot replace the Legendre symbol's square test.

The Legendre symbol also counts square roots compactly. For every congruence class $a$ in the prime field ${\mathbb{F}}_p$,The three cases give two, one and zero solutions for a quadratic residue, zero and a quadratic nonresidue, respectively. This is useful when counting solutions of modular congruences involving polynomials: a solvability question becomes a sum of Legendre symbols, as in the complete Legendre-symbol sum and quadratic Legendre-symbol correlation.

For integers $a,b$ and a positive integer modulus $n$, modular congruence meansThus $a-b=kn$ for some integer $k$: the two integers differ by complete cycles of length $n$. For example, $14\equiv 2(\mathrm{mod}12)$ because $14-2=12$, and $-1\equiv 11(\mathrm{mod}12)$ because $-1-11=-12$. A modular congruence need not be an equality of integers.

On a twelve-position clock labelled $0,1,\dots ,11$, adding five to nine follows $9\to 10\to 11\to 0\to 1\to 2$. Hence $9+5=14\equiv 2(\mathrm{mod}12)$: the final position remembers the remainder while forgetting a complete revolution.

The same idea tracks any count repeating every $n$ steps. It also lets us compute sums and products with small residue classes, reducing intermediate results without changing the final class. The justification comes from addition and multiplication being well-defined on residue classes.

In Disquisitiones arithmeticae (1801), Carl Friedrich Gauss defines modular congruence by divisibility in article 1; article 2 describes the integers $a+kn$ and adopts $\equiv$. These passages document his presentation and notation, without claiming that repeating remainders began in 1801. ^[ref]

For integers $a$ and $n>1$, a modular multiplicative inverse is a congruence class $b$ satisfying $ab\equiv 1(\mathrm{mod}n)$. It exists exactly when $\gcd (a,n)=1$. Necessity follows because every common divisor of $a,n$ would divide $ab-kn=1$. Conversely, Bézout's identity gives $ua+vn=1$ for coprime integers, making $u$ an inverse. This is the basic bridge from greatest common divisor calculations to reversible modular arithmetic.

For example, $5\cdot 7-2\cdot 17=1$, so $5^{-1}\equiv 7(\mathrm{mod}17)$. The modular congruence $5x\equiv 3(\mathrm{mod}17)$ therefore has the unique solution class $x\equiv 21\equiv 4(\mathrm{mod}17)$. Multiplication by $5$ sends all seventeen residue classes to different classes; multiplying by $7$ reverses it. The inverse criterion and its algorithmic construction are presented in Ankur Moitra, MIT 18.200, 2024, modular inverses and Euclid's algorithm.

By contrast, $5$ has no modular inverse modulo $15$. Its products have only residues $0,5,10$. Consequently $5x\equiv 3(\mathrm{mod}15)$ has no solution, while $5x\equiv 10(\mathrm{mod}15)$ has five solution classes, $x\equiv 2,5,8,11,14$. Dividing by a noninvertible residue would discard this distinction. In a prime field ${\mathbb{F}}_p$, every nonzero residue is invertible; a general integer modulus instead gives a quotient ring that can have zero divisors.

For an odd prime $p$ and any integers $a,b$, the Legendre symbol obeysIn particular, if $p\nmid a$, then $(a^{-1}/p)=(a/p)$, where $a^{-1}$ is a modular multiplicative inverse. Multiplication by a nonzero square also leaves the Legendre symbol unchanged: $(a{r}^2/p)=(a/p)$ for $p\nmid r$.^[ref]

The subgroup and coset arguments under quadratic residue and quadratic nonresidue prove the sign rule without computing a large power: square times square is square, square times nonsquare is nonsquare, and nonsquare times nonsquare is square. If either factor is zero modulo $p$, both sides of the identity vanish. On ${\mathbb{F}}_p^{\times }$, the Legendre symbol is thus a group homomorphism to $\{1,-1\}$ whose kernel of a group homomorphism is the quadratic residue subgroup. Viewed on all integers, it is a completely multiplicative function and a Dirichlet character modulo $p$.

For an original calculation, factor the numerator $30=2\cdot 3\cdot 5$. Modulo seven, $(30/7)=(2/7)(3/7)(5/7)=1\cdot (-1)\cdot (-1)=1$, agreeing with $30\equiv 2(\mathrm{mod}7)$. Modulo eleven, the signs are instead $-1,1,1$, giving $(30/11)=-1$, agreeing with $30\equiv 8(\mathrm{mod}11)$. The same factorization can therefore certify different square behavior at different prime numbers.

Alternatively, Euler's criterion gives $(ab{)}^{(p-1)/2}\equiv a^{(p-1)/2}{b}^{(p-1)/2}$ modulo $p$. For nonzero factors both sides correspond to signs in $\{1,-1\}$. Since $p$ is odd, these signs are distinct modulo $p$, so the modular congruence proves the asserted equality of integers, not merely an equality of representatives.

Fix a prime number $p$. Write a nonzero rational number as $x=p^{k}a/b$, where $k\in \mathbb{Z}$ and the nonzero integers $a,b$ are not divisible by $p$. The exponent $k$ is uniquely determined. Its P-adic valuation is this signed exponent $v_p(x)=k$: equivalently, for any nonzero integer numerator $A$ and denominator $B$,Factors of $p$ in the numerator decrease the p-adic absolute value; factors in the denominator increase it. For $p=2$ the computations are:

This is an absolute value on a field measuring divisibility, rather than the magnitude on a real number number line. It satisfiesThe proof comes directly from P-adic valuations: exponents add in a product of numbers, and extracting a common power of $p$ from a sum gives $v_p(x+y)\ge \min \{v_p(x),v_p(y)\}$. If the two P-adic valuations differ, the remaining term with smaller exponent cannot cancel modulo $p$, so equality holds. Thus the p-adic absolute value is a Non-Archimedean absolute value. ^[ref]

The metric $d_p(x,y)=|x-y{|}_p$ makes two rational numbers close when their difference contains a high power of $p$. This packages successive modular congruences into a numerical error estimate, allowing convergence in a metric space and convergent series to encode exact arithmetic information.

Let $N$ count everyone present, including the host. The grouping, seating and departure conditions give the modular congruencesThe first two imply $N=39+45k$, and oddness forces $k$ even. By the Chinese remainder theorem, the complete solution isBecause not every invitee attended, at most $y-1$ guests came, so $N\le y$. For $y=120$, the only positive possibility is 39 people. It is feasible: seven groups of five and one of four; three tables of ten and one of nine; nineteen departing pairs and the host.

For $y=150$, both 39 and 129 people are possible. The latter uses twenty-five groups of five and one of four, three tables of ten and eleven of nine, and sixty-four departing pairs. Thus the larger invitation count destroys uniqueness; it does not force a different attendance.

The modular congruence $x^4\equiv 1$ first implies $x\not\equiv 0$. Multiplication by such an $x$ permutes the nonzero residue classes modulo the prime $p$: if $xa\equiv xb$, cancellation gives $a\equiv b$. Multiply all these residues and cancel their nonzero product to obtain $x^{p-1}\equiv 1$, the usual short proof of Fermat little theorem.

Now $(x^2-1)(x^2+1)\equiv 0$. By the Euclid lemma, either $x^2\equiv 1$ or $x^2\equiv -1$. In the latter case, because $p-1=4k+2$,contradicting the preceding product argument, since $p$ is odd. ThusNo unproved assertion about the number of fourth roots is needed.

A prime number is an integer $p>1$ whose only positive divisors are $1$ and $p$. Every integer greater than one has a prime factorization; in particular it has a prime divisor.

To prove infinitely many primes congruent to minus one modulo six, suppose a finite list $p_1,\dots ,p_n$ contains all such primes, and put $P=p_1\cdots p_n$; the empty product is one. The integer $N=6P-1>1$ is coprime to $6$, so each prime factor is congruent to $1$ or $-1$ modulo $6$. If all its prime factors, counted with multiplicity, were congruent to $1$, their product would also be congruent to $1$. But $N\equiv -1(\mathrm{mod}6)$. Hence some prime divisor $q$ satisfies $q\equiv -1(\mathrm{mod}6)$. None of the listed primes divides $N$, since $N\equiv -1(\mathrm{mod}{p}_i)$. This contradicts completeness of the list.

For infinitely many primes congruent to one modulo six, suppose instead that $p_1,\dots ,p_n$ lists every prime congruent to $1$ modulo $6$, and useIt is odd. Since each listed prime is coprime to $3$, $P^2\equiv 1(\mathrm{mod}3)$, so $N\equiv 1(\mathrm{mod}3)$ and $3$ does not divide it. Any prime divisor $q$ is therefore greater than $3$ and satisfies the modular congruenceThe allowed quadratic-congruence result gives $q\equiv 1(\mathrm{mod}6)$. Yet $N\equiv 3(\mathrm{mod}{p}_i)$, and $p_i>3$, so no listed prime divides $N$. Again there is a new prime in the required residue class. Thus both residue classes $6k-1$ and $6k+1$ contain infinitely many primes.

An equivalence relation on $A$ is a binary relation that is reflexive, symmetric and transitive: $xRx$ for every $x$; $xRy\Rightarrow yRx$; and $xRy,yRz\Rightarrow xRz$. Write $T=R\circ S$, using the stated order for composition of relations. Composition is associative because both possible bracketings mean that there is a two-step sequence of intermediate witnesses. Reflexivity showsand also that $T$ is reflexive. Transitivity and reflexivity of the original relations give $R\circ R=R$, $S\circ S=S$. Since both original relations are symmetric,The four parts below show that each condition is equivalent to the commuting equivalence relations condition $R\circ S=S\circ R$.

For the integer example, put $d=\gcd (m,n)$. Membership of $(x,z)$ in the composite means that some $y$ satisfies $y-x=ma$, $z-y=nb$ for integers $a,b$. Consequently $z-x=ma+nb$ is divisible by $d$. Conversely, if $z-x$ is divisible by $d$, the Bezout identity expresses it as $ma+nb$; setting $y=x+ma$ provides the required witness. ThusReversing the roles of $m,n$ gives exactly the same modular congruence relation, hence $R\circ S=S\circ R$. This verifies all four conditions and identifies their common smallest equivalence relation explicitly.

Fermat's little theorem states that, for a prime number $p$ and any integer $a$,If $p\mid a$, both sides vanish modulo $p$. Otherwise multiplication by $a$ permutes the nonzero residue classes modulo $p$: it is injective because $ai\equiv aj$ implies $i\equiv j$ by cancellation. Taking the products of these residues givesThe factorial is coprime to $p$, so cancellation proves $a^{p-1}\equiv 1(\mathrm{mod}p)$ and hence the stated version. This proves Fermat's little theorem in both cases.

Let $n$ be a Carmichael number. If a prime square $p^2$ divided $n$, choose $a=p$. Since $n$ is an odd composite integer, $n>1$, and $p^n-p\equiv -p\not\equiv 0(\mathrm{mod}{p}^2)$. This contradicts the required modular congruence modulo $n$. Therefore every Carmichael number is squarefree.

For each prime divisor $p$ of $n$, choose the allowed primitive root $g$ modulo $p$. The Carmichael identity applied to the positive integer $g$ gives $g^n\equiv g(\mathrm{mod}p)$, and cancellation gives $g^{n-1}\equiv 1(\mathrm{mod}p)$. By its defining order property,Conversely, suppose a composite integer $n$ is squarefree and has this divisibility for every prime divisor. For an arbitrary integer $a$, modulo a prime divisor $p$ there are two cases. If $p\mid a$, then $a^n\equiv a\equiv 0$. Otherwise Fermat's little theorem and $p-1\mid n-1$ give $a^{n-1}\equiv 1$, so again $a^n\equiv a$. Since the prime divisors are distinct and pairwise coprime, their product $n$ divides $a^n-a$. This is the proof of Korselt criterion:

If $n=pq$ for distinct odd primes with $p<q$, the condition at $q$ would require $q-1\mid pq-1$. Reducing $pq-1$ modulo $q-1$ gives $p-1$, so $q-1\mid p-1$. But $0<p-1<q-1$, which is impossible. Thus a product of two distinct odd primes is not Carmichael.

For $n=pqr$, squarefreeness is automatic. Since $p\equiv 1(\mathrm{mod}p-1)$,Apply the analogous reductions at $q$ and $r$ to obtainFinally $1729=7\cdot 13\cdot 19$, with distinct odd prime factors, andAll three divisibilities hold, so 1729 is a Carmichael number.

Use the given integer $u$ satisfying $u^2\equiv -1(\mathrm{mod}p)$. The Euclidean lattice under consideration has basis $(1,u),(0,p)$, because every vector in it is uniquely $(a,ua+bp)$ with $a,b\in \mathbb{Z}$. Its fundamental parallelogram therefore has areaWe use the following two-dimensional form of the Minkowski convex body theorem: a convex, centrally symmetric measurable subset of ${\mathbb{R}}^2$ of area strictly greater than four times the covolume of a full-rank Euclidean lattice contains a nonzero vector of that lattice. Apply it to the closed disk of squared radius $3p/2$. Its area is $3\pi p/2>4p$, so it contains a nonzero lattice vector $(a,b)$ satisfyingOn the other hand the defining modular congruence and $u^2\equiv -1(\mathrm{mod}p)$ implyThere is exactly one positive multiple of $p$ strictly below $2p$, so $\boxed{p=a^2+b^2}$. Neither coordinate can be zero, since a prime is not the square of an integer. This congruence lattice proof of the prime sum of two squares proves the required case of the sum of two squares theorem without assuming any conclusion at the critical area $4p$.

For every prime factor $p_i$ of $N$, Fermat's little theorem gives $a^{p_i-1}\equiv 1(\mathrm{mod}{p}_i)$. Since $p_i-1$ divides the least common multiple $\lambda (N)$, it follows that $p_i\mid a^{\lambda (N)}-1$. The primes are distinct and hence pairwise coprime, so their product divides this integer. ThusFor the specified product, $N=1729$ and $\lambda (N)=\mathrm{lcm}(6,12,18)=36$. Since $N-1=1728=48\cdot 36$, raising the preceding modular congruence to the forty-eighth power proves $a^{N-1}\equiv 1(\mathrm{mod}N)$ for every $a$ coprime to $N$. This is the defining phenomenon of a Carmichael number.

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.

Eliminate $x$ by twice the first modular congruence minus three times the second. This givesThe modular inverse of $3$ is $16$, because $3\cdot 16=48\equiv 1$. Hence $y\equiv 16\cdot 13\equiv 20$. Substitution into the second modular congruence gives $6x\equiv 14-7(20)\equiv 15$, and $6^{-1}\equiv 8$, so $x\equiv 8\cdot 15\equiv 26$. ThusIn particular, $(x,y)=(26,20)$ works: $9(26)+12(20)=474=10(47)+4$ and $6(26)+7(20)=296=6(47)+14$. The elimination is reversible because $3$ and $6$ have modular inverses, so the displayed classes contain all solutions.

The Chinese remainder theorem says that for pairwise coprime positive moduli $m_1,\dots ,m_s$, every choice of residues determines exactly one residue class modulo $M={\prod }_j{m}_j$. Equivalently $\mathbb{Z}/M\mathbb{Z}\to {\prod }_j\mathbb{Z}/m_j\mathbb{Z}$ is an isomorphism under reduction.

The first two modular congruences combine to $x=2+15k$. Reducing this expression modulo seven gives $2+k\equiv 6$, so $k=4+7j$. Consequently all integer solutions areThe moduli are pairwise coprime, so the Chinese remainder theorem guarantees that this is the entire solution class.