# solving the congruence: $5^n\equiv3^n+2 \pmod{11}.$

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

-
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

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

-
Shouldn't it be ".. modulo 11" instead of "...modulo 10" in your first line above, @Wonder ? –  DonAntonio Jul 5 '12 at 11:27
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
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.

-

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

-

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)

-