Number Theory

Đề bài :
Bài 1
[QUOTE=thekid112;74894]Các bạn làm bài này cho vui chút nhé:
Tìm tổng tất cả các ước của 1000000000 (1 tỉ)[/QUOTE]
link:
http://www.maths.vn/forums/showthread.php?t=14443
Bài 2
[QUOTE=hoc_tro9x;83642]cho số nguyên dương n, 2n có 45 ước số nguyên dương, 5n co 48 ứoc số nguyên dương.Hỏi 10n có bao nhieu uoc só nguyen duong
em ra 90 ko bit dung ko[/QUOTE]

http://www.maths.vn/forums/showthread.php?t=16049
Bài 3
[QUOTE=’hizo[+_0];64502′][B][COLOR=”RoyalBlue”]Phần số học:[/COLOR][/B]
3. Cho {2}^{n} + 1 là số nguyên tố. CMR n có dạng {2}^{k} (k \in Z).
4. Cho a, n nguyên dương, p nguyên tố. CMR nếu {2}^{p} + {3}^{p} = {a}^{n} thì n = 1.
5. Giả sử {2}^{n} + 1 = xy (x, y, n nguyên, x, y :geq 2, n :geq 1). CMR {2}^{a} | (x - 1) :Leftrightarrow {2}^{a} | (y - 1).[/QUOTE]
[QUOTE=’hizo[+_0];64517′]
6. CMR với \forall n nguyên dương, {2}^{{2}^{n}} + {2}^{{2}^{n - 1}} có không ít hơn n ước nguyên tố khác nhau.
7. Cho a là số tự nhiên lẻ. CMR với :forall m, n nguyên dương và m khác n, {a}^{{2}^{n}} + {2}^{{2}^{n}}{a}^{{2}^{m}} + {2}^{{2}^{m}} nguyên tố cùng nhau.[/QUOTE]

Link:3,4,5,6,7
http://www.maths.vn/forums/showthread.php?t=12831
Tổng quát Bài 3:
[QUOTE=anh hung;64577]giả sử a là số nguyên dương và{a}^{m}+1 là số nguyên tố.Chứng minh rằng m={2}^{n} với số nguyen dương n nào đó[/QUOTE]
http://www.maths.vn/forums/showthread.php?t=9861

Bài 8

[QUOTE=khanhtm;140971]Cho n là số lẻ, n>1.Chứng minh rằng:
{3}^{n}+1 không chia hết cho n[/QUOTE]
link:
http://math.vn/showthread.php?p=134&posted=1#post134
http://www.maths.vn/forums/showthread.php?t=24973

Bài 10
[QUOTE=anh hung;64570]mình có mấy bài toán vẫn chưa làm được

mong các bạn giải hộ mình nhé:

1> Chứng minh rằng nếu;
f(x)={a}_{n}{x}^{n}+{a}_{n-1}{x}^{n-1}+.......+{a}_{1}{x}^{1}+{a}_{0}
là đa thức với hệ số nguyên, thì tồn tại y sao cho f(y) là hợp số[/QUOTE]
link :http://www.maths.vn/forums/showthread.php?t=9861
Bài 11
[QUOTE=chien than;79040]Chứng minh rằng tồn tại vô hạn số nguyên tố p thỏa mãn 13|p^3+1[/QUOTE]
link http://www.maths.vn/forums/showthread.php?t=15217

Bài 12
[QUOTE=Nguyễn;1352]1. Với m,n nguyên dương thì \phi(m.n)=(m,n).\phi([m,n]).

2. Nếu (a,n)=1 thì a^{\phi(n)}=1(mod n).[/QUOTE]
http://math.vn/showthread.php?t=363

Posted in All. 13 Comments »

