NTIC Exercises

🔗

Exercises 5.6 Exercises

🔗

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 $a x \equiv b$ (mod $n$ ) in the form of congruence classes modulo $n .$ 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 $a x \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 modulo $n$ which do not have solutions when $n = 15,$ but do have solutions when $n = 16 .$ (You do not have to solve them, but should explain how you know they do or do not have solutions.)

🔗

7.

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

🔗

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

🔗

8.

$15 x \equiv 9$ (mod $25$ )

🔗

9.

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

🔗

10.

$14 x \equiv 42$ (mod $50$ )

🔗

11.

$15 x \equiv 42$ (mod $50$ )

🔗

12.

$13 x \equiv 42$ (mod $50$ )

🔗

13.

$980 x \equiv 1540$ (mod $1600$ )

🔗

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 – and many other variations in other cultures)

🔗

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 $4 x \equiv 2$ (mod $6$ ), $3 x \equiv 5$ (mod $7$ ), $2 x \equiv 4$ (mod $11$ ).

🔗

20.

Solve the congruence $5 x \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.)

🔗

22.

Solve Master Sun's only such problem: $x \equiv 2$ (mod $3$ ), $x \equiv 3$ (mod $5$ ), $x \equiv 2$ (mod $7$ ). (This same problem shows up again in Fibonacci's Liber Abaci.)

🔗

23.

Solve one of Qin's problems (adapted from [E.5.10, Chapter 22]). Does it seem any more realistic than any ‘word problems’ you did in high school?

Thieves have stolen rice, measured in ge (today, about 100 milliliters), from three identical full containers. The first thief stole all but one ge from the first container with a ladle containing 19 ge; the second one left fourteen ge after stealing with a shoe which could hold 17 ge; the third left only one ge, using a bowl which held 12 ge. How much rice was lost, and how much did each thief take?