Đến nội dung

Hình ảnh

Lí thuyết đồng dư


  • Please log in to reply
Chủ đề này có 44 trả lời

#1
hongthaidhv

hongthaidhv

    GS-TSKHVMF. Lê Hồng Thái

  • Thành viên
  • 442 Bài viết
Lời tựa: Đ?#8220;ng dư là một công cụ quan trọng trong số học. Đ?#8220;ng dư được xây dựng bởi nhà tóan học thiên tài Gass. Tuy nhiên thì đối với các em THCS đ?#8220;ng dư là phân học khá khó hiểu và trìu tượng. Qua nhiều cuộc trò chuyện với các em lớp 8,9 đ?#8220;ng thời đáp ứng nhu cầu thi trường chuyên lớp chọn của cá em, mình quyết định lập ra topic này để mọi người vào trao đổi về đ?#8220;ng dư và lí thuyết đ?#8220;ng dư, mình hi vọng rằng mọi thắc mắc về đ?#8220;ng dư sẽ đc giải quyết ở đây và topic này sẽ có ích nhiều cho các em trong việc học tập và nghiên cứu toán học
Dự định của mình là sẽ post 4 bài giảng lớn của các thầy mà mình đc học (có chọn lọc) và một số bài tập. Mong mọi ngưởi cho ý kiến
Lưu ý Trong topic này ta chỉ xét các số trên tập Z vì vậy nếu hok nói chi thêm thì các số đó là số nguyên
---------------------------------------------------------------------------------------------------------------------------

BÀI 1: ĐỒNG DƯ THỨC

1.1 Định nghĩa : cho số nguyên m>1 và các số nguyên a,b. Nếu khi chia a, b cho m ta đc cùng một số dư thì ta nói a đồng dư với b theo modulo m
$=> a \equiv b \Leftrightarrow a=mp+r; b=mq+r ( r< m) $
khi đó ta kí hiệu $a \equiv b \pmod{m}$

1.2 Định lí: Các mệnh đề sau là tương đương
i, $ a \equiv b$
ii, $m|(a-b)$
iii, $\exists t \in \mathbb{Z} : a=b +mt$
Ba mệnh đề trên ta dễ dàng cm đc bằng định nghĩa.

1.3 Tính Chất. Hệ quả

1. phản xạ: $a \equiv a \pmod{m}$
đối xứng: $a \equiv b \pmod{m} \Rightarrow b \equiv a \pmod{m}$
bắc cầu: $a \equiv b(modm); b \equiv c (modm) => a \equiv c (modm)$
2. Ta có thể cộng (trừ) từng vế nhiều đ?#8220;ng dư thức của cùng một modulo m với nhau: $a_{k} \equiv b_{k} (modm) k=1,2,..,n; \varepsilon_{k} \in {1, -1} => \sum\limits_{k=1}^{n} \varepsilon_{k} a_{k} \equiv \sum\limits_{k=1}^{n} \varepsilon_{k} b_{k} (modm)$
3. Có thể nhân từng vế đông dư thức của cùng một modulo m : $a_{k} \equiv b_{k} (modm) k=1,2,..,n => \prod\limits_{k=1}^{n}a_{k} \equiv \prod\limits_{k=1}^{n} b_{k} (modm)$
*hệ quả:
a, $a \equiv b (modm) \Leftrightarrow a \pm c \equiv b \pm c (modm)$
$b, a \equiv b+c (modm) \Leftrightarrow a-b \equiv c (modm)$
$c, a \equiv b (modm) => ac \equiv bc (modm)$
điều ngược lại chỉ đúng khi (m,c)=1
d, $a \equiv b (modm) \Leftrightarrow a \equiv b+mp (modm)$
$e, a \equiv b(modm) => a^{n} \equiv b^{n} (modm)$
4. Nếu d\a, d\b (d,m)=1 khi đó $a \equiv b(modm) \Leftrightarrow \dfrac{a}{d} \equiv \dfrac{b}{d} (modm)$

