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?
Prime Factorization is Unique, Correct?
Moderator: Alyrium Denryle
-
- Jedi Knight
- Posts: 884
- Joined: 2006-11-14 03:48pm
- Location: The Boonies
Prime Factorization is Unique, Correct?
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.
Any views expressed herein are my own unless otherwise noted, and very likely wrong.
I shave with Occam's Razor.
- Kuroneko
- Jedi Council Member
- Posts: 2469
- Joined: 2003-03-13 03:10am
- Location: Fréchet space
- Contact:
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).]
[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