# $5^{2012}+1$ is divisible with $313$

Prove that: $\displaystyle5^{2012}+1$ is divisible with $313$.

What I try and what I know:

$313$ is prime and I try use the following formula :

$$a^n+b^n=(a+b)(a^{n-1}-a^{n-2}b+\ldots\pm(-1)^{n}b^{n-1})$$

but still nothing. this problem can be solved using a elementary proof because I found it a mathematical magazine for children with the age of 14.

-
Note that the formula that you are trying to use is for odd n –  Amr Dec 7 '12 at 11:36

$5^4=625\equiv -1\pmod {313}$ as $626=2\cdot313$

So, $5^{2012}=(5^4)^{503}\equiv (-1)^{503}\pmod {313}\equiv-1$

Alternatively, $5^4=625=313\cdot2-1$

So, $5^{2012}=(5^4)^{503}=(313\cdot2-1)^{503}=(313\cdot2)^{513}+\binom {513}1(313\cdot2)^{512}(-1)^1+\cdots+\binom {513}{512}(313\cdot2)(-1)^{512}-1$

Observe that all the except the last is divisible by $313$

So, the remainder i.e., $5^{2012} \mod {313}$ is $-1$

-
can you give me another solution without using $mod$? thaks, and thanks for the proof . –  Iuli Dec 7 '12 at 11:24
@Iuli, please find the edited answer and share your queries, if any . –  lab bhattacharjee Dec 7 '12 at 11:37
it is ok :) thanks :) –  Iuli Dec 7 '12 at 11:40
@Iuli: Asking for an argument about divisibility without using modulus is like asking for a salad without any vegetables. –  Henning Makholm Dec 7 '12 at 12:57
@HenningMakholm I'm totally agree with you, but this problem must be done by a child who didn't learn anything about $mod$. –  Iuli Dec 7 '12 at 15:18

$$\frac {5^{2012} + 1}{626} =\frac {5^{2012} + 1}{5^{4} + 1 } = \frac {(5^{4})^{503} + 1}{(5^{4}) + 1 } = \frac {a^{n} + b ^n }{a+b}$$

Where $a = 5^4 and\$ $b =1 \ and\$ $n=503 (odd)$

## Concept : ${a^{n} + b ^n }$ is always a multiple of $a+b\$ when n is odd

.

so this division gives remainder $0$.

As $626 = 313 *2$ It should also be divisible by 313 .

hence $\frac {5^{2012} + 1}{313}$ gives remainder $0$.

so its divisible by 313 .

Hence proved

-
+1 This is the cleanest answer. –  Sawarnik Feb 24 at 10:01

$5^{2012}+1=(5^4)^{503}-(-1)^{503}$, thus $5^4-(-1)|5^{20212}+1$ Finally we note that $313|5^4-(-1)$. This is because $5^4-(-1)=626=2(313)$

-

Just use the fact that $a+b$ divides $a^n+b^n$, if $n$ is odd.

Here $5^4+1=626$ divides $(5^4)^{503}+1^{503}=5^{2012}+1$.

-