Exercises 4.7 Exercises
1.
Give the sets of least absolute residues and least nonnegative residues for n=21.
2.
Prove that 13 divides 1456+1 and 431 divides 243β1 without a computer (but definitely using congruence).
It is definitely worth while gaining intuition for modular manipulation by doing a bunch of examples.
3.
Compute 743 (mod 11) as in Subsection 4.5.2 without using Sage or anything that can actually do modular arithmetic. (You should never have to compute a number bigger than (11β1)2=100, so it shouldn't be too traumatic.)
4.
Repeat Exercise 4.7.3, but with 625 (mod 11).
5.
Repeat Exercise 4.7.3, but with 625 (mod 12). Why is this one easier?
6.
Make up an exercise like Exercise 4.7.3 and dare a friend in class to solve it. (Make sure you can solve it before doing so!)
7.
Use the properties of congruence (in Proposition 4.3.2) or the definition to show that if aβ‘b (mod n), then a3β‘b3 (mod n).
8.
Use the properties of congruence (in Proposition 4.3.2, not the definition) and induction to show that if aβ‘b (mod n), then amβ‘bm (mod n) for any positive m.
9.
Finish the details of proving Proposition 4.3.1, especially the second part (symmetric).
10.
Finish the details of proving Proposition 4.3.2.
11.
Find and prove what the possible last decimal digits are for a perfect square.
12.
Prove that if the sum of digits of a number is divisible by 3, then so is the number. (Hint: Write 225 as 2β 102+2β 10+5, and consider each part modulo 3.)
13.
Prove that if the sum of digits of a number is divisible by 9, then so is the number.
14.
For which positive integers m is 27β‘5 (mod m)?
15.
Complete the proof of Lemma 4.1.2 that having the same remainder when divided by n is the same as being congruent modulo n.
Consider Example 4.5.4 in these three extensions.
16.
Find some a and n such that an (mod 5) equals an+5 (mod 5), where aβ 0,1 and nβ 0.
17.
Try to find some a and n such that an (mod 5) equals an+5 (mod 5), where aβ’ and n\neq 0\text{.}
18.
Find some a and n such that a^n (mod 6) equals a^{n+6} (mod 6), where a\not\equiv 0,1 and n\neq 0\text{.} Then try to find an example where they are not equal.
19.
Explore, using the interact after Question 4.6.7 or βby handβ, for exactly which moduli n the only solutions to x^2\equiv x (mod n) are x=[0] and x=[1]\text{.}