5. Nếu d\ (a,b,m) khi đó $a \equiv b(modm) \Leftrightarrow \dfrac{a}{d} \equiv \dfrac{b}{d} (mod \dfrac{m}{d})$

6. $a \equiv b( mod m_{k} ) k=1,2,..,n => a \equiv b(mod [m_{1}, m_{2},..m_{n}])$ ở đây $[m_{1},...m_{n}]$ là bội chung nhỏ nhất của $m_{1}, m_{2},..m_{n}$. Đây là tc khá quan trọng và có ứng dụng khá lớn.

7. nếu $a \equiv b (modm)$ thì tập hợp ước chung của a và m (X) bằng tập ước chung của b và m (Y)
CM : cm $X \subset Y$ và $Y \subset X$
giả sử $x \in X$ khi đó a,m chia hết cho x mà a-b chia hết cho m => a-b chia hết cho x, do a chia hết cho x => b chia hết cho x => x là ước chung của b và m => $x \in Y => X \subset Y$
tương tự ta sẽ cm đc $Y \subset X => X=Y$

-----------------------------------------------------------------------------------------------------------------
Các tính chất và hệ quả đc cm khá đơn giản bằng định nghĩa vì vậy mọi người có thể tự cm ( nếu hok cm đc cái nào có thể mạnh dạn hỏi mình sẽ giải đáp cho)
TO BE CONTINEU.......(mỏi tay rùi)

Bài viết đã được chỉnh sửa nội dung bởi Phạm Quang Toàn: 08-09-2011 - 13:08

M.Lê Hồng Thái
La classe des Matériaux Avancés - Groupe des Écoles des Mines (GEM)
Mél: [email protected]
Y!M: turjnto_le
Facebook: http://www.facebook.com/hongthai.le
Télé: +84(0)936 431 156
+84(0) 979 646 777

#2
inhtoan

inhtoan

    <^_^)

  • Thành viên
  • 964 Bài viết
BT cơ bản :

1)CM:$ 12^{2n + 1} + 11^{n + 2} \vdots 133 $

2)CM:$ 2.31^n + 1 \vdots 3 $

3)CM:$ 3^{2010} + 5^{2013} \vdots 13 $

4)Cho:$ x,y,z \in Z $,$ x^2 + y^2 = z^2 $.CM:$ xy \vdots 6 $

5)Có $ \exists n \in Z^ + $ hay không để $ 2008^{n^2 + 2n + 1} + 2008 \vdots 223 $

6)Tìm dư:
$ {\rm{a}}{\rm{. 23}}^{{\rm{34}}} ^{^{{\rm{19 }}} } {\rm{:17 b}}{\rm{. 46}}^{{\rm{2345}}} {\rm{ : 37 c}}{\rm{. 239}}^{237^{54} } {\rm{ :135 d}}{\rm{. 2}}^{{\rm{1000000}}} {\rm{ : 3}}^{10} $

7)n là số nguyên dương lẻ .CM:$ A = 46^n + 296.13^n \vdots 1947 $ (Hungari-1947)

Bài viết đã được chỉnh sửa nội dung bởi Phạm Quang Toàn: 08-09-2011 - 13:13


#3
hung0503

hung0503

    benjamin wilson

  • Thành viên
  • 492 Bài viết
có bài này e ko hiểu anh chị giúp đỡ, em cảm ơn
đề:cm nếu m là số nguyên dương thì bất kì số nguyên a nào cũng đồng dư với một và chỉ một số của dãy số 0,1,2,....,m-1 theo mod m
bài giải: ta có $a=mq+r ;0 \leq r<m \Rightarrow a-r=mq \Rightarrow a \equiv r(mod m)$
cần cm hai số dư bằng nhau trong phép chia cho m
giả sử $ 0 \leq r_{1} <m ; 0 \leq r_{2} <m $
và $ r_{1} \equiv r_{2}(mod m)* \Rightarrow r_{1}- r_{2}=pm $
Ta có $ 0 \leq r_{1}<m$ ;$ -m< -r_{2} \leq 0 $
$ \Rightarrow -m< r_{1}- r_{2}<m \Rightarrow r_{1}- r_{2}=0** \Rightarrow r_{1}= r_{2}$
cho em hỏi cái * này là ở đâu ra ạ và sao mình lại suy ra được cái **

