Chủ đề này có 5 trả lời

[ducthinh26032011]

Bài 1:$a,m\in N$.C/m:
$a^{m}\equiv a^{m-\varphi (m)}(modm)$
Bài 2:$n\in N$.C/m:
$\varphi (n)\geq \frac{\sqrt{n}}{2}$

Bài viết đã được chỉnh sửa nội dung bởi ducthinh26032011: 15-10-2012 - 21:06

[nguyenta98]

Bài 1:$a,m\in N$.C/m:
$a^{m}\equiv a^{m-\varphi (m)}(modm)$
Bài 2:$\dpi{150} n\in N$.C/m:
$\varphi (n)\geq \frac{\sqrt{n}}{2}$

Đây là hai bài toán hết sức cơ bản, để giải nó, ta cần một mệnh đề phụ trợ
Giải như sau:
Bổ đề: $\phi(n)$ là số số không vượt quá $n$ mà nguyên tố cùng nhau với $n$, thí dụ $\phi(10)=4$
Khi ấy $\boxed{n=p_1^{a_1}...p_k^{a_k} \Rightarrow \phi(n)=(p_1-1)p_1^{a_1-1}...(p_k-1)^{a_k-1}}$
Chứng minh:
Ta sẽ cm với $gcd(m,n)=1$ thì $\phi(m).\phi(n)=\phi(mn)$
Gọi $d_1,d_2,...,d_k$ là các số không vượt quá $m$ mà $gcd(d_i,m)=1$ và $e_1,e_2,...,e_t$ là các số không vượt quá $n$ mà $gcd(e_i,n)=1$ suy ra xét số có dạng $d_i.n+e_j.m$ khi ấy ta sẽ cm tập các số có dạng $d_i.n+e_j.m$ lập thành hệ thu gọn $mod(mn)$ (hay nó chính là $\phi(mn)$)
Thật vậy thấy hiển nhiên $gcd(d_i.n+e_j.m,mn)=1$ (chú ý $gcd(d_i,m)=gcd(e_j,n)=1$)
Ta có xét $x$ là một số nguyên thỏa $gcd(x,mn)=1$ khi ấy cần cm $x \equiv d_i.n+e_j.m \pmod{mn}$
Hay $x-d_i.n-e_j.m \vdots mn$
Thật vậy ta có xét $x-d_1.n,x-d_2.n,...,x-d_k.n$ vì $gcd(x,mn)=1 \Rightarrow gcd(x,m)=1$ khi ấy $x-d_i.n \not \equiv x-d_t.n \pmod{m}$ (vì giả sử ngược lại suy ra $d_t-d_i \vdots m$ vô lí do chúng nhỏ hơn $m$) khi ấy $x-d_1.n,x-d_2.n,...,x-d_k.n$ lập thành hệ thu gọn $mod(m)$ do đó tồn tại $x-d_i.n \vdots m$ tương tự tồn tại $e_j$ sao cho $x-e_j.m \vdots n$
Khi ấy $x-d_i.n-e_j.m \vdots mn \Rightarrow x \equiv d_i.n+e_j.m \pmod{mn}$
Mà $x<mn$ và thấy $d_i.n+e_j.m$ là duy nhất để $x \equiv d_i.n+e_j.m$ vì nếu ngược lại tồn tại $d',e' \Rightarrow d_i.n+e_j.m \equiv d'n+e'm \pmod{mn} \Rightarrow d_i \equiv d' \pmod{m},e' \equiv e_i \pmod{n}$ khi đó vô lí do chúng cùng nhỏ hơn $m,n$ tương ứng
Do đó $x$ lập thành hệ thu gọn $mod(mn)$ nên công thức $\phi(m).\phi(n)=\phi(mn)$ với $gcd(m,n)$ được chứng minh
Áp dụng đặt $n=p_1^{a_1}...p_k^{a_k}=\phi(p_1^{a_1})...\phi(p_k^{a_k})=(p_1-1)p_1^{a_1-1}...(p_k-1)p_k^{a_k-1}$

