Định Lý Fermat Và Định Lý Euler Trong Lý Thuyết Số

by Thầy Đông · January 7, 2026

Rate this post

Định lý Fermat và Định lý Euler là hai kết quả nền tảng trong lĩnh vực Lý thuyết Số, cung cấp những hiểu biết sâu sắc về tính chất của các số nguyên và phép toán đồng dư. Hiểu rõ hai định lý này không chỉ mở ra cánh cửa khám phá nhiều bài toán số học thú vị mà còn ứng dụng rộng rãi trong mật mã học và khoa học máy tính. Bài viết này sẽ đi sâu vào Định lý Fermat và Định lý Euler, phân tích chi tiết, kèm theo các ví dụ minh họa và hướng dẫn giải bài tập để bạn đọc có thể nắm vững kiến thức.

Đề Bài

1. Định lý Fermat Nhỏ (Little Fermat Theorem):
Cho $p$ là một số nguyên tố và $a$ là một số nguyên không chia hết cho $p$. Khi đó, ta có:
$a^{p-1} equiv 1 pmod{p}</code> Một trường hợp tổng quát hơn là: với mọi số nguyên $a$ và mọi số nguyên tố $p$, ta có: <code>[]a^p equiv a pmod{p}</code> 2. Định lý Euler (Euler's Totient Theorem): Cho hai số nguyên dương $a$ và $n$ nguyên tố cùng nhau (tức là <code>[]\text{gcd}(a, n) = 1</code> ). Khi đó, ta có: <code>[]a^{phi(n)} equiv 1 pmod{n}</code> Trong đó, <code>[]phi(n)</code> là hàm phi Euler, đếm số các số nguyên dương nhỏ hơn hoặc bằng $n$ và nguyên tố cùng nhau với $n$. 3. Bài Tậpminh Họa: Bài 1: Chứng minh rằng với mọi số nguyên $a$, <code>[]a^7 - a</code> chia hết cho 42. Bài 2: Tìm số dư của <code>[]3^{100}</code> khi chia cho 35. Bài 3: Cho $p$ là một số nguyên tố lẻ. Chứng minh rằng <code>[]a^{p-1} equiv 1 pmod{p}</code> với mọi số nguyên $a$ không chia hết cho $p$. (Đây là phát biểu của Định lý Fermat Nhỏ). Bài 4: Cho []n = 10$ . Tìm $phi(10)</code> và sử dụng Định lý Euler để tính số dư của <code>[]3^{100}</code> khi chia cho 10. Bài 5: Tìm số dư của <code>[]2^{1000}</code> khi chia cho 13. <img width="800" height="495" src="https://dehocsinhgioi.com/wp-content/uploads/2026/01/5365811_cover.jpg" class="aligncenter aiagcs-inserted-image" alt="Định Lý Fermat Và Định Lý Euler Trong Lý Thuyết Số" /> <h2>Phân Tích Yêu Cầu</h2> Các bài toán trên tập trung vào việc áp dụng Định lý Fermat Nhỏ và Định lý Euler để giải quyết các bài toán về đồng dư thức, đặc biệt là tính toán lũy thừa lớn modulo một số. <ul> <li>Bài 1: Yêu cầu chứng minh một biểu thức chia hết cho một hợp số (42 = 2 3 7). Cần áp dụng định lý cho từng thừa số nguyên tố của 42.</li> <li>Bài 2: Yêu cầu tính số dư của một lũy thừa lớn. Cần xác định xem có thể áp dụng Định lý Euler hay không.</li> <li>Bài 3: Yêu cầu chứng minh lại một trường hợp cụ thể của Định lý Fermat Nhỏ.</li> <li>Bài 4: Yêu cầu tính hàm phi Euler và áp dụng Định lý Euler cho một trường hợp cụ thể.</li> <li>Bài 5: Tương tự Bài 2, yêu cầu tính số dư của lũy thừa lớn. Cần xác định số nguyên tố $p$ và áp dụng Định lý Fermat Nhỏ.</li> </ul> Nhìn chung, các bài toán yêu cầu sự hiểu biết về định nghĩa, điều kiện áp dụng và cách vận dụng hai định lý này vào việc đơn giản hóa các phép tính đồng dư. <h2>Kiến Thức/Nền Tảng Cần Dùng</h2> Để giải quyết các bài toán liên quan đến Định lý Fermat và Định lý Euler, chúng ta cần nắm vững các khái niệm và công cụ sau: <ol> <li>Số Nguyên Tố: Một số tự nhiên lớn hơn 1, chỉ có hai ước số dương là 1 và chính nó (ví dụ: 2, 3, 5, 7, 11, 13...).</li> <li>Hợp Số: Một số tự nhiên lớn hơn 1, không phải là số nguyên tố (có nhiều hơn hai ước số dương).</li> <li>Ước Chung Lớn Nhất (GCD): Cho hai số nguyên $a, b$, <code>[]\text{gcd}(a, b)</code> là số nguyên dương lớn nhất chia hết cả $a$ và $b$. Hai số nguyên tố cùng nhau nếu <code>[]\text{gcd}(a, b) = 1</code>.</li> <li>Đồng Dư Thức: []a equiv b pmod{n}$ nghĩa là $a$ và $b$ có cùng số dư khi chia cho $n$, hay $n</code> chia hết <code>[]a - b</code>. <ul> <li>Các tính chất cơ bản: <ul> <li>Nếu <code>[]a equiv b pmod{n}</code> và <code>[]c equiv d pmod{n}</code>, thì: <ul> <li><code>[]a + c equiv b + d pmod{n}</code></li> <li><code>[]a - c equiv b - d pmod{n}</code></li> <li><code>[]a \times c equiv b \times d pmod{n}</code></li> <li><code>[]a^k equiv b^k pmod{n}</code> với $k$ là số nguyên dương.</li> </ul> </li> </ul> </li> </ul> </li> <li>Phép Chia Hết: <code>[]a</code> chia hết cho $b$ (ký hiệu <code>[]b | a</code>) nghĩa là tồn tại số nguyên $k$ sao cho <code>[]a = bk</code>. Điều này tương đương với <code>[]a equiv 0 pmod{b}</code>.</li> <li>Phân Tích Số Nguyên Tố: Biểu diễn một số tự nhiên dưới dạng tích của các số nguyên tố. Ví dụ: <code>[]42 = 2 \times 3 \times 7</code>.</li> <li>Hàm Phi Euler <code>[]phi(n)</code>: <ul> <li>Nếu $p$ là số nguyên tố, <code>[]phi(p) = p - 1</code>.</li> <li>Nếu $p$ là số nguyên tố và []k \ge 1$ , $phi(p^k) = p^k - p^{k-1} = p^k(1 - 1/p)</code>.</li> <li>Nếu <code>[]\text{gcd}(m, n) = 1</code>, thì <code>[]phi(mn) = phi(m)phi(n)</code>.</li> <li>Công thức tổng quát cho <code>[]n = p_1^{k_1} p_2^{k_2} \ldots p_r^{k_r}</code> là <code>[]phi(n) = n prod_{i=1}^r (1 - \frac{1}{p_i}) = n \frac{p_1-1}{p_1} \frac{p_2-1}{p_2} \ldots \frac{p_r-1}{p_r}</code>.</li> </ul> </li> </ol> <h3>Định lý Fermat Nhỏ (Little Fermat Theorem):</h3> Cho $p$ là một số nguyên tố và $a$ là một số nguyên không chia hết cho $p$. Khi đó, ta có: <code>[]a^{p-1} equiv 1 pmod{p}</code> Lưu ý: Nếu $a$ chia hết cho $p$, tức là <code>[]a equiv 0 pmod{p}</code>, thì <code>[]a^{p-1} equiv 0 pmod{p}</code> (với []p-1 \ge 1$ ). Tuy nhiên, trường hợp tổng quát $a^p equiv a pmod{p}</code> vẫn đúng cho mọi số nguyên $a$ và mọi số nguyên tố $p$. <h3>Định lý Euler (Euler's Totient Theorem):</h3> Cho hai số nguyên dương $a$ và $n$ nguyên tố cùng nhau (tức là <code>[]\text{gcd}(a, n) = 1</code> ). Khi đó, ta có: <code>[]a^{phi(n)} equiv 1 pmod{n}</code> Mối quan hệ: Định lý Fermat Nhỏ là một trường hợp đặc biệt của Định lý Euler. Khi $n$ là một số nguyên tố $p$, thì <code>[]phi(p) = p - 1</code>. Do đó, nếu <code>[]\text{gcd}(a, p) = 1</code> (tức $p$ không chia hết $a$), thì Định lý Euler trở thành <code>[]a^{phi(p)} equiv 1 pmod{p}</code>, hay <code>[]a^{p-1} equiv 1 pmod{p}</code>, chính là Định lý Fermat Nhỏ. <h2>Hướng Dẫn Giải Chi Tiết</h2> Bài 1: Chứng minh rằng với mọi số nguyên $a$, <code>[]a^7 - a</code> chia hết cho 42. Phân tích: Ta cần chứng minh <code>[]a^7 - a equiv 0 pmod{42}[]. Vì</code>[]42 = 2 \times 3 \times 7<code>, và 2, 3, 7 là các số nguyên tố đôi một nguyên tố cùng nhau, ta chỉ cần chứng minh</code>[]a^7 - a` chia hết cho 2, 3 và 7. <ul> <li> Chứng minh chia hết cho 2: <ul> <li>Nếu$ a $chẵn, <code>[]a equiv 0 pmod{2}</code>. Suy ra `[]a^7 - a equiv 0^7 - 0 equiv 0 pmod{2}$ .

