NTIC Exercises

🔗

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

🔗

4.

Repeat Exercise 4.7.3, but with $6^{25}$ (mod $11$ ).

🔗

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

🔗

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\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{.}$