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**

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

# Relative Primes and mod

Loading...

Similar Threads for Relative Primes |
---|

I Determining functional relation of two dependant variables |

I Paradox analyses related? |

A Defining the membership relation in set theory? |

I Terminology for relations |

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