Nếu $a$ lẻ,  $a equiv 1 pmod{2}</code>. Suy ra `[]a^7 - a equiv 1^7 - 1 equiv 1 - 1 equiv 0 pmod{2}[].</li> <li>Hoặc dùng Định lý Fermat Nhỏ với$ p=2 $: <code>[]a^2 equiv a pmod{2}</code>. Ta có <code>[]a^7 - a = a(a^6 - 1)</code>. Nếu$ a equiv 0 pmod{2} $thì <code>[]a^7 - a equiv 0 pmod{2}$ . Nếu  $a equiv 1 pmod{2}$  thì $a^7 - a equiv 1^7 - 1 equiv 0 pmod{2}[].</li> <li>Hoặc cách khác: <code>[]a^7 = a^2 \cdot a^2 \cdot a^2 \cdot a equiv a \cdot a \cdot a \cdot a = a^4 equiv a^2 \cdot a^2 equiv a \cdot a = a^2 equiv a pmod{2}</code>. Vậy `[]a^7 - a equiv 0 pmod{2}$ .

Chứng minh chia hết cho 3:

Dùng Định lý Fermat Nhỏ với $p=3$ : Với mọi số nguyên $a$, ta có $a^3 equiv a pmod{3}</code>.</li> <li>Từ đó suy ra: `[]a^7 = a^{3 \times 2 + 1} = (a^3)^2 \cdot a equiv a^2 \cdot a = a^3 equiv a pmod{3}[].</li> <li>Vậy `[]a^7 - a equiv a - a equiv 0 pmod{3}$ .

