การหารเหลือเศษ

[Hutchjang]

รบกวนสอบถามวิธีคิดข้อนี้ครับ แนวคิดมันเป็นยังไงครับ กำลังมันเยอะๆอย่างงี้ต้องทำอย่างไรครับ

ปล.ได้โจทย์มาจาก FB ห้องคณิตมัธยมปลายครับ

[gon]

ข้อนี้คิดออกหรือยังครับ

[Hutchjang]

ข้อความเดิมเขียนโดยคุณ gon

ข้อนี้คิดออกหรือยังครับ

ยังไม่ทราบแนวคิดเลยครับผม

[gon]

ข้อความเดิมเขียนโดยคุณ Hutchjang

ยังไม่ทราบแนวคิดเลยครับผม

ดูจากลักษณะของโจทย์แล้วน่าจะใช้แนวคิดจาก Fermat's Little Theorem ครับ

ประมาณว่า $a^{p - 1} \equiv 1\mod p$ เมื่อ $p$ เป็นจำนวนเฉพาะและ $(a, p) = 1$

ลองดูทฤษฎีบทนี้เพิ่มเติมนะครับ น่าจะไปต่อได้

[Anton]

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$.