0

I'm learning proof by induction and I understand the property that

if $p|a$ and $p|b$ then $p|(a+b)$

Can someone elucidate why the following is always true (I'm assuming it's an extension of the property above):

In the below equation $a_1,a_2,k,l$ are all integers and $p$ is prime. We are assuming in our antecedent that $p|(a_1a_2)$

$a_2=pka_2+a_1a_2l$

Why is it clear from the above equation that $p|a_2$?

ClownInTheMoon
  • 1,987
  • 3
    Say $a_1a_2=pm$. Then $a_2=pka_2+pml=p(ka_2+ml)$. – lulu Sep 09 '16 at 22:00
  • Ah! Foolish me. Thanks! – ClownInTheMoon Sep 09 '16 at 22:03
  • 1
    $a_2 = pka_2 + a_1a_2l$. We see $p|a_1a_2$ so $p|a_1a_2l$. We see $p|pka_2$. Add $a_1a_2l$ to $pka_2$ to get $ p|pka_2 + a_1a2l$$ = a_2$. or as lulu points out ... or if $a_2 = pka_2 + a_1a_2l \implies pk + a_1l = 1$ (unless $a_2 =0$ and everything divides $0$). As p doesn't divide 1 and p does divide pk, p doesn't divide $a_1l$ so p doesn't divide $a_1$. As p is prime and indivisible $p|a_1a_2$ means either $p|a_1$ OR $p|a_2$. As one is impossible the other must be true. – fleablood Sep 09 '16 at 22:16

1 Answers1

2

$p$ divides the write hand side of the equation since $p \mid p k a_2$ (Because $p \mid p$) and $p \mid a_1 a_2 l$ (Because $p \mid a_1 a_2$) so $p$ also divides the sum (Just using the fact that you brought at first). Thus $p$ has to divide the left hand side which is $a_2$.

Hope that this is helpful.

Kummer
  • 74