Does the product of two primes only have those primes, itself, and 1 as factors?

2.3k Views Asked by At

Happened to review RSA key generation today, and it has led me to this question. I've tried it with a few but obviously that doesn't make it mathematically proven.

3

There are 3 best solutions below

0
On BEST ANSWER

An integer greater than one is a prime if it has no divisors other than one and itself. Therefore, if $p,q$ are primes, $pq$ has no divisors other than $p$, $q$, and one.

3
On

This is trivially true. If $p$ and $q$ are primes, the only way to write them is $p$ and $q$. So $pq$ can only be written as $pq$

0
On

If you're only looking at positive integers, then yes, of course, the product of two positive primes has only $1$, the two primes and itself as divisors.

Call $\sigma_0(n)$ the function that tells you how many positive divisors a positive number $n$ has. Then, if $p$ and $q$ are primes, then $\sigma_0(pq) = 4$ and those four divisors are $1, p, q, pq$. Example: $65 = 5 \times 13$. The only positive divisors are $1, 5, 13, 65$.

If you broaden your view to the negative integers, you can just take the positive divisors and multiply each by $-1$ to get the negative divisors: $-65, -13, -5, -1$.

And if you further broaden your view to a domain in which those numbers are not primes, things get more interesting: $(2 - i)(2 + i)(2 - 3i)(2 + 3i) = 65.$