13 Responses to “Number Theory”

  1. vanchanh123 Says:

    Bài 1:
    10^9=2^9.5^9
    Đặt \sigma(n)=\sum_{d|n,d>0}d
    Một số kết quả liên quan cho : \sigma(.)
    i) Hàm \sigma(.) này nhân tính
    ii) n=\prod_{i=1}^{k}p_i^{r_i} \Rightarrow \sigma(n)=\prod_{i=1}^{k}\frac{p_i^{r_i+1}-1}{p_i-1}

    Do đó :\sigma(10^9)=\frac{(2^{10}-1)(5^{10}-1)}{4}
    Kết quả của ll931110 trước khi tính cụ thể là đúng , việc tính ra cụ thể thì mình chưa thể kiềm tra

    Bài 2:

    Tương tự hàm \sigma(.), hàm \gamma(n)=\sum_{d|n,d>0}1 cũng là hàm nhân tính và có một kết quả tính toán cụ thể như sau:
    n=\prod_{i=1}^{k}p_i^{r_i},r_i>0\Rightarrow \gamma(n)=\prod_{i=1}^{k}({r_i+1})

    Nếu sử dụng công thức tính toán này thì bài toán trở nên đơn giản
    Trong công thức tính ta thay đổi chút đề thuận tiện :
    n=2^x5^y\prod_{i=1}^{k}p_i^{r_i},r_i>0,p_i>5 \forall i=1,2,...,k\\\Rightarrow\gamma(n)=(x+1)(y+1)\prod_{i=1}^{k}({r_i+1})
    Đặt t=\prod_{i=1}^{k}({r_i+1})
    Nên \gamma(2n)=(x+2)(y+1)t=45\gamma(5n)=(x+1)(y+2)t=48
    Tính \gamma(10n)=(x+2)(y+2)t=\text{??}

    Tìm x,y,t
    t |(45,48)=3
    * TH: t=1
    Ta có :\fbox{(x+2)(y+1)=45\\ \text{and}  (x+1)(y+2)=48} vô nghiệm tự nhiên
    * TH: t=3
    Ta có :\fbox{(x+2)(y+1)=15\\ \text{and}   (x+1)(y+2)=16}\Rightarrow x=3,y=2

    \gamma(10n)=(x+2)(y+2)t=5.4.3=60

    Bài 3:
    TH1: n có một ước thật sự m lẻ, khi đó : 11 2^n+1\equiv (-1)^n+1\equiv 0 \text{ mod } 3,2^n+1>3
    nên 2^n+1không là nguyên tố
    Do đó :n=1 hoặc chỉ có ước dạng 2^k\Rightarrow n=2^m
    Bài 4:

    Bài 5:
    2^a|(x-1) , hiền nhiên a\le n \Rightarrow (x,2^{a})=1,2^a|2^n(*)
    2^n-(x-1)=x(y-1) (1)
    Từ (*) và (1), suy ra đpcm

    Bài 6:

    Bài 7:

    Bài 8:

    Bài 9:

    Bài 10:

  2. vanchanh123 Says:

    x^7+2x=\sqrt{x^9+2x^4}
    Tex tham khảo
    http://truonglang.wordpress.com/about/
    ———-
    Bản gốc tại đây. (translated by hpngon)

    Gắn thêm các chú thích ở bên lề trái hoặc phải của trang sẽ thuận tiện hơn, dễ thấy hơn là viết các chú thích hay bình luận ngay trong bài viết.

    LaTeX cung cấp một cách để thêm chú thích ở bên lề rất dễ dàng mà không làm thay đổi cấu trúc bài viết hay ảnh hưởng đến việc canh lề.

    Đây là một lệnh chuẩn trong LaTeX nên bạn không cần phải sử dụng gói lệnh nào cả. Chỉ cần nhớ lệnh thôi. Bạn có thể chú thích bất cứ thứ gì bạn muốn, chữ hoặc công thức. Ví dụ bạn muốn thêm dòng chữ Năm Canh Dần, bạn gõ như sau:

    \marginpar{Năm Canh Dần}
    \marginpar{Năm Canh Dần}

    http://hpngon.wordpress.com/2010/03/30/chu-thich-ben-l%E1%BB%81-trong-latex/

    ————-
    Cài latex http://www.ngohaibac.net/cai-dat-latex-plugin-cho-blog-wordpress/

  3. vanchanh123 Says:

    Chủ điểm : Căn nguyên thủy
    1. Định lý 1:[Sự tồn tại căn nguyên thủy]
    Các số tự nhiên dạng : 2,4,p^{t},2p^{t},p\in P,p>3 đều có căn nguyên thủy

    . .(Note: P là tập hợp các số nguyên tố)
    . . Một định lý về nhóm liên quan Z_n^{*} là nhóm cyclic . .khi và chỉ khi n có dạng 2,4,p^{t},2p^{t},p\in .          P,p>3
    2. Xét định lý 2:
    Nếu p là số nguyên tố lẻ , có căn nguyên thủy r thì r hoặc r+p là căn nguyên thủy của p^2

    Trước hết , ta thấy :
    i) \phi(p^2)=p^2(1-\frac{1}{p})=p(p-1)
    ii) r^{\phi(p)}\equiv r^{p-1}\equiv 1 \text{ mod } p

    Rỏ ràng r^{\phi(p^2)}=r^{p(p-1)}=[(r^{p-1}-1)+1]^{p}=\sum\limits_{i=0}^{p} C_{p}^{i}(r^{p-1}-1)^i  (1.1)
    Ta có hai kết quả sau :
    2i) Với p nguyên tố thì p|C_{p}^{i},\forall i \in [1,p-1]
    2ii) r^{p-1}\equiv 1 \text{ mod } p

    Từ 1.1 ,2i, 2ii) \Rightarrow r^{\phi(p^2)}  \equiv 1+(r^{p-1}-1)^p\text{ mod } p^2

    p|(r^{p-1}-1 )\Rightarrow p^x|(r^{p-1}-1 )^x \Rightarrow (r^{p-1}-1)^p\equiv 0\text{ mod } p^2
    Do đó r^{\phi(p^2)}  \equiv 1\text{ mod } p^2
    Gọi n=\text{ord}_{p^2}(r) thì n|p(p-1), mặt khác :
    r^{n}  \equiv 1\text{ mod } p^2\Rightarrow r^{n}  \equiv 1\text{ mod } p . Từ đây , suy ra : \phi(p)=p-1|n

    Do vậy : \left [\begin{array}{l}n=p-1\\n=p(p-1)\end{array}\right.

    Case 1: n=p(p-1) nghĩa là r là căn nguyên thủy của p^2
    Case 2: n=p-1
    Ta cm t=\text{ord}_{p^2}(r+p) không là p-1
    Rỏ ràng :
    3i) (r+s)^{p-1}\equiv 1+(p-1)pr^{p-2} \text{ mod }p^2
    3ii) (r+s)^{p(p-1)}\equiv 1 \text{ mod }p^2 được chứng minh như trên
    Nếu t=p-1 thì từ 3i) suy ra p|r^{p-2}
    (vô lý , vì r là căn nguyên thủy của p)
    Mặt khác :t|p(p-1) , kết hợp t\neq p-1 \Rightarrow t=p(p-1)

    Suy ra đpcm
    3. Định lý 3: Với \large p nguyên tố lẻ , chứng minh rằng \large  p^k có căn nguyên thủy với mọi k nguyên dương.
    Và nếu \large  r là căn nguyên thủy của \large  P^2 thì \large  r cũng là căn nguyên thủy của \large p^k

  4. vanchanh123 Says:

    tem: ten cac them :
    Andrea by Lucian E. Marin

  5. vanchanh123 Says:

    Bài tập chương 3:
    Bài 1 / P87
    Hàm Mobius được định nghĩa : \mu(n)=\left [ \begin{array}{l}(-1)^k (1)\\\mu(1)=1\\\mu(n)=0 (2)\end{array}\right.
    (1) n không có ước chính phương khác 1, k là số ước nguyên tố của n
    (2) n có ước chính phương khác 1
    CMR: với n>1 thì \sum_{d|n}\mu(d)=0

    Giải :
    Trước hết , ta nhận thấy 2 điều sau :
    i) hàm \mu(n) là hàm nhân tính,
    ii) Nếu \mu(.) thì G(n)=\sum_{d|n}\mu(d) cũng là hàm nhân tính

    Ta công nhận mệnh đề ii), tiến hành chứng mệnh đề i) dùng định nghĩa hàm nhân tính

    Lấy (a,b)=1  . Với a=\prod_{i=1}^{n} p_i^{r_i},b=\prod_{j=1}^{m} q_j^{t_j}, p_i,Q_j\in P

    (a,b)=1 nên p_i\neq q_j,i=...,j=...
    Nếu tồn tại r_i hoặc t_j  là số chẳn thì \mu(ab)a=0=\mu(a)\mu(b)

    Ngược lại :a\neq 1, b\neq 1,2|r_i,2|t_j
    Ta có : \mu(ab)=(-1)^{n+m}=(-1)^n(-1)^m=\mu(a)\mu(b)
    (TH: a=1 hoặc b=1 thì kq hiển nhiên)

    Như vậy \mu(.) là hàm nhân tính

    ————————-
    Chứng minh mệnh đề trên😦 G(.)\equiv 0) bằng qui nạp

    * Kiểm chứng với n=1
    * Giả thiết qui nạp : Kết quả đúng đến n=k , nghĩa là mọi j\le k thì G(j)=0
    *n=k+1
    Nếu k+1 là số nguyên tố hoặc lũy thừa của một số nguyên tố thì kiểm tra đơn giản bằng định nghĩa của G đề có G(k+1)=0
    Nếu k+1 là hợp số và không là lũy thừa của một số nguyên tố thì k+1 có thể tách thành k+1=ab , với (a,b)=1,a,b<k+1
    Khi đó , sử dụng tính chất hàm G là hàm nhân tính để tính G(k+1)=G(ab)=G(a)G(b)=0.0=0
    Từ đây suy ra đpcm

  6. vanchanh123 Says:

    Trích từ http://vnmaths.com/de-thi-va-dap-an/2009/12/2753/d%E1%BB%81-thi-mon-d%E1%BA%A1i-s%E1%BB%91-va-s%E1%BB%91-h%E1%BB%8Dc-2/
    Đề Thi Môn Đại Số và Số Học 2
    Tháng Mười Hai 26th, 2009 VNmaths
    Đến phản hồi

    Dành cho sinh viên K58

    Thời gian làm bài: 120 phút

    Câu 1: a) Cho f,g: N^* \to C là hai hàm nhân. Hàm số h: N^* \to C được xác định như sau:

    h(n) = f(n)g(n){\text{ }}\forall {\text{n}} \in {{\text{N}}^*}.

    Chứng minh rằng h là một hàm nhân.

    b) Giả sử số tự nhiên n>1 có phân tích tiêu chuẩn là: . Chứng minh rằng:

    \sum\limits_{d|n} {\mu {{(d)}^2}\tau (d)} = {3^k},

    trong đó \mu là hàm Mobius và \tau(d) là số các ước nguyên dương của d.

    Câu 2: Chứng minh rằng

    [1,2,...,2009,2010] = [1006,1007,....2010].,

    trong đó [a_1,a_2,...,a_n] là bội chung nhỏ nhất của các số nguyên .

    Câu 3: Cho p là một số nguyên tố lớn hơn 7. Chứng minh rằng p^6-1 chia hết cho 504.

    Câu 4: Giải hệ phương trình đồng dư sau:
    ………..

    Câu 5: Giải phương trình đồng dư sau: 7{x^4} - 8x \equiv 2{\text{ (mod 27}}) .

    Câu 6: Cho p là một số nguyên tố lẻ. Tìm điều kiện cần và đủ của p để phương trình x(x-1)+p^2y+1 có nghiệm nguyên.

    Câu 7: Cho x là số tự nhiên lớn hơn 1. Chứng minh rằng nếu p là một ước nguyên tố của x^4+1 thì p \equiv 1 (mod 8). Từ đó hãy chứng minh rằng có vô số số nguyên tố dạng 8k+1,k \in N.

    • vanchanh123 Says:

      Giải danh sách bài tập trên

      Bài 7:
      Xuất phát từ ý tưởng giải bài toán : p=4k+3. CMR : p không thể là ước của a^2+1

      Chứng minh kết quả này , có hai cách để cm:
      i) Dùng thặng dư bình phương
      ii) Dùng định lý Fermat

      Cm dùng i) Phản chứng
      a^2+1 \equiv 0 \text{ mod } p nghĩa là -1 là một thặng dư bình phương theo mod p.
      Nên (-1)^{\frac{p-1}{2}}=1. Do đó , p=4k+1 với k\in N nào đó . (mâu thuẩn với gt)

      Chứng minh dùng ii)
      Nếu p|(x^2+1)\Rightarrow (p,x)=1.Nên $latexx^{p-1}\equiv 1 \text{ mod } p$ (định lý Fermat)
      Mặt khác , nếu với p=4k+3 , ta có :
      a^{p-1}=a^{4k}a^2\equiv a^2\equiv -1 \text{ mod }p

      ————-
      Dùng i) không thể giải quyết được cho bài toán 7
      Dùng ii) thì có thể giải quyết .
      Dùng kết quả bổ đề trên , ta thấy p=4k+1, nghĩa là p có dạng : 8k+1 hoặc 8k+5

      Ta chứng minh p\neq 8k+5
      Thật vậy : p=8k+5 thì
      x^{p-1}=x^{8k}x^4\equiv x^4 \equiv -1 \text{  mod} p Mâu thuẩn với định lý Fermat

    • vanchanh123 Says:

      Câu 2:

      Ta cố gắng chứng minh phần 1,2,...,1005  đều là ước của phần sau 1006,...,2010
      Nhưng xem ra không dễ.

      Dùng phương pháp qui nạp toán học để chứng minh điều đó .

      Xét mệnh đề :
      P(n) : [1,2,...,2n]=[n+1,...,2n]
      !!! Ta dễ dàng thấy với n=1 thì mệnh đề P(1)  đúng
      !!! Giả sử mệnh đề đúng với n=k   . Nghĩa là : [1,2,...,2k]=[k+1,..,2k]

      !!! Với n=k+1
      Ta có : [1,2,...,2n,2n+1,2n+2]=[[1,2,..,2n],2n+1,2n+2]= [[n+1,...,2n],2n+1,2n+2]=[n+1,n+2,...,2n+1,2n+2]
      Ta thấy (n+1)|(2n+2)
      Do đó : [1,2,...,2n,2n+1,2n+2]=[n+2,...,2n+1,2n+2]
      Tức P(k+1) đúng
      Nên kết quả trên đúng với mọi n theo nguyên lý qui nạp

  7. vanchanh123 Says:

    Bài 18/P.89

    a) Chứng minh : nếu đa thức f có bậc n, mà có quá n nghiệm theo mod p thì tất cả các hệ số của đa thức đều chia hết cho p
    b) Cho p là số nguyên tố. CMR: tất cả các hệ số của đa thức
    f(x)=\prod_{i=1}^{p-1} (x-i) -x^{p-1}-x+1 đều chia hết cho p
    c) Dùng câu b để chứng minh định lý Wilson

    Giải :
    a/ Ta sử dụng định lý :
    p là đa thức bậc n có hệ số ứng với bậc cao nhất khác 0 trong Z_p thì p không quá n nghiệm theo mod p

    Dùng kết quả này , thì a_n\equiv 0 \text{ mod } p
    Tiếp tục áp dụng định lý trên với g_{i-1}(x)=g_i(x)-a_ix^i ,Trong đó :g_n(x)=f(x),i=n,n-1,...,1
    Suy ra được a_{n-1}=0=...=a_0
    b/ Cố gắng tìm n+1 nghiệm khác nhau

  8. vanchanh123 Says:

    Tiếp tục bài tập 24,25,26/ P.90

    Bài 25: Với n có căn nguyên thủy , chứng minh rằng mọi tích các số nhỏ hơn n , nguyên tố cùng nhau với n đồng dư với -1 \text{ mod } n

      Note: Công cụ đắc lực mà giả thuyết tồn tại căn nguyên thủy là n có dạng 2,4,p^t,2p^t,p\in P,p>3 ,t\in N^{*}
    • Nhận xét 1: Giả sử r là căn nguyên thủy của n.Khi đó : 1,r,r^2,..,r^{\pi(n)} tạo thành hệ thặng dư thu gọn \text{ mod } n
      \Rightarrow \prod_{i|i<n,(i,n)=1}i=\prod_{i=1}^{\phi(n)}r^i=r^{\frac{\phi(n)(\phi(n)+1))}{2}}
    • Nhận xét 2: Một bài toán khác có liên quan: khi n có căn nguyên thủy thì ptr x^2 \equiv \text{ mod } n chỉ có hai nghiệm x=\pm 1 \text{ mod } n
      Từ nhận xét này , ta thấy :1<j<n-1 , (j,n)=1 \Rightarrow \exists ! i\neq j : ij\equiv 1 \text{ mod } n<
      .Nên \prod_{i|i<n,(i,n)=1}i=1.(n-1)\prod_{i|i<n,(i,n)=1,1<i<n-1}i\equiv n-1 \equiv -1 \text{ mod } n
    • Trong bài toán này , có một số lưu ý : n=2,4 có thể kiểm tra bằng cách tính toán cụ thể
      \phi(2p^t)=\phi(p^t)=p^{t}-p^{t-1}

  9. vanchanh123 Says:

    Bài 26/ P.90 Tìm tất cả các nghiệm ptr đồng dư sau

        a.) x^2+x+1\equiv 0 \text{ mod } 7
        b.) x^2+5x+1\equiv 0 \text{ mod } 7
        c.) x^2+3x+1\equiv 0 \text{ mod } 7

    Giải :
    Lưu ý : 7 có căn nguyên thủy (7 là snt), nên ptr x^2\equiv 1 \text {mod }7 (*) chỉ có hai nghiệm , nên chúng ta sẽ qui các ptr sau về dạng ptr (*)

    • a. )x^2+x+1\equiv 0 \text{ mod } 7
      \Leftrightarrow (2x+1)^2\equiv 4 \text{ mod  }7
      \Leftrightarrow 2.(2x+1)^2\equiv 1\text{ mod  }7 (do 2=4^{-1} trong Z_7^{*})
      \Leftrightarrow  [3(x+1)]^2\equiv 1\text{ mod  }7 (do 2=3^2 trong Z_7^{*})
      \Leftrightarrow  3(x+1)equiv \pm 1\text{ mod  }7
      \Leftrightarrow  x+1 \equiv \pm 3^{-1}\text{ mod  }7

    • b.)  x^2+5x+1\equiv 0 \text{ mod } 7
      \Leftrightarrow (2x+5)^2\equiv 3 \text{ mod  }7
      Ptr vô nghiệm do 3 không chính phương trong mod 7
    • c.) x^2+3x+1\equiv 0 \text{ mod } 7
      \Leftrightarrow (2x+3)^2\equiv 5 \text{ mod  }7

      PT vô nghiệm vì 5 không là chính phương theo mod 7

  10. vanchanh123 Says:

    Bài 4,5 / P.124
    Chứng minh tồn tại vô hạn số nguyên tố dạng

    • 4k+1
    • 8k+1
    • 8k+5
    • 8k+7

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: