Prime Factorization is Unique, Correct?

SLAM: debunk creationism, pseudoscience, and superstitions. Discuss logic and morality.

Moderator: Alyrium Denryle

Post Reply
darthbob88
Jedi Knight
Posts: 884
Joined: 2006-11-14 03:48pm
Location: The Boonies

Prime Factorization is Unique, Correct?

Post by darthbob88 »

As an extra credit question, my professor asked us to determine whether two functions are one-to-one, whether there exist two different sets of inputs that produce the same output. The functions map positive integers for X to positive integers for Y; F(m, n) = 3^m * 5^n, and G(m) = 3^m * 6^n.

Obviously, so long as m and n are restricted to positive integers, the first is merely the prime factorization of whatever the output is, and must be one-to-one, since there is no possible way to rewrite 3^m as 5^n, where m and n are not 0.

The second makes me a little dubious; admittedly, there is no mathematical reason why it should not be one-to-one, for the same reasoning as above. Still, the fact that 6^n can be re-written as 2^n * 3^n leads me to believe that this function is not entirely one-to-one.

Quite frankly, am I or am I not being paranoid about this?
This message approved by the sages Anon and Ibid.
Any views expressed herein are my own unless otherwise noted, and very likely wrong.
I shave with Occam's Razor.
User avatar
Kuroneko
Jedi Council Member
Posts: 2469
Joined: 2003-03-13 03:10am
Location: Fréchet space
Contact:

Post by Kuroneko »

Prime factorization of integers greater than 1 is unique up to order. As for your functions, both of them are one-to-one. Hint: given an arbitrary output of G(m,n), first show that one there can be at most one n that gives that output; from this, the rest (uniqueness of pair (m,n)) is easy. Starting with n is important.
[Edit: minor clarification (on second thought, let's be more vague so as to not give it away).]
"The fool saith in his heart that there is no empty set. But if that were so, then the set of all such sets would be empty, and hence it would be the empty set." -- Wesley Salmon
Post Reply