Cấp Của Một Số Nguyên, Căn Nguyên Thủy | Huy Cao's Blog

Có thể bạn quan tâm

By Đình Huy

Bài toán : Tìm số nguyên dương $n$ sao cho $n\mid 3^n-2^n$ .

Lời giải :

Hiển nhiên $n=1$ thỏa mãn. Xét $n\geq 2$ , khi đó $n$ có ước nguyên tố nhỏ nhất, gọi ước nguyên tố nhỏ nhất đó là $p$ .

Gọi $t\in \mathbb{N}$ là nghịch đảo của $2$ modulo $p$ , tức là $2t\equiv 1\;(mod\;p),1\leq t\leq p-1$ .

Ta có $3^{n}\equiv 2^{n}\;(mod\;p)\Rightarrow (3t)^{n}\equiv (2t)^{n}\equiv 1\;(mod\;p)\Rightarrow ord_p(3t)\mid n\;\;(1)$

Nếu $p=3$ thì $3\mid 3\Rightarrow 3\mid 3^{n}-2^{n}\Rightarrow 3\mid 2^n$ (vô lí). Vậy $p\neq 3$ và vì $1\leq t\leq p-1$ nên $gcd(t,p)=1\Rightarrow gcd(3t,p)=1$ .

Theo định lí $Fermat$ nhỏ, ta có $\left ( 3t \right )^{p-1}\equiv 1\;(mod\;p)\Rightarrow ord_p(3t)\mid p-1\;\;(2)$

Từ $(1)(2)$ suy ra $ord_p(3t)$ có một ước nguyên tố $r$ mà $r\mid n$ và $r\leq p-1<p$ . Điều này mâu thuẫn với tính nhỏ nhất của $p$ . Suy ra $ord_p(3t)=1\Rightarrow 3t\equiv 1\equiv 2t\;(mod\;p)\Rightarrow t\equiv 0\;(mod\;p)$

Ta gặp điều mâu thuẫn.

Kết luận : Có duy nhất một số nguyên dương $n$ thỏa đề là $n=1$ .

By Đình Huy

Bài toán : Cho $n$ là số nguyên dương thỏa mãn $n\mid 2^{n}+5^{n}$ . Chứng minh rằng $n$ chia hết cho $7$ .

Lời giải :

Dễ thấy $n$ là số nguyên dương lẻ. Gọi $p$ là ước nguyên tố bé nhất của $n$ .

Gọi $a$ là nghịch đảo của $2$ modulo $p$ . Khi đó thì $2a\equiv 1\;(mod\;p),gcd(2,a)=gcd(a,p)=1$ .

Ta có $p\mid 2^{n}+5^{n}\Rightarrow p\mid (2a)^n+(5a)^n\Rightarrow (2a)^n+(5a)^{n}\equiv (5a)^n+1\;(mod\;p)\Rightarrow -(5a)^n=(-5a)^n\equiv 1\;(mod\;p)\Rightarrow ord_p(-5a)\mid n\;\;\;\;(1)$

Dễ dàng thấy $gcd(5a,p)=1$ nên theo định lí $Fermat$ nhỏ ta có $(-5a)^{p-1}\equiv 1\;(mod\;p)\Rightarrow ord_p(-5a)\mid p-1\;\;\;\;(2)$

Từ $(1)(2)$ suy ra tồn tại một ước nguyên tố $r$ của $ord_p(-5a)$ mà $r<p-1<p,r\mid n$ . Điều này mâu thuẫn với tính nhỏ nhất của $p$ . Như vậy phải có $ord_p(-5a)=1$ . Suy ra $-5a\equiv 1\equiv 2a\;(mod\;p)\Rightarrow 7a\equiv 0\;(mod\;p)$

Mà $gcd(a,p)=1$ nên $p=7$ . Suy ra $n$ chia hết cho $7$ .

By Đình Huy

Bài toán (Korea Final Round 2007)

Tìm các số nguyên tố $p,q$ thỏa mãn $pq \mid p^p+q^q+1$ .

Lời giải :

Bổ đề : Cho các số nguyên tố $p,q,r$ trong đó $p$ lẻ và thỏa mãn $p \mid q^r+1$ thì khi đó $2r \mid p-1$ hoặc $p\mid q^2-1$ .

Bài toán :

Từ đề bài ta có $p^{p}+1\equiv 0\;(mod\;q)$ và $q^{q}+1\equiv 0\;(mod\;p)$

Xét $p=2$ ta có $4+1\equiv 0\;(mod\;q)\Rightarrow q=5$ , thử lại cặp $(2,5)$ thỏa mãn. Tương tự cặp $(5,2)$ cũng thỏa mãn.

