Problems

Some of these problems expand on ideas presented in the theory above; others are purely recreational. None are intended to be completely trivial, though they are arranged roughly in order of difficulty. Enjoy!

1. Let $p$ be a fixed odd prime. An infinite square grid has an integer written in each square so that each number is the average of the number below it and the number to its right, and such that any two squares of the same column $p$ squares apart contain numbers which are congruent modulo $p$. Show that any two squares of the same row $p$ squares apart contain numbers congruent modulo $p$.
2. (Turkey, 1995) Given a positive integer $n$, prove that the following are equivalent:

   (a)

   For any positive integer $a$, $n\ \vert\ a^n - a$;

   (b)

   For any prime divisor $p$ of $n$, $p^2$ does not divide $n$, and $p-1\ \vert\ n-1$.

3. (Balkan Olympiad, 1999) Let $p > 2$ be a prime number such that $3\ \vert\ p-2$. Let
   $$S = \{y^2 - x^3 - 1\ \vert\ x, y \in{\mathbb{Z}}, 0 \leq x, y \leq p-1\}.$$
   Prove that at most $p-1$ elements of $S$ are divisible by $p$.
4. (Bulgaria, 1996) Find all prime numbers $p, q$ such that $pq\ \vert\ (5^p-2^p)(5^q-2^q)$.
5. (Germany, 1997) Define the functions
   $$f(x) = x^5 + 5x^4 + 5x^3 + 5x^2 + 1,$$
   $$g(x) = x^5 + 5x^4 + 3x^3 - 5x^2 - 1.$$
   Find all prime numbers $p$ for which there exists an integer $x, 0 \leq x < p$, such that both $f(x)$ and $g(x)$ are divisible by $p$, and for each such $p$, find all such $x$.
6. Prove that every finite field contains a subfield isomorphic to ${\mathbb{F}}_p$ for some $p$ -- that is, a subfield that becomes ${\mathbb{F}}_p$ upon relabeling of its elements.
7. Let $p$ be an odd prime, and let $k, n \in \{1,2,\ldots,p-2\}$. Consider the set $S = \{1,2,\ldots,n\} \subseteq {\mathbb{F}}_p$. If $ka \in S$ for all $a \in S$, prove that $k = 1$.
8. Given an odd prime $p$, how many of the integers $i = 0,1,2,\ldots,p-1$ have the property that both $i$ and $i-1$ are quadratic residues modulo $p$?
9. (from Ireland & Rosen)

   (a)

   Suppose $p > 3$ is a Fermat prime, i.e. $p-1$ is a power of $2$. Show that $3$ is a primitive root modulo $p$.

   (b)

   Suppose $p$ is a prime, $p \equiv 3 \pmod{8}$, and further suppose $(p-1)/2$ is also a prime. Show that $2$ is a primitive root modulo $p$.

