Relative Primes and mod

1. Feb 26, 2009

mets19

Hi all,
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 $$\frac{1-xy}{q}$$=n which is equal to q(1-xy)=n.

Maunil

Last edited: Feb 26, 2009
2. Feb 27, 2009

yyat

There you go!
1-xy=qn implies 1-xy=0 (mod n), hence 1=xy (mod n).

No, n|(1-xy) implies (1-xy)=kn for some k, which you already knew.

3. Feb 28, 2009

robert Ihnot

Another way to look at this is to remember that the elements of a residue system are always less than N.

If we look at the powers of X they must come to repeat and $$X^S \equiv X^T Mod N$$ Since X is relatively prime to N we can cancel out powers of X.

This gives $$X^{S-T} \equiv 1 Mod N$$ Assuming S is the larger value, we can not have S-T = 1 unless X is its own inverse.

Thus S-T = 2 or more, and $$X^{S-T-1} \equiv X^{-1} Mod N.$$

Last edited: Feb 28, 2009