1

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.

Mr. Brooks
  • 1,098
Discrete Math
  • 188
  • 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. – TenaliRaman May 25 '16 at 03:51
  • 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. – Mr. Brooks May 25 '16 at 21:34
  • @TenaliRaman I'm asking how to prove that, and although it sounds naturally implicative, I want to know how to prove with mods. – Discrete Math May 25 '16 at 22:33
  • 1
    @Mr.Brooks although a and n coprime implies that, it does not go the other way. Take a=6, n=4 for counter example. – JMoravitz May 25 '16 at 22:37

1 Answers1

3

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

JMoravitz
  • 79,518