# Math Help - Fermat's Theorm and Divisibility

1. ## Fermat's Theorm and Divisibility

I am trying to find n such that $3^{n} + 2^{n}$ is divisible by 13.

I am trying to let $n = 12x + r$ and $n = 12y + s$ which gives $3^{12x + r} + 2^{12y + s}$. But I end up running in circles and getting nowhere!

Any ideas?

2. $\begin{array}{rcll} 3^1 & \equiv & 3 & (\text{mod } 13) \\ 3^2 & \equiv & 9 & (\text{mod } 13) \\ 3^3 & \equiv & 1 & (\text{mod } 13) \\ 3^4 & \equiv & 3 & (\text{mod } 13) \\ & \vdots & & \end{array}$

And this cycle repeats. So we know the least residues of $3^n$ (mod 13) for all $n$ is 3, 9, or 1.

Since $a \equiv m \ (\text{mod } m)$ implies $m \mid a$, we have to find $n$ such that $2^n \equiv 10, 4, \ \text{or } 12 \ (\text{mod }13)$.

As it turns out, 2 is a primitive root modulo 13. So see for which $n \in [1, 12]$ such that $2^n \equiv 10, 4, \ \text{or } 12 \ (\text{mod }13)$.

See if you can figure it out from here.

3. great that worked! I just determined the reside system for $2^{n}$ and then checked for what values of n, their sum added appropriately!

Merci