This site is being phased out.

# Number theory: exercises

From Mathematics Is A Science

Jump to navigationJump to searchThese are exercises for Number theory: course.

- Discuss the interplay between long division and the division algorithm (Theorem 1.1).
- Decide whether each of the following statements is true or false, and give a proof or a counterexample:
- $(a,b)=(a,c) => (a^2,b^2)=(a^2,c^2)$.
- $(a,b)=(a,c) => (a,b)=(a,b,c)$.
- $p|(a^2+b^2)$ and $p|(a^2+b^2) => p|(a^2+c^2)$.

- Show that the sum of two reduced fractions a/b and c/d is not an integer unless b=d.
- Show that if $(a,b)=1$ then $(a-b,a+b)=1$ or $2$.
- Solve: $19x+20y=1909$ for $x>0,y>0$.
- Prove that the Diophantine equation $ax+by+cz=d$ is solvable in the integers if and only if $gcd(a,b,c)$ divides $d$.
- Is the difference of two consecutive cubes divisible by 2?
- For $n>3$, show that the integers $n, n+2, n+4$ cannot be all prime.
- If $p>2$ and $p^2+8$ are both prime numbers, prove that $p^3+4$ is also prime.
- Suppose $n|((n-1)!+1)$ and $n>1$. Show that $n$ is prime.
- Solve $9x=21(\mod 30)$.
- Show that any composite three-digit number must have a prime factor less than or equal to 31.
- Prove that $53^{103}+103^{53}$ is divisible by $39$.
- Show that if a is an odd integer, then for all $n>0$, $a^{2^n}=1(\mod 2^{n+2})$.
- A certain integer between 1 and 1200 leaves the remainders $1,2,6$ when divided by $9,11,13$, respectively. Find the integer.
- 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)$.
- Show that for any integer $n>0$, $13|11^{12n+6}+1$.
- 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$.
- Find all the solutions of $x^3-3x^2+27=0(\mod 1125)$.
- Prove that for $1<k<p-1$, $(p-k)!(k-1)!=(-1)^k(\mod p)$.
- Code and decode the message NO WAY in RSA with $p=29,q=53,k=47$.
- If every prime that divides $n$ also divides $m$, establish that $\phi (nm)=\phi (m)n$.
- 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$.
- For what primes $p$ is $a^{17}=a \mod p$ for all $a$?
- Find all the primitive roots mod $37,29,81,26$.
- Deduce the Chinese Remainder Theorem from Theorem 6.13.