Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

The question is as per the subject line. Does the fundamental theorem of arithmetic imply (prove?) that if I multiply two primes, then those two primes are the only factors of the product? I.e. 17 x 23 = 391 and the only factors of 391 are 17 and 23. I have searched, but can't find an answer to this precise question.

share|improve this question

closed as off-topic by figlesquidge, DrLecter, AFS, Thomas, e-sushi Apr 25 at 16:34

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions on mathematics are off-topic unless they relate directly to cryptography. These questions can usually be asked on Mathematics Stack Exchange." – figlesquidge, DrLecter, AFS, Thomas, e-sushi
If this question can be reworded to fit the rules in the help center, please edit the question.

    
The answer is "Yes". –  Henrick Hellström Apr 25 at 13:15

1 Answer 1

up vote 3 down vote accepted

Yes, that is true (unless you count the trivial factors of 391, namely 1 and 391). The fundamental theorem of arithmetic states that any postive integer is a product of a unique multiset of primes, and that no other multiset will multiply together to form that integer.

And so, since $391$'s multiset of primes is $(17, 23)$ (because both $17$ and $23$ are prime, and $17 \times 23 = 391$), that implies that no other prime can possibly divide $391$. If there were such a prime $p$, then we'd have an alternative multiset that consisted of $p$ and a multiset that was the factorization of $391/p$; that would be a different multiset (because, by assumption, $p$ is neither $17$ nor $23$) with the same product, and we know that can't happen.

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.