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.

Tell me hint for solve :

1) $ 2222^{5555}+5555^{2222} \equiv \mathord? \pmod 7$

2) $ 9^{2n+1}+8^{n+2} \equiv \mathord ?\pmod{73}$

thank you.

share|improve this question
1  
Note that for a prime $p$, you have $a^{p-1} \equiv 1\pmod p$ for every $a$ with $\gcd(a,p) = 1$, by Euler. So, as $5555 \equiv 5 \pmod 6$ and $2222 \equiv 3 \pmod 7$, we have $2222^{5555} \equiv 3^5 \pmod 7$. Can you continue? –  martini Nov 29 '12 at 10:37
    
In problem 2, what is n? –  Gautam Shenoy Nov 29 '12 at 11:45
    
@GautamShenoy n is integer. –  Sali Me Nov 29 '12 at 12:16
add comment

3 Answers

up vote 4 down vote accepted

for 2>

$9^2 \equiv 8(\mod 73)$ and $8^2 \equiv -9 (\mod73)$

then $ 9^{2n+1}+8^{n+2} \equiv 9^{2n}.9 + 8^n.8^2 \equiv 8^n.9 + 8^n.(-9) \equiv 0 (\mod 73)$

share|improve this answer
    
nice work up there (+1) –  Chris's sis Nov 30 '12 at 9:05
add comment

(2)I was trying to figure out how the problem came to being.

Observe that $73=8\cdot9+1$

Replacing $8$ with $a$ we get $a(a+1)+1=a^2+a+1$

Now as the root of $a^2+a+1=0$ are the imaginary cube roots of $1,$ let $\omega$ be one of the imaginary cube roots of $1.$

So, $\omega^3=1\implies \omega^{3n}=1$

$\omega^{3n+2m+n}=\omega^{2m+n}$

Now,$\omega^{3n+2m+n}=(\omega^2)^{m+2n}=\{-(1+\omega)\}^{m+2n}=(-1)^m (1+\omega)^{m+2n}$

So, $\omega^{2m+n}=(-1)^m (1+\omega)^{m+2n}$

So, $\omega$ is a root of $x^{2m+n}-(-1)^m (1+x)^{m+2n}=0$ $\implies(x-\omega)\mid \{x^{2m+n}-(-1)^m (1+x)^{m+2n}\}$

Similarity, $\omega^2$ is a root,$\implies (x-\omega^2)\mid \{x^{2m+n}-(-1)^m (1+x)^{m+2n}\}$

But we know, $(x-\omega)(x-\omega^2)=x^2+x+1$

So, $$x^{2m+n}-(-1)^m (1+x)^{m+2n}\equiv0\pmod{x^2+x+1}$$

Once derived, it can be verified using Congruence like following:

As $1+x\equiv-x^2\pmod{x^2+x+1}$ and $x^3\equiv1\pmod{x^2+x+1},$

$(1+x)^{m+2n}\equiv(-x^2)^{m+2n}\pmod{x^2+x+1}\equiv(-1)^{m+2n} x^{2m+4n}\equiv(-1)^m x^{2m+n} (x^3)^n$

or, $(1+x)^{m+2n}\equiv (-1)^m x^{2m+n}\pmod{x^2+x+1}$

or, $(1+x)^{m+2n}(-1)^m\equiv x^{2m+n}$

Here in this problem, $x=8,m=1$

(1)$$2222\equiv3\pmod 7\implies 2222^5\equiv 3^5\pmod 7\equiv3^3\cdot3^2\equiv(-1)9\equiv5$$

$$5555\equiv4\pmod 77\implies 5555^2\equiv4^2\pmod7\equiv 2$$

So, $$2222^5+5555^2\equiv5+2\pmod 7\equiv 0$$

But , $$(2222^5+5555^2)\mid\{(2222^5)^{1111}+(5555^2) ^{1111} \} $$

share|improve this answer
    
thanks @lab bhattacharjee –  Sali Me Nov 30 '12 at 13:29
    
@SaliMe, welcome.Could I make the idea clear? –  lab bhattacharjee Nov 30 '12 at 13:35
add comment

For problem 1) You can show by elementary division that $$2222 \equiv 3 \mod 7$$ Now $$3^6 \equiv 1 \mod 7$$ And therefore (all mod 7) $$2222^{5555} \equiv 3^{5555} \equiv 3^{6\times 925+5} \equiv 3^5 \mod 7 $$ Now since inverse of 3 is 5 in mod 7, the above becomes $3^6.3^{-1}\equiv 5 \mod 7$

Similarly you can show $5555 \equiv 4 \mod 7$. Now $4^3 \equiv 1\mod7$. So

$$5555^{2222} \equiv 4^{2222} \equiv 4^{3\times 740+2} \equiv 4^2 \equiv 2 \mod 7$$

Therefore the sum will be $0 \mod 7$. This means that it is divisible by 7.

share|improve this answer
add comment

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.