Đồng Dư

You are currently browsing articles tagged Đồng Dư.

Trong Shortlist IMO 2001 có bài toán

Bài toán. Cho số nguyên tố $p$ lớn hơn $5$, chứng minh rằng có một phần tử $a$ của nhóm các ước của đơn vị mod $p$ (tức là $a\in\mathcal U_p=\{1,\,2,\,\ldots ,\,p-1\}$), sao cho\[{v_p}\left( {{a^{p – 1}} – 1} \right) = {v_p}\left( {{{\left( {a + 1} \right)}^{p – 1}} – 1} \right) = 1.\]Đây là một bài toán có lời giải dùng đến thương đồng dư khá thú vị, như sau Read the rest of this entry »

Tags: , , , ,

Cá nhân tôi nghĩ rằng, khởi đầu của Số Học có lẽ là từ sự nhận thức của con người về tập hợp số tự nhiên $\mathbb N$, về bản năng thì điều này rất.. tự nhiên do nhu cầu đếm. Tuy nhiên, đưa ra một định nghĩa đàng hoàng về $\mathbb N$ là một điều khó khăn. Ở đây, chúng ta sẽ xây dựng $\mathbb N$ dựa trên hệ tiên đề Peano, như sau đây.

Hệ tiên đề Peano cho tập số tự nhiên.  Chúng ta thừa nhận sự tồn tại của tập hợp các số tự nhiên $\mathbb N$, mà trên đó xác định một quan hệ gọi là “liền sau”, thỏa mãn cả bốn tiên đề dưới đây. Read the rest of this entry »

Tags: , , , , , ,

Bài toán. Cho dãy số nguyên dương $\{a_n\}_{n\in\mathbb N^*}$, thỏa mãn $a_1=a$ và\[a_{n+1}=a_n^2+1,\quad\forall\,n\in\mathbb N^*.\]Chứng minh rằng không tồn tại $n\in\mathbb N^*$ sao cho $\prod\limits_{1 \le k \le n} {\left( {a_k^2 + {a_k} + 1} \right)} $ là một số chính phương. Read the rest of this entry »

Tags: ,

Bài toán Dãy số nguyên $\left( {{x_n}} \right)$, thỏa $0\le x_0<x_1\le 100$ và\[{x_{n + 2}} = 7{x_{n+1}} – {x_n} + 280,\;\;\;{\kern 1pt} \forall {\mkern 1mu} n \in \mathbb N.\]

  1. Với $x_0=2,\,x_1=3$, chứng minh rằng tổng các ước số dương của $x_{n}x_{n+1}+x_{n+1}x_{n+2}+x_{n+2}x_{n+3}+2018$ là bội số của $24$.
  2. Tìm các cặp $\left(x_0,\,x_1\right)$ sao cho $x_nx_{n+1}+2019$ là số chính phương với vô số số tự nhiên $n$.

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

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

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

Với $m$ là một số nguyên dương cho trước và $f(x)=a_nx^n+\ldots+a_1x+a_0$ là một đa thức hệ số nguyên, chúng ta sẽ nghiên cứu phương trình đồng dư\[f(x)\equiv 0\pmod m.\]Nhận xét rằng, nếu $x_0$ là một nghiệm của phương trình đồng dư trên thì với mọi số nguyên $t$ ta có $x_0+mt$ cũng là nghiệm. Điều đó cho thấy hễ $x_0$ là một nghiệm, thì lớp thặng dư sinh bởi $x_0$ cũng ta nghiệm. Bởi vậy, khi ta nói đến số nghiệm của một phương trình đồng dư thì ta hiểu đó là số các lớp thặng dư khác nhau thoả mãn phương trình. Read the rest of this entry »

Tags: , , , , ,

Định lý 9.1. Với $p$ là một số nguyên tố. Lúc đó số nghiệm của đồng dư  $$\begin{align} f(x)=a_nx_n+\ldots+a_0\equiv 0\pmod p,\end{align}\quad (7)$$không vượt quá $n$.         

Chứng minh. Ta có thể giả sử rằng $p\nmid a$. Định lý sẽ trở nên tầm thường nếu $(7)$ không có nghiệm. Nếu $a$ là một nghiệm khi đó ta có thể viết \[f(x)=(x-a)f_1(x)+r_1,\] trong đó ta thấy rằng $p\mid r_1=f(a)$. Từ đó $$f(x)\equiv (x-a)f_1(x)\pmod p.$$ Read the rest of this entry »

Tags: , , ,

Định lý. Với $p$ là số nguyên tố lớn hơn 3, và ta kí hiệu số nguyên $s^*$ thoả $ss^*\equiv 1 \pmod{p^2}$ là $\dfrac{1}{s}$. Lúc đó ta có \[1 + \dfrac{1}{2} + \dfrac{1}{3} + \ldots + \dfrac{1}{{p – 1}} \equiv 0 \pmod {p^2} \]

Chứng minh. Với Read the rest of this entry »

Tags: , , , ,

« Older entries