Xét các số nguyên tố $p,q$ đều lẻ.

Vì $q\mid p^p+1$ nên áp dụng bổ đề ta có $2p\mid q-1$ hoặc $q\mid p^2-1$ .

Nếu $2p\mid q-1\Rightarrow q\equiv 1\;(mod\;p)\Rightarrow 0\equiv q^{q}+1\equiv 2\;(mod\;p)\Rightarrow p=2$ (loại)

Nếu $q\mid p^2-1$ thì $q\mid p-1$ hoặc $q\mid p+1$ . Lập luận như trên ta chỉ ra rằng $q\mid p-1$ là vô lí nên phải có $q\mid p+1$ . Tuy nhiên thì $p+1$ chẵn và $gcd(q,2)=1$ nên ta có $2q\mid p+1\Rightarrow p+1\geq 2q$ .

Hoàn toàn tương tự ta có $q+1\geq 2p$ . Suy ra $p+q+2\geq 2(p+q)\Rightarrow p+q\leq 2$ và điều này thì vô lí

Kết luận : $\boxed{(p,q)=(2,5),(5,2)}$

By Đình Huy

Bài toán : Tìm số nguyên dương $n$ thỏa mãn $n\mid 2^n-1$ .

Lời giải :

Ta thấy $n=1$ thỏa mãn. Xét $n>1$ . Gọi $p$ là ước nguyên tố bé nhất của $n$ .

Theo đề bài ta có $2^{n}\equiv 1\;(mod\;p)\Rightarrow ord_p(2)\mid n$ .

Theo định lí $Fermat$ nhỏ thì $2^{p-1}\equiv 1\;(mod\;p)\Rightarrow ord_p(2)\mid p-1\Rightarrow p>p-1>ord_p(2)$

Ta gọi $q$ là ước nguyên tố của $ord_p(2)$ , ta thấy $q\mid n$ và $p>q$ . Điều này mâu thuẫn vì $p$ là ước nguyên tố bé nhất của $n$ . Trường hợp này không tìm được $n$ thỏa đề.

Kết luận : Có duy nhất số nguyên dương thỏa mãn đề bài là $\boxed{n=1}$

By Đình Huy

Bài toán (USA TST 2003): Tìm các số nguyên tố $p,q,r$ thỏa mãn đồng thời $p\mid q^r+1\;,\;q\mid r^p+1\;,\;r\mid p^q+1$ .

Lời giải :

Bổ đề : Cho các số nguyên tố $p,q,r$ trong đó $p$ lẻ và thỏa mãn $p\mid q^r+1$ thì khi đó $2r\mid p-1$ hoặc $p\mid q^2-1$

Xem chứng minh bổ đề tại đây

Trở lại bài toán.

Nhận thấy rằng các số nguyên tố $p,q,r$ phải phân biệt.

Trường hợp 1 : Xét các số nguyên tố $p,q,r$ đều lẻ.

Theo bổ đề ta có $2r\mid p-1$ hoặc $p\mid q^2-1$ .

Nếu $2r\mid p-1\Rightarrow p\equiv 1\;(mod\;r)\Rightarrow 0\equiv p^{q}+1\equiv 2\;(mod\;r)\Rightarrow r=2$ (loại)

Do vậy phải có $p\mid q^2-1\Rightarrow p\mid q-1\;\;\vee p\mid q+1$ .

Nếu $p\mid q-1\Rightarrow q\equiv 1\;(mod\;p)\Rightarrow 0\equiv q^{r}+1\equiv 2\;(mod\;p)\Rightarrow p=2$ (loại)

Suy ra $p\mid q+1$ mà $q+1$ chẵn và $gcd(2,p)=1$ nên $2p\mid q+1$ , từ đó $q+1\geq 2p$

Hoàn toàn tương tự ta được $r+1\geq 2q$ và $p+1\geq 2r$ .

Như vậy $p+q+r+3\geq 2(p+q+r)\Leftrightarrow p+q+r\leq 3$ và đây là điều vô lí.

Trường hợp 2 : Trong các số $p,q,r$ có ít nhất một số chẵn. Gỉa sử $r=2$ .

Khi đó giả thiết trở thành $q\mid 2^p+1$ và $p\mid q^2+1$ .

Cũng theo bổ đề trên thì ta được $q\mid r^{2}-1$ hoặc $2p\mid q-1$ . Nếu mà $2p\mid q-1$ thì $q\equiv 1\;(mod\;p)\Rightarrow 0\equiv q^{2}+1\equiv 2\;(mod\;p)\Rightarrow p=2$ (loại vì $p,q,r$ phải phân biệt)

