Exercises

2..

1. Prove that for any positive integer $n$ , the set $(\mathbb{Z}/n\mathbb{Z}{})^*$ under multiplication modulo $n$ is a group.
2. Compute the following gcd's using Algorithm 1.1.13:
   $$\gcd(15,35),\quad \gcd(247,299),\quad \gcd(51,897), \quad \gcd(136,304)$$

3. Use Algorithm 2.3.7 to find $x, y\in\mathbb{Z}$ such that $2261x + 1275y = 17$ .

4. Prove that if $a$ and $b$ are integers and $p$ is a prime, then $(a+b)^p \equiv a^p + b^p\pmod{p}$ . You may assume that the binomial coefficient
   $$\frac{p!}{r!(p-r)!}$$
   is an integer.

5. 1. Prove that if $x,y$ is a solution to $ax + by = d$ , then for all $c\in \mathbb {Z}$ ,

      $$x' = x+ c\cdot\frac{b}{d}, \qquad y' = y - c\cdot\frac{a}{d}$$ (2.6.1)

      
      
      is also a solution to $ax + by = d$ .
   2. Find two distinct solutions to $2261x + 1275y = 17$ .
   3. Prove that all solutions are of the form (2.6.1) for some $c$ .

6. Let $f(x)=x^2+ax+b \in\mathbb{Z}[x]$ be a quadratic polynomial with integer coefficients and positive leading coefficients, e.g., $f(x)=x^2+x+6$ . Formulate a conjecture about when the set $\{ f(n) : n\in \mathbb{Z}$ and $f(n)$ is prime$\}$ is infinite. Give numerical evidence that supports your conjecture.

7. Find four complete sets of residues modulo $7$ , where the $i$ th set satisfies the $i$ th condition: (1) nonnegative, (2) odd, (3) even, (4) prime.

8. Find rules in the spirit of Proposition 2.1.8 for divisibility of an integer by $5$ , $9$ , and $11$ , and prove each of these rules using arithmetic modulo a suitable $n$ .

9. (*)The following problem is from the 1998 Putnam Competition. Define a sequence of decimal integers $a_n$ as follows: $a_1 = 0$ , $a_2 = 1$ , and $a_{n+2}$ is obtained by writing the digits of $a_{n+1}$ immediately followed by those of $a_n$ . For example, $a_3 = 10$ , $a_4 = 101$ , and $a_5 = 10110$ . Determine the $n$ such that $a_n$ a multiple of $11$ , as follows:
   1. Find the smallest integer $n>1$ such that $a_n$ is divisible by $11$ .
   2. Prove that $a_n$ is divisible by $11$ if and only if $n\equiv 1\pmod{6}$ .

10. Find an integer $x$ such that $37x \equiv 1\pmod{101}$ .

11. What is the order of $2$ modulo $17$ ?

12. Let $p$ be a prime. Prove that $\mathbb{Z}/p\mathbb{Z}{}$ is a field.

13. Find an $x\in\mathbb{Z}$ such that $x \equiv -4 \pmod{17}$ and $x\equiv 3\pmod{23}$ .

14. Prove that if $n>4$ is composite then
    $$(n-1)! \equiv 0 \pmod{n}.$$

15. For what values of $n$ is $\varphi (n)$ odd?

16. 1. Prove that $\varphi$ is multiplicative as follows. Suppose $m,n$ are positive integers and $\gcd(m,n)=1$ . Show that the natural map $\psi:\mathbb{Z}/mn\mathbb{Z}{} \rightarrow \mathbb{Z}/m\mathbb{Z}{} \times \mathbb{Z}/n\mathbb{Z}{}$ is an injective homomorphism of rings, hence bijective by counting, then look at unit groups.
    2. Prove conversely that if $\gcd(m,n)>1$ then the natural map $\psi:\mathbb{Z}/mn\mathbb{Z}{} \rightarrow \mathbb{Z}/m\mathbb{Z}{} \times \mathbb{Z}/n\mathbb{Z}{}$ is not an isomorphism.

17. Seven competitive math students try to share a huge hoard of stolen math books equally between themselves. Unfortunately, six books are left over, and in the fight over them, one math student is expelled. The remaining six math students, still unable to share the math books equally since two are left over, again fight, and another is expelled. When the remaining five share the books, one book is left over, and it is only after yet another math student is expelled that an equal sharing is possible. What is the minimum number of books which allow this to happen?

18. Show that if $p$ is a positive integer such that both $p$ and $p^2+2$ are prime, then $p=3$ .

19. Let $\varphi :\mathbb{N}\rightarrow \mathbb{N}$ be the Euler $\varphi$ function.
    1. Find all natural numbers $n$ such that $\varphi (n)=1$ .
    2. Do there exist natural numbers $m$ and $n$ such that $\varphi (mn)\neq \varphi (m)\cdot \varphi (n)$ ?

20. Find a formula for $\varphi (n)$ directly in terms of the prime factorization of $n$ .

21. 1. Prove that if $\varphi :G\to H$ is a group homomorphism, then $\ker(\varphi )$ is a subgroup of $G$ .
    2. Prove that $\ker(\varphi )$ is normal, i.e., that if $a\in G$ and $b\in\ker(\varphi )$ , then $a^{-1} b a \in \ker(\varphi )$ .

22. Is the set $\mathbb{Z}/5\mathbb{Z}=\{0,1,2,3,4\}$ with binary operation multiplication modulo $5$ a group?

23. Find all four solutions to the equation
    $$x^2 - 1\equiv 0 \pmod{35}.$$

24. Prove that for any positive integer $n$ the fraction $(12n+1)/(30n+2)$ is in reduced form.

25. Suppose $a$ and $b$ are positive integers.
    1. Prove that $\gcd(2^a-1, 2^b-1) = 2^{\gcd(a,b)}-1.$
    2. Does it matter if $2$ is replaced by an arbitrary prime $p$ ?
    3. What if $2$ is replaced by an arbitrary positive integer $n$ ?

26. For every positive integer $b$ , show that there exists a positive integer $n$ such that the polynomial $x^2-1\in(\mathbb{Z}/n\mathbb{Z}{})[x]$ has at least $b$ roots.

27. 1. Prove that there is no primitive root modulo $2^n$ for any $n\geq 3$ .
    2. (*) Prove that $(\mathbb{Z}/2^n\mathbb{Z}{})^*$ is generated by $-1$ and $5$ .

28. Let $p$ be an odd prime.
    1. (*) Prove that there is a primitive root modulo $p^2$ . (Hint: Use that if $a, b$ have orders $n, m$ , with $\gcd(n,m)=1$ , then $ab$ has order $nm$ .)
    2. Prove that for any $n$ , there is a primitive root modulo $p^n$ .
    3. Explicitly find a primitive root modulo $125$ .

29. (*) In terms of the prime factorization of $n$ , characterize the integers $n$ such that there is a primitive root modulo $n$ .

30. Compute the last two digits of $3^{45}$ .

31. Find the integer $a$ such that $0\leq a < 113$ and
    $$102^{70}+1 \equiv a^{37}\pmod{113}.$$

32. Find the proportion of primes $p<1000$ such that $2$ is a primitive root modulo $p$ .

33. Find a prime $p$ such that the smallest primitive root modulo $p$ is $37$ .