Discrete Mathematics and Proof

Modular inverses and linear congruences

Modulo n we can add, subtract and multiply freely, but we cannot simply divide. When can a multiplication be undone, and how do we solve an equation like 23x = 7 when only remainders count?

You need

Bezout's identity and the extended Euclidean algorithmDiscrete Mathematics and Proof Congruence modulo n and its arithmeticDiscrete Mathematics and Proof

Unlocks

RSA public-key encryptionDiscrete Mathematics and Proof The Chinese remainder theoremDiscrete Mathematics and Proof

Where you are 7 in Modular arithmetic

Logic, proof and discrete math6

Introductory number theory8

Modular arithmetic7

▴ 2 above Where the divisibility tests come from Fermat's little theorem

Modular inverses and linear congruences

RSA public-key encryption The Chinese remainder theorem

Why this exists

Congruences modulo n may be added, subtracted and multiplied like equations (Congruence modulo n and its arithmetic), but division breaks: 2 \cdot 3 \equiv 2 \cdot 8 \pmod{10} while 3 \not\equiv 8 \pmod{10}. With rational numbers, dividing by a is multiplying by \tfrac{1}{a}, the number whose product with a is 1 (Inverse operations and the properties of equality). Modulo n there are no fractions, but there may be an integer b with ab \equiv 1 \pmod{n}, and multiplying by b undoes multiplying by a. Day 1 decides when such a b exists and finds it; day 2 uses it to solve ax \equiv b \pmod{n} in every case.

Definition

Throughout, n \ge 2 is the modulus (modulo 1 everything is congruent). The lesson writes plain integers; in \mathbb{Z}_n (Relations, equivalence classes and partitions) each statement is about classes, and “unique modulo n” means “one class.”

Day 1: inverses

An inverse of a modulo n is an integer b with

ab \equiv 1 \pmod{n}.

If a has an inverse modulo n, then a is a unit modulo n. The inverse in \{1, 2, \dots, n - 1\} is written a^{-1} \bmod n. For example 23 \cdot 47 = 1{,}081 = 18 \cdot 60 + 1, so 47 is an inverse of 23 modulo 60. The symbol a^{-1} here names an integer, never the fraction \tfrac{1}{a}.

Day 2: linear congruences

A linear congruence is ax \equiv b \pmod{n} with integers a, b and unknown x. A solution is an integer x that makes it true. If x is one, so is every x' \equiv x, by the multiplication rule, so the number of solutions modulo n means the number among 0, 1, \dots, n - 1.

Intuition

Multiply each remainder modulo 12 by 5, and separately by 3, and reduce:

x	0	1	2	3	4	5
5x \bmod 12	0	5	10	3	8	1
3x \bmod 12	0	3	6	9	0	3

x	6	7	8	9	10	11
5x \bmod 12	6	11	4	9	2	7
3x \bmod 12	6	9	0	3	6	9

Multiplying by 5 shuffles the twelve remainders, each appearing once, so 5x \equiv b always has exactly one solution, and 1 appears: 5 \cdot 5 \equiv 1. Multiplying by 3 collapses them onto the multiples of 3, each hit three times, so 3x \equiv 1 has no solution and 3x \equiv 6 has three. The difference: \gcd(5, 12) = 1, while \gcd(3, 12) = 3 is the number of hits. Modulo a prime nothing collapses except 0; the figure joins each nonzero remainder modulo 11 to its inverse.

Figure 1Modulo the prime 11, every remainder except 0 has an inverse. A chord joins each pair whose product is congruent to 1, and a ring marks the two remainders, 1 and 10, that are their own inverses.

Results

Theorem 1 (existence). An integer a has an inverse modulo n if and only if \gcd(a, n) = 1.

Theorem 2 (uniqueness). If b and c are both inverses of a modulo n, then b \equiv c \pmod{n}. Every integer congruent to an inverse is an inverse. So the inverse is unique modulo n.

Theorem 3 (cancellation). Let c be an integer. The rule “if ca \equiv cb \pmod{n} then a \equiv b \pmod{n}” holds for all integers a, b if and only if \gcd(c, n) = 1.

