Fermat's Theorm and Divisibility

**apsis** · November 18th 2008, 09:05 PM

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?

**o_O** · November 18th 2008, 09:53 PM

$\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.

**apsis** · November 19th 2008, 05:19 AM

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

Thread: Fermat's Theorm and Divisibility

LinkBack

Thread Tools

Display

Fermat's Theorm and Divisibility

Similar Math Help Forum Discussions

factor theorm

Rolles Theorm

Can someone help me with the Chebyshev's Theorm?

Help with Chebyshev's theorm!

Residue Theorm - Q1

Search Tags