Irska

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(\mathrm{mod}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(\mathrm{mod}7kn)\equiv 2$ which cannot hold as $7\nmid 2$. If $n$ is even, then $a^n\equiv 1(\mathrm{mod}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(\mathrm{mod}{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+\cdots +(2^3{)}^{m-1})}{7}=-m(\mathrm{mod}7)$$ $$\text{and }{2}^{n-1}\equiv 2^{3m-1}\equiv 4(\mathrm{mod}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^{\prime }$ 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⟺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⟺-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⟺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 $$\begin{gathered} \frac{1-3^n}{7}=\frac{1-3^{6m}}{7}=\frac{(1-3^6)(1+3^6+\cdots +(3^6{)}^{m-1})}{7}\equiv m\mathrm{mod}7 \\ \text{and }{3}^{n-1}\equiv 5\mathrm{mod}7 \end{gathered}$$ 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⟺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⟺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+\cdots +(3^3{)}^{2m})}{7}\equiv 4(2m+1)\mathrm{mod}7,$$ $a^n=1$ becomes $3^{6m+3}k(2m+1)=4(2m+1)(\mathrm{mod}7)$, equivalently $6k(2m+1)=4(2m+1)(\mathrm{mod}7)$, which holds for all $m$ when $k=3$, and for all $k$ when $(2m+1)\equiv 0(\mathrm{mod}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⟺-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)\iff 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)$.