Proving a conditional statement by induction

Question

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.

Answer 1

All that has been shown by line 10 is that if $p|A$ the the theorem is true. But we don't know that $p|A$. All we know is that $p|Ax_{k+1},$ and so we also have to consider the case that $p\nmid A.$

Having said that, I think most people would structure this proof differently. First prove by Bezout's identity that if $p|ab$ then $p|a \text{ or } p|b$ then prove that it's true for any number of factors by induction.

Answer 2

The key is that the base case was $n =1$. Not $n= 2$. And.... it's easier if I were to explain how I would have done it.

I'd start with base case $n=1$ so $p|x_1$ then $p|x_1$.

Then I'd do a second base case $n=2$ and prove if $p|x_1x_2$ then $p|x_1$ or $p|x_2$ and .... I'd basically do the stuff from step 12 on.

Now what I can't do is: Show it true for base case $n=1$ and then say: Well, I assumed it was true for $n=k$ and then for $n=k+1$ it is then $x_1....x_kx_{k+1} = (x_1....x_k)(x_{k+1})$ and that's really just two numbers so it is true that $p|(x_1....x_k)$ or $p|x_{k+1}$.

I can't say that because we haven't proven it for $2$ numbers! We proved (well, demonstrated) it for a base case of $1$! Not $2$!.

I must say this is kind of a weird in that the induction is used to dismiss the larger cases and the gyst is proving the case for two numbers. Normally that would be done by taking the base case of two and proving it in the base case.

====

This taking a proper base case is important. There's a famous false proof that all horses in a field are the same color. (I first heard it as marbles in a bag.)

Thats true for $n =1$.

If you assume it is true for $n= k$ then if you have a field of $n=k$ horse they are the same color. Walk a $k+1$th horse up to your field. Remove one of your old horses. The remaining horses are the same color. Put the new horse in. Youu have $n=k$ horses so the new horse must be the same color as all the old horses. Put the other horse back in and you have $n=k+1$ horses and they are all the same color.

Note: That in you base case $n= 1$ then that sentence the remaining horses are the same color refers to $n-1 = 0$ horses! There are no horses for the new horse to assimilate to. The new horse is the same color but it doesn't need to be the same color of the removed horse because once you remove the old horse there are no horses left to stay the original color.

Answer 3

Let $(x_k)_{k\in\Bbb N^+}$ be any finite sequence of integers, $p$ be any prime integer, and $n$ be any positive integer.

let $X_n := \prod\limits_{k\in [n]^+} x_k$ be the product of the first $n$ terms of that sequence.

Let $P(n)$ state that $(p\mid X_n )\to\exists i\in[n]^+:(p\mid x_i)$ .   That says: If $p$ is a factor of a product of a finite sequence integers, then it is a factor of at least one from the sequence.

Trivially, $P(1)$ does clearly hold.   Because $X_1=x_1$ therefore $(p\mid X_1)\to \exists i\in[1]^+:(p\mid x_i)$.

• Assume $P(n)$ holds for any positive integer $n$.

  • Assume $(p\mid X_n)$ or $(p\mid x_{n+1})$.

    • You need to use proof by cases to derive $\exists i\in[n+1]^+:(p\mid x_i)$.
    • From that you may derive $(p\mid X_nx_{n+1})\to \exists i\in[n+1]^+:(p\mid x_i)$ .
    • That is $P(n+1)$ can be derived from assuming $P(n)$ and either $(p\mid X_n)$ or $(p\mid x_{n+1})$.

  • Assume $(p\nmid X_n)$ and $(p\nmid x_{n+1})$.

    • You need to derive $\neg\exists i\in[n+1]^+:(p\mid x_i)$ from the assumptions.
    • From you may derive $(p\mid X_nx_{n+1})\to \exists i\in[n+1]^+:(p\mid x_i)$
    • That is $P(n+1)$ can be derived from assuming $P(n)$ and both $(p\nmid X_n)$ and $(p\nmid x_{n+1})$.

  • That is $P(n+1)$ can be derived from assuming $P(n)$ in both the above. Do so.

• Therefore $\forall n\geq 1: (P(n)\to P(n+1))$

---

$[n]^+=\{k\in\Bbb N^+: k\leq n\}$