*

Let $n \geqslant 3$ be a natural number. Let $x$ and $y$ be distinct natural numbers, between 1 and $n-1$. We say that $x$ and $y$ are friends if there exist natural numbers $a$ and $b$ such that $a x=b y \neq 0(\bmod n)$.

Determine the values of $n$ for which each integer between 1 and $n-1$ has an even number of friends between 1 and $n-1$.

Solved by Gaëtan Dautzenberg and Georges Tézé
** solved by Gaëtan Dautzenberg and Georges Tézé

Let's start by showing that $x$ and $y$ are friends if and only if $n \nmid \operatorname{ppcm}(x, y)$. First, if $n \nmid \operatorname{ppcm}(x, y)$, we can take $a = \operatorname{ppcm}(x, y) / x$ and $b = \operatorname{ppcm}(x, y) / y$ to have $a x = b y \not\equiv 0 \pmod{n}$, and $x$ and $y$ are friends. On the other hand, if $n \mid \operatorname{ppcm}(x, y)$, let $a$ and $b$ be such that $a x = b y$. This common value is a multiple of $x$ and $y$, and thus of $n$. Therefore, $a x = b y \equiv 0 \pmod{n}$, and $x$ and $y$ are not friends.

The number 1 is a friend with all numbers $y$ between 2 and $n-1$ by taking $b=1$ and $a=y$. If $n$ satisfies the condition in the statement, it is therefore even.

Suppose that $n$ is a multiple of an odd prime. Write $n = 2^s q$ with $q$ odd and $s \geq 1$. We have $n \mid \operatorname{ppcm}(2^s, y) \Longleftrightarrow q \mid y$. Therefore, the friends of $2^s$ are the numbers between 1 and $n-1$ except $2^s$ and the $2^s - 1$ multiples of $q$ between 1 and $n-1$. This results in an odd number of friends for $2^s$. Thus, only powers of 2 can be the numbers sought in the statement.

If $n = 2^s$ with $s \geq 1$ and if $x, y$ are between 1 and $n-1$, we have $x = 2^{s_1} q_1$ and $y = 2^{s_2} q_2$ with $s_1, s_2 < s$

![](https://cdn.mathpix.com/cropped/2024_05_10_10c029b6c4865f8b8ca3g-421.jpg?height=63&width=1699&top_left_y=662&top_left_x=181)
each number is a friend with all other numbers between 1 and $n-1$, which gives it an even number of friends.

Thus, the numbers sought are the $2^s$ with $s \geq 1$.