Skip to main content

Exercises 4.7 Exercises

1.

Give the sets of least absolute residues and least nonnegative residues for \(n=21\text{.}\)

2.

Prove that 13 divides \(145^6+1\) and 431 divides \(2^{43}-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 \(7^{43}\) (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\text{,}\) so it shouldn't be too traumatic.)

5.

Repeat Exercise 4.7.3, but with \(6^{25}\) (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\equiv b\) (mod \(n\)), then \(a^3\equiv b^3\) (mod \(n\)).

8.

Use the properties of congruence (in Proposition 4.3.2, not the definition) and induction to show that if \(a\equiv b\) (mod \(n\)), then \(a^m\equiv b^m\) (mod \(n\)) for any positive \(m\text{.}\)

9.

Finish the details of proving Proposition 4.3.1, especially the second part (symmetric).

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\cdot10^2+2\cdot 10+5\text{,}\) 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\equiv 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\text{.}\)

Consider Example 4.5.4 in these three extensions.

16.

Find some \(a\) and \(n\) such that \(a^n\) (mod \(5\)) equals \(a^{n+5}\) (mod \(5\)), where \(a\neq 0,1\) and \(n\neq 0\text{.}\)

17.

Try to find some \(a\) and \(n\) such that \(a^n\) (mod \(5\)) equals \(a^{n+5}\) (mod \(5\)), where \(a\not\equiv 0,1\) 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{.}\)