Như vậy có $q\mid r^2-1=2^2-1=3\Rightarrow q=3$ . Từ đó $p\mid q^2+1=3^2+1=10\Rightarrow p=5$

Bộ số $(p,q,r)=(5,3,2)$ thoả mãn.

Kết luận : $\boxed{(p,q,r)=(5,3,2),(2,5,3),(3,2,5)}$

By Đình Huy

Bài toán : Cho số nguyên dương $n$ lớn hơn $1$ và thỏa mãn $n\mid 3^n-1$ . Chứng minh rằng $n$ là số chẵn.

Lời giải :

Gọi $p$ là ước nguyên tố bé nhất của $n$

Theo giả thiết thì $3^{n}\equiv 1\;(mod\;p)\Rightarrow ord_p(3)\mid n\;\;\;(1)$

Hiển nhiên $p\neq 3$ vì nếu vậy thì $3\mid 3^{n}-1$ (vô lí). Khi đó theo định lí $Fermat$ nhỏ ta có $3^{p-1}\equiv 1\;(mod\;p)\Rightarrow ord_p(3)\mid p-1\Rightarrow p>p-1>ord_p(3)\;\;\;(2)$ .

Gọi $q$ là một ước nguyên tố của $ord_p(3)$ thì theo $(1)$ , $q$ là một ước nguyên tố của $n$ nhưng theo $(2)$ thì $p>q$ . Điều này mâu thuẫn với tính nhỏ nhất của $p$ .

Suy ra $ord_p(3)=1$ . Khi đó $3\equiv 1\;(mod\;p)\Rightarrow p=2$ . Suy ra $n$ chẵn. Đây là điều phải chứng minh.

Tổng quát bài toán : Cho số nguyên tố $p$ sao cho tồn tại số nguyên dương $n$ sao cho $n\mid (p+1)^n-1$ . Chứng minh rằng $n$ chia hết cho $p$ .

By Đình Huy

Bài toán Tìm các số nguyên tố $p,q$ thỏa mãn $p^q+q^p+1$ chia hết cho $pq$

Lời giải :

Bổ đề : Cho các số nguyên tố $p,q,r$ trong đó $p$ lẻ và thỏa mãn $p\mid q^r+1$ khi đó thì $2r\mid p-1$ hoặc $p \mid q^2-1$ .

Chứng minh bổ đề :

Từ giả thiết ta có $q^{2r}\equiv 1\;(mod\;p)\Rightarrow ord_p(q)\mid 2r\Rightarrow ord_p(q)\in \left \{ 1,2,r,2r \right \}$

Mà theo định lí $Fermat$ nhỏ thì $q^{p-1}\equiv 1\;(mod\;p)\Rightarrow ord_p(q)\mid p-1$

Nếu $ord_p(q)=1$ thì $q-1\equiv 0\;(mod\;p)\Rightarrow p\mid q^2-1$

Nếu $ord_p(q)=2$ thì $q^2\equiv 1\;(mod\;p)\Rightarrow p\mid q^2-1$

Nếu $ord_p(q)=r$ thì $r\mid p-1$ mà $p-1$ chẵn và $gcd(2,r)=1$ nên $2r\mid p-1$

Nếu $ord_p(q)=2r$ thì $2r \mid p-1$

Tóm lại bổ đề được chứng minh

BÀI TOÁN :

Từ đề bài ta suy ra $q \mid p^q+1$ và $p \mid q^p+1$ .

Nếu $p=2$ thì ta có $q\mid 2^{q}+1$ hay $2^{q}\equiv -1\;(mod\;q)$ . Theo định lí $Fermat$ nhỏ thì $2^{q}\equiv 2\;(mod\;q)$

Suy ra $-1\equiv 2\;(mod\;q)\Rightarrow q=3$ .

Tương tự nếu $q=2$ thì $p=3$

Bây giờ, ta xét các số nguyên tố $p,q$ đều lẻ.

Khi đó vì $q\mid p^{q}+1$ nên theo bổ đề trên thì ta có $2q \mid q-1$ hoặc $q\mid p^2-1$ .

Rõ ràng trường hợp $2q \mid q-1$ không xảy ra do đó phải có $q \mid p^2-1$ .

Suy ra $q\mid (p-1)$ hoặc $q\mid (p+1)$ .

Nếu như $q\mid p-1\Rightarrow p^{q}+1\equiv 2\;(mod\;q)$ , mâu thuẫn.

