Cho các số nguyên dương $m,\,n$ và số nguyên $a$ thỏa mãn $\gcd(a,\,m)=1$, giả sử phân tích ra thừa số nguyên tố của $m$ là\[m=p_1^{k_1}p_2^{k_2}\ldots p_t^{k_t}.\]Trong đó, $k_i\in\mathbb{Z}^+,\,p_i\in\mathbb P,\;\forall\,i=\overline{1,\,t}$ và $p_1<p_2<\ldots<p_t$.

Nếu $a$ là một thặng dư bậc $n$ theo mod $m$, thì từ $a\equiv r^n\pmod m$ với $r$ là một căn bậc $n$ của $a$ theo mod $m$, ta có Read the rest of this entry »

Tags: , , , , , ,

Cho trước các số nguyên dương $m,\,n$, và số nguyên $a$ thỏa mãn $\gcd(a,\,m)=1$. Khi đó, với việc biết cấp của $a$ theo mod $m$ là $\text{ord}_m(a)=h$ chúng ta đã có được thuật toán tìm số dư $r$ của $a^n$ khi chia $m$ đó là.

  •  Tìm số dư $r_0$ của $n$ khi đem chia cho $h$.
  •  Tìm số dư $r$ khi đem $a^{r_0}$ chia cho $m$.

Công việc này dù rắc rối hơn đôi chút, nhưng cũng giống như vấn đề ở đại số sơ cấp đó là tính giá trị của lũy thừa $a^n$ khi biết trước $a$ và $n$. Read the rest of this entry »

Tags: , , , , ,

Rất nhiều vấn đề trong Số Học liên quan đến sự tồn tại vô hạn các số nguyên tố trong một dãy nguyên. Ví dụ như định lý Dirichlet, các số nguyên tố Fermat hay các số nguyên tố Mersene. Một vấn đề đơn giản hơn, đó là nói đến các ước nguyên tố của phần tử trong dãy. Bài viết này bàn về khái niệm ước nguyên tố của một dãy số nguyên, và tập các ước nguyên tố đó. Phạm vi bài viết là ở mức độ các bài toán sơ cấp, mặc dù vấn đề trong bài vẫn được nghiên cứu ở lý thuyết Số cao cấp. Read the rest of this entry »

Tags: , , , , , , ,

Suốt dọc từ đây của bài giảng này đến hết, mỗi khi viết $\text{ord}_m(a)$ ta sẽ mặc định các điều kiện là $m\in\mathbb Z^+,\;a\in\mathbb Z$ và $\gcd(a;\,m)=1$. Tính chất đầu tiên của mục này, sẽ cho ta thấy ngay tác dụng của cấp trong việc tìm số dư của lũy thừa bậc cao.

Tính chất 1. Với các số mũ $k;\,l\in\mathbb N$ và $\text{ord}_m(a)=d$ khi đó đồng dư $a^k\equiv a^l\pmod m$ xảy ra khi và chỉ khi xảy ra đồng dư $k\equiv l\pmod d$.

Chứng minh. Không mất tính tổng quát, ta giả sử $k\ge l$. Trước tiên ta đi chứng minh rằng hễ $k\equiv l\pmod d$ thì $a^k\equiv a^l\pmod m$, thật vậy. Vì $k\equiv l\pmod d$ nên $k=l+qd$ với $q\in\mathbb N$ khi ấy do $a^d\equiv 1\pmod m$ nên Read the rest of this entry »

Tags: , , , , , ,

Bài giảng này viết về khái niệm tập hợp, một khái niệm nền móng và cơ bản của Toán Học hiện đại. Khái niệm tập hợp giữ vai trò đặc biệt quan trọng trong Toán Học, không chỉ vì cho đến nay, lý thuyết Tập Hợp đã trở thành một nhánh rộng rãi và phong phú, mà còn vì từ sự xuất hiện từ chừng hai thế kỷ trước, lý thuyết Tập Hợp đã và vẫn đang có những ảnh hưởng sâu sắc đến toàn bộ Toán Học. Ở phạm vi bài viết này, tôi chỉ đưa ra các khái niệm cơ bản thuần túy, cùng các phép toán trên tập cơ bản nhất như giao, hợp, hiệu các tập. Một mục đích nữa của bài giảng, là cung cấp nền tảng khởi đầu cho môn Tổ Hợp. Vì thế, nên trong bài giảng có bàn đến các quy tắc xác định lực lượng tập hợp như nguyên lý cộng, bù trừ và nguyên lý nhân. Read the rest of this entry »