Chứng minh chia hết cho 7:

Dùng Định lý Fermat Nhỏ với $p=7$ : Với mọi số nguyên $a$ không chia hết cho 7, ta có ` $a^{7-1} equiv a^6 equiv 1 pmod{7}[].</li> <li>Suy ra <code>[]a^7 = a^6 \cdot a equiv 1 \cdot a equiv a pmod{7}</code>.</li> <li>Trường hợp$ a $chia hết cho 7: <code>[]a equiv 0 pmod{7}$ . Khi đó

 $a^7 - a equiv 0^7 - 0 equiv 0 pmod{7}[].</li> <li>Như vậy, <code>[]a^7 equiv a pmod{7}</code> với mọi số nguyên$ a $.</li> <li>Do đó, `[]a^7 - a equiv 0 pmod{7}$ .Kết luận: Vì  $a^7 - a</code> chia hết cho 2, 3 và 7, và <code>[]\text{gcd}(2, 3, 7) = 1</code>, nên <code>[]a^7 - a</code> chia hết cho <code>[]2 \times 3 \times 7 = 42</code>.</p> <p><strong>Mẹo kiểm tra:</strong> Kiểm tra với một vài giá trị của $a$.</p> <ul> <li>Nếu []a=1$ :  $1^7 - 1 = 0</code>, chia hết cho 42.</li> <li>Nếu []a=2$ :  $2^7 - 2 = 128 - 2 = 126</code>. <code>126 / 42 = 3</code>. Chia hết cho 42.</li> <li>Nếu []a=3$ :  $3^7 - 3 = 2187 - 3 = 2184</code>. <code>2184 / 42 = 52</code>. Chia hết cho 42.</li> </ul> <p><strong>Lỗi hay gặp:</strong> Quên kiểm tra trường hợp $a$ chia hết cho $p$ khi áp dụng Định lý Fermat Nhỏ cho <code>[]a^p equiv a pmod{p}</code>. Tuy nhiên, <code>a^p equiv a pmod{p}</code> đúng cho mọi $a$. Đối với <code>[]a^{p-1} equiv 1 pmod{p}</code> thì cần điều kiện <code>p</code> không chia hết <code>a</code>.</p> <hr /> <p><strong>Bài 2:</strong> Tìm số dư của <code>[]3^{100}</code> khi chia cho 35.</p> <p><strong>Phân tích:</strong> Ta cần tính <code>[]3^{100} pmod{35}[]. Ở đây, ta có</code>[]n = 35 = 5 \times 7<code>. Cả 5 và 7 đều là số nguyên tố. Ta sẽ áp dụng Định lý Euler. Trước hết, cần kiểm tra</code>[]\text{gcd}(3, 35)<code>. </code>[]\text{gcd}(3, 35) = 1<code>, vì 3 là số nguyên tố và 35 không chia hết cho 3. Ta cần tính</code>[]phi(35)<code>. Vì</code>[]35 = 5 \times 7<code>và</code>[]\text{gcd}(5, 7) = 1<code>, ta có: </code>[]phi(35) = phi(5) \times phi(7)<code>. Vì 5 và 7 là số nguyên tố,</code>[]phi(5) = 5 - 1 = 4<code>và</code>[]phi(7) = 7 - 1 = 6<code>. Vậy</code>[]phi(35) = 4 \times 6 = 24`.</p> <p>Theo Định lý Euler, vì <code>[]\text{gcd}(3, 35) = 1</code>, ta có: <code>[]3^{phi(35)} equiv 1 pmod{35}</code> <code>[]3^{24} equiv 1 pmod{35}</code>.</p> <p>Bây giờ, ta biểu diễn số mũ 100 theo 24: <code>[]100 = 24 \times 4 + 4</code>.</p> <p>Do đó: <code>[]3^{100} = 3^{24 \times 4 + 4} = (3^{24})^4 \times 3^4</code>.</p> <p>Áp dụng tính chất đồng dư: <code>[]3^{100} equiv (3^{24})^4 \times 3^4 pmod{35}</code> <code>[]3^{100} equiv (1)^4 \times 3^4 pmod{35}</code> <code>[]3^{100} equiv 1 \times 3^4 pmod{35}</code> <code>[]3^{100} equiv 3^4 pmod{35}</code>.</p> <p>Ta tính <code>[]3^4</code>: <code>[]3^4 = 81</code>.</p> <p>Cuối cùng, tìm số dư của 81 khi chia cho 35: <code>[]81 = 2 \times 35 + 11</code>. Vậy `[]81 equiv 11 pmod{35}$ .
