# Proving a conditional statement by induction

I’m a university freshman and I saw this in the lecture slides of my Discrete Mathematics module. I do not know what the name of the theorem is, so I will just copy the proof to the best of my ability.

Theorem: If p is a prime and $x_1, x_2,... x_n$ are any integers such that: $p\mid x_1x_2...x_n$; then $p\mid x_i$ , for some $i ,\; 1\le i\le n$.

Proof: by Induction

1. Let $P(n) = ( (p\mid x_1x_2...x_n) \to (p\mid x_i\text{ for some } i \in[1,n]) )$
2. Base case: $n = 1$
3. Clearly, $P(1)$ is true.
4. Inductive step: For any $k \in \Bbb Z^+$:
5. If $P(k)$ ie. $(p\mid x_1x_2...x_k) \to (p\mid x_i\text{ for some } i \in[1,k])$.
6. Consider the case $k + 1$:
7. Suppose $p\mid x_1x_2...x_{k+1}$:
8. Let $A = x_1x_2...x_k$ , so that $p\mid Ax_{k+1}$.
9. If $p\mid A$:
10. Then $p\mid x_i$ for some $i \in [1, k]$ by the inductive hypothesis. So $P(k + 1)$ is true.
11. Else $p \not\mid A$:
12. Then $\gcd(p,A) = 1$, because $p$ is prime and $p \not\mid A$.
13. Then there exist integers $r, s$ such that $pr + As = 1$ by Bézout's Identity.
14. Now, $x_{k+1} = 1\cdot x_{k+1} = (pr + As)x_{k+1} = p(rx_{k+1}) + (Ax_{k+1})s$ by basic algebra.
15. Since $p$ divides both terms, it divides their linear combination by Theorem 4.1.1. [For all $a, b, c \in \Bbb Z$, if $a\mid b$ & $a\mid c$, then for all $x,y \in \Bbb Z$, $a\mid(bx + cy)$]
16. Thus, $p\mid x_{k+1}$ and $P(k + 1)$ is true.
17. Hence, by mathematical induction, the theorem is true.

Judging from the given proof, I would think in line 9 onwards, there is 2 cases we should consider(I would have stopped at line 10 and assume $P(k+1)$ is true if I wrote the proof myself). My question would be what is so special about this proof that we need to consider an (if-else) structure for it. Pardon my ignorance about induction as I only have used induction on Mathematical functions like summations from high school.

PS: New to Latex as well. Don't know how to write not | and subscript things like (k+1), see line 7,8,11,12,14,16. Would anyone kindly edit it for me so that I learn from my mistakes? Sorry for the confusion caused.

• Just put the subscript in braces: x_{k+1} gives $x_{k+1}$ – saulspatz Jul 22 '18 at 13:55
• I keep trying to edit it but you post an edit and forestall me. Stop editing it and I'll fix it. – saulspatz Jul 22 '18 at 14:04
• Sorry about that @saulspatz , saw ur comment and tried editing immediately, thanks for ur initiative. – Prashin Jeevaganth Jul 22 '18 at 14:07
• The symbol for ‘divides’ is obtained by the command \mid. – Bernard Jul 22 '18 at 14:09