2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Just put the subscript in braces: x_{k+1} gives $x_{k+1}$ $\endgroup$ – saulspatz Jul 22 '18 at 13:55
  • $\begingroup$ I keep trying to edit it but you post an edit and forestall me. Stop editing it and I'll fix it. $\endgroup$ – saulspatz Jul 22 '18 at 14:04
  • $\begingroup$ Sorry about that @saulspatz , saw ur comment and tried editing immediately, thanks for ur initiative. $\endgroup$ – Prashin Jeevaganth Jul 22 '18 at 14:07
  • $\begingroup$ The symbol for ‘divides’ is obtained by the command \mid. $\endgroup$ – Bernard Jul 22 '18 at 14:09
  • 1
    $\begingroup$ @Peter a\nmid b gives $a\nmid b$. If you right-click on a formula you get a pop-up that says "Show Math As" and then if you pick "TeX commands" you'll see the TeX commands that you just need to put inside $ signs. This has helped me a lot. Try it. $\endgroup$ – saulspatz Jul 22 '18 at 14:20
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Oh I think I saw something. Do u mean that even though we assumed that P(k) is true from the inductive step(which is the entire conditional statement), we do not know the truth value for the hypothesis, hence there are 2 cases, and to prove that a conditional statement is True, we have to prove that the conclusion of the conditional statement is True for both True and False values of the hypothesis. $\endgroup$ – Prashin Jeevaganth Jul 22 '18 at 14:28
  • $\begingroup$ I don't know what you mean by "the hypothesis." There are a lot of different hypotheses floating around. (You never have to prove that anything is true for a false value of a hypothesis, though. A false statement implies anything.) You have to prove the conclusion is true if the hypothesis is true, just as in the proof of every theorem. In this particular example, it's a proof by cases. $\endgroup$ – saulspatz Jul 22 '18 at 17:58
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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\}$

$\endgroup$

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.