Question

Determine all functions f that assign to each pair (m,n) of positive integers a positive integer f(m,n) satisfying
(1) f(n,n) = n
(2) f(m,n) = f(n,m)
(3) whenever n>m, then (n-m)*f(m,n) = n*f(m,n-m)

Answer 1

does this just return m*n? im working out some examples, and thats what im getting. Not exactly sure how one would prove that atm though.

Answer 2

It can't possibly return m*n because f(n,n) equals n, not n^2

Answer 3

oh, its the LCM. It returns the LCM of the two numbers. I had continually picked numbers where their GCD was 1, thats why I thought it was m*n lol.

Answer 4

haha yep you're right...its the LCM

Answer 5

Cool, is there any way to prove this?

Answer 6

im not going to write a full out proof on here, but basically if you start off with f(m,n), where n > m, then you can use the division algorithm on n to re write it as:
\[n = mq+r\] where r < m.
So now we have:
\[f(m,qm+r)\]
Using the last rule, we can subtract all the m's from qm+r, leaving:
\[f(m,qm+r) = \frac{qm+r}{(q-1)m+r}f(m, (q-1)m+r) \]
\[\frac{qm+r}{(q-1)m+r}*\frac{(q-1)m+r}{(q-2)m+r}*f(m, (q-2)m+r) = \cdots \]
Notice the denominator of the fraction will cancel out with the numerator in the fraction after it. This will happen all the way down till you cant anymore, by which point the function will look like:
\[(somefraction)f(m,r)\]
Then, because r is less than m, you use the symmetric property to flip them, and just repeat the process. Im still working out the finer details on paper unfortunately. =/

Answer 7

oh im sry, i guess i should have noted i changed the last property to look like:
\[f(m,n) = \frac{n}{n-m}f(m,n-m)\]so it was easier to compute things.