Here’s a game for two players.
Player 1: Choose a positive integer that is greater than \(1\). Call it \(n\).
Player 2: Choose two positive integers, say \(a\) and \(b\), in such a way that \(n\) divides the product \(ab\) (that is, \(ab\) is a multiple of \(n\)).
If \(n\) divides \(a\) or \(n\) divides \(b\), then Player 1 wins.
If \(n\) divides neither \(a\) nor \(b\), then Player 2 wins.
Play this game against a partner a few times, to get a feel for the rules. You might want to swap so that you each experience being Player 1 and Player 2. Can you find a winning strategy for Player 1? Can you find a winning strategy for Player 2?
Why does your strategy work? Are you sure that it works? There are some suggestions below that might help you to structure your proof, but do try to come up with your own ideas before you look below.
You should be really careful that you use only facts about primes and integers that you can prove for yourself. Otherwise you run the risk of having a circular argument: you use some fact to prove your conjecture in this question, and then use the result in this question to prove that fact.
Tip: here’s some conventional notation that you might find useful while working on this problem.
If \(a\) and \(b\) are integers, then we might write \(a \mid b\) (the symbol in the middle is a vertical line) to mean “\(a\) divides \(b\)”. More formally, that tells us that there is some integer \(c\) such that \(b = ac\). If you’re reading \(a \mid b\) out loud, then you should say “\(a\) divides \(b\)”.
If it is not true that \(a\) divides \(b\), then we can write \(a \not\mid b\) (that is, a vertical line with a little dash through it), and we’d read that as “\(a\) does not divide \(b\)”.
Be careful to get the symbols in the right order! It is true that \(3 \mid 12\), but it is definitely not true that \(12 \mid 3\) (in fact, \(12 \not\mid 3\)).
On this page, we’ve written things out in words rather than using this notation, but you might like to use it in your own working.