Let $p_1 , p_2$ be prime. Then prove that the only divisors of $p_1 p_2$ are $1 , p_1 , p_2 , p_1 p_2$.

Let $p_1 , p_2$ be prime. Then prove that the only divisors of $p_1 p_2$ are $1 , p_1 , p_2 , p_1 p_2$.

How do I prove it? I don't even intuitively get this... after so long time of trying to prove it.

• What is your definition of prime? Is it "only positive divisors of it are itself and one"? Or is it "$p$ is prime when $p$ divides $ab$ $\implies$ $p$ divides $a$ or $p$ divides $b$"? – Zev Chonoles Apr 8 '13 at 8:11
• Prime number is a number that is divided by 1 and itself. I generally consider only positive integers actually.. – jachilles Apr 8 '13 at 8:12
• The former one. I was actually trying to prove the former and the latter are equivalent, and in the course of it, I needed the above theorem as a lemma. – jachilles Apr 8 '13 at 8:16
• If $d$ is a divisor of $p_1 p_2$, what can you say about the prime factorization of $d$? What primes can it be 'made up of'? – copper.hat Apr 8 '13 at 8:18
• @copper.hat Not much actually... The thing is even though I assume $d$ is not one of $1, p_1 , p_2 , p_1 p_2$ I cannot derive a contradiction. – jachilles Apr 8 '13 at 8:21

For the intuition: take the primes $p_1=5$ and $p_2=11$. Then $p_1\cdot p_2=55$ and indeed the only divisors (among the natural numbers) of the product are $1,5,11$, and $55$. Now take not both numbers prime, say $p_1=24$ and $p_2=11$. Then $p_1\cdot p_2=264$ and the divisors of the product this time certainly include $1,24,11$, and $264$, but also $2,3,6,12$.

For the proof: suppose $p_1,p_2$ are prime and that $n\mid p_1p_2$, where $n\in \mathbb N$. If $n\ne 1$ then it has a prime divisor. Let $q$ be an arbitrary prime divisor of $q$. Then in particular, $q$ divides $p_1p_2$. Now, according to Euclid's Lemma, if a prime divides a product, then it divides one of the factors. Thus, either $q\mid p_1$ or $q\mid p_2$. Assume, without loss of generality, that $q\mid p_2$. But since $p_2$ is prime, it follows that $q$ is either $1$ or $q=p$. Since $q$ is prime, the possibility of $q=1$ is (explicitly in the definition of prime number) ruled out. We conclude that $q=p$.

Now consider $m=n/q=n/p_1$. It follows that $m\mid p_2$. Thus, either $m=1$ or $m=p$. In the case $m=1$, it follows that $n=p_1$. If $m=p_2$ it follows that $n=p_1p_2$.

To conclude, we just showed that the only possible prime divisor of the product $p_1p_2$ are $1,p_1,p_2$, and $p_1p_2$.

• To relate this to @chango's answer, the argument above basically amounts to proving the fundamental theorem of arithmetic. – Ittay Weiss Apr 8 '13 at 8:27
• Hm... the thing is I was actually trying to prove Euclid's Lemma but then I need the above formula as a lemma for proving Euclid's... – jachilles Apr 8 '13 at 8:28
• The common proof of Euclid's Lemma is via Bezout's identity. See the wiki page. – Ittay Weiss Apr 8 '13 at 8:30
• @julypraise: As Ittay Weiss says, this is not the way to prove Euclid's Lemma. Any elementary number theory text should show you how to proceed instead. – Pete L. Clark Apr 8 '13 at 8:32
• no, it basically amounts to Euclid's Lemma. – Ittay Weiss Apr 8 '13 at 8:35

You only need the Fundamental Theorem of Arithmetics to conclude that really !

