7
$\begingroup$

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.

  • 4
    Note that the formula that you are trying to use is for odd n2012-12-07

4 Answers 4

10

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

  • 0
    @HenningMakholm I'm totally agree with you, but this problem must be done by a child who didn't learn anything about $mod$.2012-12-07
3

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

$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)$

0

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