Determine for how many positive integers $n\in\{1, 2, \ldots, 2022\}$ it holds that $402$ divides at least one of \[n^2-1, n^3-1, n^4-1\]
Problem
Source: Cyprus 2022 TST-2 Problem 2
Tags: number theory
21.02.2022 23:00
I claim the answer is $31$ Note that $402 = 2\cdot 3\cdot 67$. From here, we immediately obtain that $n\equiv 1\pmod{2}$. Next, assume $402\mid n^2-1$. Then, $n\in\{1,2\}\pmod{3}$ and $n\in\{\pm 1\}\pmod{67}$. There are four such residue classes in modulo $402$. Likewise, if $402\mid n^4-1=(n^2-1)(n^2+1)$, then we must have (a) $n\in\{1,2\}\pmod{3}$; and (b) $67\mid n^2-1$. Indeed, the last conclusion is due to the fact that $67\nmid n^2+1$ since $67$ is a prime of form $4k+3$. This is the same residue classes as above. Finally, if $402\mid n^3-1=(n-1)(n^2+n+1)$, then $n\equiv 1\pmod{3}$ and if $n\not\equiv 1\pmod{67}$, we must have $67\mid n^2+n+1\implies 67\mid (2n+1)^2+3$. Thus, $2n+1\equiv \pm 8\pmod{67}\iff n\in\{29,37\}\pmod{67}$. This brings two extra residue classes modulo $402$, thus a total of $6$. Now that $\lfloor 2022/402\rfloor=5$, we obtain that among $\{1,2,\dots,2010\}$, there are $30$ such numbers. Our final focus is on $\{2011,\dots,2022\}$. From here, $2011$ is the only such number satisfying the modulo $3\cdot 67$ condition.
21.02.2022 23:39
@above you can't have $n \equiv 2 \pmod{3}$ and $n \equiv 29, 37 \pmod{67}$, so there are $6$ residue classes.
22.02.2022 02:35
No, you certainly can: if $n\equiv 2\pmod{3}$, then $3\mid n^2-1$. Likewise, if $n\in\{29,37\}$ then $67\mid n^2+n+1\implies 67\mid n^3-1$. Edit. I was wrong, thx to poster below. See my updated solution above.
22.02.2022 03:24
The problem asks for $402$ to divide at least one of $n^2-1$, $n^3-1$, $n^4-1$, not their product.