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 .
Jump to navigation Jump to search
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).
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.