Phan Đình Trung: Lí thuyết đồng dư

Friday, June 6, 2014

Lí thuyết đồng dư

Bài toán 1 : Cho số nguyên tố $p\equiv 2\;(mod\;3)$ và dãy $a_k=k^2+k+1$ với $k=1,2,...,p-1$ . Chứng minh rằng :

$a_1a_2...a_{p-1}\equiv 3\;(mod\;p)$

Lời giải :

Bổ đề 1 : Cho số nguyên tố $p\equiv 2\;(mod\;3)$ . Khi đó ta có $a\equiv b\;(mod\;p)\Leftrightarrow a^3\equiv b^3\;(mod\;p)$

Chứng minh bổ đề 1 :

Nếu $a\equiv b\;(mod\;p)$ thì hiển nhiên là $a^3\equiv b^3\;(mod\;p)$ . Gỉa sử $a^3\equiv b^3\;(mod\;p)\Rightarrow p\mid (a-b)(a^2+ab+b^2)$

Nếu $p\mid a-b$ thì ta hoàn tất bổ đề.

Nếu $p\mid a^2+ab+b^2\Rightarrow p\mid 4(a^2+ab+b^2)\Rightarrow (a+2b)^2+3a^2\equiv 0\;(mod\;p)\Rightarrow \left ( \dfrac{-3}{p} \right )=1$ .

Suy ra $p\equiv 1\;(mod\;3)$ . Mâu thuẫn.

Bổ đề 2 : Cho số nguyên tố $p\equiv 2\;(mod\;3)$ . Khi đó ta có $\left \{ 2^3-1,3^3-1,...,p^3-1 \right \}$ là hệ thặng dư thu gọn modulo $p$ .

Chứng minh bổ đề 2 :

Nếu tồn tại $i,j$ với $i,j\in \left \{ 2,3,..,p \right \}$ sao cho :

$i^3-1\equiv j^3-1\;(mod\;p)\Rightarrow i^3\equiv j^3\;(mod\;p)$

Theo bổ đề 1 ta có $i\equiv j\;(mod\;p)$ và điều này vô lí. Bổ đề 2 chứng minh hoàn tất.

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

Theo bổ đề 2 ta có :

$(2^3-1)(3^3-1)...(p^3-1)\equiv 1.2.3...(p-1)\;(mod\;p)\Leftrightarrow (2^2+2+1)(3^2+3+1)...(p^2+p+1)\equiv 1\;(mod\;p)\Leftrightarrow a_2a_3...a_p\equiv 1\;(mod\;p)$

Lại chú ý rằng $a_1=1^2+1+1\equiv 3\;(mod\;p),a_p=p^2+p+1\equiv 1\;(mod\;p)$ nên :

$a_1a_2...a_{p-1}\equiv 3\;(mod\;p)$

Bài toán 2 : Chứng minh rằng với mọi số nguyên $k$ , $k<m$ thì luôn tồn tại số nguyên $h$ sao cho $hp^m+p^k\;\vdots \;k!$

Lời giải :

Đặt $k!=p^{a}.t\;\;(gcd(t,a)=1)$

Để ý rằng tập $\left \{ 0,p^{m-k},2p^{m-k},...,(t-1)p^{m-k} \right \}$ chính là hệ thặng dư đầy đủ modulo $t$ nên tồn tại số nguyên $h$ sao cho $h.p^{m-k}\equiv -1\;\;(mod\;t)\Leftrightarrow h.p^{m-k}+1\;\vdots \;t\Leftrightarrow h.p^m+p^k\;\vdots \;p^kt$

Lại theo định lí $Legendre$ thì $a=\underset{i=1}{\overset{+\infty }{\sum}} \left \lfloor \dfrac{k}{p^i} \right \rfloor\leq \underset{i=1}{\overset{+\infty }{\sum} }\dfrac{k}{p^i}<k$

Tức là $p^{k}\vdots p^a$

Từ đó suy ra $h.p^m+p^k\;\vdots \;p^at\Leftrightarrow h.p^m+p^k\;\vdots \;k!$ . Đây là điều phải chứng minh.

Bài toán 3 : Cho các số nguyên dương nguyên tố cùng nhau $m,n$ . Chứng minh rằng : $m^{\varphi (n)}+n^{\varphi (m)}\equiv 1\;(mod\;\;mn)$

Lời giải :

Áp dụng định lí $Euler$ :

$m^{\varphi (n)}\equiv 1\;(mod\;n)\Rightarrow m^{\varphi (n)}+n^{\varphi (m)}\equiv 1\;(mod\;n)\Rightarrow m^{\varphi (n)}+n^{\varphi (m)}=np+1\qquad(p\in \mathbb{N})$

Hoàn toàn tương tự thì :

$m^{\varphi (n)}+n^{\varphi (m)}\equiv 1\;(mod\;m)\Rightarrow np+1\equiv 1\;(mod\;m)\Rightarrow np\equiv 0\;(mod\;m)$ .

Mà $gcd(m,n)=1\Rightarrow m|p\Rightarrow p=mq\qquad(q\in \mathbb{N})\Rightarrow m^{\varphi (n)}+n^{\varphi (m)}=mnq+1$

Hay $m^{\varphi (n)}+n^{\varphi (m)}\equiv 1\;(mod\;mn)$ . Đây là điều phải chứng minh

Bài toán 4 : Tìm số nguyên dương $n$ sao cho :

$a)$ $\varphi (n)=\dfrac{n}{2}$ $b)$ $\varphi (n)=\dfrac{n}{3}$

Lời giải :

Gỉa sử $n=p_{1}^{e_{1}}p_{2}^{e_{2}}...p_{m}^{e_{m}}$ với $p_{i}\in \mathbb{P},e_{i}\in \mathbb{Z}^{+},i=\overline{1,m}$

a) Ta có $\varphi (n)=n\left (1-\dfrac{1}{p_{1}} \right )\left ( 1-\dfrac{1}{p_{2}} \right )...\left ( 1-\dfrac{1}{p_{m}} \right )=\dfrac{n}{2}\Rightarrow 2\prod_{i=1}^{m}\left ( p_{i}-1\right )=\prod_{i=1}^{m}p_{i}$

Gỉa sử trong các số $p_i$ có $t$ số lẻ, khi đó :

$2^{t+1}\parallel 2\prod_{i=1}^{m}p_i\Rightarrow 2^{t+1}\parallel \prod_{i=1}^{m}p_i$ .

Suy ra có $t+1$ số chẵn trong các số $p_i$ $\Rightarrow t=0,m=1$

Kết luận : $\boxed{n=2^{k}}\;\;\;(k\in \mathbb{N}^{*})$

b) Ta có $\varphi (n)=n\left (1-\dfrac{1}{p_{1}} \right )\left ( 1-\dfrac{1}{p_{2}} \right )...\left ( 1-\dfrac{1}{p_{m}} \right )=\dfrac{n}{3}\Rightarrow 3\prod_{i=1}^{m}\left ( p_{i}-1\right )=\prod_{i=1}^{m}p_{i}$