Problem 1649

1. Assume the contrary: Suppose it is possible to color all integers greater than 1 in three colors (red, green, blue) such that the product of any two differently colored numbers is colored differently from each of the factors.

2. Define sets:
- Let $A = \{ x \in \mathbb{N} \setminus \{1\} \mid x \text{ is red} \}$
- Let $B = \{ y \in \mathbb{N} \setminus \{1\} \mid y \text{ is green} \}$
- Let $C = \{ z \in \mathbb{N} \setminus \{1\} \mid z \text{ is blue} \}$

From the problem statement, we have:
$$A \cup B \cup C = \mathbb{N} \setminus \{1\}$$
$$A \cap B = A \cap C = B \cap C = \emptyset$$
$$x \in A, y \in B \implies xy \in C$$
$$x \in A, z \in C \implies xz \in B$$
$$y \in B, z \in C \implies yz \in A$$

3. Claim 1: Let $p \in A$ be a prime number. Then $p^n \in A$ for all $n \in \mathbb{N}$.

Proof:
- Assume there exists $k \in \mathbb{N} \setminus \{1\}$ such that $p^k \in B$.
- Since $p \in A$ and $p^k \in B$, it follows that $p^{k+1} \in C$.
- Since $p \in A$ and $p^{k+1} \in C$, it follows that $p^{k+2} \in B$.
- By induction, $p^m \in B \cup C$ for all $m \ge k$.

On the other hand:
- Since $p^k \in B$ and $p^{k+1} \in C$, it follows that $p^{2k+1} \in A$, which contradicts the previous statement that $p^m \in B \cup C$ for all $m \ge k$.

Hence, the assumption is false, and $p^n \in A$ for all $n \in \mathbb{N}$.

4. Claim 2: Let $p \in A$ be a prime number. Then $q^n \in A$ for all prime numbers $q$ and for all $n \in \mathbb{N}$.

Proof:
- Assume there exists a prime number $q$ such that $q \in B$.
- Since $p \in A$ and $q \in B$, it follows that $pq \in C$.
- Since $p \in A$ and $pq \in C$, it follows that $p^2q \in B$.
- By Claim 1, $p^2 \in A$.
- Since $p^2 \in A$ and $q \in B$, it follows that $p^2q \in C$, which contradicts the previous statement that $p^2q \in B$.

Hence, the assumption is false, and $q \in A$ for all prime numbers $q$.

5. Conclusion from Claims 1 and 2:
- All prime numbers and their powers belong to the same set $A$.

6. Contradiction:
- Assume $p^n \in A$ for all prime numbers $p$ and $n \in \mathbb{N}$, and let $N \in B$.
- Then $N$ can be expressed as $N = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_m^{\alpha_m}$ where $p_1, p_2, \ldots, p_m$ are pairwise distinct prime numbers and $\alpha_1, \alpha_2, \ldots, \alpha_m \in \mathbb{N}$.
- Since $p_1 \in A$ and $N \in B$, it follows that $p_1^{\alpha_1+1} p_2^{\alpha_2} \cdots p_m^{\alpha_m} \in C$.
- Since $N \in B$ and $p_1^{\alpha_1+1} p_2^{\alpha_2} \cdots p_m^{\alpha_m} \in C$, it follows that $p_1^{2\alpha_1+1} p_2^{2\alpha_2} \cdots p_m^{2\alpha_m} \in A$.

On the other hand:
- Since $p_1^{\alpha_1+1} \in A$ and $N \in B$, it follows that $p_1^{2\alpha_1+1} p_2^{\alpha_2} \cdots p_m^{\alpha_m} \in C$.
- Since $p_2^{\alpha_2} \in A$ and $p_1^{2\alpha_1+1} p_2^{\alpha_2} \cdots p_m^{\alpha_m} \in C$, it follows that $p_1^{2\alpha_1+1} p_2^{2\alpha_2} p_3^{\alpha_3} \cdots p_m^{\alpha_m} \in B$.

Using the same reasoning for $p_3^{\alpha_3}, \ldots, p_m^{\alpha_m} \in A$, we finally obtain $p_1^{2\alpha_1+1} p_2^{2\alpha_2} \cdots p_m^{2\alpha_m} \in B \cup C$, which contradicts the previous statement that $p_1^{2\alpha_1+1} p_2^{2\alpha_2} \cdots p_m^{2\alpha_m} \in A$.

Conclusion:
It is not possible to color all integers greater than 1 in three colors such that the color of the product of any two differently colored numbers is different from the color of each of the factors. $\blacksquare$