อ้างอิง:
|
Problem. Determine the number of positive integers $n<180$ such that the remainder of $(n^3+3n+1)^{180}$ when divided by $180$ is equal to $1$.
|
Note that $180=2^2\cdot 3^2\cdot 5$. Therefore,
$$\lambda(180)=\operatorname{lcm}\big(\phi(2^2),\phi(3^2),\phi(5)\big)=\operatorname{lcm}(2,6,4)=12\,.$$
Here, $\operatorname{lcm}$ is the least-common-multiple function, $\phi$ is Euler's totient function, and $\lambda$ is the Carmichael function. Therefore,
$$x^{12}\equiv 1\pmod{180}$$
for any integer $x$ divisible by none of $2$, $3$, and $5$. Therefore, it follows immediately that, for any $x\in\mathbb{Z}$, $x^{180}\equiv 1\pmod{180}$ if and only if $x$ is not divisible by $2$, $3$, or $5$.
Therefore, we need to find the number of positive integers $n$ such that $n<180$ and $$\gcd(n^3+3n+1,2\cdot3\cdot5)=1\,.$$ Note that $n^3+3n+1$ is always odd for any integer $n$. Furthermore, $$n^3+3n+1\equiv n^3+1\equiv (n+1)^3\pmod{3}\,,$$ whence $n^3+3n+1$ is not divisible by $3$ if and only if $n\equiv 0,1\pmod{3}$. Finally, $$n^3+3n+1\equiv (n-1)(n^2+n-1)\equiv (n-1)(n-2)^2\pmod{5}$$ implies that $n^3+3n+1$ is not divisible by $5$ if and only if $n\equiv 0,3,4\pmod{5}$. Therefore, $(n^3+3n+1)^{180}\equiv 1\pmod{180}$ if and only if
$$n\equiv 0,3,4,9,10,13\pmod{15}\,.$$
There are $\dfrac{6}{15}\cdot 180-1=72-1=71$ such positive integers less than $180$.