Bài viết đã được chỉnh sửa nội dung bởi hung0503: 06-12-2008 - 13:59

What if the rain keeps falling?
What if the sky stays gray?
What if the wind keeps squalling,
And never go away?
I still ........

Hình đã gửi


#4
hongthaidhv

hongthaidhv

    GS-TSKHVMF. Lê Hồng Thái

  • Thành viên
  • 442 Bài viết
có bài này e ko hiểu anh chị giúp đỡ, em cảm ơn
đề:cm nếu m là số nguyên dương thì bất kì số nguyên a nào cũng đ?#8220;ng dư với một và chỉ một số của dãy số 0,1,2,....,m-1 theo mod m


Bài này dễ mà em ( tính chất cơ bản). Giả sử $a \equiv p ( modm)$ và $a \equiv r ( modm) ( 0 \leq p\ , r < m\ , p \neq m)
=> p \equiv r (modm) =>( p-r) \vdots m$, giả sử $p>r => (p-r ) \geq m$ ( tính chất cơ bản) ( vô lí do $p, r < m$) $=> p=r$ ( đpcm)
M.Lê Hồng Thái
La classe des Matériaux Avancés - Groupe des Écoles des Mines (GEM)
Mél: [email protected]
Y!M: turjnto_le
Facebook: http://www.facebook.com/hongthai.le
Télé: +84(0)936 431 156
+84(0) 979 646 777

#5
hung0503

hung0503

    benjamin wilson

  • Thành viên
  • 492 Bài viết
anh hiểu sai ý em rồi..........ý em là em ko hiểu một số chỗ trong cách cm trên........anh giúp em với....em cảm ơn

What if the rain keeps falling?
What if the sky stays gray?
What if the wind keeps squalling,
And never go away?
I still ........

Hình đã gửi


#6
hung0503

hung0503

    benjamin wilson

  • Thành viên
  • 492 Bài viết
ko biết em post vào đây đúng ko vì nó thuộc về chia hết......
ta có tính chất : nếu a và b là 2 số nguyên, b dương thì ta được a=bq+r trong đó $ 0 \leq r<b$
vậy tại sao trong bài cm $ a^{3}-3$ ko chia hết cho 7 thì ta lại biểu diễn a=7k+r với r thuộc {0,1,-1,-2,2,3,-3}
sao lúc thì để là $ 0 \leq r<b$ còn lúc thì lại để là r thuộc {0,1,-1,-2,2,3,-3}
xin anh chị giúp đỡ em còn nhiều thiếu sót, em xin cảm ơn

Bài viết đã được chỉnh sửa nội dung bởi hung0503: 06-12-2008 - 19:08

What if the rain keeps falling?
What if the sky stays gray?
What if the wind keeps squalling,
And never go away?
I still ........

Hình đã gửi


#7
inhtoan

inhtoan

    <^_^)

  • Thành viên
  • 964 Bài viết

vậy tại sao trong bài cm $ a^{3}-3$ ko chia hết cho 7 thì ta lại biểu diễn a=7k+r với r thuộc {0,1,-1,-2,2,3,-3}
sao lúc thì để là $ 0 \leq r<b$ còn lúc thì lại để là r thuộc {0,1,-1,-2,2,3,-3}

a=7k+r(r=0,1,-1,-2,2,3,-3) không mâu thuẫn với điều kiện $ 0 \leq r<b$ .Ví dụ:a=7k-3=7(k-1)+4=7u+4 ; a=7k-1=7(k-1)+6=7u+6...
Nếu ta biểu diễn a=7k+6 và a=7k-1 vậy khi $ a^3 $ thì cách biểu diễn nào dễ chứng minh bài toán hơn...:D
Bài toán này cũng có thể giải bằng đồng dư.

