Product of two integers a and b (less then integer n) is congruent to 1 if a or b integer is relativity prime to n .

From ProofWiki
Jump to navigation Jump to search

Theorem:-

      If n is any positive integer then for every positive integer m<n and relatively prime to n then  positive integer b<n :
                                 m*b≡1(mod n).

Proof:-

      Let n is any positive integer and m is positive integer less then n and co-prime to n.
      that's way we can able to write
                                 (m,n)=1       where 1 is greatest common divisor of m and n
      we also known from number theory that greatest common divisor of ant two integers can be
      written as combination of that numbers,
      therefore their exist s,t belong to integers :
                                1=ms+tn
            this implies        1-ms=tn
            this implies        n|(1-ms)
            this implies        ms≡1(mod n)
      now if s<n then we have done.
      But if s>n then we can take b≡s(mod n) which will give the same result
            so                  bm≡1(mod n)
                        hence prove.