Corollary 4 (prime modulus). Let p be prime. Every integer a with p \nmid a has an inverse modulo p. So modulo p any factor c \not\equiv 0 may be cancelled, and ab \equiv 0 \pmod{p} forces a \equiv 0 or b \equiv 0.

Theorem 5 (one solution). If \gcd(a, n) = 1, the solutions of ax \equiv b \pmod{n} are exactly the integers x \equiv a^{-1}b \pmod{n}: one solution modulo n.

Theorem 6 (all linear congruences). Let d = \gcd(a, n). The congruence ax \equiv b \pmod{n} has a solution if and only if d \mid b. When d \mid b, it is equivalent to

\tfrac{a}{d}x \equiv \tfrac{b}{d} \pmod{\tfrac{n}{d}},

which has one solution x_0 modulo \tfrac{n}{d}. The original then has exactly d solutions modulo n, namely x_0 + k\tfrac{n}{d} for k = 0, 1, \dots, d - 1.

For a prime modulus there is also a formula, a^{-1} \equiv a^{p-2} \pmod{p}, which comes from Fermat's little theorem and is not used here.

Why it is true

The tools are from Bezout's identity and the extended Euclidean algorithm: “coprime means 1 is a combination,” Euclid’s lemma, and the theorem on ax + by = c.

Proof of Theorem 1. Suppose ab \equiv 1 \pmod{n}. Then ab - 1 = kn for some integer k, so 1 = ab + n(-k) is an integer combination of a and n, and therefore \gcd(a, n) = 1. Conversely, suppose \gcd(a, n) = 1. Then ax + ny = 1 for some integers x, y, so ax - 1 = n(-y) and ax \equiv 1 \pmod{n}. The x of Bezout’s identity is the inverse. \square

Proof of Theorem 2. Suppose ab \equiv 1 and ac \equiv 1 \pmod{n}. By the multiplication rule and the associative and commutative properties,

b \equiv b(ac) = (ab)c \equiv 1 \cdot c = c \pmod{n}.

If b' \equiv b, then ab' \equiv ab \equiv 1, so b' is an inverse too. \square

Proof of Theorem 3. Suppose \gcd(c, n) = 1 and let c' be an inverse of c (Theorem 1). If ca \equiv cb, multiplying both sides by c' gives c'ca \equiv c'cb, that is 1 \cdot a \equiv 1 \cdot b. For the converse we prove the contrapositive: suppose d = \gcd(c, n) > 1. Take a = \tfrac{n}{d} and b = 0. Then

c \cdot \tfrac{n}{d} = \tfrac{c}{d} \cdot n \equiv 0 = c \cdot 0 \pmod{n},

but 0 < \tfrac{n}{d} < n, so n \nmid \tfrac{n}{d} - 0 and a \not\equiv b. The rule fails for this pair. \square

Proof of Corollary 4. The positive divisors of p are 1 and p, and p \nmid a, so \gcd(a, p) = 1, and Theorem 1 applies. Cancellation follows from Theorem 3. If ab \equiv 0 and a \not\equiv 0, cancel a from ab \equiv a \cdot 0 to get b \equiv 0. \square

Proof of Theorem 5. Let a' be an inverse of a. If ax \equiv b, multiplying by a' gives x \equiv a'b. Conversely, x = a'b works: a(a'b) = (aa')b \equiv b. By Theorem 2 a different choice of inverse changes a'b only within its class. \square

Proof of Theorem 6. By definition, ax \equiv b \pmod{n} holds exactly when ax - b = ny for some integer y, that is, when (x, -y) solves ax + ny = b. By the theorem on linear equations in integers, such a pair exists if and only if d \mid b.