#8
hongthaidhv

hongthaidhv

    GS-TSKHVMF. Lê Hồng Thái

  • Thành viên
  • 442 Bài viết

ko biết em post vào đây đúng ko vì nó thuộc về chia hết......
ta có tính chất : nếu a và b là 2 số nguyên, b dương thì ta được a=bq+r trong đó $ 0 \leq r<b$
vậy tại sao trong bài cm $ a^{3}-3$ ko chia hết cho 7 thì ta lại biểu diễn a=7k+r với r thuộc {0,1,-1,-2,2,3,-3}
sao lúc thì để là $ 0 \leq r<b$ còn lúc thì lại để là r thuộc {0,1,-1,-2,2,3,-3}
xin anh chị giúp đỡ em còn nhiều thiếu sót, em xin cảm ơn

Hi, đây là câu hỏi hay. Bài toán này ta hoàn toàn có thể giả sử $a=7k+r$ với $r \in {\ {0;1;2;3;4;5;6}\ }$ nó không ảnh hưởng chi đến cách cm cả. Nhưng ở đây khi ta đặt nó là $\pm1; \pm2; \pm 3$ thì khi ta lập phương lên nó sẽ gọn hơn thui , nếu em hok thích thì có thể đặt lại
M.Lê Hồng Thái
La classe des Matériaux Avancés - Groupe des Écoles des Mines (GEM)
Mél: [email protected]
Y!M: turjnto_le
Facebook: http://www.facebook.com/hongthai.le
Télé: +84(0)936 431 156
+84(0) 979 646 777

#9
hongthaidhv

hongthaidhv

    GS-TSKHVMF. Lê Hồng Thái

  • Thành viên
  • 442 Bài viết

có bài này e ko hiểu anh chị giúp đỡ, em cảm ơn
đề:cm nếu m là số nguyên dương thì bất kì số nguyên a nào cũng đồng dư với một và chỉ một số của dãy số 0,1,2,....,m-1 theo mod m
bài giải: ta có $a=mq+r ;0 \leq r<m \Rightarrow a-r=mq \Rightarrow a \equiv r(mod m)$
cần cm hai số dư bằng nhau trong phép chia cho m
giả sử $ 0 \leq r_{1} <m ; 0 \leq r_{2} <m $
và $ r_{1} \equiv r_{2}(mod m)* \Rightarrow r_{1}- r_{2}=pm $
Ta có $ 0 \leq r_{1}<m$ ;$ -m< -r_{2} \leq 0 $
$ \Rightarrow -m< r_{1}- r_{2}<m \Rightarrow r_{1}- r_{2}=0** \Rightarrow r_{1}= r_{2}$
cho em hỏi cái * này là ở đâu ra ạ và sao mình lại suy ra được cái **

à anh hiểu ý em rùi, cái * này là ta giả sử khi chia a cho q ta đc hai số dư là $r_{1}$ và $r_{2}$ . Còn từ * => ** là giả sử $r_{1}-r_{2} \neq 0$, ta luôn giả sử đc $r_{1} >r_{2}$ khi đó ta có $m>r_{1} -r_{2} >0$, lại do $r_{1} -r_{2}$ chia hết cho $m>0 => r_{1} -r_{2} >m$ ( mâu thuẫn) $=> r_{1}-r_{2} =0$
M.Lê Hồng Thái
La classe des Matériaux Avancés - Groupe des Écoles des Mines (GEM)
Mél: [email protected]
Y!M: turjnto_le
Facebook: http://www.facebook.com/hongthai.le
Télé: +84(0)936 431 156
+84(0) 979 646 777

#10
No Problem

No Problem

    Hạ sĩ

  • Thành viên
  • 67 Bài viết

BT cơ bản :

1)CM:$ 12^{2n + 1} + 11^{n + 2} \vdots 133 $

2)CM:$ 2.31^n + 1 \vdots 3 $

3)CM:$ 3^{2010} + 5^{2013} \vdots 13 $


