#1
|
|||
|
|||
การหารเหลือเศษ
รบกวนสอบถามวิธีคิดข้อนี้ครับ แนวคิดมันเป็นยังไงครับ กำลังมันเยอะๆอย่างงี้ต้องทำอย่างไรครับ ปล.ได้โจทย์มาจาก FB ห้องคณิตมัธยมปลายครับ |
#2
|
||||
|
||||
ข้อนี้คิดออกหรือยังครับ
|
#3
|
|||
|
|||
|
#4
|
||||
|
||||
ดูจากลักษณะของโจทย์แล้วน่าจะใช้แนวคิดจาก Fermat's Little Theorem ครับ
ประมาณว่า $a^{p - 1} \equiv 1\mod p$ เมื่อ $p$ เป็นจำนวนเฉพาะและ $(a, p) = 1$ ลองดูทฤษฎีบทนี้เพิ่มเติมนะครับ น่าจะไปต่อได้
__________________
The Lost Emic <<-- หนังสือเฉลยข้อสอบระดับประถมนานาชาติ EMIC ครั้งที่ 1 - ครั้งที่ 8 ชุดสุดท้าย หลงมา 26 กรกฎาคม 2019 20:45 : ข้อความนี้ถูกแก้ไขแล้ว 2 ครั้ง, ครั้งล่าสุดโดยคุณ gon |
#5
|
||||
|
||||
อ้างอิง:
$$\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$.
__________________
Потом доказывай, что ты не верблюд. 28 กรกฎาคม 2020 21:22 : ข้อความนี้ถูกแก้ไขแล้ว 5 ครั้ง, ครั้งล่าสุดโดยคุณ Anton |
|
|