Number Theory: In Context and Interactive

1.

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

2.

Complete the outline of the proof of Proposition 5.2.7, including “the direction when we assume $a\equiv b$”.

3.

Solve one or both of the congruences in Example 5.2.4.

4.

In Proposition 5.1.1 and Proposition 5.1.3, we found solutions to $ax\equiv b$ (mod $n$) in the form of congruence classes modulo $n\text{.}$ But since $\gcd(a,n)=d$ is so important here, it could be worth asking about congruence classes modulo $n/d$ instead.

Well, for a general congruence $ax\equiv b$ (mod $n$), how many congruence classes (mod $n/d$) do we get? Prove it. (A good approach is to pick a specific problem and try it, then see if you get the same answer in general.)

5.

Answer the questions in Question 5.3.6.

6.

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

7.

Come up with a counterexample to Proposition 5.2.7 when $\gcd(a,n)\neq 1\text{.}$

14.

Solve the simultaneous system below. ([E.2.1, Exercise 3.8])

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

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

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

15.

Solve the simultaneous system below.

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

• $x\equiv 4$ (mod $5$)

• $x\equiv 6$ (mod $13$)

16.

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

17.

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)

18.

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.

19.

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

20.

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

21.

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 congruences. (Hint: trial and error.)