Đến nội dung

Các định nghĩa, định lí trong Số học


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

#1
Khách- thachpbc_*

Khách- thachpbc_*
  • Khách
Định lí Lagrange

Cho đa thức $P(x)= \sum\limits_{i=0}^{n} a_ix^i \in Z[x] $. Nếu tồn tại $n+1$ tự nhiên phân biệt $k_i$ thỏa mãn :
$i) k_i \not \equiv k_j (mod m)$, mọi $i \neq j $.
$ii) P(k_i) \equiv 0 (mod m) $ mọi $i=1,2,...,n+1$.
thì $a_i \equiv 0 (mod m) $ mọi $i$.

(Chứng minh rất đơn giản bằng quy nạp)

Một số hệ quả:
Hệ quả 1:Định lí Wilson $ (p-1)! \equiv -1(mod p)$ moi số nguyên tố $p $
Hệ quả 2: $\sum\limits_{1 \leq i<j \leq p-1} ij \equiv 0 (mod p)$ mọi $p$ nguyên tố .

Hệ quả 3:
$ \sum\limits_{1 \leq i <j \leq \dfrac{p-1}{2}} i^2j^2 \equiv 0 (mod p)$ mọi số nguyên tố $ p >5$

Bài viết đã được chỉnh sửa nội dung bởi thachpbc: 04-01-2007 - 17:34


#2
DinhCuongTk14

DinhCuongTk14

    Tiến sĩ Diễn đàn Toán

  • Hiệp sỹ
  • 749 Bài viết
Một bổ đề mà mình muốn giới thiệu với các bạn
Theo mình đây cũng là một bổ đề quan trọng khi giải toán :
Nếu $\ p^{h}|| a-1 $ và $ \ p^{k}|| b $ với p là số nguyên tố
thì $\ p^{h+k}|| a^{b} -1 $
Bài này mình thấy thực sự có ý nghĩa
Sau đây là một số ví dụ điển hình :
Cm phuơng trình sau có hữu hạn nghiệm nguyên dương : $\ n!= a^{b}- a^{c} $ (TST CHINA)
Và bài ISL : chứng minh nếu $ (a^n)-1$ và $a-1$ có cùng ước nguyên tố thì $a-1$ là lũy thừa của $2$
và 2 bài
IMO 99
bài 4 VMEO tháng 11 nũa
các bạn cùng đóng góp thêm nữa nha.

Bài viết đã được chỉnh sửa nội dung bởi thachpbc: 08-01-2007 - 18:22


#3
HUYVAN

HUYVAN

    CTCVAK08

  • Hiệp sỹ
  • 1126 Bài viết
Cho mình tham gia với nhé!
Định lí Lucas: Nếu tồn tại một số nguyên $a$ thỏa mãn $ a^{n-1} \equiv 1$($modn)$ và $a^{(n-1)/p}\not \equiv 1$ ($ mod n$), với mọi số nguyên tố $p$ chia hết $n-1$, khi đó $n$ là số nguyên tố.
Trước khi chứng minh định lí này, mình xin nhắc lại một số kiến thức cơ bản về lý thuyết bậc và căn nguyên thủy để mọi người tiện theo dõi.
Định nghĩa bậc của $a$ modulo $n$: Cho $n>1$ và $UCLN(a,n)=1$. Bậc của $a$ modulo $n$ là số nguyên dương $k$ nhỏ nhất sao cho $a^k \equiv 1$ ($mod n$ ).
Định lí cơ bản: Gọi $k$ là bậc của $a$ modulo $n$. Khi đó, $a^h \equiv 1$ ($mod n$) khi và chỉ khi $k|h$, trong trường hợp đặc biệt thì $k$| $\phi$ $(n)$. Việc chứng minh định lí này khá dễ nên cho mình bỏ qua.
Quay lại việc chứng minh định lí Lucas:
Gọi $k$ là bậc của $a$ modulo $n$
Vì $a^{n-1} \equiv 1$( $mod n$ ) nên theo định lí cơ bản thì $k$| $n-1$, hay $km=n-1$ (với $m$ là số nguyên bất kì)
Nếu $m>1$ thì $m$ sẽ có ước số nguyên tố $q$: $m=qh$( với $h$là số nguyên tùy ý)
Ta có: $a^{(n-1)/q}=(a^k)^h \equiv 1^h=1$($mod n$), điều này trái với giả thiết. Từ đó suy ra $m=1$.
Mặt khác, bậc của $a$ không vượt quá $\phi$ $(n)$, suy ra $n-1=\phi (n)$, hay $n$ là số nguyên tố.