Kết luận: Số dư của  $3^{100}</code> khi chia cho 35 là 11.</p> <p><strong>Mẹo kiểm tra:</strong></p> <ul> <li>Tính <code>[]3^{24} pmod{35}</code> để đảm bảo nó bằng 1.</li> <li>Kiểm tra lại <code>phi(35)</code> và phép chia 100 cho 24.</li> </ul> <p><strong>Lỗi hay gặp:</strong></p> <ul> <li>Sai sót khi tính <code>phi(n)</code> cho hợp số.</li> <li>Quên kiểm tra điều kiện <code>[]\text{gcd}(a, n) = 1</code> trước khi áp dụng Định lý Euler. Nếu <code>[]\text{gcd}(a, n) \ne 1</code>, ta không thể áp dụng trực tiếp Định lý Euler.</li> </ul> <hr /> <p><strong>Bài 3:</strong> Cho $p$ là một số nguyên tố lẻ. Chứng minh rằng <code>[]a^{p-1} equiv 1 pmod{p}</code> với mọi số nguyên $a$ không chia hết cho $p$.</p> <p><strong>Phân tích:</strong> Đây chính là phát biểu của Định lý Fermat Nhỏ, với điều kiện $p$ là số nguyên tố lẻ và $a$ không chia hết cho $p$. Ta có thể chứng minh nó bằng cách xây dựng tập hợp các số nguyên còn lại modulo $p$.</p> <p><strong>Chứng minh:</strong> Cho $p$ là một số nguyên tố lẻ. Xét tập hợp các số nguyên dương nhỏ hơn $p$: <code>[]S = {1, 2, 3, \ldots, p-1}</code>. Tập hợp này có <code>[]p-1</code> phần tử. Xét tập hợp các số nguyên dương nhân với $a$ (với $a$ không chia hết cho $p$), nhỏ hơn hoặc bằng []p-1$  và lấy modulo $p$:
 $aS = {a \cdot 1, a \cdot 2, a \cdot 3, \ldots, a \cdot (p-1)}</code>.</p> <p>Các phần tử trong tập hợp <code>[]aS</code> khi lấy modulo $p$ sẽ là: <code>[]{a pmod{p}, 2a pmod{p}, 3a pmod{p}, \ldots, (p-1)a pmod{p}}</code>.</p> <p>Ta cần chứng minh hai điều:</p> <ol> <li> <p><strong>Các phần tử trong <code>[]aS</code> khác nhau và không có phần tử nào bằng 0 modulo $p$:</strong></p> <ul> <li>Vì $a$ không chia hết cho $p$ và $p$ là số nguyên tố, nên <code>[]\text{gcd}(a, p) = 1</code>.</li> <li>Nếu <code>[]ka equiv la pmod{p}</code> với []1 \le k, l \le p-1$ , thì ta có thể nhân cả hai vế với nghịch đảo của $a$ modulo $p$ (tồn tại vì  $\text{gcd}(a, p) = 1</code>).</li> <li>Điều này suy ra `[]k equiv l pmod{p}$. Vì $1 \le k, l \le p-1$, nên điều này chỉ xảy ra khi $k=l[].</li> <li>Vậy, tất cả các phần tử <code>[]ka pmod{p}</code> cho$ k in {1, 2, ldots, p-1} $đều khác nhau.</li> <li>Hơn nữa, vì$ a notequiv 0 pmod{p}$ và $p $là nguyên tố, thì <code>[]ka notequiv 0 pmod{p}</code> với mọi$ k$ không chia hết cho $p $. Do đó, không có phần tử nào trong <code>[]aS</code> bằng 0 modulo$ p $.</li> </ul> </li> <li> <p><strong>Tập hợp <code>[]aS pmod{p}</code> là một hoán vị của tập hợp <code>[]S</code>:</strong></p> <ul> <li>Vì có <code>[]p-1</code> phần tử khác nhau và không có phần tử nào bằng 0 modulo$ p $, tập hợp <code>[]aS pmod{p}</code> phải bao gồm chính xác các số nguyên từ 1 đến$ p-1 $, nhưng có thể theo một thứ tự khác.</li> <li>Tức là, tập hợp <code>{a \cdot 1 pmod{p}, a \cdot 2 pmod{p}, \ldots, a \cdot (p-1) pmod{p}}</code> chính là tập hợp <code>{1, 2, \ldots, p-1}</code>.</li> </ul> </li> </ol> <p>Bây giờ, ta nhân tất cả các phần tử của hai tập hợp này lại với nhau: Tích các phần tử trong <code>[]S</code>: <code>[]1 \cdot 2 \cdot 3 cdots (p-1) = (p-1)!</code>. Tích các phần tử trong <code>[]aS</code>: <code>[](a \cdot 1) \cdot (a \cdot 2) cdots (a \cdot (p-1)) pmod{p}</code>. <code>[]= a^{p-1} \cdot (1 \cdot 2 cdots (p-1)) pmod{p}</code> <code>[]= a^{p-1} \cdot (p-1)! pmod{p}</code>.</p> <p>Vì hai tập hợp là hoán vị của nhau, nên tích của các phần tử của chúng cũng phải bằng nhau modulo$ p $: <code>[](p-1)! equiv a^{p-1} \cdot (p-1)! pmod{p}</code>.</p> <p>Vì <code>[](p-1)!</code> không chia hết cho$ p$ (vì $p$ là nguyên tố và các thừa số $1, 2, ldots, p-1$ đều nhỏ hơn $p $), ta có thể chia cả hai vế cho <code>[](p-1)!</code>: <code>[]1 equiv a^{p-1} pmod{p}</code>.</p> <p>Điều này hoàn thành chứng minh cho Định lý Fermat Nhỏ với điều kiện$ p$ là nguyên tố lẻ và $a$ không chia hết cho $p $.</p> <p><strong>Lưu ý:</strong> Trường hợp$ p=2 $là nguyên tố chẵn. Định lý Fermat Nhỏ phát biểu là <code>[]a^2 equiv a pmod{2}</code>.</p> <ul> <li>Nếu$ a $chẵn, <code>[]a equiv 0 pmod{2}</code>, thì `[]a^2 equiv 0^2 equiv 0 equiv a pmod{2}$ .