Bài 1: Đúng phải là $gcd(a,m)=1$ Áp dụng công thức Euler, ta sẽ cm $a^{\phi(m)} \equiv 1 \pmod{m}$
Ta có $a^{(p_1-1)} \equiv 1 \pmod{p_1}$ (Fermat nhỏ)
Suy ra cm quy nạp ta dễ dàng có $a^{(p_1-1).p_1^{a_1-1}} \equiv 1 \pmod{ p_1^{a_1}}$
Tương tự với $p_2,...,p_k$ suy ra $a^{(p_1-1)p_1^{a_1-1}....(p_k-1)p_k^{a_k-1}} \equiv 1 \pmod{m}$
Áp dụng bổ đề $(p_1-1)p_1^{a_1-1}....(p_k-1)p_k^{a_k-1}=\phi(n)$
Như vậy $a^{\phi(m)} \equiv 1 \pmod{m}$ nên suy ra $a^{m} \equiv a^{m-\phi(m)} \pmod{m}$ đpcm
Bài 2: $\phi(n)=(p_1-1)p_1^{a_1-1}...(p_k-1)p_k^{a_k-1}$
Ta sẽ cm $4.\phi(n)^2\geq p_1^{a_1}...p_k^{a_k}$
$\Rightarrow 4.\prod(p_i-1)^2.\prod(p_i^{2a_i-2})\geq p_1^{a_1}...p_k^{a_k}$
Giả sử $a_1,a_2,...,a_t$ là số mũ mà $a_1=a_2=...=a_t=1$ và $a_{t+1},...,a_k>1$
Khi ấy hiển nhiên có $p_1^{2a_1-2}...p_t^{2a_t-2}\geq p_1^{a_1}.p_2^{a_2}...p_t^{a_t}$
Do vậy cần cm $4.(p_{t+1}-1)^2...(p_k-1)^2\geq p_{t+1}...p_k$
Ta có với $p$ là số nguyên tố mà $p\geq 3$ thì $(p-1)^2>p$ (do $(p-1)^2-p=p^2-3p+1>0$ vì $p\geq 3$)
Nếu trong $p_i$ với $i \in (t+1,...,k)$ mà $p_i>2$ thì BDT đúng, có đpcm
Nếu trong $p_i$ có một số bằng $2$, giả sử $p_{t+1}=2$ khi đó $4.(p_{t+1}-1)^2>p_{t+1}$ và các số nguyên tố còn lại theo công thức $(p-1)^2>p$ với $p\geq 3$ BDT cũng được cm
Tuy nhiên dấu bằng không xảy ra, có lẽ xảy ra khi đề cho là $\dfrac{\sqrt{n}}{\sqrt{2}}$ thì xảy ra

Bài viết đã được chỉnh sửa nội dung bởi nguyenta98: 15-10-2012 - 22:23

[ducthinh26032011]

....

Bài 1 là $a,m$ bất kì mà em.Đâu có $gcd(a,m)= 1$.Em xem lại nhé!
Bài 3:
Tìm $p\in N^{*}$ để các phương trình sau có nghiệm nguyên dương.
$a)x^{2}+y^{2}-pxy-p=0$
$b)x^{2}+y^{2}+z^{2}=pxyz$

[nguyenta98]

Bài 1 là $a,m$ bất kì mà em.Đâu có $gcd(a,m)= 1$.Em xem lại nhé!
Bài 3:
Tìm $p\in N^{*}$ để các phương trình sau có nghiệm nguyên dương.
$a)x^{2}+y^{2}-pxy-p=0$
$b)x^{2}+y^{2}+z^{2}=pxyz$

$a,m$ bất kì thì đâu có đúng anh, thử lấy ví dụ mà xem đây chính là định lý Euler. chỉ đúng khi $gcd(a,m)=1$ hoặc $a \vdots m$
Giải như sau:
Bài 3:
a) $x^2+y^2-p(xy+1)=0 \Rightarrow x^2-x(py)+y^2-p=0$
Giả sử $x\geq y$
Gọi $x_0,y_0$ là nghiệm của phương trình trên mà $x_0+y_0$ nhỏ nhất
Khi đó phương trình $x_0^2-x_0(py_0)+y_0^2-p=0$
Giả sử $y_0^2-p \neq 0$
Theo định lý tam thức bậc hai suy ra tồn tại nghiệm $x_1$ mà $x_1+x_0=py_0,x_1.x_0=y_0^2-p$ suy ra $x_1$ nguyên dương do nếu giả sử ngược lại suy ra $x_1$ âm thì $x_1=-x_1' \Rightarrow x_1'>0 \Rightarrow x_1'^2+x_1'(py_0)+y_0^2-p=0$ mà $x_1'>0$ nên $x_1'(py_0)>p$ suy ra $x_1'^2+x_1'(py_0)+y_0^2-p>0$ vô lí
Do đó $x_1$ dương
Mà $x_0+y_0$ nhỏ nhất do đó $x_1+y_0\geq x_0+y_0 \Rightarrow x_1\geq x_0$
Ta lại có $x_0.y_1=y_0^2-p \Rightarrow x_0^2\le y_0^2-p<y_0^2$ suy ra $x_0<y_0$ vô lí
Như vậy điều giả sử là sai hay $y_0^2-p=0 \Rightarrow p=y_0^2$ hay $p$ là số chính phương
Như vậy ta chỉ ra điều kiện cần $x^2+y^2-pxy-p=0$ có nghiệm là $p$ chính phương, giờ ta chỉ ra điều kiện đủ tức chỉ ra nghiệm $(x.y)$ khi $p=N^2$ là số chính phương, thật vậy chọn $x=N^3,y=N$ khi đó dễ cm $(x,y)$ là nghiệm do đó ta có điều kiện cần và đủ
$$\boxed{x^2+y^2-pxy-p=0 \Leftrightarrow p=N^2}$$

Bài viết đã được chỉnh sửa nội dung bởi nguyenta98: 16-10-2012 - 21:21

[ducthinh26032011]

$a,m$ bất kì thì đâu có đúng anh, thử lấy ví dụ mà xem đây chính là định lý Euler. chỉ đúng khi $gcd(a,m)=1$ hoặc $a \vdots m$
Giả sử $x\geq y$
Theo định lý tam thức bậc hai suy ra tồn tại nghiệm $x_1$ mà $x_1+x_0=py_0,x_1.x_0=y_0^2-p$ suy ra $x_1$ nguyên dương

Thầy nói đó là định lí $Euler$ mở rộng với mọi $a,m$ nguyên dương.Em xem lại nhé!
Còn chỗ bôi đỏ,anh nghĩ từ đó mới suy ra được $x_{1}$ nguyên thôi chứ chưa chắc dương vì chưa chắc $y_{0}^{2}\geq p$

Bài viết đã được chỉnh sửa nội dung bởi ducthinh26032011: 16-10-2012 - 20:53

[Secrets In Inequalities VP]

Bài 1:$a,m\in N$.C/m:
$a^{m}\equiv a^{m-\varphi (m)}(modm)$

Ta cần chứng minh :
$A=a^m-a^{m-\phi (m)}= a^{m-\phi (m)}(a^{\phi (m)}-1)$ $\vdots m$
Giả sử q là ước nguyên tố bất kì của m và $\alpha$ là số mũ của $q$ trong $m$ .
Ta sẽ chứng minh rằng nếu $(a,q)=1$ thì $a^{\phi (m)}-1\vdots q^\alpha$ và nếu $a\vdots q$ thì
$a^{m-\phi (m)}-1\vdots q^\alpha$ . Từ đó $A\vdots q^{\alpha }$
+ Nếu $(a,q)=1$ . Theo Ơle : $a^{\phi (q^\alpha) }-1\vdots q^\alpha$
Mà dễ thấy $\phi (q^\alpha )\mid \phi (m)\rightarrow a^{\phi (m) }-1\vdots a^{\phi (q^\alpha) }-1\vdots q^\alpha$ $\rightarrow A\vdots q^\alpha$
+ Nếu $a\vdots q\rightarrow a^{m-\phi (m)}\vdots q^{m-\phi (m)}$.
Mà dễ thấy $m-\phi (m)\geq \alpha$. Vì có ít nhất $\alpha$ số không nguyên tố với m là $q,q^{2},...,q^\alpha$.
Suy ra $a^{m-\phi (m)}\vdots q^{m-\phi (m)}\vdots q^{\alpha }\rightarrow A\vdots q^{\alpha }$
Thế là đã xong vì q là ước nguyên tố bất kì của m nên mọi ước của m đều có TC này .

Bài viết đã được chỉnh sửa nội dung bởi Secrets In Inequalities VP: 18-10-2012 - 20:09