Now let d \mid b and write a = da', b = db', n = dn'. The equation d(a'x - b') = dn'y holds exactly when a'x - b' = n'y, since d \ne 0 cancels in the integers. So ax \equiv b \pmod{n} exactly when a'x \equiv b' \pmod{n'}. Here \gcd(a', n') = 1, since a common divisor e of a' and n' makes de a common divisor of a and n. So by Theorem 5 (or trivially, if n' = 1) the solutions are x = x_0 + tn', t \in \mathbb{Z}.

To count them modulo n, write t = qd + s with 0 \le s < d; then x_0 + tn' = (x_0 + sn') + qn, so every solution is congruent to one of the d numbers x_0 + sn'. These are pairwise incongruent: two of them differ by (s - s')n' with 0 < |s - s'| < d, strictly between 0 and n = dn' in size, so not a multiple of n. \square

Worked examples

Examples 1 to 3 go with day 1, examples 4 to 7 with day 2.

Example 1

The inverse of 23 modulo 60

Find 23^{-1} \bmod 60.

Solution

Since 23 is prime and does not divide 60, \gcd(23, 60) = 1, so an inverse exists by Theorem 1. Run the Euclidean algorithm:

\begin{aligned} 60 &= 2 \cdot 23 + 14, \\ 23 &= 1 \cdot 14 + 9, \\ 14 &= 1 \cdot 9 + 5, \\ 9 &= 1 \cdot 5 + 4, \\ 5 &= 1 \cdot 4 + 1. \end{aligned}

Back substitution writes 1 as a combination, replacing each remainder by the line that made it:

\begin{aligned} 1 &= 5 - 4 = 2 \cdot 5 - 9 \\ &= 2 \cdot 14 - 3 \cdot 9 \\ &= 5 \cdot 14 - 3 \cdot 23 \\ &= 5 \cdot 60 - 13 \cdot 23. \end{aligned}

So 23 \cdot (-13) = 1 - 5 \cdot 60 \equiv 1 \pmod{60}, and -13 is an inverse. By Theorem 2 so is -13 + 60 = 47, the one in \{1, \dots, 59\}: 23^{-1} \bmod 60 = 47. Check: 23 \cdot 47 = 1{,}081 = 18 \cdot 60 + 1.

Example 2

Tables of inverses modulo 12 and modulo 11

List every unit modulo 12 with its inverse, and do the same modulo 11.

Solution

For a small modulus, Theorem 1 says which entries to look for and a short search finds each. Modulo 12 the units are the remainders coprime to 12: 1, 5, 7, 11; the other eight share a factor 2 or 3 with 12. Since 5^2 = 24 + 1, 7^2 = 48 + 1 and 11^2 = 120 + 1, every unit modulo 12 is its own inverse.

Modulo the prime 11, all of 1, \dots, 10 are units (Corollary 4). For each a, search for the multiple of a among 1, 12, 23, \dots, 100, the numbers 11k + 1:

a	1	2	3	4	5
a^{-1} \bmod 11	1	6	4	3	9

a	6	7	8	9	10
a^{-1} \bmod 11	2	8	7	5	10

For instance 5 \cdot 9 = 45 and 7 \cdot 8 = 56. The pairs are the chords of the figure; only 1 and 10 \equiv -1 are their own inverses.

Example 3

Which cancellations are allowed

Modulo 72, decide whether 35 may be cancelled from 35x \equiv 35y, and whether 33 may be cancelled from 33x \equiv 33y.

Solution

By Theorem 3 the question is whether the factor is a unit. Since 35 = 5 \cdot 7 and 72 = 2^3 \cdot 3^2 share no prime, \gcd(35, 72) = 1 and cancelling 35 is valid. In fact 35^2 = 1{,}225 = 17 \cdot 72 + 1, so multiplying both sides by 35 does the cancelling.

But \gcd(33, 72) = 3, so cancelling 33 is not valid. The proof of Theorem 3 gives a failing pair, x = \tfrac{72}{3} = 24 and y = 0: 33 \cdot 24 = 792 = 11 \cdot 72 \equiv 33 \cdot 0, while 24 \not\equiv 0 \pmod{72}.

Example 4

Solving with the inverse

Solve (a) 23x \equiv 7 \pmod{60} and (b) 23x + 41 \equiv 18 \pmod{60}.

Solution

(a) Since \gcd(23, 60) = 1, Theorem 5 gives one solution modulo 60. Multiply both sides by 23^{-1} \bmod 60 = 47 from Example 1:

