I know this is one of the most fundamental basis of arithmetic but I can't find the result by myself.
how do we prove $p|q\cdot r\rightarrow p=q$ or $p=r$? ($p, q, r$ being prime numbers)
$\begingroup$
$\endgroup$
2
-
$\begingroup$ I think this question is much harder than it looks. If you use the uniqueness of prime factorization, then you end up with a circular argument. Because how do you prove uniqueness of prime factorization? I struggled with this question for several days. I ended up using Euclid's algorithm for finding the highest common factor. But I would have to rack my brain to remember how it went. $\endgroup$– Stephen Montgomery-SmithNov 26, 2013 at 15:42
-
$\begingroup$ Looking back in my old answers, I see that this question is very closely related to this question. $\endgroup$– robjohn ♦Nov 26, 2013 at 15:55
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
4
If $p\mid q$, we are done.
Suppose that $p\not\mid q$. Since $p$ is only divisible by itself and $1$, $\gcd(p,q)=1$. By Bezout's Identity, there are $a$ and $b$ so that $$ ap+bq=1\tag{1} $$ Multiply $(1)$ by $r$ to get $$ (ar)p+b(qr)=r\tag{2} $$ Since $p\mid qr$, there is a $k$ so that $kp=qr$. Using this in $(2)$ gives $$ r=p(ar+bk)\tag{3} $$ which says that $p\mid r$.
QED
-
$\begingroup$ And Bezout's identity follows from Euclid's algorithm for HCF, doesn't it? $\endgroup$ Nov 26, 2013 at 15:47
-
$\begingroup$ @StephenMontgomery-Smith: Yes, but it can also be shown using the properties of a Euclidean domain without first proving the Euclidean algorithm. I do so in this answer. $\endgroup$– robjohn ♦Nov 26, 2013 at 15:52
-
$\begingroup$ Well I don't see how you can prove the properties of a Euclidean domain without invoking the algorithm in some form. (Using induction or a well-ordering principle may, in effect, be the same as invoking the algorithm.) $\endgroup$ Nov 26, 2013 at 15:57
-
$\begingroup$ @StephenMontgomery-Smith: To implement Euclid's Algorithm, we need to know that we can divide, getting a quotient and remainder. That means we are assuming that we are in a Euclidean domain before we use the Euclidean Algorithm. Perhaps I am misunderstanding what you are trying to say. $\endgroup$– robjohn ♦Nov 26, 2013 at 16:05
$\begingroup$
$\endgroup$
The fully rigorous chain of proofs actually follows the following order:
You can prove the division algorithm using base axioms of the natural numbers (commutativity, distributivity, associativity, multiplicative identity, well-ordering principle), which is the claim that, given $a,b\in\Bbb N$, there exist $q,r\in\Bbb N$ such that $a=bq+r$ and $0\leq r<|b|$. This easily generalizes to $\Bbb Z$.
From there, you can prove that Linear Diophantine Equations always have a solution: given $a,b\in\Bbb Z$, there exist $x,y\in\Bbb Z$ such that $ax+by=\gcd(a,b)$.
After you've proven this, what you're looking for is easy to prove. Consider $a,b,c\in\Bbb N$ such that $a|bc$ and $\gcd(a,b)=1$. Then there exist $x,y\in \Bbb Z$ such that $ax+by=1$, or $acx+bcy=c$. Note that, since $a|bc$, $\exists k\in \Bbb Z$ such that $ak=bc$, so we have $acx+aky=a(cx+ky)=c$. Since $cx+ky$ is an integer by closure under addition and multiplication, $a|c$.
Note: unique prime factorization, as assumed by other answers, is not an axiom of the integers. Sure, it's perfectly okay to use it most of the time, but it is in fact a consequence of this chain of reasoning, and it's always best to be fully rigorous. Luckily, RobJohn did it the right way.
(Ask if you want proofs of the first two; that would take a bit longer).
$\begingroup$
$\endgroup$
3
Hint : what are prime divisors of $q \cdot r$ ?
-
$\begingroup$ Answering a question with a question... shaky ground, you might consider adding wording that describes your answer as a hint rather than risking downvotes... $\endgroup$– abiessuNov 26, 2013 at 15:32
-
$\begingroup$ its a question. but diluted one. its a hint no? $\endgroup$– GA316Nov 26, 2013 at 15:35
-
$\begingroup$ the answer to your hint is based on the question I am asking, isn't it ? :) $\endgroup$– ThomasNov 26, 2013 at 17:33
$\begingroup$
$\endgroup$
This is actually almost axiomatic, but you just have to consider the prime factors of $qr$, which are $q$ and $r$. Therefore - if $p$ divides $qr$ one of them have to be equal to $p$, since unique factorisation holds in $\Bbb Z$.
