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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 '14 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 '14 at 13:15
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.