#4
HUYVAN

HUYVAN

    CTCVAK08

  • Hiệp sỹ
  • 1126 Bài viết
Tiếp theo phần trên, mình sẽ giới thiệu với các bạn một bổ đề quen thuộc trong Số học.
Bổ đề: Cho $p$ là số nguyên tố lẻ và $p-1=2^hm$, với $m$ lẻ và $h\geq 1$. Khi đó sẽ có nguyên $a$ ($1<a<p-1$) thỏa mãn $a^m \equiv 1$ (mod $n$) hoặc $a^{{2^j}m} \equiv -1 $ (mod $p$), với $j=1,2,..., h-1$
Chứng minh:
Giả sử $k$ kà bậc của $a$ modulo $p$. Theo định lí cơ bản thì $k$ chia hết $p-1=2^hm$
Nếu $k$ lẻ thì $m=kr$, với $r$ là số nguyên tùy ý. Khi đó: $a^m=(a^k)^r \equiv 1^r =1$ (mod $p$)
Nếu $k$ chẵn, ta viết $k$ dưới dạng $k=2^{j+1}d$ (với $j\geq 0$ và $d$ là số nguyên lẻ)
Vì $2^{j+1}d$|$2^hm$, suy ra $j+1 \neq h$ và $d$| $m$
Mặt khác, từ $a^{{2^{j+1}d} \equiv 1$ (mod $p$), chúng ta có: $ a^{{2^j}d} \equiv \pm 1$ (mod $p$). Đặt $m=dq$ ($q$ là số nguyên lẻ). Suy ra: $a^{{2^j}m}=(a^{{2^j}d})^q \equiv (\pm 1)^q=\pm 1$ (mod $p$)

#5
2007vmo

2007vmo

    Binh nhì

  • Thành viên
  • 19 Bài viết
ai đó giới thiệu về căn nguyên thủy được không?
ZARATHUSTRA đã nói như thế (NIETZSCHE)

#6
vo thanh van

vo thanh van

    Võ Thành Văn

  • Hiệp sỹ
  • 1197 Bài viết
Căn nguyên thủy:Cho $a,m$ là các số nguyên,$m>0 ;(a;m)=1$ .Ta gọi $a$ là căn nguyên thủy $mod m$ nếu $ord_{m}(a)= \phi (m)$

Bài viết đã được chỉnh sửa nội dung bởi thachpbc: 22-01-2007 - 18:26

Quy ẩn giang hồ

#7
DinhCuongTk14

DinhCuongTk14

    Tiến sĩ Diễn đàn Toán

  • Hiệp sỹ
  • 749 Bài viết
Liên quan tới căn nguyên thủy có một tính chất không thể quên đó là
Mọi số nguyên tố đều có căn nguyên thủy
Tính chất này rất hay để giải quyết một số bài toán

#8
tmt_k08

tmt_k08

    Lính mới

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

Liên quan tới căn nguyên thủy có một tính chất không thể quên đó là
Mọi số nguyên tố đều có căn nguyên thủy
Tính chất này rất hay để giải quyết một số bài toán

Ví dụ vài bài?

#9
DinhCuongTk14

DinhCuongTk14

    Tiến sĩ Diễn đàn Toán

  • Hiệp sỹ
  • 749 Bài viết
Thieu gi vi du ha ban !
Mot so vi du quen thuoc nhu :
1. Tim tat ca bo 4 so tu nhien $( x,y,z,t )$ $0 \leq x,y,z,t \leq36$ thoa man :$ x^{2}+ y^{2} \equiv z^{2}+ t^{2}(mod37)$ (Turkey 2000) .
2. Cho$p$ la so nguyen to dong du 2 mod 3 .CM : Co the chon ra
$ \dfrac{p.(p+1)}{3} $ tap con p phan tu cua tap co $ \dfrac{p.(p+1)}{3} $ phan tu sao cho giao cua hai tap con bat ki co toi da 3 phan tu .
(MOSP 2002) .
3.Neu $p$ la so nguyen to va $(m,n)=1$ ;$p| m^{ 2^{d} } + n^{ 2^{d} } $ thi : $ 2^{d+1} |(p-1)$.
4.Tim tat ca cac so nguyen to $p,q$ sao cho $ a^{3.pq} \equiv a(mod3.pq)$ voi moi a
Ngoải ra có một tính chất khá thú vị nữa là tập $g, g^{2},... g^{p-1} \equiv {1,2,..p-1} $ cái này cực kì thú vị
Nó giống với căn bậc p của đoen vị và có nhiều tc thú vị khác nữa
Bữa sau sẽ nói tiếp !

Dinh li so nguyen to ( The Prime Number Theorem).
Kí hiệu $ \pi (x)$ là số các số nguyên tố bé hơn hoăc bang x
Khi do ta co :
$ \lim_{x\to \infty}\ frac{\pi (x).lnx }{x} $=1 .
(Conjectured by Gauss and Legendre, on the basis of computation, around)
1800.Proved by Hadamard and de la Vallée Poussin in 1896.)
Co the phat bieu mot cach tuong minh nhu sau :
Với mọi $c>0$ tuy y thi ton tai r du lon sao cho voi moi $ n>r $thi trong doan $(r ,(1+c).r)$ chứa tốii thieu mot so nguyen to .
Sau day la mot so vi du :
1 .Cho $P(x)$ la da thuc voi he so nguyen thoa man voi moi $ p /in P $ thi $P(x)$ la luy thừa cua 2 .(AMM)
2. Cm dãy : $ \sum_{i=1}^n p_i $ phan ki .Va ket qua sau :$ \sum_{i=1} p_i $ $ /$$lognlogn$.
3. Tìm 2 số nguyên tố $p$ va $q$ sao cho voi moi so thuc r du lon thi trong khoang $[r, /frac{16.r}{13} ]$
chứa 1 trong cac só co dạng : $ 2^{n} , 2^{n}.p, 2^{n}.q, 2^{n}.p.q$ voi so tu nhien n nao do ! .
Va mot so bai toan khac nua vi du nhu bai toan ve so 'cao cap' (ISL 2005).Day al mot trong nhung co so de cm Dinh li Dirichle !
Noi ve van de nay con rat nhieu vi du khac nua nhung noi chung nhung vi du nay chi de tham khao ren luyen va kiem tra tinh dung dan mot so bai toan
Bac nao hoc thich chuyen sau ve cai nay thi nghien cuu them thoi