Nếu $a$ lẻ,  $a equiv 1 pmod{2}</code>, thì <code>[]a^2 equiv 1^2 equiv 1 equiv a pmod{2}[]. Vậy</code>[]a^2 equiv a pmod{2}<code>luôn đúng. Tuy nhiên, nếu áp dụng</code>[]a^{p-1} equiv 1 pmod{p}<code>với$ p=2 $, ta được</code>[]a^{2-1} equiv a^1 equiv 1 pmod{2}<code>. Điều này chỉ đúng khi$ a$ lẻ (tức $a equiv 1 pmod{2}$). Nếu $a$ chẵn ($a equiv 0 pmod{2} $), thì</code>[]a equiv 0 notequiv 1 pmod{2}$ . Do đó, điều kiện “$a$ không chia hết cho $p$” là quan trọng cho dạng  $a^{p-1} equiv 1 pmod{p}</code>.</li> </ul> <p><strong>Mẹo kiểm tra:</strong> Chứng minh này dựa trên lý luận về tập hợp và tính chất của phép nhân dưới modulo nguyên tố. Nó khá chặt chẽ.</p> <p><strong>Lỗi hay gặp:</strong> Quên hoặc hiểu sai điều kiện "$a$ không chia hết cho $p$" khi áp dụng `[]a^{p-1} equiv 1 pmod{p}[].</p> <hr /> <p><strong>Bài 4:</strong> Cho$ n = 10 $. Tìm <code>[]phi(10)</code> và sử dụng Định lý Euler để tính số dư của <code>[]3^{100}</code> khi chia cho 10.</p> <p><strong>Phân tích:</strong> Đầu tiên, ta cần tính <code>[]phi(10)</code>. Số 10 có các ước nguyên tố là 2 và 5 (<code>[]10 = 2 \times 5</code>). Sử dụng công thức <code>[]phi(mn) = phi(m)phi(n)</code> khi <code>[]\text{gcd}(m, n) = 1</code>: <code>[]phi(10) = phi(2 \times 5) = phi(2) \times phi(5)</code>. Vì 2 và 5 là số nguyên tố: <code>[]phi(2) = 2 - 1 = 1</code>. <code>[]phi(5) = 5 - 1 = 4</code>. Vậy, <code>[]phi(10) = 1 \times 4 = 4</code>.</p> <p><strong>Kiểm tra <code>phi(10)</code>:</strong> Các số nguyên dương nhỏ hơn hoặc bằng 10 và nguyên tố cùng nhau với 10 là: 1, 3, 7, 9. Có tất cả 4 số. <code>[]phi(10) = 4</code> là đúng.</p> <p>Bây giờ, ta áp dụng Định lý Euler để tính số dư của <code>[]3^{100}</code> khi chia cho 10. Ta cần kiểm tra <code>[]\text{gcd}(3, 10)</code>. <code>[]\text{gcd}(3, 10) = 1</code> (vì 3 là nguyên tố và 10 không chia hết cho 3). Theo Định lý Euler: <code>[]3^{phi(10)} equiv 1 pmod{10}</code> <code>[]3^4 equiv 1 pmod{10}</code>.</p> <p>Ta cần tính <code>[]3^{100} pmod{10}$ . Biểu diễn số mũ 100 theo 4:  $100 = 4 \times 25`.</p> <p>Do đó: <code>[]3^{100} = 3^{4 \times 25} = (3^4)^{25}</code>.</p> <p>Áp dụng tính chất đồng dư: <code>[]3^{100} equiv (3^4)^{25} pmod{10}</code> <code>[]3^{100} equiv (1)^{25} pmod{10}</code> <code>[]3^{100} equiv 1 pmod{10}</code>.</p> <p><strong>Kết luận:</strong> Số dư của <code>[]3^{100}</code> khi chia cho 10 là 1.</p> <p><strong>Mẹo kiểm tra:</strong></p> <ul> <li>Kiểm tra <code>phi(10)</code> bằng cách liệt kê các số nguyên tố cùng nhau.</li> <li>Kiểm tra <code>3^4 pmod{10}</code>. <code>[]3^4 = 81</code>, <code>81 equiv 1 pmod{10}</code>. Đúng.</li> <li>Kiểm tra phép chia 100 cho 4.</li> </ul> <p><strong>Lỗi hay gặp:</strong> Tính sai <code>phi(n)</code> hoặc nhầm lẫn giữa Định lý Fermat Nhỏ và Định lý Euler.</p> <hr /> <p><strong>Bài 5:</strong> Tìm số dư của <code>[]2^{1000}</code> khi chia cho 13.</p> <p><strong>Phân tích:</strong> Ta cần tính <code>[]2^{1000} pmod{13}$. Số 13 là một số nguyên tố. Ta có thể áp dụng Định lý Fermat Nhỏ. Điều kiện: $p = 13$ là số nguyên tố. Ta cần kiểm tra xem $a=2$ có chia hết cho $p=13[]không. Rõ ràng 2 không chia hết cho 13. Vậy, theo Định lý Fermat Nhỏ: </code>[]a^{p-1} equiv 1 pmod{p}<code> </code>[]2^{13-1} equiv 2^{12} equiv 1 pmod{13}$ .

