GCD

You are currently browsing articles tagged GCD.

I. Khái niệm về căn nguyên thủy.

Số nguyên dương $m$ gọi là có căn nguyên thủy khi và chỉ khi tồn tại số nguyên $a$ sao cho $a$ và $m$ nguyên tố cùng nhau và $$\text{ord}_{m}(a)=\varphi(m).$$

II. Điều kiện để có căn nguyên thủy.

Ta xét đến một ví dụ sau Read the rest of this entry »

Tags: , , , , , ,

Định lý 7.1. Cho $N$ đối tượng, và giả sử rằng có $N_{\alpha}$ đối tượng trong chúng mang tính chất $\alpha$, $N_{\beta}$ đối tượng trong chúng mang tính chất $\beta,\,\ldots,$ $N_{\alpha\beta}$ trong chúng mang cả hai tính chất $\alpha\beta,\,\ldots,\,N_{\alpha\beta\gamma}$ trong chúng mang cả ba tính chất $\alpha,\,\beta $ và $\gamma,\,\ldots$. Lúc đó số các đối tượng không có bất kì tính chất nào được nêu trên được tính bởi công thức
\[\begin{align*}
N &- {N_\alpha } – {N_\beta } – \ldots \\
&+ {N_{\alpha \beta }} +N_{\alpha \gamma } \ldots \\
&- {N_{\alpha \beta \gamma }} – \ldots \\
&+ \ldots – \ldots
\end{align*}; \qquad (A).\] Read the rest of this entry »

Tags: , , , ,

Chọn $x_1;\,x_2;\, \ldots ;\, x_n$ là $n$ số nguyên bất kì. Ta kí hiệu $\min\left(x_1;\,x_2;\, \ldots ;\, x_n\right)$ và $\max\left(x_1;\,x_2 \ldots ;\, x_n\right)$ lần lượt là số nhỏ nhất và số lớn nhất trong các số $x_1;\,x_2;\, \ldots ;\, x_n$ đó. Định lý nêu ra sau đây là hiển nhiên.

Định lý 6.1. Với $a,\,b$ là hai số nguyên dương và $p_1,\,p_2,\,\ldots,p_s$ là những ước nguyên tố thì, lúc đó ta có thể viết
\[\begin{align*}
a &= p_1^{{a_1}}p_2^{{a_2}} \ldots p_s^{{a_s}},\quad {a_v} \ge 0,\\ \\
b &= p_1^{{b_1}}p_2^{{b_2}} \ldots p_s^{{b_s}},\quad {b_v} \ge 0,\,{\mkern 1mu} {\mkern 1mu} {\mkern 1mu} {\mkern 1mu} {p_1} < {p_2} < \ldots {p_s}.
\end{align*}\] Read the rest of this entry »

Tags: , , , , ,

Một modulus được hiểu là một tập hợp các số nguyên với tính đóng với những phép toán cộng và trừ. Nói cách khác, nếu $m,\,n$ là các số nguyên ở trong một modulus thì $m+n$ và $m-n$ cũng thuộc modulus đó. Một modulus chỉ bao gồm duy nhất số $0$ được gọi là modulus $0$. Một tập hợp các số nguyên có dạng một modulus cũng giống như tập của các số nguyên là bội của một số nguyên $k$ cố định.

Định lý 4.1.  Chúng ta có một số tính chất cơ bản như sau về modulus

  1.  Số $0$ thuộc về tất cả các modulus
  2.  Với $a,\,b$ cùng thuộc về một modulus và $m,\,n $ là các số nguyên, lúc đó $am+bn$ cũng thuộc về modulus.

Read the rest of this entry »

Tags: , , , , ,

 

1. Cho số nguyên dương $m$, và $n$ (với $n>1$) số nguyên khác $0$ là $x_1,\,x_2,\,\ldots ,\,x_n$. Biết rằng số nguyên tố $p$ thỏa mãn $p^m\mid x_1$ còn $x_k$ không chia hết cho $p^m$ với mọi $k>1$. Chứng minh rằng:\[\frac{1}{{{x_1}}} + \frac{1}{{{x_2}}} + \ldots + \frac{1}{{{x_n}}} \notin \mathbb Z.\]

2. Cho các số nguyên dương $a,b,c$ thỏa mãn $\gcd (a,\,b,\,c)=1$ và $$a\mid bc,\;b\mid ca,\;c\mid ab.$$ Chứng minh rằng $\dfrac{bc}{a}$ là một số chính phương. Read the rest of this entry »

Tags: , , , , ,

 

