Proof by induction (Chinese remainder theorem?)

Question

Suppose that $a_1,a_2,\dots,a_n \in \mathbb{Z}$ are each relatively prime to m $\in \mathbb{N}.$ Use induction to show that $$a = a_1 \cdot a_2 \cdot \dots\cdot a_n$$ is relatively prime to $m$.

Thought process

Base Case Let $n = 1$. Thus, $a = a_1$ and $a_1$ is already reltively prime to $m$.

Assume this holds for $n = k$.

Inductive Step

Now we show that $n = k + 1$ holds.

This is as far as I've gotten. Is everything up to this point. If so, how should I proceed the inductive step?

Answer 1

First of all, the key to these inductive proofs is to stay organized and very carefully state the claims you are trying to prove. You're doing a pretty good job at this, but I think you can make things a bit more explicit. And that is not just for the sake of whoever grades your answer ... it is also so that you don't get lost in your own proof.

So, make sure to explicitly state the claim $P_i$ you are trying to prove for any $1 \le i \le n$ (also explicitly state these kinds of boundaries!). In this case, that will be:

$$P_i: \text{ the number } a_1 \cdot ... \cdot a_i \text{ is relatively prime to } m$$

Then, after the base case, take some $1\le k < n$, and assume the inductive hypothesis:

$$P_k: \text{ the number } a_1 \cdot ... \cdot a_k \text{ is relatively prime to } m$$

(again, state this explicitly!)

Finally, explicitly state what your goal is of the inductive step. So that will be:

$$P_{k+1}: \text{ the number } a_1 \cdot ... \cdot a_{k+1} \text{ is relatively prime to } m$$

OK, so now that you have the robust set-up, let's prove this ... and let's do a proof by contradiction:

Suppose the number $a_1 \cdot ... \cdot a_{k+1}$ is not relatively prime to $m$.

OK, so then we have some prime number $p$ that divides both $a_1 \cdot ... \cdot a_{k+1}$ and $m$.

But by Eucliud's Lemma (I see from the comments you covered that one), if $p$ divides $a_1 \cdot ... \cdot a_{k+1}$, then $p$ divides $a_1 \cdot ... \cdot a_k$ or $p$ divides $a_{k+1}$ (or both).

But if $p$ divides $a_1 \cdot ... \cdot a_k$, then $p$ divides both $a_1 \cdot ... \cdot a_k$ and $m$, and so $a_1 \cdot ... \cdot a_k$ and $m$ are not relatively prime, which contradicts the inductive hypothesis. Likewise, $p$ dividing $a_{k+1}$ leads to a contradiction as well, since $a_{k+1}$ and $m$ are relatively prime.

Hence, we have obtained a contradiction.

Answer 2

The key is to show the result for two numbers.

Suppose $a$ and $b$ are coprime with $m$. By Bézout, $1=ax+my$ for some $x$ and $y$.

Multiply by $b$: $b=abx+mby$.

Now $1=br+ms$ for some $r$ and $s$, so $$ 1=(abx+mby)r+ms=ab(xr)+m(byr+s) $$ This implies $ab$ and $m$ are coprime (reverse Bézout).

Can you apply this to your induction step?