Bây giờ, ta biểu diễn số mũ 1000 theo 12:
Ta thực hiện phép chia 1000 : 12.
$1000 = 12 \times q + r</code>. <code>[]1000 = 12 \times 83 + 4</code>. (Vì <code>[]12 \times 83 = 996</code>, <code>1000 - 996 = 4</code>). Do đó: <code>[]2^{1000} = 2^{12 \times 83 + 4} = (2^{12})^{83} \times 2^4</code>. Áp dụng tính chất đồng dư: <code>[]2^{1000} equiv (2^{12})^{83} \times 2^4 pmod{13}</code> <code>[]2^{1000} equiv (1)^{83} \times 2^4 pmod{13}</code> <code>[]2^{1000} equiv 1 \times 2^4 pmod{13}</code> `[]2^{1000} equiv 2^4 pmod{13}[]. Ta tính <code>[]2^4</code>: <code>[]2^4 = 16</code>. Cuối cùng, tìm số dư của 16 khi chia cho 13: <code>[]16 = 1 \times 13 + 3</code>. Vậy `[]16 equiv 3 pmod{13}$ .

Kết luận: Số dư của $2^{1000}</code> khi chia cho 13 là 3. Mẹo kiểm tra: <ul> <li>Kiểm tra xem 13 có phải là số nguyên tố không. Đúng.</li> <li>Kiểm tra xem 2 có chia hết cho 13 không. Không.</li> <li>Thực hiện phép chia 1000 cho 12 và kiểm tra số dư. <code>1000 / 12 = 83.33...</code>, <code>12 83 = 996</code>, <code>1000 - 996 = 4</code>. Đúng.</li> <li>Tính <code>2^4 = 16</code>, <code>16 pmod{13} = 3</code>. Đúng.</li> </ul> Lỗi hay gặp: <ul> <li>Nhầm lẫn giữa []p-1$ và $p$ trong số mũ.

