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

Section4.7Exercises

1

Give the least absolute residues and the least nonnegative residues for \(n=21\).

2

Prove that 13 divides \(145^6+1\) and 431 divides \(2^{43}-1\) without a computer (but definitely using congruence).

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\), so it shouldn't be too traumatic.)

4

Use the properties of congruence (in Proposition 4.3.1) or the definition to show that if \(a\equiv b\) (mod \(n\)), then \(a^3\equiv b^3\) (mod \(n\)).

5

Use the properties of congruence (in Proposition 4.3.1, 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\).

6

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

8

Find and prove what the possible last decimal digits are for a perfect square.

9

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\), and consider each part modulo 3.)

10

Prove that if the sum of digits of a number is divisible by 9, then so is the number.

11

For which positive integers \(m\) is \(27\equiv 5\) (mod \(m\))?

12

Complete the proof that having the same remainder when divided by \(n\) is the same as being congruent modulo \(n\).

13

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,1\). Then try to find an example where they are not equal.

14

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]\).