Hi all,(adsbygoogle = window.adsbygoogle || []).push({});

Supppose that n > 0 and 0 < x < n are integers and x is relatively prime to n, show that there is an integer y with the property:

x*y is congruent to 1 (mod n)

I have attempted the following, I am not sure if I am on the right track:

1 = xy + qn which implies 1 - xy = qn

n|(1-xy) which implies q(1-xy) = n

so if I divide q in the first equation i get [tex]\frac{1-xy}{q}[/tex]=n which is equal to q(1-xy)=n.

Thanks in advance

Maunil

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Relative Primes and mod

**Physics Forums | Science Articles, Homework Help, Discussion**