Question

Any tips on how should I tackle this? Question attached.

Answer 1

geez, Near what do you study ?

Answer 2

What is gcd(m,n)

Answer 3

@siddhantsharan gcd = greatest common divisor.
@EarthCitizen, I am majoring in Physics, I like to solve these problems for fun, albeit they took me hours to solve.

Answer 4

First thought: Let m=1. Now use induction to prove that it's true for all n if m=1. Now that we have that, use induction on m.

Also, you should take a longer look at the problem I posted today. It was putnam practice for me last semester.

Answer 5

@KingGeorge The one to prove f(n) = n for all n? I took notice of it not too long ago, but my brain is malfunctioning right now. Well, I think I have to sleep and will come back to this tomorrow. Will definitely check your post. I also thought about induction but, well, I couldn't come up with anything.

Answer 6

Very well. I must also sleep on your problem :)

Answer 7

On a note, I thought about trying by linear combination of m and n? Don't know if it works though.

Answer 8

I don't think it would work, but there's no harm in trying.

Answer 9

Well, anyway, I am off for now, but I will give it a shot when I get back. :-) Good luck for those who are trying it also.

Answer 10

George said:
First thought: Let m=1. Now use induction to prove that it's true for all n if m=1. Now that we have that, use induction on m.

Letting m=1 makes it actually super simple to solve for all n... doesn't even require induction.
\[\left(\begin{matrix}n \\ 1\end{matrix}\right) * \frac{\gcd(1,n)}{n} = \frac{n!}{(n-1)!1!}*\frac{1}{n} = \frac{n}{1}*\frac{1}{n} = 1\]

Answer 11

Don't know if induction on m works after that or not.

Answer 12

The fact that gcd(m,n) is a linear combination of m and n will lead to a solution.

Answer 13

Hmm I think you're right there, Joebro.

Answer 14

@joemath314159 Yeah, that looks correct. Intuitively it makes sense, but I wasn't able to prove that the gcd will be a linear combination of m and n. From there I came up with the fact that that\(\frac{\gcd(n,m)}{n} \left(\begin{matrix}n\\ m\end{matrix}\right)\) is a linear combination of \( \left(\begin{matrix}n-1\\ m-1\end{matrix}\right)\) and \( \left(\begin{matrix}n\\ m\end{matrix}\right)\), both integers. So, the former will also be an integer. But saying that \(\frac{\gcd(n,m)}{n} \left(\begin{matrix}n\\ m\end{matrix}\right)\) is a linear combination of \( \left(\begin{matrix}n\\ m\end{matrix}\right)\) isn't redundant?

Answer 15

You wouldnt have to prove that the gcd(m,n) is a linear combination m and n on the Putnam Exam. That is a well known Number Theory result (look up Bezout's Identity). Seems like youve solved the problem. After you call out the linear combination, the only trouble left is showing that:\[\frac{m}{n}\left(\begin{matrix}n \\ m\end{matrix}\right)\]is an integer. But it looks like you already figured that out :)

Answer 16

its funny how knowing a theorem or two can turn a hard putnam problem into a homework exercise (i got this problem as a homework exercise lol)

Answer 17

Thanks for the heads up about Bezout's identity. Does the fact that\[\frac{m}{n}\left(\begin{matrix}n \\ m\end{matrix}\right) = \left(\begin{matrix}n-1 \\ m-1\end{matrix}\right)\]holds for every m,n (except for n = 0, that is) or only for integers? Yeah, without knowing the Bezout's identity, I think this would be very hard.

Answer 18

It looks like that would only hold for integers, but the problem states we are only dealing with:\[n\ge m \ge 1\]so we are covered.

Answer 19

er, n and m integers.

Answer 20

Yup, I thought so. Thanks for the help :-)