10. Prove two generalizations of Fermat's Little Theorem:

    (a)

    (Euler's Theorem) If $a, n$ are two relatively prime natural numbers, $a^{\phi(n)} \equiv 1 \pmod{n}$.

    (b)

    In a $q$-element field, $x^q = x$ for all $x$.

11. (Turkey, 1997) Prove that, for each prime $p \geq 7$, there exists a positive integer $n$ and integers $x_1,\ldots,x_n,y_1,\ldots,y_n$ not divisible by $p$, such that
    

    $$x_1^2 + y_1^2 \equiv x_2^2 \pmod{p},$$

    $$x_2^2 + y_2^2 \equiv x_3^2 \pmod{p},$$

    $$\vdots$$

    $$x_n^2 + y_n^2 \equiv x_1^2 \pmod{p}.$$

    
    

12. (Putnam, 1987) Suppose $p$ is an odd prime. Let $F$ be the set of ordered pairs of elements of ${\mathbb{F}}_p$, not both equal to zero, and let $S$ be a subset of $F$ with the property that whenever $(a,b)\in F$, exactly one of $(a,b)$ and $(-a,-b)$ is in $S$. Let $N$ be the number of elements in the intersection $S \cap \{(2a,2b)\ \vert\ (a,b) \in S\}$. Prove that $N$ is even.
13. (from Ireland & Rosen) Given $p$, compute the sum of all the primitive roots in ${\mathbb{F}}_p$. (Your answer will depend on $p$.)
14. (American Mathematical Monthly, 1999) Let $p$ be a prime number with $p \equiv 7 \pmod{8}$, and let $L_p = \{1,2,\ldots,(p-1)/2\}$. Prove that the sum of the quadratic residues (i.e. the squares) modulo $p$ in $L_p$ equals the sum of the quadratic nonresidues modulo $p$ in $L_p$. (The sums are taken in ${\mathbb{Z}}$, not in ${\mathbb{F}}_p$.)
15. (American Mathematical Monthly, 2001) Given a prime $p \equiv 7 \pmod{8}$, evaluate
    $$\sum_{k=1}^{(p-1)/2} \left\lfloor \frac{k^2}{p} + \frac{1}{2} \right\rfloor.$$

16. Let $p$ be an odd prime and $n$ a positive integer. Show the existence of primitive roots modulo $p^n$ -- that is, there exists some $a$ such that every integer not divisible by $p$ is congruent to some power of $a$ modulo $p^n$. What happens when $p = 2$?
17. (Putnam, 1996) If $p > 3$ is a prime and $k = \lfloor 2p/3 \rfloor$, prove that the sum
    $${p\choose 1} + {p\choose 2} + \cdots + {p\choose k}$$
    of binomial coefficients is divisible by $p^2$.
18. (Poland, 1995) Let $p \geq 3$ be a given prime. Define a sequence $(a_n)$ by $a_n = n$ for $n = 0,1,2,\ldots,p-1$, and $a_n = a_{n-1} + a_{n-p}$ for $n \geq p$. Determine the remainder when $a_{p^3}$ is divided by $p$.
19. (MOP 1999) Let $p$ be a prime, $d$ a positive integer, and $n$ any integer. Prove that one can find $d$ or fewer $d$th powers whose sum is congruent to $n \pmod{p}$.
20. (American Mathematical Monthly, 1999) Let $p$ be an odd prime. Prove that
    $$\sum_{i=1}^{p-1} 2^i\cdot i^{p-2} \equiv \sum_{i=1}^{(p-1)/2} i^{p-2} \pmod{p}.$$

21. (Oaz Nir, MOP 2000) Prove that ${qp\choose p} \equiv q \pmod{p^3}$, where $p$ is a prime greater than $5$.
22. (IMO, 1999) Find all pairs $(n,p)$ of positive integers such that
    • $p$ is prime;
    • $n \leq 2p$;
    • $(p-1)^n + 1$ is divisible by $n^{p-1}$.
23. (American Mathematical Monthly, 1999) Let $p \geq 5$ be prime, and let $n$ be an integer such that $(p+1)/2 \leq n \leq p-2$. Let $R = \sum (-1)^i {n\choose i}$, where the sum is taken over all $i \in \{0,1,\ldots,n-1\}$ such that $i+1$ is a quadratic residue modulo $p$, and let $N = \sum (-1)^j {n\choose j}$, where the sum is taken over all $j \in \{0,1,\ldots,n-1\}$ such that $j+1$ is a quadratic nonresidue modulo $p$. Prove that exactly one of $R$ and $N$ is divisible by $p$.
24. (IMO, 1990) Determine all positive integers $n$ such that $(2^n+1)/n^2$ is an integer.
25. (USAMO, 1999) Let $p > 2$ be a prime, and let $a, b, c, d$ be integers not divisible by $p$, such that
    $$\{ra/p\} + \{rb/p\} + \{rc/p\} + \{rd/p\} = 2$$
    for any integer $r$ not divisible by $p$. Prove that at least two of the numbers $a+b, a+c,a+d,b+c,b+d,c+d$ are divisible by $p$. (Note: $\{x\} = x - \lfloor x \rfloor$ denotes the fractional part of $x$.)