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.

  • 1
    $\begingroup$ 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. $\endgroup$ – Chinmay Nirkhe Dec 28 '14 at 19:17
  • $\begingroup$ 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? $\endgroup$ – Bill Dubuque Dec 28 '14 at 19:44
  • $\begingroup$ I'm quite confident $a *_n b$ reminder of $ab$ when dividing by $n$. $\endgroup$ – Wojowu Dec 28 '14 at 19:49
  • $\begingroup$ @Wojowu That would be my guess too. But readers should not have to guess the denotation. $\endgroup$ – 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$.


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.