# Prove that if $k_1$ and $k_2$ are relatively prime to n, then so is $k_1 *_n k_2$

I think this should be done by contradiction.

Let's assume that $k_1 *_n k_2$ is not relatively prime to n.

This means that there exist the gcd($k_1 *_n k_2$, n) that is greater than 1. And I am stuck here.

• Let $A_1$ be the set of prime factors of $k_1$ and $A_2$ the set of prime factors of $k_2$, $B$ the set of prime factors of $n$. If $k_1$ and $n$ are relatively prime, then $A_1 \cap B = \emptyset$. (Because sharing common prime factors means not relatively prime). Similarly, $A_2 \cap B = \emptyset$. $\Rightarrow (A_1 \cup A_2) \cap B = \emptyset$. The prime factors of $k_1 *_n k_2$ are obviously $A_1 \cup A_2$. So $k_1 *_n k_2$ and $n$ are relatively prime. – Chinmay Nirkhe Dec 28 '14 at 19:17
• You should define the (nonstandard) notation $\ a *_n b.\$ Also, it would help to know what tools you have available, e.g. Bezout, Euclid's Lemma, Fund. Theorem of Arith? – Bill Dubuque Dec 28 '14 at 19:44
• I'm quite confident $a *_n b$ reminder of $ab$ when dividing by $n$. – Wojowu Dec 28 '14 at 19:49
• @Wojowu That would be my guess too. But readers should not have to guess the denotation. – Bill Dubuque Dec 28 '14 at 19:55

Note that $k_1 *_n k_2=k_1k_2-nl$ for some $l$. Then, if prime $p\mid k_1 *_n k_2=k_1k_2-nl$ and $p\mid n$, then $p\mid k_1k_2$, so $p\mid k_1$ or $p\mid k_2$, so either of $k_1,k_2$ wasn't relatively prime with $n$, as they would share prime factor $p$.