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.

I'd really like your help with solving the following congruence:

$$5^n\equiv3^n+2 \pmod{11}.$$

I don't know with what to start.

Any help?

Thanks

share|improve this question
1  
As a general advice to this kind of a problem, where all the integers are relatively small, I would offer (if nothing else looks attractive to you) is to start trying things out, and build tables like the one created by Wonder below. Do that often enough, and you (hopefully) see a pattern emerge. A repeating pattern indicates that a cyclic group is out there! –  Jyrki Lahtonen Jul 5 '12 at 15:52

4 Answers 4

up vote 8 down vote accepted

Just note that 11 is prime so you only need to consider n modulo 10 here. Just list $5^n$ and $3^n$ modulo 11 for n going from 0 to 9:

$n\,\;\quad 0\quad 1\quad 2\quad 3\quad 4\quad 5\quad 6\quad 7\quad 8\quad 9$

$5^n\quad 1\quad 5\quad 3\quad 4\quad 9\quad 1\quad 5\quad 3\quad 4\quad 9$

$3^n\quad 1\quad 3\quad 9\quad 5\quad 4\quad 1\quad 3\quad 9\quad 5\quad 4$

Easy to see that this only happens at $n$ being $1$ or $6$ modulo $10$. So in other words we want $n$ to be $1$ modulo $5$.

share|improve this answer
    
Shouldn't it be ".. modulo 11" instead of "...modulo 10" in your first line above, @Wonder ? –  DonAntonio Jul 5 '12 at 11:27
2  
No, I know by Fermat's little theorem that $a^10$ will be 1 mod 11 for any a, and $a^0$ is anyway 1. So for the exponent n here, only its value mod 10 matters. –  Wonder Jul 5 '12 at 11:38
1  
I see what you say but it succeeded to confuse me and, perhaps, it could confuse others: you're right, it is enough to consider the power modulo $\,p-1=10=\varphi(11)\,$, yet the value $\,a^n\,$ must be considered, of course, modulo 11. It wasn't your fault, of course, but my confusion. +1 –  DonAntonio Jul 5 '12 at 11:44

We observe that $\mathrm{ord}_{11}(3) = \mathrm{ord}_{11}(5)=5$

So, the minimal non-negative solution(s) if any will lie between 0 and 4.

Clearly, $s=1$.

Now $5^{5t+s}-3^{5t+s} \equiv 5^s-3^s \mod\ 11$

So, the general solution will be $5t+1$ where $t$ is any integer.

share|improve this answer

Brute force works quickly as others have noted. Here is another way: mod $\,11,\,\ 3 \equiv 5^2,\,$ hence $\rm\, 0 \,\equiv\, 3^n\!-\!5^n\!+\! 2\, \equiv\, 5^{2n}\!-\!5^n\!+\!2\,\equiv\, x^2-x+2\,\equiv\, (x+\color{#C00}4)(x-\color{#0A0}5),\ $ for $\rm\, x = 5^n.\,$ Noticing that the sequence $\rm\, 5^n \equiv 1,\,5,\,3,\,4,\,-2,\,1,5,\,\ldots$ $\Rightarrow$ $\rm\,5^n = x\not\equiv -\color{#C00}4,\,$ and $\rm\,\color{#0A0}5\equiv x\!\iff\! n\equiv 1\pmod 5.$

share|improve this answer

For $n=0,1,2,\cdots,10 $, $5^n-3^n=0,2,5,10,5,0,2,5,10,5,0\implies $ only solutions for $5^n-3^n\equiv 2\pmod {11}$ are $n\equiv1\pmod {5}$(as the pattern repeats itself after $5$ terms)

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.