Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
4  
Note that the formula that you are trying to use is for odd n –  Amr Dec 7 '12 at 11:36

4 Answers 4

up vote 10 down vote accepted

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

share|improve this answer
    
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
3  
@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

share|improve this answer
1  
+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)$

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.