# 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

## Theorem:-

Ifnis any positive integer then for every positive integerm<nand relatively prime tonthen∃positive integerb<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)=1where 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 exists,tbelong to integers :1=ms+tnthis implies 1-ms=tn this implies n|(1-ms) this implies ms≡1(mod n) now ifs<nthen we have done. But ifs>nthen we can take b≡s(mod n) which will give the same result sobm≡1(mod n)hence prove.