# Thread: Fermat's Theorm and Divisibility

1. ## Fermat's Theorm and Divisibility

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

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

Any ideas?

2. $\displaystyle \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 $\displaystyle 3^n$ (mod 13) for all $\displaystyle n$ is 3, 9, or 1.

Since $\displaystyle a \equiv m \ (\text{mod } m)$ implies $\displaystyle m \mid a$, we have to find $\displaystyle n$ such that $\displaystyle 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 $\displaystyle n \in [1, 12]$ such that $\displaystyle 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 $\displaystyle 2^{n}$ and then checked for what values of n, their sum added appropriately!

Merci