Question 1207857
.
Find all integers {{{n}}}, {0 <= n < 163}, such that n is its own inverse modulo 163.
~~~~~~~~~~~~~~~~~~~~


<pre>
(a)  For our solution, the important fact is that 163 is a prime number.

     Integer x is an inverse to integer n modulo 163 if and only if

         nx = 1 mod 163   by the definition.


     According to it, integer n is its own inverse modulo 163 if and only if

         n^2 = 1 modulo 163.


     One solution is trivial: it is n = 1 mod 163, or simply n= 1.


     It is easy to find another (non-trivial) solution n.  Take n = -1 mod 163;  then  n^2 = (-1)*(-1) = 1 mod 163.

     So, the class n = -1 mod 163 is the other possible solution. 

     If we want n in the interval 0 <= n < 163, we should take n = 162, which is 163-1.

     Then we have n^2 = (163-1)*(163-1) = 163^2 - 2*163 + 1 = 1 mod 163.


     So, this part (one half) of the problem is solved.  
     We found two solutions in the given interval: n = 1  and n = 162.



(b)   Now we want to prove that these two solutions, n= 1 and n= 162, are unique in the given interval 

      OK.  Let  assume that m is another integer number in the interval 0 <= m < 163,
           inverse to itself mod 163.  Then we have these two modular equations

               m*m = 1  mod 163

               1*1 = 1  mod 163.

      Taking the difference, we have

               (m+1)*(m-1) = 0 mod 163.


      It means that either (m-1) or (m+1) is divisible by 163.

      In combination with the fact that 0 <= m < 163, it means that either m= 1 or m= 162.

      Thus we proved that in interval [0,163) there is no other own-inverse numbers mod 163
</pre>

Solved, with complete explanations.


---------------------


This problem is from &nbsp;22nd &nbsp;Philippine &nbsp;Mathematical &nbsp;Olympiad of &nbsp;2019.