Chúng ta quan tâm đến chứng minh cho khẳng định sau đây

Mệnh đề 1. Cho các số nguyên dương $a,\,b,\,c$ thỏa mãn $\gcd (a,\,b)=1$ và $ab=c^2.$ Khi đó, sẽ tồn tại các số nguyên dương $u$ và $v$ sao cho $$a=u^2,\,b=v^2.$$

Chứng minh.  Giả sử $\gcd (b,\,c)=d$, khi ấy ta viết được $b=dv$ và $c=du$. Ở đây, $u,\,v\in\mathbb N^*$ và $\gcd(u,\,v)=1$, lúc đó từ giả thiết ta sẽ có \[\frac{a}{b} =  \frac{{{c^2}}}{{{b^2}}} = \frac{{{d^2}{u^2}}}{{{d^2}{v^2}}} = \frac{{{u^2}}}{{{v^2}}}.\]Do $\gcd(u,\,v)=1$, nên $\gcd\left(u^2,\,v^2\right)=1$. Như vậy, $\frac{a}{b}$ và $\frac{{{u^2}}}{{{v^2}}}$ cùng là dạng biểu diễn phân số tối giản của một số hữu tỷ, cho nên $$a=u^2,\quad b=v^2.$$

$\square$

Khẳng định trên, cũng có thể chứng minh bằng việc viết các phân tích ra thừa số nguyên tố, dựa trên định lý cơ bản của Số Học. Tuy nhiên, tôi ko thích con đường đó. Bây giờ thì, bằng thủ pháp tương tự trên, ta mở rộng vấn đề thành

Mệnh đề 2. Cho trước $n$ là một số nguyên dương lớn hơn $1$, các số nguyên dương $a,\,b,\,c$ thỏa mãn $\gcd (a,\,b)=1$ và $ab=c^n$. Khi đó, tồn tại các số nguyên dương $u$ và $v$ sao cho $$a=u^n,\,b=v^n.$$

Chứng minh.  Giả sử $\gcd (b,\,c)=d$, khi ấy ta viết được $b=dv$ và $c=dw$. Ở đây, $u,\,w\in\mathbb N^*$ và $\gcd(u,\,w)=1$, lúc đó từ giả thiết có \[\frac{a}{{{b^{n – 1}}}} = \frac{{{c^n}}}{{{b^n}}} = \frac{{{d^n}{u^n}}}{{{d^n}{w^n}}} = \frac{{{u^n}}}{{{w^n}}}.\] Do $\gcd(u,\,w)=\gcd(a,\,b)=1$, nên $\gcd\left(u^n,\,w^n\right)=\gcd\left(a,\,b^{n-1}\right)=1$. Như vậy, $\frac{a}{b^{n-1}}$ và $\frac{{{u^n}}}{{{w^n}}}$ cùng là dạng biểu diễn phân số tối giản của một số hữu tỷ, nên $$b^{n-1}=w^n,\quad a=u^n.$$ Đến đây, do vai trò như nhau của $a$ và $b$ trong mệnh đề, nên nếu đi đổi vai trò của $a$ cho $b$, thì ta sẽ có được số nguyên dương $v$ sao cho $b=v^n$.

$\square$

Lưu ý rằng, trong các chứng minh trên, tôi sử dụng hai kiến thức căn bản sau.

Tính chất 1. Nếu $a$ và $b$ là các số nguyên nguyên tố cùng nhau và $n$ là một số nguyên dương, khi đó $a^n$ và $b^n$ cũng là các số nguyên nguyên tố cùng nhau.

Tính chất này có được, nhờ để ý rằng nếu các số nguyên $a$ và $b$ cùng nguyên tố cùng nhau với số nguyên $c$ thì $ab$ cũng thế.

Tính chất 2. Dạng biểu diễn tối giản của một phân số là duy nhất.

Cái tính chất này là do; nếu số nguyên dương $a$ nguyên tố cùng nhau với số nguyên dương $m$, số nguyên dương $b$ lại nguyên tố cùng nhau với số nguyên dương $n$, và $ab=mn$ thì sẽ có $n$ và $a$ là ước số của nhau, cho nên \[a=n,\quad b=m.\]Và những tính chất vừa rồi, sẽ có được từ định lý đẹp đẽ và mạnh mẽ sau đây

Định lý Bézout. Cho các số nguyên dương $a$ và $b$ có ước chung lớn nhất là $d$, khi ấy sẽ tồn tại các số nguyên dương $k$ và $l$ sao cho\[d=ka-lb.\]

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Tags: ,