You have two unmarked jugs, one holding \(21\) litres and one holding \(15\) , and a tap. You may fill a jug from the tap, empty a jug onto the ground, or pour from one jug into the other until the first is empty or the second is full. Can you end with exactly \(3\) litres in one of the jugs? With exactly \(1\) litre?
The second question has a quick answer. Both capacities are multiples of \(3\) , and each permitted operation leaves in each jug an amount that is a multiple of \(3\) : this is an invariant in the sense of Chapter 3, so \(1\) litre is out of reach. The first question is harder, because it asks whether an invariant is the only obstacle. It is. The amounts that can be measured are exactly the multiples of \(3\) up to the jug sizes, and \(3\) is the greatest common divisor of \(21\) and \(15\) . The reason is a theorem saying that the greatest common divisor of two integers can always be written as a combination of them with integer coefficients, and the coefficients are a recipe for pouring. This chapter develops that theorem and its consequences: unique factorization into primes, and arithmetic with remainders, in which division is sometimes possible and sometimes not, and the same theorem says when.
4.1 Division with remainder
Theorem 4.1 (division theorem). Let \(a\) and \(d\) be integers with \(d>0\) . Then there exist unique integers \(q\) and \(r\) such that
The integer \(q\) is the quotient and \(r\) is the remainder; we write \(r=a\bmod d\) .
Proof. Existence. Let \(S\) be the set of natural numbers of the form \(a-xd\) with \(x\in\mathbb Z\) . It is nonempty: taking \(x=-\lvert a\rvert\) gives \(a+\lvert a\rvert d\ge a+\lvert a\rvert\ge 0\) . By the well-ordering principle \(S\) has a least element \(r\) , and \(r=a-qd\) for some integer \(q\) . By construction \(r\ge 0\) . If \(r\ge d\) , then \(r-d=a-(q+1)d\) would be a natural number of the required form smaller than \(r\) , contradicting the choice of \(r\) . So \(0\le r<d\) .
Uniqueness. Suppose \(a=qd+r=q'd+r'\) with \(0\le r<d\) and \(0\le r'<d\) . Then \((q-q')d=r'-r\) . The right side lies strictly between \(-d\) and \(d\) , and the only multiple of \(d\) in that range is \(0\) . So \(r'=r\) , and then \((q-q')d=0\) with \(d\ne 0\) gives \(q=q'\) .
The theorem pays a debt from Chapter 1. With \(d=2\) it says that every integer has exactly one of the forms \(2q\) and \(2q+1\) : every integer is even or odd, and none is both. With \(d=3\) it gives the three forms \(3q\) , \(3q+1\) , \(3q+2\) that Exercise 1.14 assumed, and in general it sorts the integers into \(d\) kinds according to their remainders.
Example 4.1: Remainders of negative numbers
Divide \(100\) by \(7\) : since \(14\cdot 7=98\) , we have \(100=14\cdot 7+2\) , so \(q=14\) and \(r=2\) .
Divide \(-17\) by \(5\) . It is tempting to write \(-17=(-3)\cdot 5+(-2)\) , but \(-2\) is not an allowed remainder. The theorem demands \(0\le r<5\) , and the correct statement is \(-17=(-4)\cdot 5+3\) , so \(q=-4\) and \(r=3\) . The quotient is the greatest integer not exceeding \(-17/5=-3.4\) , which is \(-4\) , not \(-3\) .
Divide \(-100\) by \(7\) : \(-100=(-15)\cdot 7+5\) , so \(-100\bmod 7=5\) , while \(100\bmod 7=2\) . The remainders of \(a\) and \(-a\) are not negatives of each other; when neither is zero they add up to \(d\) .
Many programming languages return a negative result for the remainder of a negative number. The mathematical convention, with the remainder always in the range from \(0\) to \(d-1\) , is the one that makes “having the same remainder” an equivalence relation with exactly \(d\) classes.
4.2 The greatest common divisor and Euclid’s algorithm
Definition 4.2 (greatest common divisor). Let \(a\) and \(b\) be integers, not both zero. The greatest common divisor \(\gcd(a,b)\) is the largest positive integer that divides both \(a\) and \(b\) . The integers \(a\) and \(b\) are coprime, or relatively prime, if \(\gcd(a,b)=1\) .
The definition makes sense: \(1\) is a common divisor, and no common divisor exceeds the larger of \(\lvert a\rvert\) and \(\lvert b\rvert\) , so there is a largest one. For \(a\ne 0\) we have \(\gcd(a,0)=\lvert a\rvert\) , because every integer divides \(0\) .
One could find \(\gcd(a,b)\) by listing all divisors of both numbers, but for large numbers that is hopeless. A far better method has been known for more than two thousand years. It rests on one observation.
Lemma 4.3 (the remainder step). Let \(a\) , \(b\) , \(q\) , \(r\) be integers with \(a=qb+r\) . Then the common divisors of \(a\) and \(b\) are exactly the common divisors of \(b\) and \(r\) . In particular, if \(b\ne 0\) then \(\gcd(a,b)=\gcd(b,r)\) .
Proof. If \(c\) divides \(b\) and \(r\) , then \(c\) divides the combination \(qb+r=a\) , by Example 1.6. If \(c\) divides \(a\) and \(b\) , then \(c\) divides the combination \(a-qb=r\) . So the two pairs have the same set of common divisors, and hence the same greatest one.
Theorem 4.4 (Euclid’s algorithm). Let \(a\) and \(b\) be integers with \(a\ge b>0\) . Put \(r_0=a\) and \(r_1=b\) , and for \(i\ge 1\) , as long as \(r_i\ne 0\) , let \(r_{i+1}=r_{i-1}\bmod r_i\) . Then some remainder \(r_{m+1}\) equals \(0\) , and the last nonzero remainder \(r_m\) equals \(\gcd(a,b)\) .
Proof. Termination. By the division theorem, \(0\le r_{i+1}<r_i\) whenever \(r_{i+1}\) is defined. So \(r_1>r_2>r_3>\dots\) is a strictly decreasing sequence of natural numbers: the current remainder is a monovariant, and by Theorem 3.13 the process stops, which happens only when some \(r_{m+1}=0\) .
Correctness. Each step has the form \(r_{i-1}=q_ir_i+r_{i+1}\) , so by Lemma 4.3, \(\gcd(r_{i-1},r_i)=\gcd(r_i,r_{i+1})\) . Thus the value \(\gcd(r_{i-1},r_i)\) is the same at every step: it is an invariant. At the start it is \(\gcd(a,b)\) and at the end it is \(\gcd(r_m,0)=r_m\) .
This proof is the model for the analysis of any algorithm: a decreasing quantity shows that it stops, and a preserved quantity shows that what it returns is right. The question that closed Chapter 3 is answered. The set of common divisors stays the same, and the remainder decreases.
Example 4.2: The algorithm on two three-digit numbers
To find \(\gcd(662,414)\) , divide repeatedly, each time dividing the previous divisor by the previous remainder:
The last nonzero remainder is \(2\) , so \(\gcd(662,414)=2\) . Five divisions were needed. The remainders \(248,166,82,2,0\) decrease strictly, as the proof requires, and at every line the two numbers being divided have the same common divisors as \(662\) and \(414\) , namely \(1\) and \(2\) and their negatives.
Compare the effort with factoring. To find the answer from prime factorizations one would need \(662=2\cdot 331\) and \(414=2\cdot 3^{2}\cdot 23\) , and confirming that \(331\) is prime takes more work than the whole of Euclid’s algorithm.
4.3 Bézout’s identity
An integer combination of \(a\) and \(b\) is a number of the form \(ax+by\) with \(x,y\in\mathbb Z\) . Example 1.6 showed that every common divisor of \(a\) and \(b\) divides every integer combination of them. The central theorem of this chapter is the converse fact about the greatest common divisor.
Theorem 4.5 (Bézout’s identity). Let \(a\) and \(b\) be integers, not both zero, and let \(d=\gcd(a,b)\) .
(a) There exist integers \(x\) and \(y\) with \(ax+by=d\) .
(b) The set of all integer combinations of \(a\) and \(b\) is exactly the set of multiples of \(d\) . In particular, \(d\) is the least positive integer combination of \(a\) and \(b\) .
Proof. Let \(S\) be the set of positive integer combinations of \(a\) and \(b\) . It is nonempty, since \(a\cdot a+b\cdot b>0\) . By the well-ordering principle it has a least element \(e\) ; write \(e=ax_0+by_0\) .
We claim that \(e\) divides \(a\) . By the division theorem, \(a=qe+r\) with \(0\le r<e\) . Then
so \(r\) is an integer combination of \(a\) and \(b\) . If \(r\) were positive it would be an element of \(S\) smaller than \(e\) , which is impossible. So \(r=0\) and \(e\mid a\) . The same argument with the roles of \(a\) and \(b\) exchanged shows \(e\mid b\) .
So \(e\) is a common divisor of \(a\) and \(b\) , and therefore \(e\le d\) . On the other hand, \(d\) divides \(a\) and \(b\) , hence divides the combination \(e\) ; since both are positive, \(d\le e\) . Therefore \(e=d\) , which proves (a).
For (b): every integer combination is a multiple of \(d\) , because \(d\) divides both \(a\) and \(b\) . Conversely every multiple \(kd\) of \(d\) is the combination \(a(kx_0)+b(ky_0)\) .
Corollary 4.6 (common divisors divide the greatest one). Every common divisor of \(a\) and \(b\) divides \(\gcd(a,b)\) .
Proof. A common divisor divides every integer combination of \(a\) and \(b\) , and \(\gcd(a,b)\) is one.
The corollary says that \(\gcd(a,b)\) is greatest in a stronger sense than size. In the poset of positive integers under divisibility from Section 2.6, it lies above every common divisor.
The proof of Theorem 4.5 shows that \(x\) and \(y\) exist without saying how to find them. Euclid’s algorithm finds them. Each remainder is the previous two remainders combined, so each remainder can be written as a combination of \(a\) and \(b\) , and the bookkeeping can be carried along with the divisions. This is the extended Euclidean algorithm.
Example 4.3: Bézout coefficients, and the jugs
We express \(\gcd(662,414)=2\) as \(662x+414y\) . Keep, for each remainder \(r\) of Example 4.2, coefficients \(s\) and \(t\) with \(r=662s+414t\) . The first two rows are obvious, and each later row is obtained from the two before it exactly as its remainder was: subtract \(q\) times the previous row from the one before that.
| Step | \(q\) | \(r\) | \(s\) | \(t\) |
|---|---|---|---|---|
| start | \(662\) | \(1\) | \(0\) | |
| start | \(414\) | \(0\) | \(1\) | |
| 1 | \(1\) | \(248\) | \(1\) | \(-1\) |
| 2 | \(1\) | \(166\) | \(-1\) | \(2\) |
| 3 | \(1\) | \(82\) | \(2\) | \(-3\) |
| 4 | \(2\) | \(2\) | \(-5\) | \(8\) |
For instance the row for \(82\) is the row for \(248\) minus \(1\) times the row for \(166\) : \(s=1-(-1)=2\) and \(t=-1-2=-3\) , and indeed \(662\cdot 2+414\cdot(-3)=1324-1242=82\) . The last row gives
The coefficients are not unique: adding \(414/2=207\) to \(x\) and subtracting \(662/2=331\) from \(y\) gives another pair, \(x=202\) and \(y=-323\) .
Now the jugs. The same procedure for \(21\) and \(15\) gives \(21=1\cdot 15+6\) , \(15=2\cdot 6+3\) , \(6=2\cdot 3\) , so \(\gcd(21,15)=3\) and
Read as a recipe: fill the \(15\) -litre jug three times and discard two full loads of the \(21\) -litre jug. In detail: fill the small jug and pour it into the large one, which then holds \(15\) . Fill the small jug again and pour until the large jug is full; that takes \(6\) litres and leaves \(9\) in the small jug. Empty the large jug and pour the \(9\) litres in. Fill the small jug a third time and pour until the large jug is full; that takes \(12\) litres and leaves exactly \(3\) in the small jug. In total \(45\) litres were drawn, \(21\) were thrown away, \(21\) are in the large jug, and \(3\) remain. By Theorem 4.5(b) no amount other than a multiple of \(3\) can ever appear, which is the invariant found at the start.
Bézout’s identity is the tool for proving divisibility statements that involve coprime numbers. The pattern is always the same: write \(1\) as a combination, multiply through, and read off the divisibility.
Theorem 4.7 (consequences of coprimality). Let \(a\) , \(b\) , \(c\) , \(m\) , \(n\) be integers with \(m,n\ge 1\) .
(a) If \(\gcd(a,n)=1\) and \(n\mid ab\) , then \(n\mid b\) .
(b) If \(\gcd(m,n)=1\) , \(m\mid c\) , and \(n\mid c\) , then \(mn\mid c\) .
(c) (Euclid’s lemma.) If \(p\) is prime and \(p\mid ab\) , then \(p\mid a\) or \(p\mid b\) . More generally, if \(p\mid a_1a_2\cdots a_k\) , then \(p\mid a_i\) for some \(i\) .
Proof. (a) By Theorem 4.5 there are integers \(x\) , \(y\) with \(ax+ny=1\) . Multiplying by \(b\) gives \(b=abx+nby\) . Now \(n\) divides \(ab\) by hypothesis, so \(n\) divides \(abx\) , and \(n\) divides \(nby\) . Hence \(n\) divides their sum \(b\) .
(b) Write \(c=mk\) . Then \(n\mid mk\) and \(\gcd(m,n)=1\) , so \(n\mid k\) by (a). Write \(k=n\ell\) ; then \(c=mn\ell\) .
(c) Suppose \(p\mid ab\) and \(p\nmid a\) . The only positive divisors of \(p\) are \(1\) and \(p\) , and \(p\) does not divide \(a\) , so \(\gcd(a,p)=1\) . By (a), \(p\mid b\) . The general statement follows by induction on \(k\) : the case \(k=1\) is trivial, and if \(p\mid(a_1\cdots a_k)a_{k+1}\) then \(p\mid a_1\cdots a_k\) or \(p\mid a_{k+1}\) by the case of two factors, and in the first alternative the induction hypothesis applies.
Every part needs its coprimality or primality hypothesis. Exercise 1.16 found that \(6\mid 4\cdot 9\) although \(6\) divides neither factor; \(6\) is not prime, and it is not coprime to \(4\) .
4.4 Primes and unique factorization
Theorem 3.7 showed that every integer \(n\ge 2\) is a product of primes. Euclid’s lemma is what is needed to show that there is only one such product.
Theorem 4.8 (fundamental theorem of arithmetic). Every integer \(n\ge 2\) can be written as a product of primes, and this product is unique apart from the order of the factors.
Proof. Existence is Theorem 3.7. For uniqueness, suppose that some integer has two factorizations that differ by more than the order of the factors, and by the well-ordering principle let \(n\) be the least such integer:
with all \(p_i\) and \(q_j\) prime. The prime \(p_1\) divides \(q_1q_2\cdots q_s\) , so by Theorem 4.7(c) it divides some \(q_j\) . Since \(q_j\) is prime and \(p_1\ge 2\) , this forces \(p_1=q_j\) . If \(n=p_1\) , then \(r=s=1\) and the two factorizations coincide, which is not the case. Otherwise cancel \(p_1\) from both sides: the integer \(n/p_1\) satisfies \(2\le n/p_1<n\) and has the two factorizations obtained by deleting \(p_1\) from the first and \(q_j\) from the second. These still differ by more than order, since restoring the deleted prime to both would otherwise make the original two agree. That contradicts the minimality of \(n\) .
Collecting equal primes, every \(n\ge 2\) has a unique expression \(n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}\) with \(p_1<p_2<\dots<p_k\) prime and all \(e_i\ge 1\) . Uniqueness is what makes exponents meaningful: one may speak of the exponent of a prime \(p\) in \(n\) , taken to be \(0\) when \(p\nmid n\) . Divisibility then becomes a comparison of exponents: \(a\mid b\) exactly when, for every prime, its exponent in \(a\) is at most its exponent in \(b\) .
Theorem 4.9 (Euclid). There are infinitely many primes.
Proof. We show that no finite list of primes contains all of them. Let \(p_1,p_2,\dots,p_k\) be any finite list of primes, and let \(N=p_1p_2\cdots p_k+1\) . Then \(N\ge 2\) , so \(N\) has a prime divisor \(p\) by Theorem 3.7. If \(p\) were equal to some \(p_i\) , then \(p\) would divide both \(N\) and \(p_1\cdots p_k\) , hence their difference \(1\) , which is impossible. So \(p\) is a prime not on the list.
The proof does not say that \(N\) itself is prime. For the list \(2,3,5,7,11,13\) we get \(N=30031=59\cdot 509\) , which is composite; its prime divisors \(59\) and \(509\) are new primes, as the proof guarantees.
Example 4.4: Reading divisors off a factorization
Take \(360=2^{3}\cdot 3^{2}\cdot 5\) and \(84=2^{2}\cdot 3\cdot 7\) .
A common divisor can contain each prime only as often as both numbers do, so the greatest common divisor takes the smaller exponent of each prime: \(\gcd(360,84)=2^{2}\cdot 3=12\) . The least common multiple takes the larger exponent of each prime: \(\operatorname{lcm}(360,84)=2^{3}\cdot 3^{2}\cdot 5\cdot 7=2520\) . Since the smaller and the larger of two exponents add up to their sum,
and the same reasoning gives \(\gcd(a,b)\operatorname{lcm}(a,b)=ab\) for all positive integers \(a\) and \(b\) .
The positive divisors of \(360\) are the numbers \(2^{i}3^{j}5^{k}\) with \(0\le i\le 3\) , \(0\le j\le 2\) , \(0\le k\le 1\) , and different exponent triples give different divisors by uniqueness. There are \(4\cdot 3\cdot 2=24\) of them. This is the structure that Figure 2.2 displayed for the divisors of \(60\) .
Euclid’s algorithm confirms the first result without any factoring: \(360=4\cdot 84+24\) , \(84=3\cdot 24+12\) , \(24=2\cdot 12\) , so the greatest common divisor is \(12\) .
4.5 Congruence
In many problems only the remainder of an integer matters: the day of the week, the last digit, whether a number is even. Gauss introduced a notation that lets remainders be manipulated like numbers.
Definition 4.10 (congruence). Let \(n\) be a positive integer. Integers \(a\) and \(b\) are congruent modulo \(n\) , written \(a\equiv b\pmod n\) , if \(n\mid(a-b)\) . The number \(n\) is the modulus.
Theorem 4.11 (congruence and remainders). Let \(n\) be a positive integer.
(a) Congruence modulo \(n\) is an equivalence relation on \(\mathbb Z\) .
(b) \(a\equiv b\pmod n\) if and only if \(a\) and \(b\) leave the same remainder on division by \(n\) .
(c) There are exactly \(n\) equivalence classes, \([0],[1],\dots,[n-1]\) , and the class \([r]\) consists of the integers whose remainder is \(r\) .
Proof. (a) Reflexive: \(a-a=0=n\cdot 0\) . Symmetric: if \(a-b=nk\) then \(b-a=n(-k)\) . Transitive: if \(a-b=nk\) and \(b-c=n\ell\) then \(a-c=n(k+\ell)\) .
(b) Write \(a=qn+r\) and \(b=q'n+r'\) with \(0\le r,r'<n\) . Then \(a-b=(q-q')n+(r-r')\) , so \(n\mid(a-b)\) if and only if \(n\mid(r-r')\) . Since \(r-r'\) lies strictly between \(-n\) and \(n\) , this happens if and only if \(r=r'\) .
(c) By (b), every integer is congruent to its remainder, which is one of \(0,1,\dots,n-1\) , and two different numbers in that range are not congruent. So these \(n\) numbers represent all the classes, each once.
The classes are called residue classes, and the set of them is written \(\mathbb Z_n\) . By Theorem 2.17 they partition \(\mathbb Z\) ; for \(n=2\) the partition is into even and odd integers.
What makes congruence a tool and not just a notation is that it is compatible with arithmetic.
Theorem 4.12 (arithmetic of congruences). If \(a\equiv a'\pmod n\) and \(b\equiv b'\pmod n\) , then
and \(a^{k}\equiv a'^{\,k}\pmod n\) for every \(k\in\mathbb N\) .
Proof. By hypothesis \(n\) divides \(a-a'\) and \(b-b'\) . Then \(n\) divides \((a-a')+(b-b')=(a+b)-(a'+b')\) and \((a-a')-(b-b')=(a-b)-(a'-b')\) . For products, write
an integer combination of two multiples of \(n\) . The statement about powers follows from the product rule by induction on \(k\) .
In the language of Chapter 2, the theorem says that addition and multiplication of residue classes are well defined: the class of \(a+b\)
and the class of \(ab\)
depend only on the classes of \(a\)
and \(b\)
. So in a computation modulo \(n\)
any number may be replaced at any stage by any number congruent to it, and the sensible strategy is to reduce early and often, keeping the numbers small. The set \(\mathbb Z_n\)
with these two operations is the first example of the algebraic structure called a ring, which is studied in Abstract Algebra (math.abstract-algebra.rings-ideals-and-basic-examples).
One operation is missing from Theorem 4.12, and its absence is deliberate. Exponents may not be reduced modulo \(n\) : \(2^{5}=32\equiv 2\pmod 5\) , while \(2^{0}=1\) , although \(5\equiv 0\pmod 5\) . Division is not mentioned either; it is the subject of the next section.
Example 4.5: Three computations with small numbers
A last digit. The last digit of an integer is its remainder modulo \(10\) . To find the last digit of \(7^{2026}\) , note that \(7^{2}=49\equiv -1\pmod{10}\) , so \(7^{4}\equiv 1\pmod{10}\) . Since \(2026=4\cdot 506+2\) ,
The last digit is \(9\) , found without computing a number of more than seventeen hundred digits.
Tests for divisibility. Since \(10\equiv 1\pmod 9\) , every power of \(10\) is congruent to \(1\) , and so an integer is congruent modulo \(9\) to the sum of its decimal digits. For \(738945\) the digit sum is \(7+3+8+9+4+5=36\) , a multiple of \(9\) , so \(738945\) is divisible by \(9\) . Since \(10\equiv -1\pmod{11}\) , the powers of \(10\) are alternately congruent to \(1\) and \(-1\) , and an integer is congruent modulo \(11\) to the alternating sum of its digits taken from the right. For \(918082\) this is \(2-8+0-8+1-9=-22\) , a multiple of \(11\) ; indeed \(918082=11\cdot 83462\) .
Repeated squaring. To find the last two digits of \(3^{45}\) , work modulo \(100\) and square repeatedly: \(3^{2}=9\) , \(3^{4}=81\) , \(3^{8}=6561\equiv 61\) , \(3^{16}\equiv 61^{2}=3721\equiv 21\) , \(3^{32}\equiv 21^{2}=441\equiv 41\) . Since \(45=32+8+4+1\) ,
Now \(41\cdot 61=2501\equiv 1\) , so the product is congruent to \(81\cdot 3=243\equiv 43\) . The last two digits of \(3^{45}\) are \(43\) . Five squarings and three multiplications replaced forty-four multiplications; for exponents with hundreds of digits the same method is the only practical one.
4.6 Inverses, cancellation, and linear congruences
Among ordinary numbers, dividing by \(a\) means multiplying by a number \(x\) with \(ax=1\) . The same definition works modulo \(n\) , with one difference: such an \(x\) may not exist.
Definition 4.13 (inverse modulo n). An inverse of \(a\) modulo \(n\) is an integer \(x\) with \(ax\equiv 1\pmod n\) . If one exists, \(a\) is invertible modulo \(n\) , or a unit modulo \(n\) .
Theorem 4.14 (which numbers are invertible). An integer \(a\) has an inverse modulo \(n\) if and only if \(\gcd(a,n)=1\) . When an inverse exists, it is unique modulo \(n\) .
Proof. The congruence \(ax\equiv 1\pmod n\) holds for some \(x\) if and only if \(ax-1=ny'\) for some integers \(x\) and \(y'\) , that is, if and only if \(1\) is an integer combination \(ax+ny\) of \(a\) and \(n\) . By Theorem 4.5(b) the integer combinations of \(a\) and \(n\) are the multiples of \(\gcd(a,n)\) , and \(1\) is a multiple of \(\gcd(a,n)\) exactly when \(\gcd(a,n)=1\) .
For uniqueness, suppose \(ax\equiv 1\) and \(ax'\equiv 1\pmod n\) . Then \(x\equiv x\cdot(ax')=(xa)\cdot x'\equiv x'\pmod n\) .
The proof is constructive: the coefficient \(x\) in a Bézout identity \(ax+ny=1\) is the inverse, and the extended Euclidean algorithm computes it.
Theorem 4.15 (cancellation). Suppose \(ac\equiv bc\pmod n\) and let \(d=\gcd(c,n)\) . Then \(a\equiv b\pmod{n/d}\) . In particular, if \(\gcd(c,n)=1\) then \(a\equiv b\pmod n\) .
Proof. By hypothesis \(n\mid c(a-b)\) . Write \(n=dn'\) and \(c=dc'\) . Then \(dn'\mid dc'(a-b)\) , so \(n'\mid c'(a-b)\) . A Bézout identity \(cx+ny=d\) divided by \(d\) gives \(c'x+n'y=1\) , so \(\gcd(c',n')=1\) by Theorem 4.5(b). By Theorem 4.7(a), \(n'\mid(a-b)\) .
Theorem 4.16 (linear congruences). Let \(a\) , \(b\) be integers, \(n\) a positive integer, and \(d=\gcd(a,n)\) . The congruence \(ax\equiv b\pmod n\) has a solution if and only if \(d\mid b\) . If \(d\mid b\) , the solutions are the integers \(x\equiv x_0\pmod{n/d}\) for a single \(x_0\) , and they make up exactly \(d\) residue classes modulo \(n\) .
Proof. The congruence has a solution if and only if \(ax+ny=b\) for some integers \(x\) , \(y\) , that is, if and only if \(b\) is an integer combination of \(a\) and \(n\) . By Theorem 4.5(b) this holds exactly when \(d\mid b\) .
Suppose \(d\mid b\) , and write \(a=da'\) , \(n=dn'\) , \(b=db'\) . Then \(n\mid(ax-b)\) means \(dn'\mid d(a'x-b')\) , which is equivalent to \(n'\mid(a'x-b')\) . So the original congruence has the same solutions as \(a'x\equiv b'\pmod{n'}\) . As in the previous proof \(\gcd(a',n')=1\) , so \(a'\) has an inverse \(c\) modulo \(n'\) , and multiplying by \(c\) shows that the solutions are exactly the integers \(x\equiv cb'\pmod{n'}\) . Put \(x_0=cb'\) . The integers congruent to \(x_0\) modulo \(n'\) are \(x_0+kn'\) with \(k\in\mathbb Z\) , and two of them are congruent modulo \(n=dn'\) exactly when their values of \(k\) are congruent modulo \(d\) . So they form the \(d\) classes of \(x_0,\ x_0+n',\ \dots,\ x_0+(d-1)n'\) modulo \(n\) .
Example 4.6: An inverse by the extended algorithm
Find the inverse of \(17\) modulo \(43\) , and solve \(17x\equiv 4\pmod{43}\) .
Euclid’s algorithm: \(43=2\cdot 17+9\) , \(17=1\cdot 9+8\) , \(9=1\cdot 8+1\) . So \(\gcd(17,43)=1\) and an inverse exists. Substituting backwards,
Reading this modulo \(43\) gives \(17\cdot(-5)\equiv 1\) , so the inverse is \(-5\equiv 38\) . Check: \(17\cdot 38=646=15\cdot 43+1\) .
To solve \(17x\equiv 4\pmod{43}\) , multiply both sides by \(38\) : \(x\equiv 38\cdot 4=152\equiv 152-129=23\pmod{43}\) . Check: \(17\cdot 23=391=9\cdot 43+4\) . By Theorem 4.16 with \(d=1\) this is the only solution modulo \(43\) .
Example 4.7: A congruence with four solutions and one with none
Solve \(8x\equiv 4\pmod{12}\) . Here \(d=\gcd(8,12)=4\) , and \(4\mid 4\) , so there are solutions, forming \(4\) classes modulo \(12\) . Dividing everything by \(4\) gives the equivalent congruence \(2x\equiv 1\pmod 3\) . The inverse of \(2\) modulo \(3\) is \(2\) , since \(2\cdot 2=4\equiv 1\) , so \(x\equiv 2\pmod 3\) . Modulo \(12\) the solutions are \(x\equiv 2,5,8,11\) . Check: \(8\cdot 2=16\) , \(8\cdot 5=40\) , \(8\cdot 8=64\) , and \(8\cdot 11=88\) all leave remainder \(4\) on division by \(12\) .
Now consider \(8x\equiv 6\pmod{12}\) . Since \(4\nmid 6\) , there is no solution: every multiple of \(8\) is congruent modulo \(12\) to a multiple of \(4\) .
Figure 4.1 displays Theorems 4.14 and 4.16 at once. Modulo the prime \(7\) every nonzero residue is coprime to the modulus, every row is a rearrangement of \(0,1,\dots,6\) , and every congruence \(ax\equiv b\) with \(a\not\equiv 0\) has exactly one solution. Modulo \(12\) only the rows of \(1\) , \(5\) , \(7\) , and \(11\) behave this way. In row \(8\) the value \(4\) occurs in columns \(2,5,8,11\) and the value \(6\) does not occur.
Common mistake. Cancelling a common factor from both sides of a congruence without looking at the modulus. From \(8\cdot 2\equiv 8\cdot 5\pmod{12}\) , which is true because \(16\) and \(40\) both leave remainder \(4\) , one cannot conclude \(2\equiv 5\pmod{12}\) . Theorem 4.15 gives the correct conclusion: since \(\gcd(8,12)=4\) , the modulus must be divided by \(4\) , and \(2\equiv 5\pmod 3\) is true. Cancellation with the modulus unchanged is legitimate only when the cancelled factor is coprime to the modulus.
4.7 Fermat’s little theorem and the Chinese remainder theorem
Modulo a prime, every nonzero residue is invertible, and the powers of a residue have a striking regularity.
Theorem 4.17 (Fermat’s little theorem). Let \(p\) be a prime and \(a\) an integer not divisible by \(p\) . Then \(a^{p-1}\equiv 1\pmod p\) . Consequently \(a^{p}\equiv a\pmod p\) for every integer \(a\) .
Proof. Let \(R=\{1,2,\dots,p-1\}\) . For \(x\in R\) let \(f(x)\) be the remainder of \(ax\) on division by \(p\) . Since \(p\) divides neither \(a\) nor \(x\) , it does not divide \(ax\) , by Euclid’s lemma; so \(f(x)\ne 0\) and \(f\) is a function from \(R\) to \(R\) . It is injective: if \(f(x)=f(x')\) then \(ax\equiv ax'\pmod p\) , and since \(\gcd(a,p)=1\) , Theorem 4.15 gives \(x\equiv x'\pmod p\) , hence \(x=x'\) because both lie in \(R\) . So \(f(1),f(2),\dots,f(p-1)\) are \(p-1\) different elements of the \((p-1)\) -element set \(R\) , and therefore are all the elements of \(R\) in some order.
Multiply them together. On one hand the product is \(1\cdot 2\cdots(p-1)=(p-1)!\) . On the other hand each \(f(x)\equiv ax\) , so the product is congruent to \(a^{p-1}(p-1)!\) . Hence
The prime \(p\) divides none of the factors of \((p-1)!\) , so by Theorem 4.7(c) it does not divide \((p-1)!\) , and \(\gcd((p-1)!,p)=1\) . Cancelling \((p-1)!\) by Theorem 4.15 gives \(a^{p-1}\equiv 1\pmod p\) . Multiplying by \(a\) gives \(a^{p}\equiv a\) , and this last congruence holds also when \(p\mid a\) , since both sides are then congruent to \(0\) .
The proof is the first row-is-a-rearrangement observation of Figure 4.1, multiplied out.
Example 4.8: A large power modulo seven
Find the remainder of \(3^{100}\) on division by \(7\) . By Fermat’s little theorem \(3^{6}\equiv 1\pmod 7\) . Divide the exponent by \(6\) : \(100=6\cdot 16+4\) . Hence
because \(81=11\cdot 7+4\) . The remainder is \(4\) .
The rearrangement in the proof can be seen directly: the remainders of \(3\cdot 1,3\cdot 2,\dots,3\cdot 6\) modulo \(7\) are \(3,6,2,5,1,4\) , which is the third row of the left table in Figure 4.1.
The theorem lets exponents be reduced modulo \(p-1\) , not modulo \(p\) . Its converse is false: \(2^{340}\equiv 1\pmod{341}\) , although \(341=11\cdot 31\) is not prime. This follows from \(2^{10}=1024=3\cdot 341+1\) .
The last theorem of the chapter concerns several moduli at once. An old puzzle asks for a number that leaves remainder \(2\) when divided by \(3\) , remainder \(3\) when divided by \(5\) , and remainder \(2\) when divided by \(7\) .
Theorem 4.18 (Chinese remainder theorem). Let \(m\) and \(n\) be coprime positive integers and let \(a\) and \(b\) be any integers. Then there is an integer \(x\) with
and any two such integers are congruent modulo \(mn\) .
Proof. Existence. By Theorem 4.5 there are integers \(u\) , \(v\) with \(mu+nv=1\) . Let \(x=a\,nv+b\,mu\) . Modulo \(m\) , the term \(b\,mu\) vanishes and \(nv=1-mu\equiv 1\) , so \(x\equiv a\) . Modulo \(n\) , the term \(a\,nv\) vanishes and \(mu=1-nv\equiv 1\) , so \(x\equiv b\) .
Uniqueness. If \(x\) and \(x'\) both satisfy the two congruences, then \(m\mid(x-x')\) and \(n\mid(x-x')\) . Since \(\gcd(m,n)=1\) , Theorem 4.7(b) gives \(mn\mid(x-x')\) .
In the terms of Chapter 2: the function from \(\mathbb Z_{mn}\) to \(\mathbb Z_m\times\mathbb Z_n\) sending the class of \(x\) to the pair of its classes modulo \(m\) and modulo \(n\) is a bijection when \(m\) and \(n\) are coprime. Existence is surjectivity and uniqueness is injectivity.
Example 4.9: Three remainders
Solve \(x\equiv 2\pmod 3\) , \(x\equiv 3\pmod 5\) , \(x\equiv 2\pmod 7\) .
Combine the first two congruences. A Bézout identity for \(3\) and \(5\) is \(3\cdot 2+5\cdot(-1)=1\) , so in the notation of the proof \(mu=6\) and \(nv=-5\) , and \(x=2\cdot(-5)+3\cdot 6=8\) . Indeed \(8=2\cdot 3+2\) and \(8=1\cdot 5+3\) . So the first two congruences together say \(x\equiv 8\pmod{15}\) .
Now combine \(x\equiv 8\pmod{15}\) with \(x\equiv 2\pmod 7\) ; the moduli \(15\) and \(7\) are coprime. A Bézout identity is \(15\cdot 1+7\cdot(-2)=1\) , so \(mu=15\) and \(nv=-14\) , and
The solutions are the integers congruent to \(23\) modulo \(105\) . Check: \(23=7\cdot 3+2\) , \(23=4\cdot 5+3\) , \(23=3\cdot 7+2\) .
4.8 An application: a lock that anyone can close
The tools of this chapter combine into one of the most widely used inventions of modern mathematics, a cipher in which the method of locking a message is published and only the method of unlocking is secret.
Proposition 4.19 (the RSA identity). Let \(p\) and \(q\) be distinct primes, let \(n=pq\) , and let \(e\) and \(d\) be positive integers with \(ed\equiv 1\pmod{(p-1)(q-1)}\) . Then \(m^{ed}\equiv m\pmod n\) for every integer \(m\) .
Proof. Write \(ed=1+k(p-1)(q-1)\) with \(k\in\mathbb N\) . We first show \(m^{ed}\equiv m\pmod p\) . If \(p\mid m\) , both sides are congruent to \(0\) . If \(p\nmid m\) , then \(m^{p-1}\equiv 1\pmod p\) by Theorem 4.17, so
By the same argument with \(q\) in place of \(p\) , \(m^{ed}\equiv m\pmod q\) . Thus \(p\) and \(q\) both divide \(m^{ed}-m\) , and since distinct primes are coprime, Theorem 4.7(b) gives \(pq\mid m^{ed}-m\) .
To use the identity, a receiver chooses the primes, computes \(n\) , picks \(e\) coprime to \((p-1)(q-1)\) , and finds \(d\) as the inverse of \(e\) modulo \((p-1)(q-1)\) by the extended Euclidean algorithm. The pair \((n,e)\) is made public. A sender turns a message into a number \(m\) with \(0\le m<n\) and transmits \(c=m^{e}\bmod n\) . The receiver computes \(c^{d}\bmod n\) , which is \(m\) by the proposition. Finding \(d\) from the public pair appears to require the factors of \(n\) , and no fast method for factoring large integers is known; that gap between multiplying and factoring is the lock.
Example 4.10: The cipher with two-digit primes
Take \(p=11\) and \(q=13\) , so \(n=143\) and \((p-1)(q-1)=120\) . Choose \(e=7\) , which is coprime to \(120\) . Its inverse modulo \(120\) comes from Euclid’s algorithm: \(120=17\cdot 7+1\) , so \(1=120-17\cdot 7\) and \(d\equiv -17\equiv 103\pmod{120}\) . Check: \(7\cdot 103=721=6\cdot 120+1\) .
Encrypt the message \(m=9\) . By repeated squaring modulo \(143\) : \(9^{2}=81\) , and \(9^{4}=81^{2}=6561\equiv 126\) since \(6561=45\cdot 143+126\) . Then \(9^{7}=9^{4}\cdot 9^{2}\cdot 9\equiv 126\cdot 81\cdot 9\) . Now \(126\cdot 81=10206\equiv 53\) , and \(53\cdot 9=477\equiv 48\) . The ciphertext is \(c=48\) .
Decrypting means computing \(48^{103}\bmod 143\) , which by Proposition 4.19 must return \(9\) ; carried out by repeated squaring, it does. A real system uses primes of several hundred digits, and every step, from finding inverses to raising to powers, is done by the algorithms of this chapter.
The chapter has used, in order, well-ordering, the invariant and the monovariant, equivalence classes and well-defined operations, and bijections. One idea from the proof of Fermat’s theorem was used without comment: that \(p-1\) different elements of a set of size \(p-1\) must exhaust it. That is a statement about counting, and counting is the subject of the next chapter. A question to carry forward: how many of the residues \(0,1,\dots,n-1\) are units modulo \(n\) when \(n=pq\) is a product of two distinct primes, and why does the answer explain the number \((p-1)(q-1)\) ?
Exercises
-
Find the quotient and remainder, in the sense of Theorem 4.1, when \(100\) is divided by \(7\) , when \(-100\) is divided by \(7\) , when \(7\) is divided by \(100\) , and when \(-1\) is divided by \(5\) , writing each result in the form \(a=qd+r\) .
Answer
\(100=14\cdot 7+2\) ; \(-100=(-15)\cdot 7+5\) ; \(7=0\cdot 100+7\) ; \(-1=(-1)\cdot 5+4\) . In each case the remainder lies between \(0\) and \(d-1\) .
-
Show that the uniqueness part of the division theorem fails if the condition \(0\le r<d\) is weakened to \(0\le r\le d\) . Then prove that every integer \(a\) can be written in exactly one way as \(a=3q+r\) with \(r\in\{-1,0,1\}\) .
Hint
For the first part, write \(6\) in two ways as \(3q+r\) with \(0\le r\le 3\) . For the second, apply the division theorem to \(a+1\) with \(d=3\) , obtaining \(a+1=3q+s\) with \(s\in\{0,1,2\}\) , and put \(r=s-1\) . Uniqueness of \((q,r)\) follows from uniqueness of \((q,s)\) .
-
Run Euclid’s algorithm on the pairs \((252,105)\) and \((1071,462)\) , listing every division, and state the greatest common divisor and the number of divisions in each case.
Answer
\(252=2\cdot 105+42\) , \(105=2\cdot 42+21\) , \(42=2\cdot 21+0\) : \(\gcd(252,105)=21\) after three divisions. \(1071=2\cdot 462+147\) , \(462=3\cdot 147+21\) , \(147=7\cdot 21+0\) : \(\gcd(1071,462)=21\) after three divisions.
-
Find integers \(x\) and \(y\) with \(252x+105y=21\) by back-substitution, and then describe all pairs of integers \((x,y)\) satisfying the equation, justifying that your description is complete.
Solution
From the divisions \(252=2\cdot 105+42\) and \(105=2\cdot 42+21\) ,
\[ 21=105-2\cdot 42=105-2(252-2\cdot 105)=5\cdot 105-2\cdot 252 . \]So \((x,y)=(-2,5)\) is one solution.
Dividing the equation by \(21\) gives the equivalent equation \(12x+5y=1\) . Let \((x,y)\) be any solution. Subtracting \(12\cdot(-2)+5\cdot 5=1\) gives \(12(x+2)+5(y-5)=0\) , so \(5\mid 12(x+2)\) . Since \(\gcd(5,12)=1\) , Theorem 4.7(a) gives \(5\mid(x+2)\) ; write \(x=-2+5t\) . Substituting, \(5(y-5)=-12\cdot 5t\) , so \(y=5-12t\) . Conversely, for every integer \(t\) , \(12(-2+5t)+5(5-12t)=-24+25=1\) . Hence the solutions are exactly the pairs
\[ (x,y)=(-2+5t,\ 5-12t),\qquad t\in\mathbb Z . \]The steps \(5=105/21\) and \(12=252/21\) are the amounts by which the coefficients can be shifted without changing the combination.
-
Decide which of the equations \(15x+25y=40\) and \(15x+25y=42\) has a solution in integers. Give a solution where one exists and a proof of impossibility where none does.
Answer
\(\gcd(15,25)=5\) . Since \(5\mid 40\) , the first equation is solvable; for instance \((x,y)=(1,1)\) . Since \(5\nmid 42\) , the second has no solution: the left side is a multiple of \(5\) for all integers \(x\) , \(y\) , by Theorem 4.5(b).
-
Prove by induction, using Lemma 4.3, that consecutive Fibonacci numbers are coprime: \(\gcd(F_{n+1},F_n)=1\) for every \(n\ge 1\) .
Solution
Let \(P(n)\) be the statement \(\gcd(F_{n+1},F_n)=1\) .
Base case: \(F_2=1\) and \(F_1=1\) , and \(\gcd(1,1)=1\) .
Inductive step: let \(k\ge 1\) and assume \(\gcd(F_{k+1},F_k)=1\) . The Fibonacci recurrence says \(F_{k+2}=1\cdot F_{k+1}+F_k\) , which has the form \(a=qb+r\) with \(a=F_{k+2}\) , \(b=F_{k+1}\) , \(q=1\) , \(r=F_k\) . Since \(F_{k+1}\ne 0\) , Lemma 4.3 gives
\[ \gcd(F_{k+2},F_{k+1})=\gcd(F_{k+1},F_k)=1 , \]the last equality by the induction hypothesis. This is \(P(k+1)\) . The lemma does not require \(r\) to be the remainder of a division, only that the equation \(a=qb+r\) holds, so it applies even when \(F_k\) is not smaller than \(F_{k+1}\) .
-
Give numerical examples showing that parts (a) and (b) of Theorem 4.7 fail when the coprimality hypothesis is dropped. Then prove that if \(\gcd(a,b)=1\) then \(\gcd(a,bc)=\gcd(a,c)\) for every integer \(c\) with \(a\) and \(c\) not both zero.
Solution
For (a): \(6\mid 4\cdot 9=36\) but \(6\nmid 9\) ; here \(\gcd(4,6)=2\) . For (b): \(4\mid 12\) and \(6\mid 12\) , but \(4\cdot 6=24\nmid 12\) ; here \(\gcd(4,6)=2\) .
Now suppose \(\gcd(a,b)=1\) , and let \(d=\gcd(a,c)\) and \(e=\gcd(a,bc)\) . First, \(d\) divides \(a\) and \(c\) , hence divides \(a\) and \(bc\) , so \(d\) is a common divisor of \(a\) and \(bc\) and \(d\le e\) . Second, \(e\) divides \(a\) and \(bc\) . Any common divisor of \(e\) and \(b\) divides \(a\) and \(b\) , so it is \(1\) ; thus \(\gcd(e,b)=1\) . Since \(e\mid bc\) , Theorem 4.7(a) gives \(e\mid c\) . So \(e\) is a common divisor of \(a\) and \(c\) , and \(e\le d\) . Therefore \(d=e\) .
-
Prove that \(\gcd(n,n+1)=1\) and \(\gcd(2n+1,3n+1)=1\) for every integer \(n\ge 1\) by exhibiting, in each case, an integer combination equal to \(1\) , and say which theorem turns the combination into the conclusion.
Hint
\((n+1)-n=1\) and \(3(2n+1)-2(3n+1)=1\) . By Theorem 4.5(b), every integer combination of two numbers is a multiple of their greatest common divisor, and the only positive divisor of \(1\) is \(1\) .
-
Find the prime factorizations of \(504\) and \(540\) . Use them to compute \(\gcd(504,540)\) , \(\operatorname{lcm}(504,540)\) , and the number of positive divisors of \(504\) .
Answer
\(504=2^{3}\cdot 3^{2}\cdot 7\) and \(540=2^{2}\cdot 3^{3}\cdot 5\) . Taking smaller exponents, \(\gcd=2^{2}\cdot 3^{2}=36\) ; taking larger ones, \(\operatorname{lcm}=2^{3}\cdot 3^{3}\cdot 5\cdot 7=7560\) . The number of positive divisors of \(504\) is \((3+1)(2+1)(1+1)=24\) .
-
Let \(p\) be a prime. Use the fundamental theorem of arithmetic to prove that there are no positive integers \(a\) , \(b\) with \(a^{2}=pb^{2}\) , by comparing the exponent of \(p\) on the two sides. Say exactly where uniqueness of factorization is used.
Solution
Suppose \(a^{2}=pb^{2}\) with \(a\) , \(b\) positive integers, and let \(n\) be this common value; \(n\ge 2\) because \(p\ge 2\) .
Let \(\alpha\) be the exponent of \(p\) in the prime factorization of \(a\) and \(\beta\) its exponent in that of \(b\) , each taken to be \(0\) if \(p\) does not occur. Squaring a factorization doubles every exponent, so multiplying out the factorization of \(a\) twice gives a factorization of \(n\) in which \(p\) has exponent \(2\alpha\) , an even number. Multiplying out \(p\cdot b\cdot b\) gives a factorization of \(n\) in which \(p\) has exponent \(1+2\beta\) , an odd number. An even number is not equal to an odd one, so \(n\) has two factorizations into primes that differ in the number of times \(p\) occurs. This contradicts the uniqueness part of Theorem 4.8. That is the one place where uniqueness is used: without it, “the exponent of \(p\) in \(n\) ” would not be a well-defined number. Hence \(\sqrt p\) is irrational for every prime \(p\) .
-
Prove that there are infinitely many primes of the form \(4k+3\) . Adapt the proof of Theorem 4.9 using the number \(N=4p_1p_2\cdots p_k-1\) , and first show that a product of integers of the form \(4k+1\) again has that form.
Hint
First check that \((4a+1)(4b+1)=4(4ab+a+b)+1\) . Given a list \(p_1,\dots,p_k\) of primes of the form \(4k+3\) , the number \(N=4p_1\cdots p_k-1\) is odd and of the form \(4k+3\) . Its prime divisors are odd; if all were of the form \(4k+1\) , so would \(N\) be. So some prime divisor has the form \(4k+3\) , and it cannot be on the list, since it would then divide \(1\) .
-
Criticise this argument: “Let \(p_1,\dots,p_k\) be the first \(k\) primes and \(N=p_1\cdots p_k+1\) . None of \(p_1,\dots,p_k\) divides \(N\) . Hence \(N\) has no prime divisors other than itself, so \(N\) is prime.” Identify the invalid step, and give a value of \(k\) for which the conclusion is false.
Solution
The invalid step is the inference from “none of \(p_1,\dots,p_k\) divides \(N\) ” to “\(N\) has no prime divisor other than itself”. The premise rules out only the first \(k\) primes. A prime divisor of \(N\) could be any prime larger than \(p_k\) and smaller than \(N\) , and nothing in the argument excludes that.
The conclusion fails for \(k=6\) : \(N=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13+1=30031=59\cdot 509\) . For \(k=1,\dots,5\) the numbers \(3,7,31,211,2311\) happen to be prime, which is what makes the fallacy tempting. What Theorem 4.9 actually proves is weaker and sufficient: \(N\) has some prime divisor, and that divisor is not among \(p_1,\dots,p_k\) .
-
Compute, reducing as you go: (a) \(2^{50}\bmod 7\) ; (b) the last digit of \(3^{2025}\) ; (c) \(10^{100}\bmod 11\) ; (d) the remainder of \(1!+2!+3!+\dots+100!\) on division by \(12\) .
Answer
(a) \(2^{3}=8\equiv 1\pmod 7\) and \(50=3\cdot 16+2\) , so \(2^{50}\equiv 2^{2}=4\) . (b) \(3^{4}=81\equiv 1\pmod{10}\) and \(2025=4\cdot 506+1\) , so the last digit is \(3\) . (c) \(10\equiv -1\pmod{11}\) , so \(10^{100}\equiv 1\) . (d) Every \(k!\) with \(k\ge 4\) is divisible by \(12\) , so the sum is congruent to \(1+2+6=9\) .
-
Prove that a positive integer is congruent modulo \(9\) to the sum of its decimal digits and congruent modulo \(11\) to the alternating sum of its digits taken from the right. Apply both facts to \(123456789\) to find its remainders on division by \(9\) and by \(11\) .
Solution
Let the positive integer \(N\) have decimal digits \(d_k,\dots,d_1,d_0\) , so that \(N=\sum_{i=0}^{k}d_i10^{i}\) .
Modulo \(9\) : \(10\equiv 1\) , so \(10^{i}\equiv 1\) for every \(i\) by Theorem 4.12, and therefore \(N\equiv\sum_i d_i\) . Modulo \(11\) : \(10\equiv -1\) , so \(10^{i}\equiv(-1)^{i}\) , and \(N\equiv d_0-d_1+d_2-\dots\) , the alternating sum starting from the units digit.
For \(N=123456789\) the digit sum is \(45\) , and \(45=5\cdot 9\) , so \(N\equiv 0\pmod 9\) : the remainder on division by \(9\) is \(0\) . The alternating sum from the right is \(9-8+7-6+5-4+3-2+1=5\) , so the remainder on division by \(11\) is \(5\) .
-
List the possible values of \(x^{2}\) modulo \(5\) , and use the list to prove that the equation \(x^{2}-5y^{2}=2\) has no solution in integers. Explain why reducing modulo \(5\) , and not some other modulus, is the natural choice.
Solution
Every integer is congruent modulo \(5\) to one of \(0,1,2,3,4\) , and by Theorem 4.12 its square is congruent to the square of that residue: \(0,1,4,9\equiv 4,16\equiv 1\) . So \(x^{2}\) is congruent to \(0\) , \(1\) , or \(4\) modulo \(5\) , never to \(2\) or \(3\) .
Suppose integers \(x\) , \(y\) satisfied \(x^{2}-5y^{2}=2\) . Reducing modulo \(5\) , the term \(5y^{2}\) is congruent to \(0\) , so \(x^{2}\equiv 2\pmod 5\) . That contradicts the list. Hence there is no integer solution.
The modulus \(5\) is natural because it removes the unknown \(y\) entirely, leaving a condition on \(x\) alone that can be checked by a finite list. A congruence argument can only prove that an equation has no solution; an equation that is solvable modulo every \(n\) may still have no integer solution.
-
Use the extended Euclidean algorithm to find the inverse of \(7\) modulo \(26\) and the inverse of \(13\) modulo \(30\) , and explain why \(14\) has no inverse modulo \(21\) .
Answer
\(26=3\cdot 7+5\) , \(7=5+2\) , \(5=2\cdot 2+1\) , so \(1=5-2\cdot 2=3\cdot 5-2\cdot 7=3\cdot 26-11\cdot 7\) ; the inverse of \(7\) modulo \(26\) is \(-11\equiv 15\) . \(30=2\cdot 13+4\) , \(13=3\cdot 4+1\) , so \(1=13-3\cdot 4=7\cdot 13-3\cdot 30\) ; the inverse of \(13\) modulo \(30\) is \(7\) . Since \(\gcd(14,21)=7\ne 1\) , Theorem 4.14 says \(14\) has no inverse modulo \(21\) .
-
Find all solutions, as residue classes for the given modulus, of each congruence: (a) \(5x\equiv 3\pmod{11}\) ; (b) \(9x\equiv 6\pmod{15}\) ; (c) \(9x\equiv 5\pmod{15}\) .
Solution
(a) \(\gcd(5,11)=1\) , so there is one solution class. The inverse of \(5\) modulo \(11\) is \(9\) , since \(5\cdot 9=45=4\cdot 11+1\) . Hence \(x\equiv 9\cdot 3=27\equiv 5\pmod{11}\) . Check: \(5\cdot 5=25=2\cdot 11+3\) .
(b) \(d=\gcd(9,15)=3\) and \(3\mid 6\) , so there are three solution classes modulo \(15\) . Dividing by \(3\) : \(3x\equiv 2\pmod 5\) . The inverse of \(3\) modulo \(5\) is \(2\) , so \(x\equiv 4\pmod 5\) . Modulo \(15\) the solutions are \(x\equiv 4,9,14\) . Check: \(9\cdot 4=36=2\cdot 15+6\) .
(c) \(d=3\) and \(3\nmid 5\) , so by Theorem 4.16 there is no solution. Directly: \(9x\) is always a multiple of \(3\) , and any number congruent to \(5\) modulo \(15\) has the form \(15k+5\) , which is not a multiple of \(3\) .
-
A student argues: “\(6\cdot 2\equiv 6\cdot 7\pmod{10}\) , because \(12\) and \(42\) both end in \(2\) . Cancelling the \(6\) gives \(2\equiv 7\pmod{10}\) .” The conclusion is false. Say which theorem the cancellation needs, why its hypothesis fails, and what true conclusion the theorem does give.
Solution
Cancellation is governed by Theorem 4.15. To cancel a factor \(c\) and keep the modulus \(n\) , the theorem needs \(\gcd(c,n)=1\) . Here \(c=6\) and \(n=10\) , and \(\gcd(6,10)=2\) , so that hypothesis fails. Equivalently, by Theorem 4.14, \(6\) has no inverse modulo \(10\) , so there is nothing to multiply both sides by.
What the theorem does give is a congruence modulo \(n/d=10/2=5\) : from \(6\cdot 2\equiv 6\cdot 7\pmod{10}\) it follows that \(2\equiv 7\pmod 5\) , which is true since \(7-2=5\) . The false statement \(2\equiv 7\pmod{10}\) claims more than the hypothesis can deliver.
-
Use Fermat’s little theorem to find the remainder of \(5^{2026}\) on division by \(13\) . Then verify that \(2^{340}\equiv 1\pmod{341}\) although \(341\) is composite, and say what this shows about the converse of Fermat’s theorem.
Solution
Since \(13\) is prime and \(13\nmid 5\) , Fermat’s little theorem gives \(5^{12}\equiv 1\pmod{13}\) . Divide the exponent by \(12\) : \(2026=12\cdot 168+10\) , so \(5^{2026}\equiv 5^{10}\pmod{13}\) . Now \(5^{2}=25\equiv -1\pmod{13}\) , so \(5^{10}=(5^{2})^{5}\equiv(-1)^{5}=-1\equiv 12\) . The remainder is \(12\) .
For the second part, \(2^{10}=1024=3\cdot 341+1\) , so \(2^{10}\equiv 1\pmod{341}\) and \(2^{340}=(2^{10})^{34}\equiv 1\) . But \(341=11\cdot 31\) is composite. So the congruence \(a^{n-1}\equiv 1\pmod n\) for a single base \(a\) does not prove that \(n\) is prime: the converse of Fermat’s little theorem is false.
-
Solve the simultaneous congruences \(x\equiv 3\pmod 8\) , \(x\equiv 5\pmod 9\) . Then show that \(x\equiv 1\pmod 4\) , \(x\equiv 2\pmod 6\) has no solution, and explain why this does not contradict the Chinese remainder theorem.
Solution
The moduli \(8\) and \(9\) are coprime, so a solution exists and is unique modulo \(72\) . The first congruence says \(x=3+8k\) . Substituting into the second, \(3+8k\equiv 5\pmod 9\) , so \(8k\equiv 2\pmod 9\) . Since \(8\equiv -1\) , this is \(-k\equiv 2\) , that is, \(k\equiv -2\equiv 7\pmod 9\) . Taking \(k=7\) gives \(x=59\) . The solutions are \(x\equiv 59\pmod{72}\) . Check: \(59=7\cdot 8+3\) and \(59=6\cdot 9+5\) .
For the second system, \(x\equiv 1\pmod 4\) forces \(x\) to be odd, while \(x\equiv 2\pmod 6\) forces \(x\) to be even. No integer is both, so there is no solution. The Chinese remainder theorem is not contradicted, because its hypothesis fails: \(\gcd(4,6)=2\) , so the moduli are not coprime.
-
Write out the multiplication table of the residues \(1,\dots,7\) modulo \(8\) . Find all solutions of \(x^{2}\equiv 1\pmod 8\) , and then prove that for a prime \(p\) the congruence \(x^{2}\equiv 1\pmod p\) has only the solutions \(x\equiv 1\) and \(x\equiv -1\) .
Hint
The squares of \(1,\dots,7\) modulo \(8\) are \(1,4,1,0,1,4,1\) , so \(x^{2}\equiv 1\) has the four solutions \(1,3,5,7\) . For a prime \(p\) , rewrite \(x^{2}\equiv 1\) as \(p\mid(x-1)(x+1)\) and apply Euclid’s lemma. The lemma is unavailable modulo \(8\) , and that is why more than two solutions can occur there.
-
For the cipher of Section 4.8 with \(p=5\) , \(q=11\) , and \(e=3\) , find the decryption exponent \(d\) , encrypt the message \(m=7\) , and confirm by repeated squaring that decryption returns \(7\) .
Answer
\((p-1)(q-1)=40\) and \(d=27\) , since \(3\cdot 27=81=2\cdot 40+1\) . Encryption: \(7^{3}=343\equiv 13\pmod{55}\) . Decryption: \(13^{2}\equiv 4\) , \(13^{4}\equiv 16\) , \(13^{8}\equiv 36\) , \(13^{16}\equiv 31\) , and \(27=16+8+2+1\) , so \(13^{27}\equiv 31\cdot 36\cdot 4\cdot 13\equiv 16\cdot 4\cdot 13\equiv 9\cdot 13=117\equiv 7\pmod{55}\) .
-
For jugs of capacities \(7\) and \(5\) litres, find a Bézout identity for \(1\) and translate it into a sequence of fill, pour, and empty operations that leaves exactly \(1\) litre in one jug. Then prove that with jugs of capacities \(a\) and \(b\) every measurable amount is a multiple of \(\gcd(a,b)\) .
Hint
\(3\cdot 5-2\cdot 7=1\) : fill the \(5\) -litre jug three times and discard the \(7\) -litre jug twice. Pour \(5\) into the large jug; pour again until it is full, leaving \(3\) ; empty the large jug and pour the \(3\) in; fill the small jug and top up the large one with \(4\) , leaving \(1\) . For the general claim, show that each operation keeps both amounts integer combinations of \(a\) and \(b\) , and apply Theorem 4.5(b).