Do vậy $q\mid p+1\Rightarrow 2q \mid p+1$ (vì $p+1$ chẵn và $gcd(2,q)=1$ )

Suy ra $p+1\geq 2p$ . Tương tự $q+1\geq 2p$ .

Từ đó $p+q+2\geq 2(p+q)\Leftrightarrow p+q\leq 2$ và đây là điều vô lí

Kết luận : $\boxed{(p,q)=(2,3),(3,2)}$

By Đình Huy

Bài toán (IMO Shortlist 2006)

Tìm các số nguyên dương $x,y$ thỏa mãn phương trình $\dfrac{x^7-1}{x-1}=y^5-1$ .

Lời giải :

Bổ đề : Cho các số nguyên dương $x,m$ ( $x>1$ ) và số nguyên tố $p$ thỏa mãn $m\mid \dfrac{x^p-1}{x-1}$ . Khi đó thì $m\equiv 0,1\;\;(mod\;p)$

Chứng minh bổ đề :

Gọi $r$ là một ước nguyên tố của $m$ .

Từ đề bài ta có

$m\mid x^{p}-1\Rightarrow x^{p}\equiv 1\;(mod\;m)\Rightarrow x^{p}\equiv 1\;(mod\;r)\Rightarrow ord_x(r)\mid p\Rightarrow ord_x(r)\in \left \{ 1,p \right \}$

Nếu $ord_x(r)=1$ thì $x\equiv 1\;(mod\;r)\Rightarrow \dfrac{x^{p}-1}{x-1}=x^{p-1}+x^{p-2}+...+x+1\equiv \underset{p}{\underbrace{1+1+...+1}}=p\;(mod\;r)$

Mà $\dfrac{x^p-1}{x-1}\equiv 0\;(mod\;r)\Rightarrow p\equiv 0\;(mod\;r)\Rightarrow p=r\Rightarrow m\equiv 0\;(mod\;p)$

Nếu $ord_x(r)=p$ , hiển nhiên $r\nmid x$ vì nếu $r\mid x$ thì $\dfrac{x^p-1}{x-1}\equiv 1\;(mod\;r)$ và điều này trái giả thiết.

Do đó áp dụng định lí $Fermat$ nhỏ thì $x^{r-1}\equiv 1\;(mod\;r)$ , suy ra $ord_x(r)\mid r-1\Rightarrow p\mid r-1\Rightarrow r\equiv 1\;(mod\;p)\Rightarrow m\equiv 1\;(mod\;p)$

Như vậy ta có $m\equiv 0,1\;(mod\;p)$ . Bổ đề được chứng minh.

Trở lại bài toán :

Ta viết phương trình dưới dạng : $\dfrac{x^7-1}{x-1}=(y-1)(y^5+y^4+y^3+y^2+y+1)$