x \equiv 47 \cdot 7 = 329 = 5 \cdot 60 + 29 \equiv 29 \pmod{60}.

The solutions are x = 29 + 60k, k \in \mathbb{Z}. Check: 23 \cdot 29 = 667 = 11 \cdot 60 + 7.

(b) Subtract 41 from both sides, which the subtraction rule allows: 23x \equiv 18 - 41 = -23. The right side is 23 \cdot (-1), and 23 is a unit, so cancel it (Theorem 3): x \equiv -1 \equiv 59 \pmod{60}. Check: 23 \cdot 59 + 41 = 1{,}398 = 23 \cdot 60 + 18.

Example 5

When the gcd is not 1

Solve 28x \equiv 20 \pmod{44}, and show that 28x \equiv 18 \pmod{44} has no solution.

Solution

Here d = \gcd(28, 44) = 4, and 4 \mid 20, so by Theorem 6 there are exactly 4 solutions modulo 44. Divide a, b and the modulus by 4:

7x \equiv 5 \pmod{11}.

From the table in Example 2, 7^{-1} \bmod 11 = 8, so x \equiv 8 \cdot 5 = 40 \equiv 7 \pmod{11}. The step is \tfrac{44}{4} = 11, and the four solutions modulo 44 are

x \equiv 7,\ 18,\ 29,\ 40 \pmod{44}.

Check two: 28 \cdot 7 = 196 = 4 \cdot 44 + 20 and 28 \cdot 40 = 1{,}120 = 25 \cdot 44 + 20.

For 28x \equiv 18: every 28x - 44y is a multiple of 4 and 18 is not, so there is no solution (d \nmid b in Theorem 6).

Example 6

Paying with fifty-dollar bills

Dovid buys gift cards at \$27 each, pays with \$50 bills only, and gets \$11 back in change. He bought fewer than 50 cards. How many did he buy, and how many bills did he hand over?

Solution

With x cards and k bills, 27x + 11 = 50k, so 27x + 11 \equiv 0 \pmod{50}, or

27x \equiv -11 \equiv 39 \pmod{50}.

Since \gcd(27, 50) = 1, there is one solution modulo 50. The algorithm gives 50 = 1 \cdot 27 + 23, 27 = 1 \cdot 23 + 4, 23 = 5 \cdot 4 + 3, 4 = 1 \cdot 3 + 1, and back substitution gives

\begin{aligned} 1 &= 4 - 3 = 6 \cdot 4 - 23 \\ &= 6 \cdot 27 - 7 \cdot 23 \\ &= 13 \cdot 27 - 7 \cdot 50. \end{aligned}

So 27^{-1} \bmod 50 = 13 and x \equiv 13 \cdot 39 = 507 \equiv 7 \pmod{50}, and the only count below 50 is x = 7. Since 27 \cdot 7 + 11 = 200 = 4 \cdot 50, Dovid bought 7 cards with four \$50 bills.

Example 7

Which right-hand sides can be reached

For which b in \{0, 1, \dots, 35\} does 15x \equiv b \pmod{36} have a solution, and how many solutions modulo 36 does each have? Solve the case b = 21.

Solution

Here d = \gcd(15, 36) = 3. By Theorem 6 there is a solution exactly when 3 \mid b, that is for the 12 values b = 0, 3, 6, \dots, 33, and each has exactly 3 solutions modulo 36. The count is consistent: x \mapsto 15x \bmod 36 sends the 36 remainders onto 12 values, each hit 3 times, as in the Intuition.

For b = 21, divide by 3: 5x \equiv 7 \pmod{12}. From Example 2, 5^{-1} \bmod 12 = 5, so x \equiv 35 \equiv 11 \pmod{12}, and stepping by 12 gives

x \equiv 11,\ 23,\ 35 \pmod{36}.

Check: 15 \cdot 11 = 165 = 4 \cdot 36 + 21.

Boundaries

