Skip to main content
\( \newcommand{\lt}{ < } \newcommand{\gt}{ > } \newcommand{\amp}{ & } \)

Section5.6Exercises

1

Why do the latter two strategies in Fact 5.2.1 need no additional proof?

3

We found solutions to \(ax\equiv b\) (mod \(n\)) as congruence classes modulo \(n\). But since \(\gcd(a,n)=d\) is important here, it could be worth talking about how many congruence classes modulo \(n/d\) we have. Well, how many do we get? (If this sounds confusing, pick a specific problem and try it, then see if you get the same answer in general.)

4

Write down two linear congruences which do not have solutions modulo \(15\), but do have solutions modulo \(16\). (You do not have to solve them.)

5

We know that \(b\equiv c\) (mod \(n\)) implies \(ab\equiv ac\) (mod \(n\)) as well. Prove that the converse is true if \(\gcd(a,n)=1\), and give a counterexample where the converse fails if \(\gcd(a,n)\neq 1\).

6

For each of the following linear congruences, find all of its solutions.

  1. \(18x\equiv 42\) (mod \(50\))

  2. \(15x\equiv 9\) (mod \(25\))

  3. \(6x\equiv 3\) (mod \(9\))

  4. \(980x\equiv 1540\) (mod \(1600\))

7

Solve the simultaneous system below. ([C.1.1], Exercise 3.8)

  • \(x\equiv 1\) (mod \(4\))

  • \(x\equiv 2\) (mod \(3\))

  • \(x\equiv 3\) (mod \(5\))

8

Find an integer that leaves a remainder of 9 when it is divided by either 10 or 11, but that is divisible by 13.

9

When eggs in a basket are removed two, three, four, five, or six at a time, there remain, respectively, one, two, three, four, or five eggs. When they are taken out seven at a time, none are left over. Find the smallest number of eggs that could have been contained in the basket. (Brahmagupta, 7th century AD)

10

Find a problem on the internet about pirates quarreling over treasure (or monkeys over bananas) that could be solved using the CRT, and solve it.

11

Solve the system \(4x\equiv 2\) (mod \(6\)), \(3x\equiv 5\) (mod \(7\)), \(2x\equiv 4\) (mod \(11\)).

12

Solve the congruence \(5x\equiv 22\) (mod \(84\)).

13

Solve the simultaneous system \(x\equiv 4\) (mod \(6\)), \(x\equiv 7\) (mod \(15\)). Note that this doesn't fit our pattern, but you should still be able to solve this, since there are only two. (Hint: trial and error.)