You are currently browsing articles tagged GCD.
Ở trong bài viết này, nhân tiện việc xử lý bài Croatia TST2011 tôi nói về khái niệm ước số chung lớn nhất của hai số hữu tỷ, đồng thời là khái niệm về hai số hữu tỷ nguyên tố cùng nhau. Trong bài viết, tôi ký hiệu tập các số nguyên tố là $\mathbb P$, còn để thay cho diễn đạt “hai số hữu tỷ $x$ và $y$ nguyên tố cùng nhau”, tôi sẽ sử dụng ký hiệu $x\bot y$.
Xin nêu lại nội dung bài toán trong đề thi Croatia kia, như sau
Read the rest of this entry »Tags: Định Giá p-adic, GCD, Nền Tảng
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: Căn Nguyên Thuỷ, Cấp và căn theo modulo, Định Lý Euler, Định Lý Fermat bé, GCD, Phi hàm Euler, Số Học
Đị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: GCD, LCM, Nguyên Lý Bù Trừ, Số Học, Tổ Hợp
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: Bội Chung Nhỏ Nhất, Định Lý Bézout, Định Lý Cơ Bản Của Số Học, GCD, LCM, Ước Chung Lớn Nhất
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
Tags: Định Lý Bézout, GCD, Modulus, Số Học, Thuật Toán Euclidean, Ước Chung Lớn Nhất
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,\quad b=v^2.$$ Read the rest of this entry »
Tags: GCD, Sự Nguyên Tố Cùng Nhau
Phản Hồi