SOLUTION: Find all integers {{{n}}}, {{{0 <= n < 163}}}, such that {{{n}}} is its own inverse modulo {{{163.}}}

Algebra.Com
Question 1207857: Find all integers , , such that is its own inverse modulo
Answer by ikleyn(52787)   (Show Source): You can put this solution on YOUR website!
.
Find all integers , {0 <= n < 163}, such that n is its own inverse modulo 163.
~~~~~~~~~~~~~~~~~~~~

(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

Solved, with complete explanations.

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

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



RELATED QUESTIONS

Find all integers $n$, $0 \le n < 163$, such that $n$ is its own inverse modulo... (answered by ikleyn,math_tutor2020)
Find all positive integers n such that 𝑛 2 + 1 is divisible by n+... (answered by MathLover1)
)Find all positive integers n such that 𝑛^ + 1 is divisible by n+ 1. (answered by ikleyn)
Use the given values of n = 202, p =0.75 to find the minimum value that is not... (answered by Boreal)
For each positive integer n, the set of integers (0,1...,n-1) is known as the residue... (answered by ikleyn)
find two consecutive integers such that the sum of twice the smaller and 3 times the... (answered by mananth)
Given an arithmetic sequence in which a1=3 a5=19 and an=163 what is... (answered by mananth)
Let $m$ and $n$ be non-negative integers. If $m = 6n + 2$, then what integer between $0$ (answered by ikleyn,math_tutor2020)
Find all integers n for which (n^2+n+1)/(n-1) is an... (answered by josgarithmetic)