Chà nhiều bài thế này sao hok ai làm, thui để em gà làm mấy bài dễ trước vậy :Rightarrow

1)$12^{2n + 1} + 11^{n + 2}\equiv \ 11^n.12+11^{n+2}\equiv \ 0(mod 133) $
2)$ 2.31^n + 1 \equiv \ 3(mod3) $
3)$ 3^{2010} + 5^{2013} \equiv \ 3^{3.670}+5^{2.1006+1}\equiv \ 1+-1\equiv 0 (mod13)$

Bài viết đã được chỉnh sửa nội dung bởi Phạm Quang Toàn: 08-09-2011 - 13:14


#11
No Problem

No Problem

    Hạ sĩ

  • Thành viên
  • 67 Bài viết

BT cơ bản :


5)Có $ \exists n \in Z^ + $ hay không để $ 2008^{n^2 + 2n + 1} + 2008 \vdots 223 $

Ta có
$2008\equiv \ 1(mod223)$
$ 2008^{n^2 + 2n + 1} + 2008 \equiv \ 2 (mod223)$

Bài viết đã được chỉnh sửa nội dung bởi Phạm Quang Toàn: 08-09-2011 - 13:16


#12
No Problem

No Problem

    Hạ sĩ

  • Thành viên
  • 67 Bài viết

BT cơ bản :


7)n là số nguyên dương lẻ .CM:$ A = 46^n + 296.13^n \vdots 1947 $ (Hungari-1947)

$ A = 46^{2k+1} + 296.13^{2k+1} \equiv \ 13^{2k}+13^{2k+1}.296\equiv \ 13^{2k}(46+293.13)\equiv \ 0 (mod 1947) $

Bài viết đã được chỉnh sửa nội dung bởi Phạm Quang Toàn: 08-09-2011 - 13:17


#13
Zaraki

Zaraki

    PQT

  • Phó Quản lý Toán Cao cấp
  • 4273 Bài viết

4)Cho:$ x,y,z \in Z $,$ x^2 + y^2 = z^2 $.CM:$ xy \vdots 6 $


Áp dụng tính chất

_ $a^2 \equiv 0,1 \pmod{3}$.
_ $a^2 \equiv 0,1 \pmod{4}$.

Discovery is a child’s privilege. I mean the small child, the child who is not afraid to be wrong, to look silly, to not be serious, and to act differently from everyone else. He is also not afraid that the things he is interested in are in bad taste or turn out to be different from his expectations, from what they should be, or rather he is not afraid of what they actually are. He ignores the silent and flawless consensus that is part of the air we breathe – the consensus of all the people who are, or are reputed to be, reasonable.

 

Grothendieck, Récoltes et Semailles (“Crops and Seeds”). 


#14
Minhnguyenquang75

Minhnguyenquang75

    Thượng sĩ

  • Thành viên
  • 244 Bài viết
Xin góp vui
Định lí Ferma nhỏ:
Định lí ferma nhỏ khẳng định rằng: nếu p là một số nguyên tố, thì với số nguyên a bất kỳ , $a^{p}$ �ồ a sẽ chia hết cho p. Nghĩa là:
$a^{p} \equiv a (mod p) $
Một cách phát biểu khác của định lý như sau: nếu p là số nguyên tố và a là số nguyên nguyên tố cùng nhau với p, thì $a^{p-1}$ - 1 sẽ chia hết cho p. Bằng kíhiệu đ�ồng dư ta có:
$a^{p-1} \equiv 1 (mod p)$ << Cái này hay dùng

Bài viết đã được chỉnh sửa nội dung bởi Minhnguyenquang75: 08-09-2011 - 13:40


#15
Hoa Hồng Lắm Gai

Hoa Hồng Lắm Gai

    Hạ sĩ

  • Thành viên
  • 53 Bài viết


3)CM:$ 3^{2010} + 5^{2013} \vdots 13 $


Bài này mình làm nhầm chỗ nào mà không CM đc

