Irish Mathematical Olympiad

a) Unless otherwise specified, everywhere in part a), $\equiv$ will denote congruence modulo $49$. Consider the six cases $a = 7k \pm 1$, $7k \pm 2$ and $7k \pm 3$.

1. If $a = 7k + 1$, with $k \in \{0, 1, ..., 6\}$, then $a^n = 7kn + 1$, so $a^n \equiv 1 \pmod{7}$
$k = 0$ or $n$ is a multiple of $7$. Thus $1 \in A_1$ and $7k + 1 \in A_7$ for $k \in \{1, ..., 6\}$.

2. If $a = 7k - 1$, with $k \in \{1, ..., 7\}$, then $a^n = (-1)^{n-1}(7kn - 1)$. If $n$ is odd, then $a^n \equiv 1 \pmod{7kn} \equiv 2$ which cannot hold as $7 \nmid 2$. If $n$ is even, then $a^n \equiv 1 \pmod{7kn} \equiv 0$ which holds when $k = 7$ or $n$ is a multiple of $14$.
Thus $a = 48 \in A_2$ and $7k - 1 \in A_{14}$ for $k \in \{1, ..., 6\}$.

3. If $a = 7k + 2$, with $k \in \{0, 1, ..., 6\}$, then $a^n = 2^{n-1}7kn + 2^n$, so
$$a^n \equiv 1 \pmod{2^{n-1}7kn + 49l} \equiv 1 - 2^n \text{ for some integer } l.$$
This implies in a first instance that $7|(1 - 2^n)$, i.e. $n = 3m$ for some integer $m$. Then
$$\frac{1 - 2^n}{7} = \frac{1 - 2^{3m}}{7} = \frac{(1 - 2^3)(1 + 2^3 + \dots + (2^3)^{m-1})}{7} = -m \pmod{7}$$
$$\text{and } 2^{n-1} \equiv 2^{3m-1} \equiv 4 \pmod{7}.$$
Therefore, if $n = 3m$ and $k = 4$, there exists an integer $l$ such that
$$2^{n-1}kn + 7l = \frac{1 - 2^n}{7}.$$
This implies $a = 30 \in A_3$. Moreover, when $7 \nmid n$, then any two solutions $k$ and $k'$ of the equation above differ by a multiple of $7$. On the other hand, if $7|n$, any value of $k$ is a solution, so $a = 7k + 2 \in A_{21}$ for $k \in \{0, ..., 6\} \setminus \{4\}$.

4. If $a = 7k - 2$, with $k \in \{1, \dots, 7\}$, then $a^n = (-2)^{n-1}(7kn - 2)$. If $n$ is odd, then $a^n = 1 \iff 2^{n-1}7kn = 2^n + 1$ which implies that $7|(1+2^n)$. A short check of the possible values of $1+2^n$ modulo $7$ shows that this is not possible. If $n$ is even, then $a^n = 1 \iff -2^{n-1}7kn + 49l = 1-2^n$ for some integer $l$. Similarly to the previous case, this implies $a = 7 \cdot 3 - 2 = 19 \in A_6$ and $a = 7k - 2 \in A_{42}$ for $k \in \{0, \dots, 6\} \setminus \{3\}$.

5. If $a = 7k + 3$, with $k \in \{0, 1, \dots, 6\}$, then $a^n = 3^{n-1}7kn + 3^n$, so $a^n = 1 \iff 3^{n-1}7kn + 49l = 1 - 3^n$ for some integer $l$. This implies that $7|(1-3^n)$, i.e. $n = 6m$ for some integer $m$. Then
$$\frac{1-3^n}{7} = \frac{1-3^{6m}}{7} = \frac{(1-3^6)(1+3^6+\dots+(3^6)^{m-1})}{7} \equiv m \quad \mod 7 \\ \text{and } 3^{n-1} \equiv 5 \quad \mod 7$$
Therefore, if $n = 6m$ and $k = 4$, there exists an integer $l$ such that the equation
$$3^{n-1}kn + 7l = \frac{1-3^n}{7}$$
holds, so $a = 31 \in A_6$. As in the previous cases, $a = 7k + 3 \in A_{42}$ for $k \in \{0, \dots, 6\} \setminus \{4\}$.

6. If $a = 7k - 3$, with $k \in \{1, \dots, 7\}$, then $a^n = (-3)^{n-1}(7kn - 2)$. If $n$ is odd, then $a^n = 1 \iff 3^{n-1}7kn = 3^n + 1$ which implies that $7|(1+3^n)$. A short check of the possible values of $1+3^n$ modulo $7$ shows that this is equivalent to $n = 6m + 3$ and then $a^n = 1 \iff 3^{n-1}kn = \frac{3^{n+1}}{7}$, where the right hand side becomes
$$\frac{1+3^{3(2m+1)}}{7} = \frac{(1+3^3)(1-3^3+\dots+(3^3)^{2m})}{7} \equiv 4(2m+1) \quad \mod 7,$$
$a^n = 1$ becomes $3^{6m+3}k(2m+1) = 4(2m+1) \pmod 7$, equivalently $6k(2m+1) = 4(2m+1) \pmod 7$, which holds for all $m$ when $k=3$, and for all $k$ when $(2m+1) \equiv 0 \pmod 7$. Thus $a = 7 \cdot 3 - 3 = 18 \in A_3$ while $a = 7k - 3 \in A_{21}$ for $k \in \{1, \dots, 7\} \setminus \{3\}$. If $n$ is even, then $a^n = 1 \iff -3^{n-1}7kn + 49l = 1 - 3^n$ for some integer $l$. Similarly to the previous case, this implies $a^6 = 1$ for $a = 7 \cdot 3 - 2 = 18$ and $a^{42} = 1$ for $a = 7k - 2$ and $k \in \{0, \dots, 6\} \setminus \{3\}$, which was already known from the case of $n$ odd.

b) $2009 = 49 \cdot 41$. From a) it follows that $49$ divides $a^{42} - 1$ for all integers $a$ relatively prime to $49$. From Fermat's theorem, $41$ divides $a^{40} - 1$ for all integers $a$ relatively prime to $41$. The least common multiple of $40$ and $42$ is $840$ and thus $2009$ divides $a^{840} - 1$ for all integers $a$ relatively prime to $2009$. It now suffices to find an integer $a$ such that $2009|(a^n - 1) \Leftrightarrow 840|n$. It is natural to try $a \in A_{42} = \{3, 5, 10, 12, 17, 24, 26, 33, 38, 40, 45\}$. Modulo $41$, we have $3^8 \equiv 1$, $5^{20} \equiv 1$ and $10^5 \equiv 1$, but $n = 40$ is the least power such that $12^n \equiv 1$, so $n = 840$ is indeed the least power such that $2009|(12^n - 1)$.