Thực ra cái bổ đề minh đề cập đó có thể tổng quát cho $a,b$ và$(a,b)=1$ $a+b \neq 2^{h} $
Sau đây là một số bài toán khác :
1 .Cm rằng với mọi $m,a,b$ và$(a,b)=1$ $a+b \neq 2^{h} $ thì tồn tại $n$ao cho :
a, $n$ có dúng m uớc nguyên tố
b,$ a^{n} + b^{n} \vdots n $ ( TQ IMO )
2/ Cm tồn tại n sao cho : $ a^{n} + b^{n} $ có đúng q ước nguyên tố phan biệt với mọi$a,b$ thỏa mãn dk trên .
Mình sẽ viết lời giải một cách rõ rnagf trong thời gian tới
Các bạn thử sức nhé

#10
Khách- lovewin_*

Khách- lovewin_*
  • Khách

Phương trình đồng dư


Định nghĩa:
$ f(x)= a_n x^{n}+ a_{n-1} x^{n-1}+...+ a_{0} $ ( f :D Z[x]) :D
Cho trước m :perp N*(Z*)
Ta nói rằng : Số nguyên a là nghiệm của pt đồng dư :D thi` khi đó f(a) :equiv 0 (mod m)


Bậc của phương trình:
- f(x) :equiv 0 (mod m)
- Bậc của f bằng n
Nếu
$ a_n $ :D 0 (mod n) khi đó bậc phương trình f =0 là n
$ a_n $ :equiv 0 (mod m) ,gọi $ a_k $ là số lớn nhất về chỉ số sao cho: $ a_n $ :D 0(mod m) nếu :D k $ a_k $ :equiv 0 (mod m) thì pt ko có bậc

Phương trình đồng dư với modun nguyên tố
Xét pt f(x)=0 (mod p),p :in P,$ f(x)= a_n x^{n}+ a_{n-1} x^{n-1}+...+ a_{0} $ khi đó sẽ có 2 khả năng
kn1: :D x :in Z đều là nghiệm của pt
kn2: Tồn tại đa thức g(x) bậc của g(x)<p sao cho f(x) :equiv 0 (mod p) khi và chỉ khi g(x) :equiv 0 (mod p) (cái này dễ dàng cm đc)
Khi đó ta dẫn đến
Định lý : Phương trình f(x) :equiv 0(mod p),p :in P bậc n có nhiều nhất là n nghiệm phân biệt
Hệ quả: Cho đa thức hệ số nguyên,nếu có (n+1) số nguyên phân biệt theo mod p $ u_{1}, u_{2},..., u_n+1$ để f(x) =0 thì tất cả các hệ số đều chia hết cho p

Bài viết đã được chỉnh sửa nội dung bởi lovewin: 30-06-2007 - 16:58


#11
lyxuansang91

lyxuansang91

    Trung sĩ

  • Thành viên
  • 145 Bài viết
cám ơn anh Cường rất nhiều thời gian vừa qua không xem được TeX mong các bạn thông cảm và mình đền bù bằng bài dịch trong tập của Phan Phương Đức đưa
<span style='color: #FF8C00'><strong class='bbc'><em class='bbc'><span style='font-size: 36px;'>Em muốn học giỏi toán</span></em></strong></span>

#12
ThangTongHop

ThangTongHop

    Trung sĩ

  • Thành viên
  • 176 Bài viết
Ta giới thiệu 1 cách tiếp cận cho thặng dư bình phương
Gọi ( $ \dfrac{D}{p} $ ) là ký hiệu Lagendre với p là số nguyên tố, trong đó
( $ \dfrac{D}{p} $ )=0 nếu p|D
( $ \dfrac{D}{p} $ )=1 nếu D là thặng dư bình phương (mod p), và ( $ \dfrac{D}{p} $ )=-1 nếu ngược lại
Đầu tiên ta có tính chất cơ bản
( $ \dfrac{D}{p} $ ) $ \equiv D^{ \dfrac{p-1}{2} } (modp) $
Ta có các tính chất sau
I. Nếu $D \equiv D'(mod p)$ thì ( $ \dfrac{D}{p} $ )=( $ \dfrac{D'}{p} $ )
II. D,D' không là bội của p thì
( $ \dfrac{D'}{p} $ )( $ \dfrac{D'}{p} $ )=( $ \dfrac{DD'}{p} $ )
III. ( $ \dfrac{-1}{p} $ )=$(-1)^{ \dfrac{p-1}{2} }$
IV. ( $ \dfrac{2}{p} $ )=$(-1)^{ \dfrac{1}{8} (p^{2}-1) }$

Bài viết đã được chỉnh sửa nội dung bởi darksky: 23-07-2007 - 22:24

Cuộc sống không có gì nếu không cố gắng hết sức!

#13
Khách- darksky_*

Khách- darksky_*
  • Khách
Về định lý cơ bản thì $D^{ \dfrac{p-1}{2} }$ đồng dư với 0,1, hoặc -1 mod p.
Ta cm D là thặng dư bình phương mod p $ \Leftrightarrow $ $D^{ \dfrac{p-1}{2} } \equiv 1(mod p)$
Thật vậy từ giả thiết nếu $D^{ \dfrac{p-1}{2} } \equiv m(mod p)$ thì $D \equiv D^{p-1} \equiv m^{2}(mod p) $
Đảo lại do p nguyên tố nên ta có thể phân 2 tập (1,2,..,p-1) và (1,2,..,p-1) thành duy nhất các cặp (x,y) sao cho $xy \equiv D(mod p)$ với (D,p)=1( vì trường hợp p|D hiển nhiên). Nếu trong tất cả các cặp có $x \neq y $ tức D không là thặng dư bình phương mod p thì theo định lý Wilson $D^{ \dfrac{p-1}{2} } \equiv (p-1)! \equiv -1(mod p)$
Mặt khác nếu tồn tại cặp nào đó x=y thì thì cũng có cặp p-x=p-y và đó là 2 cặp duy nhất có tính chất như vậy( CM điều này bằng phản chứng)
Từ đó ta có ngay $D^{ \dfrac{p-1}{2} } \equiv -(p-1)! \equiv 1(mod p)$
Vậy định lý được CM

Các định lý còn lại CM như sau
định lý I. hiển nhiên theo định lý cơ bản
định lý II ta cũng dựa vào tính chất cơ bản và tính chất của đồng dư thức
$D^{ \dfrac{p-1}{2} }.D'^{ \dfrac{p-1}{2} } \equiv (DD')^{ \dfrac{p-1}{2} }(mod p)$
Định lý 3 cũng là hệ quả của định lý cơ bản. Từ đó ta có kết quả quen thuộc -1 là thặng dư bình phương mod p(p nguyên tố) khi và chỉ khi p=4k+1

Với định lý IV ta có 1 định lý tổng quát hơn như sau
V. ( $ \dfrac{D}{p}$ )= $ (-1)^{k} $ trong đó k là số các thặng dư lớn hơn p/2 trong dãy các thặng dư
D, 2D, 3D, ..., $ \dfrac{1}{2} (p-1)D$
Từ đó ta CM các tính chất VI và VII
VI. 2 là số chính phương mod p(p nguyên tố) khi và chỉ khi p=8k$ \pm $1
VII. 3 là số chính phương mod p(p nguyên tố) khi và chỉ khi p=12k$ \pm $1
(Lưu ý hai khái niệm thặng dư bình phương mod p và số chính phương mod p là tương đương)

#14
quangpbc

quangpbc

    Trung sĩ

  • Thành viên
  • 132 Bài viết
uhm.Cái này cũng là một phần rất hay .Mình cũng đã từng học về nó.Có nhiều điều thú vị lém.
Vd cái nhở :
Cho đa thức $P(x)=(x^2-2)(x^2-3)(x^2-6)$ .Chứng minh rằng vói mọi số nguyên tố $p$ đều tìm được $n$ sao cho$p|P(n)$ :)

Bài viết đã được chỉnh sửa nội dung bởi quangpbc: 25-07-2007 - 23:29

How can i know what the love mean ?


#15
Khách- darksky_*

Khách- darksky_*
  • Khách

uhm.Cái này cũng là một phần rất hay .Em cũng đã từng học về nó.Có nhiều điều thú vị lém.
Vd cái nhở :
Cho đa thức $P(x)=(x^2-2)(x^2-3)(x^2-6)$ .Chứng minh rằng vói mọi số nguyên tố $p$ đều tìm được $n$ sao cho$p|P(n)$ :)


Uh cái này là 1 ứng dụng hay đấy
Ta cm với p nguyên tố thì 1 trong các số 2, 3, 6 là thặng dư bình phương mod p( suy ra từ định lý II)
Từ đó ta có ngay đpcm

#16
Khách- darksky_*

Khách- darksky_*
  • Khách
Cũng giới thiệu qua chút về luật thuận nghịh bình phương( mà tên khác là luật tương hỗ Gauss)
Ta sẽ CM định lý sau
với p, q nguyên tố lẻ
($ \dfrac{p}{q} $) ($ \dfrac{q}{p} $)= $ (-1)^{ \dfrac{p-1}{2} . \dfrac{q-1}{2} } $

Ta đi ngược lại vấn đề như sau
Sử dụng phép đếm cặp số ta sẽ CM bổ đề
$ \dfrac{p-1}{2} . \dfrac{q-1}{2} $ = $ \sum\limits_{l=1}^{ \dfrac{q-1}{2} } [ \dfrac{lp}{q}] $ + $ \sum\limits_{k=1}^{ \dfrac{p-1}{2} } [ \dfrac{kq}{p} ] $
Cả 2 về của đẳng thức trên đều là số cặp (lp, kq) với $ k \leq \dfrac{p-1}{2}$ và $ l \leq \dfrac{q-1}{2}$

Bây h ta cm nốt $ \sum\limits_{l=1}^{ \dfrac{q-1}{2} } [ \dfrac{lp}{q}] $= ($ \dfrac{p}{q} $)
Ta sử dụng định lý trong bài viết bên trên
np= q$ [ \dfrac{np}{q} ]$+ $ u_{n} $ trong đó $ u_{n} $ là số dư trong phép chia ở biểu thức phần nguyên. Theo định lý đã nói ($ \dfrac{p}{q} $) = $ (-1)^{v} $ với v là số thặng dư np thuộc khoảng (q/2,q)
Đặt $ u_{i}=p-s_{i} $ với $ u_{i}< p/2$
Tổng các $ u_{n} $ sẽ cùng tính chẵn lẻ với v+$ \sum r_{i} $+ $ \sum s_{i} $ rồi dùng 1 vài bước biến đổi nữa ta sẽ có đpcm

#17
Khách- darksky_*

Khách- darksky_*
  • Khách
Một vài ứng dụng của định lý về thặng dư bình phương
1. Có vố số số nguyên tố dạng 8k-1, 8k+1
2. có vô số số nguyên tố dạng 8k+3, 8k+5
3. Có vô số số nguyên tố dạng 24k-1
4. Có vô số số nguyên tố dạng 5k-1
5. Mọi p nguyên tố dạng 6k+1 đều biểu diễn được dưới dạng $ p= 3x^{2}+ y^{2} $ với các số nguyên dương x,y

#18
FOOL90

FOOL90

    Thiếu úy

  • Thành viên
  • 628 Bài viết
Kí hiệu $ F_n$là số FIBONACCI thứ$ n$
Chứng minh rằng :
$ p| F_{p -(\dfrac{p}{5})}$ trong đó $ p $ là số nguyên tố !
HINT : Trong chứng minh sẽ gặp thặng dư bình phương!
Take it easy

#19
MathStupid

MathStupid

    Binh nhì

  • Thành viên
  • 13 Bài viết
$+ \ p=5,p=2 ... \\ + \ \left( \dfrac{p}{5} \right) = 1 \Rightarrow \left( \dfrac{5}{p} \right) = 1 \\ F_{p-1} = \dfrac{ \sum\limit_{2 \not| k }^{p-1} {p-1 \choose k} 5^{\dfrac{k-1}{2}} }{2^{p-2} }; \, 2 \not| k \Rightarrow {p-1 \choose k} \equiv -1 (mod p) \text{ so } p|F_{p-1} \Leftrightarrow p|\sum\limit_{2 \not| k }^{p-1} 5^{\dfrac{k-1}{2}} = \dfrac{5^{\dfrac{p-1}{2} } -1 }{4} \\+ \ \left( \dfrac{p}{5} \right) = -1 \Rightarrow \left( \dfrac{5}{p} \right) = -1 \\ F_{p+1} = \dfrac{ \sum\limit_{2 \not| k }^{p+1} {p+1 \choose k} 5^{\dfrac{k-1}{2}} }{2^{p} } ; \ k \not\equiv 0,\pm 1 (mod p) \Rightarrow p|{p+1 \choose k} \text{ so } p|F_{p+1} \Leftrightarrow p|5^o + 5^{\dfrac{p-1}{2}}$
Một bài khác cũng không khó lắm: $p=4k+1$, chứng minh $p|k^k - 1$

Bài viết đã được chỉnh sửa nội dung bởi MathStupid: 05-08-2007 - 11:23


#20
QUANVU

QUANVU

    B&S-D

  • Hiệp sỹ
  • 4378 Bài viết
Đọc hoài vẫn chưa thấy Định lí tương ứng của Lucas http://en.wikipedia.org/wiki/Lucas'_theorem . :D

P.S. : Rõ ràng việc lập ra một topic thế này là không tốt, phải cần cả một box con để làm điều này.
1728




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

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