3
$\begingroup$

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

  • 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!2012-07-05

4 Answers 4

8

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

  • 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. +12012-07-05
7

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.

4

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

1

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)