document.write( "Question 1207739: Find an integer $x$ such that $0 \leq x < 205$ and $x^2 \equiv 11 \pmod{205}$. \n" ); document.write( "
Algebra.Com's Answer #845782 by math_tutor2020(3817)\"\" \"About 
You can put this solution on YOUR website!

\n" ); document.write( "See this similar question before moving on
\n" ); document.write( "https://www.algebra.com/algebra/homework/divisibility/Divisibility_and_Prime_Numbers.faq.question.1207682.html
\n" ); document.write( "I'll use the ideas discussed in that link.\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "phi(n) = Euler's Totient function
\n" ); document.write( "phi(205) = phi(5*41)
\n" ); document.write( "phi(205) = phi(5)*phi(41)
\n" ); document.write( "phi(205) = (5-1)*(41-1)
\n" ); document.write( "phi(205) = 160
\n" ); document.write( "There are 160 integers in the set {1,2,3,...,203,204} such that they are relatively prime to 205.\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "The goal of solving
\n" ); document.write( "x^2 = 11 (mod 205)
\n" ); document.write( "will have us needing to solve
\n" ); document.write( "2u = 1 (mod 160)
\n" ); document.write( "which turns into
\n" ); document.write( "2u-1 = 160k
\n" ); document.write( "and then can be arranged into
\n" ); document.write( "2(u-80k) = 1\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "The left hand side is always even, but the right hand side is odd.
\n" ); document.write( "This mismatch proves 2u-1 = 160k has no integer solutions
\n" ); document.write( "This means 2u = 1 (mod 160) doesn't have any solutions either.
\n" ); document.write( "Ultimately x^2 = 11 (mod 205) doesn't have any solutions.\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "You can use spreadsheet software or a coding script like python to verify.
\n" ); document.write( " \n" ); document.write( "
\n" );