# Coprime Game I

**Number Theory**Level 5

Let \( N \ge 2 \) be a positive integer. Dan and Sam play the following coprime game: starting with the set \( C_N \) of coprime positive integers of \( N\) that are less than \( N\), the players take turns removing some elements from the set. At a player's turn, he chooses a number \( m\) that remains, and removes \(m \) and any integer that is **not** coprime of \(m \) that remains. The player who moves last loses.

For example: \( N =7, C_N = \{ 1,2,3,4,5,6\} \). Dan chooses \( m=6 \), so he removes \( 2 \), \(4\), \(3\) and \( 6 \). The remaining set is \( \{1,5\} \). Sam chooses \( m=5 \). The remaining set is \( \{1\} \). Dan is forced to take \( 1\), so he loses.

Let \( n \ge 2 \) be the largest positive integer \( \le 200 \) such that if Dan and Sam play the divisor game for \( n \) and both of them play optimally, the second player wins. Find \( n \). If no such \( n \) exists, enter \(1\).

###### This is the eighteenth problem of the set Winning Strategies.

**Your answer seems reasonable.**Find out if you're right!

**That seems reasonable.**Find out if you're right!

Already have an account? Log in here.