• Maybe for you but not for me. But Fundamental Theorem of Arithmetics does not really deal with divisors in general; it focuses on prime factorization 'structures' and possibly only them. – jachilles Apr 8 '13 at 8:35
• What do you mean? Mathematics is not a subjective field. Read the Fundamental Theorem of Arithmetics carefully. It says that every number can be descomposed uniquely (up to order) into a product of primes. Your number is already in such a form. So if you take all combinations of the factors, you get ALL divisors. – chango Apr 8 '13 at 13:57
• I'm not sure which Fundamental Theorem you are looking at. But according to wiki's one, the theorem states that any integer can be decomposed into purely by prime factors and any kind of this process will actually end up in the same factors. But you must recognize that the theorem does not state these are 'all the possible divisors' of the given integer! They are only all the prime divisors, nothing more. Purely in logical manner, prime divisor is never the same as general integer divisor. – jachilles Apr 9 '13 at 1:01
• So even though the above theorem that I proposed may be a quite direct corollary of The Fundamental Theorem, it must take more logical steps. – jachilles Apr 9 '13 at 1:02
• Of course they are ALL possible divisors, this is easy to prove. Suppose you have your unique prime factorization of say $b$. And suppose another number $a$ divides $b$. Then we can apply the FTA to $a$ and get another prime factorization for $a$. If $p$ is a prime in the factorization of $a$, it must be in the factorization of $b$. Why? Well, you can use the property that if a prime number divides a product, it must divide one of the factors. So you have proven that every divisor of $b$ has to be made out of the primes in the factorization of $b$. Done! – chango Apr 10 '13 at 8:32

Hint $\rm\,\ d\mid p_1 p_2 \:\Rightarrow\: p_1 p_2 = c d\:$ for some $\rm\: c\in \Bbb N.\:$ By the FTA (Fundamental Theorem of Arithmetic), $\rm\:c,d,cd,\:$ all have unique prime factorizations. By uniqueness, the multiset of prime factors of $\rm\,cd\,$ is the multiset union of the multiset of primes in $\rm\,c\,$ and $\rm\, d.\:$ Since $\rm\:cd = p_1 p_2,\:$ by uniqueness, this union equals $\rm\,\{p_1,\, p_2\}.\:$ Therefore the multiset of prime factors of $\rm\:d\:$ is a subset of $\rm\:\{p_1,\, p_2\}.\:$ Its four subsets yield precisely the claimed factors of $\rm\:p_1 p_2.$

Remark $\$ An obvious analogous argument shows that if $\rm\:p_i\:$ are primes then every factor of $\rm\:p_1^{e_1}\cdots p_k^{e_k}\:$ has form $\rm\: u p_1^{d_1}\cdots p^{d_k}\:$ where $\rm\:d_i \le e_i,\:$ and $\rm\:u\:$ is a unit (i.e. in $\rm\,\Bbb Z,\ u = \pm 1).\:$

The uniqueness half of the proof of FTA (unique factorization of prime products) extends to any domain, where one defines prime to mean a nonunit that satifies the prime divisor property (PDP): $\rm\:p\mid ab\:\Rightarrow\:p\mid a\ \ or\ \ p \mid b\:$ (the key property that, extended inductively, yields uniqueness of prime factorizations). However, not all domains have a FTA, since existence may fail (not all nonzero nonunits are factorable into products of atoms) or uniqueness may fail (not all atoms (irreducibles) need be prime, i.e. satisfy PDP). These two conditions are precisely what is needed for every nonzero nonunit to have a unique factorization into atoms, i.e. for the domain to be a UFD (unique factorization domain).

Let there be a divisor $q$ of $p_1p_2$ which is not in the list. This means, that $q$ should be either divisor of $p_1$ or $p_2$ which meanse, that $p_1$ or $p_2$ is not a prime.

• This is not so straightforward. How do you conclude from $q$ dividing $p_1p_2$ that $q$ must divide either $p_1$ or $p_2$? (e.g., consider $q=p_1p_2$). – Ittay Weiss Apr 8 '13 at 8:34
• $p_1p_2$ is in the list... – V-X Apr 17 '13 at 14:44
• nontrivial divisor of a given number is either prime or composed of other divisors of that number. There couldn't be any other divisor. – V-X Apr 17 '13 at 14:47
• you are not addressing the issue. Your answer depends on a nontrivial fact about divisors that you assume holds without referring to it explicitly. Can you prove what you claim in your last comment? If you can then you basically proved Euclid's Lemma which is at the heart of a proper answer to the original question. – Ittay Weiss Apr 17 '13 at 20:32