No inverse without coprimality. 2 has no inverse modulo 10: every 2b - 10k is even, so never 1. That is why 2 could not be cancelled in Congruence modulo n and its arithmetic.
An inverse belongs to its modulus. 23^{-1} \bmod 60 = 47, but modulo 7, 23 \equiv 2 and 23^{-1} \bmod 7 = 4. Changing n changes the answer, and may destroy it: 23 has no inverse modulo 46.
Dividing by a common factor of a and n divides the modulus too. From 28x \equiv 20 \pmod{44} one may pass to 7x \equiv 5 \pmod{11}, not to 7x \equiv 5 \pmod{44}, which misses three of the four solutions. A factor coprime to n cancels and keeps n (Theorem 3).
The counts are for linear congruences only. Modulo 8, x^2 \equiv 1 has four solutions, 1, 3, 5, 7 (squares 1, 9, 25, 49; even squares are even); Theorem 6 says nothing about squares.

Where this goes next

An inverse is the key step of the The Chinese remainder theorem, which pastes congruences with coprime moduli into one. In RSA public-key encryption the private exponent is an inverse of the public one, computed by the algorithm of Example 1. Fermat's little theorem gives inverses modulo a prime as powers, and inverses give negative exponents a meaning in Powers modulo n. Corollary 4 says the integers modulo a prime allow division by anything nonzero, as the rational numbers do.

Exercises

Day 1: finding inverses

Use the extended Euclidean algorithm to find 17^{-1} \bmod 43.
Find 31^{-1} \bmod 100, and check it from the last two digits of the product.
Find 37^{-1} \bmod 90.
Which of 21, 25, 35 have an inverse modulo 56? Find each inverse that exists.
Make the table of units and inverses modulo 9.
Make the table of inverses modulo 13 for a = 1, \dots, 12.
List the units modulo 15 and pair each with its inverse. Which are their own inverses?
Modulo 63, decide whether 26 may be cancelled from 26x \equiv 26y, and whether 15 may be cancelled from 15x \equiv 15y. For a factor that may not, give a failing pair.

Day 1: reasoning

Prove that if a and c are units modulo n, then so is ac, with inverse a^{-1}c^{-1}.
Prove that n - 1 is its own inverse modulo n for every n \ge 2.
Let p be prime and p \nmid a. Prove that a is its own inverse modulo p if and only if a \equiv 1 or a \equiv -1 \pmod{p}.
Prove that 1 \cdot 2 \cdot 3 \cdots (p - 1) \equiv -1 \pmod{p} for every prime p, by pairing each factor with its inverse as in the figure.

Day 2: solving linear congruences

Solve 17x \equiv 5 \pmod{43}.
Solve 37x \equiv 14 \pmod{90}.
Solve 9x + 4 \equiv 1 \pmod{25}.
Solve 30x \equiv 18 \pmod{42}, listing every solution modulo 42.
Show that 30x \equiv 20 \pmod{42} has no solution.
Solve 24x \equiv 16 \pmod{56}, listing every solution modulo 56.

Day 2: dollars and days

Concert tickets cost \$12 each. The night’s ticket money is banked in stacks of \$45, with \$21 left over. Fewer than 50 tickets were sold. How many could have been sold?
Number the weekdays Sunday 0 through Saturday 6. Dovid waters a fern every 9 days, the first time on a Monday. Which watering is the first to fall on a Friday, and how often after that is it a Friday?

Day 2: reasoning

Prove that if \gcd(a, n) = 1, the numbers a \cdot 0, a \cdot 1, \dots, a \cdot (n - 1) leave n different remainders on division by n.
Solve 6x \equiv 4 \pmod{10}. Then solve 3x \equiv 2 \pmod{10}. Which solution of the first does the second miss?
Prove directly from the definitions that if d = \gcd(a, n) and d \nmid b, then ax \equiv b \pmod{n} has no solution.
Find every n \ge 2 for which 4x \equiv 2 \pmod{n} has exactly two solutions modulo n.

Answers