Tags: , , , , , , ,

Định lý Beaty. Cho $a;\,b\in\mathbb R^+\setminus \mathbb Q$ thoả $\dfrac{1}{a}+\dfrac{1}{b}=1$, đặt $$\mathcal A=\left\{\left\lfloor an\right\rfloor:\;n\in\mathbb Z^+\right\},\;\mathcal B=\left\{\left\lfloor bn\right\rfloor:\;n\in\mathbb Z^+\right\}.$$ Khi đó\[\mathcal A\cap\mathcal B=\emptyset\;\text{và}\;\mathcal A\cup\mathcal B=\mathbb Z^+.\]
Chứng minh. Dễ thấy $\mathcal A$ và $\mathcal B$ đều là tập con của $\mathbb Z^+$, giả sử $\mathcal A\cap\mathcal B\ne\emptyset$ khi đó sẽ phải tồn tại các số nguyên dương $k;\,l;\,m$ sao cho\[\left\lfloor ka\right\rfloor=\left\lfloor lb\right\rfloor=m\]
Để ý rằng $ka;\,lb\notin\mathbb Q$ nên điều đó dẫn đến Read the rest of this entry »

Tags: , , , , ,

Chúng ta thấy rõ ràng rằng, nếu cơ số $a$ nguyên (để tránh trường hợp tầm thường thì $|a|\ne 1$) và số mũ $n$ rất lớn thì việc tính trực tiếp giá trị của $a^n$ sau đó mới lấy giá trị đó thực hiện phép chia cho $m$ để tìm dư, là một việc thường không thực tế.

Một ví dụ đơn giản, là bài toán tìm 5 chữ số tận cùng của $5^{2016}$. Về bản chất, thì công việc đó chính là đi tìm số dư của $5^{2016}$ trong phép chia cho $10^5$. Vì $10^5=2^5.5^5$ và dễ nhận ra rằng $5^5\mid 5^{2016}$ nên vấn đề sẽ quy về tìm số dư của $5^{2016}$ khi đem chia nó cho $2^5$. Công việc sau đó, chỉ là kết hợp 2 đồng dư để cho ta kết quả số dư khi chia $5^{2016}$ cho $10^5$.

Rõ ràng, việc tính ra giá trị của $5^{2016}$ sau đó đem chia cho $2^5$ rồi xem dư bao nhiêu là một chuyện không tưởng (nhất là nếu không có sự hỗ trợ của Read the rest of this entry »

Tags: , ,

Cuộc sống, được chúng ta nhận thức qua sự hiện hữu và vận động của các thành tố trong nó. Khi tồn tại để vận động và phát triển, các đối tượng tương tác với nhau theo những quy luật được xác định, để rồi có những ảnh hưởng đến giá trị về lượng và chất tương ứng. Chính sự tương tác ảnh hưởng qua lại giữa các đối tượng của cuộc sống, giúp chúng ta nhận thức được bản chất các đối tượng đó theo nhiều góc nhìn. Read the rest of this entry »

Tags: , , , , , , , , , , ,

Định lý 7.1. Với $m$ là bội chung nhỏ nhất của $m_1$ và $m_2$. Điều kiện để các đồng dư đồng thời sau \[x\equiv a_1\pmod{m_1},\] \[x\equiv a_2\pmod{m_2},\]  có nghiệm là

\[\gcd\left( m_1,\,m_2\right)\mid a_1-a_2.\]

Nếu $(1)$ cố định, lúc đó nghiệm của $(1)$ là duy nhất mod $m$.

Chứng minh. Đặt $\gcd\left(m_1,\,m_2\right)=d$. Nếu hai đồng dư đồng thời đó có một nghiệm, lúc đó Read the rest of this entry »

Tags: , ,

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: , , , , , ,

« Older entries § Newer entries »