Tính toán sai phép chia lấy dư khi biểu diễn số mũ.

Áp dụng Định lý Fermat Nhỏ khi $a$ chia hết cho $p$.

`Đáp Án/Kết Quả`

Bài 1: a^7 - a chia hết cho 42 với mọi số nguyên $a$.

Bài 2: Số dư của 3^{100} khi chia cho 35 là 11.

Bài 3: Chứng minh Định lý Fermat Nhỏ a^{p-1} equiv 1 pmod{p} với $p$ nguyên tố, $p$ lẻ, và $a$ không chia hết cho $p$.

Bài 4: phi(10) = 4. Số dư của 3^{100} khi chia cho 10 là 1.

Bài 5: Số dư của 2^{1000} khi chia cho 13 là 3.

`Conclusion`

Định lý Fermat Nhỏ và Định lý Euler là những công cụ mạnh mẽ để giải quyết các bài toán đồng dư thức, đặc biệt là với các lũy thừa lớn. Chúng cung cấp một phương pháp hệ thống để đơn giản hóa các biểu thức phức tạp, giúp chúng ta tính toán số dư một cách hiệu quả. Việc nắm vững điều kiện áp dụng và cách sử dụng hai định lý này, cùng với kiến thức về hàm phi Euler và tính chất của số nguyên tố, sẽ trang bị cho bạn khả năng giải quyết nhiều dạng bài tập số học trong chương trình học và thi cử. Hãy thường xuyên luyện tập với các bài toán khác nhau để củng cố kiến thức và nâng cao kỹ năng.

Ngày chỉnh sửa nội dung mới nhất January 7, 2026 by Thầy Đông

Thầy Đông

Thầy Đông – Giảng viên Đại học Công nghiệp Hà Nội, giáo viên luyện thi THPT Thầy Đông bắt đầu sự nghiệp tại một trường THPT ở quê nhà, sau đó trúng tuyển giảng viên Đại học Công nghiệp Hà Nội nhờ chuyên môn vững và kinh nghiệm giảng dạy thực tế. Với nhiều năm đồng hành cùng học sinh, thầy được biết đến bởi phong cách giảng dạy rõ ràng, dễ hiểu và gần gũi. Hiện thầy giảng dạy tại dehocsinhgioi, tiếp tục truyền cảm hứng học tập cho học sinh cấp 3 thông qua các bài giảng súc tích, thực tiễn và giàu nhiệt huyết.