1
$\begingroup$

Please help!

I need a proof using modulars on proving that with integers $a$, $b$, and $n$, if $a$ and $b$ are each relatively prime to $n$ then the product $ab$ is also relatively prime to $n$.

So far, what I really need help with is how to express this in modulars. I know that I need to use mod, but I am not sure how to express this.

$\endgroup$
  • $\begingroup$ gcd(a,n) = 1 implies that a and n share no prime factors. Similarly, b and n share no prime factors. So ab and n cannot share any prime factor. $\endgroup$ – TenaliRaman May 25 '16 at 3:51
  • $\begingroup$ Are $a$ and $b$ both larger than $n$? Then you can write $a \not\equiv 0 \pmod n$, $b \not\equiv 0 \pmod n$, etc. $\endgroup$ – Mr. Brooks May 25 '16 at 21:34
  • $\begingroup$ @TenaliRaman I'm asking how to prove that, and although it sounds naturally implicative, I want to know how to prove with mods. $\endgroup$ – Discrete Math May 25 '16 at 22:33
  • $\begingroup$ @Mr.Brooks although a and n coprime implies that, it does not go the other way. Take a=6, n=4 for counter example. $\endgroup$ – JMoravitz May 25 '16 at 22:37
2
$\begingroup$

$a$ is relatively prime to $n$ $\iff$ $\gcd(a,n)=1$

$\iff$ there exist integers $x,y$ such that $ax+ny=1$

$\iff$ there exists an integer $x$ such that $ax\equiv 1\pmod{n}$.

Now... does there exist an integer $x$ such that $(ab)x\equiv 1\pmod{n}$?

Note that if $a\equiv a'\pmod{n}$ and $b\equiv b'\pmod{n}$ that implies that $ab\equiv a'b'\pmod{n}$

Let $\gcd(a,n)=1$ and $\gcd(b,n)=1$. Then there exist integers $x_a$ and $x_b$ such that $ax_a\equiv 1\pmod{n}$ and $bx_b\equiv 1\pmod{n}$. Then letting $x=x_ax_b$ we have $abx\equiv\dots$ implying that $\dots$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.