Can X be its own inverse in a residue system?

[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 [tex]\frac{1-xy}{q}[/tex]=n which is equal to q(1-xy)=n.

Thanks in advance
Maunil

 

[yyat]

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

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

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

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

 

[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 [tex] X^S \equiv X^T Mod N [/tex] Since X is relatively prime to N we can cancel out powers of X.

This gives [tex]X^{S-T} \equiv 1 Mod N [/tex] 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 [tex] X^{S-T-1} \equiv X^{-1} Mod N. [/tex]