$ 3^{2010} + 5^{2013} \vdots 13 = 3^{3.670} + 5^{2.1006+1}= 27^{670} + 25^{1006}.5 \equiv 1+(-1)^{1006}.5$
$=1+1.5=6 \pmod{13} $

Bài viết đã được chỉnh sửa nội dung bởi Phạm Quang Toàn: 25-10-2011 - 20:43

Ác Ma Học Đường- Cá Sấu


#16
Zaraki

Zaraki

    PQT

  • Phó Quản lý Toán Cao cấp
  • 4273 Bài viết
Toàn nghĩ $3^{2010}+5^{2010} \ \vdots \ 13$ thì đúng hơn.

Discovery is a child’s privilege. I mean the small child, the child who is not afraid to be wrong, to look silly, to not be serious, and to act differently from everyone else. He is also not afraid that the things he is interested in are in bad taste or turn out to be different from his expectations, from what they should be, or rather he is not afraid of what they actually are. He ignores the silent and flawless consensus that is part of the air we breathe – the consensus of all the people who are, or are reputed to be, reasonable.

 

Grothendieck, Récoltes et Semailles (“Crops and Seeds”). 


#17
Trang Luong

Trang Luong

    Đại úy

  • Thành viên
  • 1834 Bài viết

Chứng minh rằng với mọi số nguyên dương $n$ thì $A=5^{n}(5^{n}+1)-6^{2}(3^{n}-2^{n})\vdots 91$


"Nếu bạn hỏi một người giỏi trượt băng làm sao để thành công, anh ta sẽ nói với bạn: ngã, đứng dậy là thành công"
Issac Newton

#18
degeawapsh

degeawapsh

    Binh nhất

  • Thành viên
  • 20 Bài viết

Chứng minh rằng với mọi số nguyên dương $n$ thì $A=5^{n}(5^{n}+1)-6^{2}(3^{n}-2^{n})\vdots 91$

Hình như ghi sai đề rồi!



#19
minhhieuchu

minhhieuchu

    Trung sĩ

  • Thành viên
  • 105 Bài viết

Chứng minh rằng với mọi số nguyên dương $n$ thì $A=5^{n}(5^{n}+1)-6^{2}(3^{n}-2^{n})\vdots 91$

n=1
n=2
...
Đề sai rồi, sửa đi bạn ơi... :D :P  :excl:  (~~)  :ukliam2:  :icon10:  :angry:


:icon12:  Số 11 Ams 2 basketball team   :icon12: 

(~~)  HỌC...   (~~)

(~~)  HỌC nữa...   (~~)

(~~)  HỌC mãi...   (~~)

:icon6:  98er   :icon6:

:namtay  PHẢI THI ĐỖ!!  :)))))))   :namtay
:wub:  :wub:
  :wub:  :wub:  :wub:  :wub:  :wub: 


#20
minhhieuchu

minhhieuchu

    Trung sĩ

  • Thành viên
  • 105 Bài viết

Bài này mình làm nhầm chỗ nào mà không CM đc

$ 3^{2010} + 5^{2013} \vdots 13 = 3^{3.670} + 5^{2.1006+1}= 27^{670} + 25^{1006}.5 \equiv 1+(-1)^{1006}.5$
$=1+1.5=6 \pmod{13} $

 

 

Toàn nghĩ $3^{2010}+5^{2010} \ \vdots \ 13$ thì đúng hơn.

Nếu như sửa đề như Jinbe thì sẽ chứng minh được ngay:
32010 chia 13 dư 1
52010 chia 13 dư 12
~~>> đpcm


:icon12:  Số 11 Ams 2 basketball team   :icon12: 

(~~)  HỌC...   (~~)

(~~)  HỌC nữa...   (~~)

(~~)  HỌC mãi...   (~~)

:icon6:  98er   :icon6:

:namtay  PHẢI THI ĐỖ!!  :)))))))   :namtay
:wub:  :wub:
  :wub:  :wub:  :wub:  :wub:  :wub: 





2 người đang xem chủ đề

0 thành viên, 1 khách, 0 thành viên ẩn danh


    Google (1)