Áp dụng bổ đề trên thì ta có $\left\{\begin{matrix} y-1\equiv 0,1\;(mod\;7) & (1) & \\ y^4+y^3+y^2+y+1\equiv 0,1\;(mod\;7) & (2) & \end{matrix}\right.$

Nhưng từ $(1)$ ta có $y\equiv 1,2\;(mod\;7)\Rightarrow y^4+y^3+y^2+y+1\equiv 5,3\;(mod\;7)$ . Mâu thuẫn với $(2)$ .

Kết luận : Không tồn tại các số nguyên dương $x,y$ thỏa mãn đề bài.

Post navigation Tìm kiếm Search Thống kê Blog

1,158,457 views

Lưu trữ

April 2017 (1)
June 2016 (2)
May 2016 (4)
April 2016 (8)
March 2016 (2)
February 2016 (3)
January 2016 (7)
December 2015 (5)
August 2015 (5)
July 2015 (3)
June 2015 (5)
May 2015 (9)
April 2015 (3)
March 2015 (1)
February 2015 (5)
January 2015 (3)
December 2014 (7)
November 2014 (2)
October 2014 (2)
September 2014 (21)
August 2014 (60)
July 2014 (58)
June 2014 (129)
May 2014 (78)
April 2014 (25)
March 2014 (103)
February 2014 (39)
January 2014 (67)
December 2013 (51)
November 2013 (47)
October 2013 (32)
September 2013 (39)
August 2013 (56)

Chuyên mục

(0) Nơi thần kinh rung rinh (5)
(1) Danh sách tổng hợp các bài toán số học (3)
(2) Danh sách tổng hợp các hệ thức lượng giác, hình học (5)
(3) Danh sách tổng hợp các bài toán về PT-HPT (4)
(4) Danh sách tổng hợp các bài toán về Đa thức – Phương trình hàm (4)
(5) Danh sách tổng hợp các bài toán Bất đẳng thức (2)
(6) Danh sách tổng hợp các bài toán về Giới hạn – Dãy số (2)
(7) Danh sách tổng hợp đề thi (5)
BẤT ĐẲNG THỨC THI ĐẠI HỌC (15)
Bất Đẳng Thức (107)
- Ứng dụng của tam thức bậc hai trong chứng minh BĐT (2)
- Bất đẳng thức hình học (21)
- Bất đẳng thức Schur và kĩ thuật đổi biến P,Q,R (7)
- BĐT với những bài toán về hằng số tốt nhất (15)
- Cân bằng hệ số, điểm rơi giả định trong chứng minh BĐT (5)
- Chứng minh BĐT bằng phương pháp S-S, S.O.S (6)
- Dồn biến trong chứng minh BĐT (5)
- Khai triển Abel trong chứng minh BĐT (7)
- Kĩ thuật AM-GM ngược dấu (1)
- Lượng giác hóa trong chứng minh BĐT (19)
- Nguyên lý Biên trong chứng minh BĐT (8)
- Những phương pháp khác chứng minh BĐT (6)
- Phép chuẩn hóa trong chứng minh BĐT thuần nhất (10)
- Sử dụng nguyên lí Dirichlet để chứng minh BĐT (2)
Các định lí hình học (11)
CHUYÊN MỤC ÔN THI ĐẠI HỌC (1)
Dãy số – Giới hạn (61)
Dãy số số học (50)
HÌNH HỌC PHẲNG TOẠ ĐỘ THI ĐẠI HỌC (3)
Hình học không gian (4)
Hình học phẳng (97)
Hệ phương trình (41)
Hệ thức lượng trong tam giác (18)
Phép thế lượng giác trong những bài toán PT-HPT (15)
PHƯƠNG TRÌNH – HỆ PHƯƠNG TRÌNH THI ĐẠI HỌC (11)
Phương pháp tọa độ trong mặt phẳng (1)
Phương trình hàm (100)
Phương trình hàm đa thức (14)
Phương trình đại số (9)
Số Học (148)
- Cấp của một số nguyên (1)
- Cấp của một số nguyên, Căn nguyên thủy (8)
- Căn nguyên thủy (1)
- Lý thuyết đồng dư (4)
- Những bài toán số học liên quan đến Lifting the Exponent Lemma (LTE) (2)
- Những dạng bài số học khác (2)
- Phần nguyên, Phần lẻ (9)
- Phương pháp Vieta Jumping (Bước nhảy Viete) (9)
- Phương trình nghiệm nguyên (83)
- Số chính phương modulo p (5)
- Số chính phương, số lập phương, số lũy thừa (16)
- Số nguyên tố (1)
- Số nguyên tố, Hợp số (10)
- Sự chia hết, đồng dư (10)
- Định lí phần dư Trung Hoa và ứng dụng (11)
Sử dụng các BĐT cổ điển để chứng minh BĐT (81)
Sự thẳng hàng, các đường đồng quy (22)
Tỉ số kép – Hàng điểm điều hòa (21)
Tổ hợp – Rời rạc (7)
Đa thức (27)

Cấp Của Một Số Nguyên, Căn Nguyên Thủy | Huy Cao's Blog

Cấp Và Căn Nguyên Thủy - Lê Xuân Đại - THPT Chuyên Vĩnh Phúc

CẤP VÀ CĂN NGUYÊN THỦY – Lê Xuân Đại

[PDF] BẬC CỦA SỐ NGUYÊN - CĂN NGUYÊN THUỶ - Diễn đàn Toán Học

Căn Nguyên Thủy Modulo N – Wikipedia Tiếng Việt

Cấp Của Phần Tử Và Căn Nguyên Thủy - 1Library

Căn Nguyên Thủy - The Numbers Of 2H

Bậc Của Một Số Nguyen Can Nguyen Thủy

Cấp Và Căn Nguyên Thủy - Dgsfg - Lê Minh Khang - Trường THPT

Cấp Của Phần Tử Và Căn Nguyên Thủy | PDF - Scribd

Cap - Can Nguyen Thuy | PDF - Scribd

Cấp Của Phần Tử Và Các Căn Nguyên Thủy - Một Số Dạng Toán Về đồng D

SH Thinh PD Cap Va Can Nguyen Thuy - Tài Liệu Text - 123doc

[TeX] CẤP CỦA MỘT SỐ NGUYÊN THEO MODULO N

Lập Trình C - Căn Nguyên Thuỷ... | Facebook

Liên Hệ