SOLUTION: Find an integer $x$ such that $0 \leq x < 205$ and $x^2 \equiv 11 \pmod{205}$.

Algebra ->  Divisibility and Prime Numbers  -> Lessons -> SOLUTION: Find an integer $x$ such that $0 \leq x < 205$ and $x^2 \equiv 11 \pmod{205}$.      Log On


   

Question 1207739: Find an integer $x$ such that $0 \leq x < 205$ and $x^2 \equiv 11 \pmod{205}$.
Found 2 solutions by greenestamps, math_tutor2020:
Answer by greenestamps(13198) About Me  (Show Source):
You can put this solution on YOUR website!


A quick check with an excel spreadsheet shows that there is no answer, so there is no sense looking for a mathematical way to find the answer.

Answer by math_tutor2020(3816) About Me  (Show Source):
You can put this solution on YOUR website!

See this similar question before moving on
https://www.algebra.com/algebra/homework/divisibility/Divisibility_and_Prime_Numbers.faq.question.1207682.html
I'll use the ideas discussed in that link.

phi(n) = Euler's Totient function
phi(205) = phi(5*41)
phi(205) = phi(5)*phi(41)
phi(205) = (5-1)*(41-1)
phi(205) = 160
There are 160 integers in the set {1,2,3,...,203,204} such that they are relatively prime to 205.

The goal of solving
x^2 = 11 (mod 205)
will have us needing to solve
2u = 1 (mod 160)
which turns into
2u-1 = 160k
and then can be arranged into
2(u-80k) = 1

The left hand side is always even, but the right hand side is odd.
This mismatch proves 2u-1 = 160k has no integer solutions
This means 2u = 1 (mod 160) doesn't have any solutions either.
Ultimately x^2 = 11 (mod 205) doesn't have any solutions.

You can use spreadsheet software or a coding script like python to verify.