Find non-negative integers $n$ such that $9^n + 1$ is divisible by 365 For which non-negative integers $n$ is $9^n + 1$ is divisible by 365?
First approach:
$365 = 5 * 73 \implies 9^n + 1 \equiv (-1)^n + 1 \equiv 0 \; \text{(mod 5)} \Leftrightarrow n = 2k + 1$
So $n$ must be odd. Thus $9^{2k+1} + 1 \equiv 0 \; \text{(mod 73)}$
Unfortunately checking all residues (mod 73) isn‘t an option… How would you proceed from this/is there a better approach?

You can note that $9\cdot 8 = 72 \equiv -1 \pmod{73}.$ So you know that $-8$ is the inverse of $9 \pmod{73}$.  Then notice that $9^2 = 81 \equiv 8 \pmod{73}.$ So $-9^2$ is the inverse of $9 \pmod{73}$.  Therefore $9^3\equiv -1 \pmod{73}$ and $9^6 \equiv 1 \pmod{73}.$  Then $9^{6k+3} \equiv -1 \pmod{73}.$
