0
$\begingroup$

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?

Improve this question
$\endgroup$
  • $\begingroup$ 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$$ ? $\endgroup$ – Peter Jun 23 '20 at 11:14
  • $\begingroup$ 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. $\endgroup$ – Szymon Pawlus Jun 23 '20 at 11:14
  • $\begingroup$ 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. $\endgroup$ – aschepler Jun 23 '20 at 11:16
  • $\begingroup$ 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 $\endgroup$ – UmbQbify Jun 23 '20 at 11:23
  • 1
    $\begingroup$ @user675453 no obviously ,it does not give the answer in one step.I have done it using FLT and many others theorems. $\endgroup$ – LAMDA Jun 23 '20 at 11:27
1
$\begingroup$

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.

Improve this answer
$\endgroup$
  • $\begingroup$ but all the steps are equivalent so solution of the last system should be solution of the first and vice versa. $\endgroup$ – LAMDA Jun 23 '20 at 11:32
  • 1
    $\begingroup$ 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$. $\endgroup$ – Siong Thye Goh Jun 23 '20 at 11:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.