Question

Let $f(x) = x^2 - 45x + 2$.

Find number of integers $n \ge 2$ such that exactly one of the number $f(1), f(2),....f(n)$ is divisible by $n$.

• A. 1
• B. 2
• C. 3
• D. 4

Answer 1

Answer: (B)

2

Answer 2

We are looking for the number of integers $n \ge 2$ such that there is a unique $k \in \{1, 2, \dots, n\}$ for which $f(k) \equiv 0 \pmod{n}$. The condition is $k^2 - 45k + 2 \equiv 0 \pmod{n}$.

First, consider the case when $n$ is even. Let $n=2m$. $f(x) = x^2 - 45x + 2 \equiv x^2 - x \pmod{2}$. Since $x^2 - x = x(x-1)$ is always even, $f(x)$ is always divisible by 2 for any integer $x$. If $n$ is even, then $f(x) \equiv 0 \pmod{2}$ for all $x$. If there exists a $k$ such that $f(k) \equiv 0 \pmod{n}$, then $f(k)$ is divisible by $n$. Since $n$ is even, $f(k)$ is divisible by 2, which is always true. However, we need exactly one such $k$. For $n=2$, $f(1) = 1 - 45 + 2 = -42 \equiv 0 \pmod{2}$ and $f(2) = 4 - 90 + 2 = -84 \equiv 0 \pmod{2}$. Both are divisible by 2, so $n=2$ is not a solution. For any even $n$, $f(x)$ is always even. It is difficult to ensure that $f(k) \equiv 0 \pmod{n}$ for exactly one $k$. This suggests $n$ must be odd.

Now, let $n$ be an odd integer, $n \ge 3$. We can complete the square for $k^2 - 45k + 2 \equiv 0 \pmod{n}$. Multiplying by 4 (since $n$ is odd, $\gcd(4, n)=1$), we get: $4k^2 - 180k + 8 \equiv 0 \pmod{n}$ $(2k)^2 - 2(2k)(45) + 45^2 - 45^2 + 8 \equiv 0 \pmod{n}$ $(2k - 45)^2 \equiv 45^2 - 8 \pmod{n}$ $(2k - 45)^2 \equiv 2025 - 8 \pmod{n}$ $(2k - 45)^2 \equiv 2017 \pmod{n}$.

Let $y = 2k - 45$. As $k$ ranges over $\{1, 2, \dots, n\}$, $y$ also ranges over all $n$ distinct residues modulo $n$ because $n$ is odd. So, the problem is equivalent to finding the number of odd $n \ge 3$ such that the congruence $y^2 \equiv 2017 \pmod{n}$ has exactly one solution for $y \in \{0, 1, \dots, n-1\}$.

Let $N(a, n)$ be the number of solutions to $y^2 \equiv a \pmod{n}$. We need $N(2017, n) = 1$. Let the prime factorization of $n$ be $n = p_1^{a_1} \cdots p_r^{a_r}$. Then $N(2017, n) = N(2017, p_1^{a_1}) \cdots N(2017, p_r^{a_r})$. For $N(2017, n) = 1$, we need $N(2017, p_i^{a_i}) = 1$ for all $i$.

Consider the congruence $y^2 \equiv a \pmod{p^k}$ where $p$ is an odd prime.

• If $p \nmid a$: $N(a, p^k) = 2$ if $(a/p)=1$, and $N(a, p^k) = 0$ if $(a/p)=-1$.
• If $p | a$: Let $a = p^s b$ with $p \nmid b$.
  • If $s \ge k$: $a \equiv 0 \pmod{p^k}$. $y^2 \equiv 0 \pmod{p^k}$.
    • For $k=1$, $y^2 \equiv 0 \pmod p$ has exactly one solution $y \equiv 0 \pmod p$. So $N(0, p)=1$.
    • For $k \ge 2$, $y^2 \equiv 0 \pmod{p^k}$ has two solutions: $y \equiv 0 \pmod{p^{\lceil k/2 \rceil}}$. These are $y=0$ and $y=p^{\lceil k/2 \rceil}$ modulo $p^k$. So $N(0, p^k)=2$ for $k \ge 2$.
  • If $s < k$: $y^2 \equiv p^s b \pmod{p^k}$.
    • If $s$ is odd, there are no solutions.
    • If $s$ is even, $s=2m$. Then $y^2 \equiv p^{2m} b \pmod{p^k}$. This implies $p^m | y$. Let $y=p^m z$. $p^{2m} z^2 \equiv p^{2m} b \pmod{p^k} \implies z^2 \equiv b \pmod{p^{k-2m}}$. Since $p \nmid b$, this congruence has 2 solutions if $(b/p)=1$ and 0 solutions if $(b/p)=-1$. This requires $k-2m \ge 1$.

Therefore, for $N(a, p^k)=1$, we must have $k=1$ and $p|a$ (i.e., $s \ge 1$).

Now, we need to determine if 2017 is prime. Checking divisibility by primes up to $\sqrt{2017} \approx 45$, we find that 2017 is prime. So, for $N(2017, n)=1$, where $n=p_1^{a_1} \cdots p_r^{a_r}$, we must have $N(2017, p_i^{a_i})=1$ for each $i$. This implies that for each prime factor $p_i$ of $n$, we must have $a_i=1$ and $p_i | 2017$. Since 2017 is prime, the only prime factor is 2017 itself. Thus, $n$ must be of the form $2017^1$. So $n=2017$ is a possible solution. Let's check $n=2017$. $y^2 \equiv 2017 \pmod{2017} \implies y^2 \equiv 0 \pmod{2017}$. Since 2017 is prime, this has a unique solution $y \equiv 0 \pmod{2017}$. So $n=2017$ is a solution.

Now consider the case where $n$ is even. We already showed that $n$ cannot be divisible by 4 or higher powers of 2. So, if $n$ is even, it must be $n=2m$, where $m$ is odd. $N(2017, n) = N(2017, 2) \cdot N(2017, m)$. We need $N(2017, 2)=1$ and $N(2017, m)=1$. For $n=2$, $y^2 \equiv 2017 \equiv 1 \pmod 2$. The solution is $y \equiv 1 \pmod 2$. So $N(2017, 2)=1$. For $m$ to satisfy $N(2017, m)=1$, $m$ must be odd. As shown above, the only odd solution for $m$ is $m=2017$. So, $n = 2 \times 2017 = 4034$ is another potential solution. Let's check $n=4034$. We need $y^2 \equiv 2017 \pmod{4034}$. This is equivalent to the system:

1. $y^2 \equiv 2017 \pmod{2} \implies y^2 \equiv 1 \pmod{2} \implies y \equiv 1 \pmod{2}$.
2. $y^2 \equiv 2017 \pmod{2017} \implies y^2 \equiv 0 \pmod{2017} \implies y \equiv 0 \pmod{2017}$. By the Chinese Remainder Theorem, there is a unique solution modulo $2 \times 2017 = 4034$. $y = 2017k$. Substituting into the first congruence: $2017k \equiv 1 \pmod{2} \implies k \equiv 1 \pmod{2}$. So $k=1$, which gives $y = 2017$. Thus, $n=4034$ is a solution.

The possible values for $n$ are $2017$ and $4034$. There are 2 such integers.