38. 43 = 2 \cdot 17 + 9, 17 = 1 \cdot 9 + 8, 9 = 1 \cdot 8 + 1, so 1 = 9 - 8 = 2 \cdot 9 - 17 = 2 \cdot 43 - 5 \cdot 17. The inverse is -5 \equiv 38. Check: 17 \cdot 38 = 646 = 15 \cdot 43 + 1.
71. 100 = 3 \cdot 31 + 7, 31 = 4 \cdot 7 + 3, 7 = 2 \cdot 3 + 1, so 1 = 7 - 2 \cdot 3 = 9 \cdot 7 - 2 \cdot 31 = 9 \cdot 100 - 29 \cdot 31, and -29 \equiv 71. Check: 31 \cdot 71 = 2{,}201, which ends in 01.
73. 90 = 2 \cdot 37 + 16, 37 = 2 \cdot 16 + 5, 16 = 3 \cdot 5 + 1, so 1 = 16 - 3 \cdot 5 = 7 \cdot 16 - 3 \cdot 37 = 7 \cdot 90 - 17 \cdot 37, and -17 \equiv 73. Check: 37 \cdot 73 = 2{,}701 = 30 \cdot 90 + 1.
Only 25, with inverse 9. \gcd(21, 56) = 7 and \gcd(35, 56) = 7, so neither is a unit. \gcd(25, 56) = 1, and 56 = 2 \cdot 25 + 6, 25 = 4 \cdot 6 + 1 give 1 = 25 - 4 \cdot 6 = 9 \cdot 25 - 4 \cdot 56. Check: 25 \cdot 9 = 225 = 4 \cdot 56 + 1.
Units 1, 2, 4, 5, 7, 8 (0, 3, 6 share the factor 3). Pairs: 1 \leftrightarrow 1, 2 \leftrightarrow 5, 4 \leftrightarrow 7, 8 \leftrightarrow 8, since 10, 28, 64 are each 1 more than a multiple of 9.
1 \leftrightarrow 1, 2 \leftrightarrow 7, 3 \leftrightarrow 9, 4 \leftrightarrow 10, 5 \leftrightarrow 8, 6 \leftrightarrow 11, 12 \leftrightarrow 12, from the products 14, 27, 40, 40, 66, 144.
Units 1, 2, 4, 7, 8, 11, 13, 14. Pairs 2 \leftrightarrow 8 and 7 \leftrightarrow 13 (products 16, 91); 1, 4, 11, 14 are their own inverses (16, 121, 196).
26 may be cancelled: 26 = 2 \cdot 13 and 63 = 3^2 \cdot 7 share no prime, so \gcd(26, 63) = 1. 15 may not: \gcd(15, 63) = 3, and 15 \cdot 21 = 315 = 5 \cdot 63 \equiv 15 \cdot 0 while 21 \not\equiv 0 \pmod{63}.
Proof. Let a' and c' be inverses of a and c. By the commutative and associative properties, (ac)(a'c') = (aa')(cc') \equiv 1 \cdot 1 = 1 \pmod{n}. So a'c' is an inverse of ac. \square
Proof. (n - 1)^2 = n^2 - 2n + 1 = n(n - 2) + 1, so (n - 1)^2 - 1 is a multiple of n and (n - 1)(n - 1) \equiv 1 \pmod{n}. \square
Proof. By Corollary 4, a has an inverse a'. If a' \equiv a then a^2 \equiv aa' \equiv 1; if a^2 \equiv 1 then a is an inverse of itself. So the condition is a^2 \equiv 1, that is p \mid a^2 - 1 = (a - 1)(a + 1). By Euclid’s lemma this holds exactly when p \mid a - 1 or p \mid a + 1, that is a \equiv 1 or a \equiv -1. \square
Proof. For p = 2 the product is 1 \equiv -1 \pmod{2}, and for p = 3 it is 2 \equiv -1. Let p \ge 5. Each a in \{2, \dots, p - 2\} has an inverse in \{1, \dots, p - 1\} (Corollary 4, Theorem 2), the inverse of the inverse is a again, and by Exercise 11 the inverse is neither 1, p - 1 nor a itself. So \{2, \dots, p - 2\} splits into pairs whose product is congruent to 1, and the product of all of them is congruent to 1. The full product is then 1 \cdot 1 \cdot (p - 1) \equiv -1 \pmod{p}. \square (This is Wilson’s theorem.)
x \equiv 18 \pmod{43}. By Exercise 1, x \equiv 38 \cdot 5 = 190 = 4 \cdot 43 + 18. Check: 17 \cdot 18 = 306 = 7 \cdot 43 + 5.
x \equiv 32 \pmod{90}. By Exercise 3, x \equiv 73 \cdot 14 = 1{,}022 = 11 \cdot 90 + 32. Check: 37 \cdot 32 = 1{,}184 = 13 \cdot 90 + 14.
x \equiv 8 \pmod{25}. Subtract 4: 9x \equiv -3 \equiv 22. Since 9 \cdot 14 = 126 = 5 \cdot 25 + 1, 9^{-1} \bmod 25 = 14 and x \equiv 22 \cdot 14 = 308 \equiv 8. Check: 9 \cdot 8 + 4 = 76 = 3 \cdot 25 + 1.
x \equiv 2, 9, 16, 23, 30, 37 \pmod{42}. \gcd(30, 42) = 6 and 6 \mid 18, so there are 6 solutions. Dividing by 6: 5x \equiv 3 \pmod{7}, and 5^{-1} \bmod 7 = 3, so x \equiv 9 \equiv 2 \pmod{7}. Check: 30 \cdot 2 = 60 = 42 + 18.
\gcd(30, 42) = 6, and 6 \nmid 20. Every 30x - 42y is a multiple of 6, so it is never 20, and Theorem 6 gives no solution.
x \equiv 3, 10, 17, 24, 31, 38, 45, 52 \pmod{56}. \gcd(24, 56) = 8 and 8 \mid 16. Dividing by 8: 3x \equiv 2 \pmod{7}, and 3^{-1} \bmod 7 = 5, so x \equiv 10 \equiv 3 \pmod{7}. Check: 24 \cdot 3 = 72 = 56 + 16.
13, 28 or 43 tickets. The condition is 12x \equiv 21 \pmod{45}. \gcd(12, 45) = 3 divides 21; dividing gives 4x \equiv 7 \pmod{15}, and 4 \cdot 4 = 16 \equiv 1, so x \equiv 28 \equiv 13 \pmod{15}. Below 50: 13, 28, 43. Check: 12 \cdot 13 = 156 = 3 \cdot 45 + 21.
The third watering, 18 days after the first; after that every 63 days. After k intervals the weekday is 1 + 9k \bmod 7, and Friday is 5, so 9k \equiv 4, that is 2k \equiv 4 \pmod{7}. Since 2^{-1} \bmod 7 = 4, k \equiv 16 \equiv 2 \pmod{7}.
Proof. Suppose ai and aj leave the same remainder, with 0 \le i, j \le n - 1. Then ai \equiv aj, and since a is a unit, Theorem 3 gives i \equiv j. Their difference is a multiple of n smaller than n in size, so i = j. \square
6x \equiv 4 \pmod{10}: d = 2 \mid 4, so it is equivalent to 3x \equiv 2 \pmod{5}, giving x \equiv 4 \pmod{5}, so x \equiv 4, 9 \pmod{10} (check: 24 and 54 end in 4). But 3x \equiv 2 \pmod{10} has the single solution x \equiv 7 \cdot 2 \equiv 4, since 3^{-1} \bmod 10 = 7; it misses 9, since 3 \cdot 9 = 27 \equiv 7. Halving the congruence must halve the modulus too.
Proof. Suppose ax \equiv b, so ax - b = kn for some integer k, and b = ax - kn. Since d \mid a and d \mid n, d divides this combination, so d \mid b. By contraposition, if d \nmid b there is no solution. \square
Every n with n \equiv 2 \pmod{4}, that is n = 2, 6, 10, 14, \dots. By Theorem 6 the count is d = \gcd(4, n) when d \mid 2 and 0 otherwise. d is 1, 2 or 4; d = 4 gives no solution and d = 1 gives one. Exactly two needs \gcd(4, n) = 2: n even but not a multiple of 4.