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

Có bạn nhờ tôi bài toán như sau

Bài toán. Chứng minh rằng, với mỗi số nguyên dương $a$ sẽ có vô số nghiệm nguyên dương của phương trình\[\frac{{x + y + 1}}{y} + \frac{{y + a}}{x} = 4.\]

Tôi có lời giải như sau

Read the rest of this entry »

Tags: , ,

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

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

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

« Older entries