Number theory: exercises

Grading

These are exercises for Number theory: course.

1. Discuss the interplay between long division and the division algorithm (Theorem 1.1).
2. Decide whether each of the following statements is true or false, and give a proof or a counterexample:
   1. $(a,b)=(a,c) => (a^2,b^2)=(a^2,c^2)$.
   2. $(a,b)=(a,c) => (a,b)=(a,b,c)$.
   3. $p|(a^2+b^2)$ and $p|(a^2+b^2) => p|(a^2+c^2)$.
3. Show that the sum of two reduced fractions a/b and c/d is not an integer unless b=d.
4. Show that if $(a,b)=1$ then $(a-b,a+b)=1$ or $2$.
5. Solve: $19x+20y=1909$ for $x>0,y>0$.
6. Prove that the Diophantine equation $ax+by+cz=d$ is solvable in the integers if and only if $gcd(a,b,c)$ divides $d$.
7. Is the difference of two consecutive cubes divisible by 2?
8. For $n>3$, show that the integers $n, n+2, n+4$ cannot be all prime.
9. If $p>2$ and $p^2+8$ are both prime numbers, prove that $p^3+4$ is also prime.
10. Suppose $n|((n-1)!+1)$ and $n>1$. Show that $n$ is prime.
11. Solve $9x=21(\mod 30)$.
12. Show that any composite three-digit number must have a prime factor less than or equal to 31.
13. Prove that $53^{103}+103^{53}$ is divisible by $39$.
14. Show that if a is an odd integer, then for all $n>0$, $a^{2^n}=1(\mod 2^{n+2})$.
15. A certain integer between 1 and 1200 leaves the remainders $1,2,6$ when divided by $9,11,13$, respectively. Find the integer.
16. Suppose $p$ and $q$ are distinct primes and $a^p=a(\mod q),a^q=a(\mod p)$. Show that $a^{pq}=a(\mod pq)$.
17. Show that for any integer $n>0$, $13|11^{12n+6}+1$.
18. Suppose $f$ is a polynomial of degree n. Show that if the values f(a) for n+1 consecutive integers a are all divisible by p, then $p|f(a)$ for all $a$ in $Z$.
19. Find all the solutions of $x^3-3x^2+27=0(\mod 1125)$.
20. Prove that for $1<k<p-1$, $(p-k)!(k-1)!=(-1)^k(\mod p)$.
21. Code and decode the message NO WAY in RSA with $p=29,q=53,k=47$.
22. If every prime that divides $n$ also divides $m$, establish that $\phi (nm)=\phi (m)n$.
23. Let a be a primitive root mod p, an odd prime. Show that $-a$ is a primitive root $mod p$ iff $p=1 \mod 4$.
24. For what primes $p$ is $a^{17}=a \mod p$ for all $a$?
25. Find all the primitive roots mod $37,29,81,26$.
26. Deduce the Chinese Remainder Theorem from Theorem 6.13.