# If $5^{2015} \equiv n \bmod 11$ and $n \in \{0,1,2,…,10\}$ then what is the value of $n$?

If $$5^{2015} \equiv n (\bmod 11)$$ and $$n \in \{0,1,2,...,10\}$$ then what is the value of n?

I have succeeded to solve this problem using Fermat's little theorem and the value of $$n$$ is $$1$$ but my problem is different using a theorem or formula I get $$n^2 \equiv 1 (\bmod 11)$$....(A)

The theorem is

$$n$$ is a positive integer and $$\gcd(a,n)=1$$.If $$x^k \equiv a (\mod n)$$ and $$gcd(k,\phi (n))=d$$; $$n$$ is prime iff $$a^{\phi (n)/d} \equiv 1 (\mod n)$$ , where $$\phi (n)$$ is Euler phi function.

Now in the equation (A) ,if we put $$n=10$$ and $$n=1$$ both values are satisfied but it is impossible since n must be any one number between $$0$$ to $$10$$.

Now I don't know know how to solve the theorem.WHAT IS THE MISTAKE IN THIS METHOD?

• I do not think that the second theorem is valid. Do you perhaps mean Euler's theorem : $$\gcd(a,n)=1\implies a^{\varphi(n)}\equiv 1\mod n$$ ? – Peter Jun 23 '20 at 11:14
• I don't know whether it'll satisfy you but to solved this problem i used that $5^5 \equiv 1 mod 11$ and using modular multiplication get n. – Szymon Pawlus Jun 23 '20 at 11:14
• No mistake. "$n = 1$ or $n = 10$" is a true statement, since we know $n=1$. "If $n=10$, then $11$ is prime" is a true statement, since the conclusion is true despite the false premise. It's just not quite enough of a conclusion to entirely solve the problem. – aschepler Jun 23 '20 at 11:16
• If I'm not wrong, fermat's little theorem is $a^{p-1}\equiv 1 \pmod p$, which I think doesn't give n=1 – UmbQbify Jun 23 '20 at 11:23
• @user675453 no obviously ,it does not give the answer in one step.I have done it using FLT and many others theorems. – LAMDA Jun 23 '20 at 11:27

Choose $$k=2015$$ and $$x=5$$, $$gcd(k, \phi(11))=gcd(2015, 10)=5$$, then we conclude that $$n^\frac{10}{5}=n^2 \equiv 1 \pmod{11}$$
However, it doesn't mean that all the solution of $$n^2 \equiv 1 \pmod{11}$$ is the solution to the original problem.
It just claims that the solution of the original system satisfy $$n^2 \equiv 1 \pmod{11}$$ since $$11$$ is a prime.
• If I substitute those numbers in, the theorem reduces to if $5^{2015}\equiv n \pmod{11}$, then $11$ is a prime iff $n^2 \equiv 1 \pmod{11}$. We know that $11$ is a prime. Hence the statement is if $5^{2015}\equiv n \pmod{11}$, then $n^2 \equiv 1 \pmod{11}$. The theorem is of the form of if A, then B iff C. It doesn't claim $C$ implies $A$. – Siong Thye Goh Jun 23 '20 at 11:36