document.write( "Question 1207857: Find all integers $\"n\"$ , $\"0+%3C=+n+%3C+163\"$ , such that $\"n\"$ is its own inverse modulo $\"163.\"$ \n" ); document.write( "

Algebra.Com's Answer #845993 by ikleyn(52782) $\"\"$ $\"About$

You can put this solution on YOUR website!
.
\n" ); document.write( "Find all integers $\"n\"$ , {0 <= n < 163}, such that n is its own inverse modulo 163.
\n" ); document.write( "~~~~~~~~~~~~~~~~~~~~\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "

\r\n" );
document.write( "(a)  For our solution, the important fact is that 163 is a prime number.\r\n" );
document.write( "\r\n" );
document.write( "     Integer x is an inverse to integer n modulo 163 if and only if\r\n" );
document.write( "\r\n" );
document.write( "         nx = 1 mod 163   by the definition.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "     According to it, integer n is its own inverse modulo 163 if and only if\r\n" );
document.write( "\r\n" );
document.write( "         n^2 = 1 modulo 163.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "     One solution is trivial: it is n = 1 mod 163, or simply n= 1.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "     It is easy to find another (non-trivial) solution n.  Take n = -1 mod 163;  then  n^2 = (-1)*(-1) = 1 mod 163.\r\n" );
document.write( "\r\n" );
document.write( "     So, the class n = -1 mod 163 is the other possible solution. \r\n" );
document.write( "\r\n" );
document.write( "     If we want n in the interval 0 <= n < 163, we should take n = 162, which is 163-1.\r\n" );
document.write( "\r\n" );
document.write( "     Then we have n^2 = (163-1)*(163-1) = 163^2 - 2*163 + 1 = 1 mod 163.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "     So, this part (one half) of the problem is solved.  \r\n" );
document.write( "     We found two solutions in the given interval: n = 1  and n = 162.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "(b)   Now we want to prove that these two solutions, n= 1 and n= 162, are unique in the given interval \r\n" );
document.write( "\r\n" );
document.write( "      OK.  Let  assume that m is another integer number in the interval 0 <= m < 163,\r\n" );
document.write( "           inverse to itself mod 163.  Then we have these two modular equations\r\n" );
document.write( "\r\n" );
document.write( "               m*m = 1  mod 163\r\n" );
document.write( "\r\n" );
document.write( "               1*1 = 1  mod 163.\r\n" );
document.write( "\r\n" );
document.write( "      Taking the difference, we have\r\n" );
document.write( "\r\n" );
document.write( "               (m+1)*(m-1) = 0 mod 163.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "      It means that either (m-1) or (m+1) is divisible by 163.\r\n" );
document.write( "\r\n" );
document.write( "      In combination with the fact that 0 <= m < 163, it means that either m= 1 or m= 162.\r\n" );
document.write( "\r\n" );
document.write( "      Thus we proved that in interval [0,163) there is no other own-inverse numbers mod 163\r\n" );
document.write( "

\r
\n" ); document.write( "\n" ); document.write( "Solved, with complete explanations.\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "---------------------\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "This problem is from 22nd Philippine Mathematical Olympiad of 2019.\r
\n" ); document.write( "
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( " \n" ); document.write( "

\n" );