Đồng Dư
You are currently browsing articles tagged Đồng Dư.
Bài toán sau, nói về đồng dư trên $\mathbb Q$ và thương Fermat trên đó.
Bài toán. Cho $p$ là một số nguyên tố lẻ, các số nguyên dương $m$ và $n$ thỏa mãn\[1 + \frac{1}{{{2^{p – 1}}}} + \ldots + \frac{1}{{{{\left( {p – 1} \right)}^{p – 1}}}} = \frac{m}{n}.\]Chứng minh rằng $(p-2)!m+n$ chia hết cho $p^2$.
Nó có lời giải như sau
Read the rest of this entry »
Tags: Đồng Dư, ideal, Thương Đồng Dư
Bài này, liên quan đến một bài viết khác của tôi, vấn đề đặt ra là như thế sau
Với $\alpha=\frac{1+\sqrt 5}{2}$, xét vành $R = \left\{ {a + b\alpha :\;a,{\mkern 1mu} {\kern 1pt} b \in \mathbb Z} \right\}$, ta cần đi tìm các số nguyên tố $p$ để $I(p)=\{pr:\;r\in R\}$ là một ideal nguyên tố. Nghĩa là, cần tìm $p$ sao cho cứ từ $xy\in I(p)$ thì phải có $x\in I(p)$ hoặc $y\in I(p)$.
Bởi vì $5=\left(\sqrt 5\right)^2$, và nếu đặt $
\frac{1-\sqrt 5}{2}=\beta$ thì $\beta\in R$ thêm nữa $-2\alpha\beta=2$ cho nên ta chỉ cần xét các số nguyên tố lẻ và khác $5$.
Read the rest of this entry »
Tags: Đồng Dư, ideal, ideal nguyên tố, Số Học, Thặng Dư Bậc Hai
Tình cờ, mình nhìn thấy cái bài này trên THTT, nội dung như sau đây
Bài toán. Cho $n$ là một số nguyên dương, chứng minh rằng phải có $3^{n+1}$ bé hơn số ${\left( {\frac{{3 + \sqrt 5 }}{2}} \right)^{{3^n}}} + {\left( {\frac{{3 – \sqrt 5 }}{2}} \right)^{{3^n}}}$, đồng thời cái số đó sẽ chia hết cho $3$.
Read the rest of this entry »
Tags: Định Giá p-adic, Đồng Dư, ideal, LTE, Số Học, Vành bậc 2
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: Bổ Đề Tiếp Tuyến, Đồng Dư, Nhóm Đơn Vị, Số Học, Thương Đồng Dư
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: Đồng Dư, Giải Tích, Nền Tảng, Nguyên Lý Cực Hạn, Nguyên Lý Quy Nạp, Số Học, Thuật Toán Chia
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: Dãy Số Nguyên, Đồng Dư
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.\]
- 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$.
- 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: Dãy Số, Dãy Số Nguyên, Đồng Dư, Số Học
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: Cấp và căn theo modulo, Định Lý Euler, Định Lý Fermat bé, Đồng Dư, Nhóm, Nhóm Đơn Vị, Số Học
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: Cấp và căn theo modulo, Đồng Dư, Số Học
Đị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: Định Lý Thặng Dư Trung Hoa, Đồng Dư, Số Học
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: Đa Thức, Định Lý Thặng Dư Trung Hoa, Đồng Dư, Đồng Dư Bậc Cao, Phương Trình Đồng Dư, Số Học
Phản Hồi