Toán [Lý thuyết] Chuyên đề HSG: Số học

[Blue Plus]

[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!

ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.

Xin chào tất cả các bạn.

Số học là một phần không thể thiếu trong các kì thi HSG. Bởi những tính chất đẹp đẽ và những quy luật lí thú, những bài toán Số học hứa hẹn sẽ là những thử thách thú vị thách thức chúng ta.

Như đã giới thiệu trong topic trước, đây sẽ là nơi tổng hợp những kiến thức về Số học, một số phương pháp thường dùng, và cũng là nơi để các bạn rèn luyện và chinh phục những thử thách thú vị của Số học.

Sau đây là nội dung của topic:
0.1. Phương pháp chứng minh.
0.2. Các khái niệm cơ bản của số học.
1. Tính chia hết trên tập số nguyên.
2. Số nguyên tố.
3. Số chính phương.
4. Đồng dư thức.

Hẹn gặp các bạn vào ngày mai với bài đầu tiên nhé.
Bài tập: Chuyên đề HSG: Số học

 

[Blue Plus]

PHƯƠNG PHÁP CHỨNG MINH THƯỜNG GẶP
​

I. Phương pháp chứng minh phản chứng:
Thông thường để chứng minh một bài toán hay định lí, ta sẽ đi từ bài toán, dùng suy luận và các tiên đề, định nghĩa, định lí trước đó để dẫn đến khẳng định đúng. Cách làm này được gọi là phương pháp chứng minh trực tiếp.
Tuy nhiên, đôi khi việc chứng minh trực tiếp một định lí gặp khó khăn. Khi đó ta có thể dùng cách chứng minh: Thay vì chứng minh khẳng định của định lí là đúng, ta chứng tỏ rằng nếu giả sử khẳng định của định lí là sai thì sẽ dẫn đến mâu thuẫn. Phương pháp này được gọi là phương pháp phản chứng.
Ví dụ 1: Chứng minh $\sqrt2$ là một số vô tỉ.
Nháp:
Ta thử chứng minh trực tiếp. Số vô tỉ là số không biểu diễn được dưới dạng phân số. Nhưng làm sao để chứng minh một số không biểu diễn được dưới dạng phân số? Đến đây ta gặp khó khăn.
Ta chuyển qua chứng minh bằng phản chứng. Giả sử ngược lại, $\sqrt2$ không là một số vô tỉ. Thế thì $\sqrt2$ là một số hữu tỉ và có thể biểu diễn dưới dạng phân số. Từ đây ta dùng các tính chất chia hết để giải quyết bài toán.
Phần còn lại của bài giải các bạn xem ở dưới.

Spoiler: Giải

Giả sử $\sqrt2$ là một số hữu tỉ. Do đó tồn tại hai số nguyên dương $m,n$ nguyên tố cùng nhau sao cho $\sqrt2=\dfrac{m}{n}$.
Nhân cả hai vế cho $n$ ta được:
$\sqrt2n=m\\\Leftrightarrow 2n^2=m^2$
Vì $n$ là số nguyên nên $m^2\vdots 2\Rightarrow m\vdots 2$
Do đó có thể đặt $m=2k$ với $k$ là số nguyên dương.
Lại thay vào phương trình trên ta được:
$2n^2=4k^2\\\Leftrightarrow n^2=2k^2$
Vì $k$ là số nguyên nên $n^2\vdots 2\Rightarrow n\vdots 2$
Suy ra $m$ và $n$ có ước chung là $2$, trái với giả sử $m,n$ nguyên tố cùng nhau.
Do đó điều giả sử là sai.
Vậy $\sqrt2$ là một số vô tỉ.

Phương pháp chứng minh phản chứng là một phương pháp thường dùng để chứng minh các bài toán số học, cũng như các bài toán bất đẳng thức, tổ hợp, … Phương pháp này có thể dùng để chứng minh sự có thể hoặc không thể của một tính chất nào đó.
Phương pháp chứng minh phản chứng có 3 bước:
Bước 1: Giả sử điều cần chứng minh là sai (phủ định mệnh đề cần chứng minh). Bước này rất quan trọng vì khi tạo mệnh đề phủ định chính xác thì mới suy ra được tính đúng/sai của điều cần chứng minh.
Bước 2: Từ điều giả sử, bằng các phép lập luận và biến đổi, ta dẫn đến điều mâu thuẫn.
Bước 3: Ta kết luận điều giả sử ban đầu là sai. Từ đó, bài toán được chứng minh.
Các bạn hãy thử sức với các ví dụ sau đây trước khi xem lời giải nhé ^^
Ví dụ 2: Tích của $10$ số nguyên cho trước bằng $1$. Chứng minh rằng tổng của $10$ số nguyên đó không thể bằng $0$.

Spoiler: Giải

Vì tích của $10$ số nguyên cho trước bằng $1$ nên các số nguyên đó chỉ có thể là $1$ hoặc $-1$.
Giả sử tổng của $10$ số nguyên đó bằng $0$, khi đó trong 10 số nguyên trên, số số $1$ phải bằng số số $-1$. Suy ra có $5$ số $-1$.
Khi đó vì có 1 số lẻ số $-1$ nên tích $10$ số nguyên trên là âm, trái với giả thiết tích của $10$ số nguyên cho trước bằng $1$.
Do đó điều giả sử là sai.
Vậy tổng của $10$ số nguyên đó không thể bằng $0$.

Ví dụ 3: Cho $2$ số thực $x,y$. Chứng minh rằng nếu $x\ne -1$ và $y\ne -1$ thì $x+y+xy\ne -1$.

Spoiler: Giải

Giả sử với $x\ne -1$ và $y\ne -1$ thì $x+y+xy=-1$. Điều này tương đương với $(x+1)(y+1)=0$. Vậy phải có $x+1=0$ hoặc $y+1=0$, hay $x=-1$ hoặc $y=-1$, trái với giả sử $x\ne -1$ và $y\ne -1$.
Vậy nếu $x\ne -1$ và $y\ne -1$ thì $x+y+xy\ne -1$.

Ví dụ 4: Cho $p$ là số nguyên tố, chứng minh rằng $\sqrt{p}$ là số vô tỉ.

Spoiler: Giải

Giả sử $\sqrt{p}$ là một số hữu tỉ. Do đó tồn tại hai số nguyên dương $m,n$ nguyên tố cùng nhau sao cho $\sqrt{p}=\dfrac{m}{n}$.
Nhân cả hai vế cho $n$ ta được:
$\sqrt{p}n=m\\\Leftrightarrow pn^2=m^2$
Vì $n$ là số nguyên nên $m^2\vdots p\Rightarrow m\vdots p$
Do đó có thể đặt $m=pk$ với $k$ là số nguyên dương.
Lại thay vào phương trình trên ta được:
$pn^2=p^2k^2\\\Leftrightarrow n^2=pk^2$
Vì $k$ là số nguyên nên $n^2\vdots p\Rightarrow n\vdots p$
Suy ra $m$ và $n$ có ước chung là $p$, trái với giả sử $m,n$ nguyên tố cùng nhau.
Do đó điều giả sử là sai.
Vậy $\sqrt{p}$ là một số vô tỉ.

II. Phương pháp chứng minh bằng quy nạp:
Đây cũng là một phương pháp chứng minh quen thuộc trong các bài toán số học, thường được dùng trong các bài toán yêu cầu chứng minh mệnh đề đúng với mọi số nguyên dương $n$ lớn hơn hoặc bằng số nguyên dương $a$ nào đó.
Phương pháp chứng minh bằng quy nạp có 2 bước:
Bước 1: (Bước cơ sở): Chỉ ra mệnh đề đúng với một số nguyên dương $a$ nào đó.
Bước 2: (Bước quy nạp): Giả sử mệnh đề đúng với một số nguyên dương $k$ (giả thiết quy nạp), ta chứng minh mệnh đề đúng với $k+1$.
Từ đó, theo nguyên lí quy nạp ta có mệnh đề đúng với mọi số nguyên dương $n$ lớn hơn hoặc bằng số nguyên dương $a$ nào đó.
Ta xem qua một ví dụ để hiểu hơn về cách chứng minh bằng quy nạp:
Ví dụ 1: Chứng minh rằng $4^{n+1}+5^{2n-1}$ chia hết cho $21$ với mọi số nguyên dương $n$.
(Bài này có thể chứng minh bằng nhiều cách, ở đây mình sử dụng cách chứng minh quy nạp).
Phân tích:
Đầu tiên, thay $n=1$ ta có $4^{1+1}+5^{2\cdot 1-1}=21\vdots 21$. Vậy mệnh đề đúng với $n=1$.
Ta xây dựng bước quy nạp. Giả sử mệnh đề đúng với $n=k$, tức là: $4^{k+1}+5^{2k-1}\vdots 21$
Cần chứng minh mệnh đề đúng với $n=k+1$, tức là cần chứng minh: $4^{k+2}+5^{2k+1}\vdots 21$
Ta biến đổi như sau: $4^{k+2}+5^{2k+1}=4\cdot 4^{k+1}+25\cdot 25^{2k-1}=4\cdot\left(4^{k+1}+5^{2k-1}\right)+21\cdot 5^{2k-1}$
Từ giả thiết quy nạp, ta có $4\cdot\left(4^{k+1}+5^{2k-1}\right)\vdots 21$, và $21\cdot 5^{2k-1}\vdots 21$.
Do đó ta suy ra $4^{k+2}+5^{2k+1}\vdots 21$. Vậy mệnh đề đúng với $n=k+1$.
Theo nguyên lí quy nạp ta có được: $4^{n+1}+5^{2n-1}$ chia hết cho $21$ với mọi số nguyên dương $n$.
Tương tự bạn hãy thử sức với ví dụ 2 sau nhé.
Ví dụ 2: Chứng minh rằng $3^{2n+1}+40n-67$ chia hết cho $64$ với mọi số nguyên dương $n$.

Spoiler: Giải

Thay $n=1$ ta có $3^{2\cdot 1+1}+40\cdot 1-67=0\vdots 64$. Vậy mệnh đề đúng với $n=1$.
Giả sử mệnh đề đúng với $n=k$, tức là: $3^{2k+1}+40k-67\vdots 64$
Cần chứng minh mệnh đề đúng với $n=k+1$, tức là cần chứng minh: $3^{2k+3}+40k-27\vdots 64$
Thật vậy, $3^{2k+3}+40k-27=9\cdot 3^{2k+1}+9\cdot 40k-9\cdot 67-320k+576=9\left(3^{2k+1}+40k-67\right)+64\left(9-5k\right)$
Từ giả thiết quy nạp, ta có $9\left(3^{2k+1}+40k-67\right)\vdots 64$, và $64\left(9-5k\right)\vdots 64$.
Do đó ta suy ra $3^{2k+3}+40k-27\vdots 64$. Vậy mệnh đề đúng với $n=k+1$.
Theo nguyên lí quy nạp ta có được: $3^{2n+1}+40n-67$ chia hết cho $64$ với mọi số nguyên dương $n$.

Vì đây là bài viết đầu tiên nên sẽ không có BTVN nhé ^^ Hẹn các bạn ở bài viết tiếp theo.

 

[Blue Plus]

CÁC KHÁI NIỆM CƠ BẢN CỦA SỐ HỌC
​

I. Ước chung lớn nhất:
1. Định nghĩa:
Cho hai số nguyên $a,b$ trong đó ít nhất một số khác $0$. Số dương $d$ được gọi là ước chung lớn nhất của $a,b$ nếu $d$ là ước chung của $a$ và $b$ đồng thời là số lớn nhất trong số các ước chung của $a$ và $b$.
Kí hiệu: $ƯCLN(a,b)$ hay $(a,b)$.
Nếu $(a,b)=1$ ta nói hai số $a$ và $b$ là nguyên tố cùng nhau.
2. Tính chất:
i. $(a\cdot c,b\cdot c)=(a,b)\cdot c$ với $c>0$.
ii. Tồn tại 2 số nguyên $x,y$ để $a\cdot x+b\cdot y=(a,b)$. (Định lí Bezout)
iii. $(a,b)=(a,a\pm b)$
iv. Nếu $(a,c)=1$ thì $(a\cdot b,c)=(b,c)$.
Hệ quả: Nếu $(a,b)=(a,c)=1$ thì $(a,b\cdot c)=1$.
II. Bội chung nhỏ nhất:
1. Định nghĩa:
Cho hai số nguyên $a,b$ khác $0$. Số nguyên dương $k$ được gọi là bội chung nhỏ nhất của $a,b$ nếu $k$ là bội chung của $a$ và $b$ đồng thời là số nguyên dương nhỏ nhất trong số các bội chung của $a$ và $b$.
Kí hiệu: $BCNN(a,b)$ hay $[a,b]$.
Ta có biểu thức: $a\cdot b=(a,b)\cdot [a,b]$
2. Tính chất:
i. $[k\cdot a, k\cdot b]=k\cdot[a,b]$ với $k>0$.
ii. Giả sử $k$ là một bội chung của $a,b$, khi đó $k=[a,b]\Leftrightarrow \left(\dfrac{k}{a},\dfrac{k}{b}\right)=1$.
III. Định lí về sự phân tích một số tự nhiên thành tích các thừa số nguyên tố:
1. Định lí:
Mọi số tự nhiên lớn hơn 1 đều phân tích được thành tích các thừa số nguyên tố và phân tích đó là duy nhất nếu không kể đến thứ tự các thừa số.
$n=p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot p_3^{\alpha_3}\cdot …\cdot p_k^{\alpha_k}$
Với $p_i$ là các số nguyên tố, $\alpha_i$ là các số nguyên dương.
Phân tích này được gọi là phân tích tiêu chuẩn của $n$.
2. Tiêu chuẩn chia hết:
Số tự nhiên $a=p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot … p_k^{\alpha_k}$ chia hết cho $d$ khi và chỉ khi $d=p_1^{\beta_1}\cdot p_2^{\beta_2}\cdot … p_k^{\beta_k}$, trong đó $0\le \beta_i\le \alpha_i(1\le i\le k)$
3. Số các ước của một số:
Cho $n=p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot p_3^{\alpha_3}\cdot …\cdot p_k^{\alpha_k}$
Số các ước của $n$ là $(\alpha_1+1)(\alpha_2+1)…(\alpha_k+1)$

 

[Blue Plus]

Chuyên đề 1: TÍNH CHIA HẾT TRONG TẬP SỐ NGUYÊN.
​

A. Lí thuyết:
1. Định nghĩa:
Cho $a,b$ là các số nguyên ($b\ne0$). Ta nói $a$ chia hết cho $b$ khi và chỉ khi tồn tại số nguyên $q$ sao cho $a=b\cdot q$.
Kí hiệu:
$a\vdots b$: $a$ chia hết cho $b$.
$b|a$: $b$ chia hết $a$ ($b$ là ước của $a$).
2. Định lí:
Với bất kì số nguyên $a$ và $b$, tồn tại duy nhất cặp số nguyên $(q;r)$ sao cho $a=b\cdot q+r(0\le r<|b|)$
3. Tính chất: Với các số nguyên $a,b,c,d$:
i. $a|0\forall a\ne 0$.
ii. Nếu $a\ne 0$ và $a\vdots b$ thì $|b|\le |a|$
iii. $a\vdots a$
iv. Nếu $a\vdots b$ và $b\vdots a$ thì $a=\pm b$
v. Nếu $a\vdots b$ và $b\vdots c$ thì $a\vdots c$
vi. Nếu $a\vdots c$ và $b\vdots c$ thì $(pa+qb)\vdots c$ ($p,q$ là các số nguyên)
vii. Nếu $a\vdots c$ và $(a\pm b)\vdots c$ thì $b\vdots c$
viii. Nếu $a\vdots b$ và $c\vdots d$ thì $(a\cdot c)\vdots (b\cdot d)$
Hệ quả: Nếu $a\vdots b$ thì $a^n\vdots b^n$ ($n\in \mathbb{N}$)
ix. Nếu $c\vdots a$, $c\vdots b$ thì $c\vdots [a,b]$
Hệ quả: Nếu $c\vdots a$, $c\vdots b$ và $(a,b)=1$ thì $c\vdots (a\cdot b)$
x. Nếu $(a\cdot b)\vdots c$ mà $(a,c)=1$ thì $b\vdots c$
Hệ quả: Với $p$ là số nguyên tố.
Nếu $(a\cdot b)\vdots p$ thì $a\vdots p$ hoặc $b\vdots p$
Nếu $a^n\vdots p$ thì $a\vdots p$ ($n\in \mathbb{N}$)
B. Các phương pháp thường dùng:
1. Phương pháp xét số dư:
Ý tưởng: Để chứng minh $f(n)$ chia hết cho $k$, ta xét các số $n=q\cdot k+r$ với $r\in \{0;1;2;…;k-1\}$ rồi thay vào giải từng trường hợp.
Ví dụ:
Chứng minh rằng $x^2+y^2$ chia hết cho $3$ thì $x$ và $y$ đồng thời chia hết cho $3$.
Ta sử dụng phương pháp trên và có lời giải như sau:
Đặt $x=3a+r;y=3b+s(a,b\in \mathbb{Z};r,s\in\{0;1;2\})$
$r=0:x=3a$
$x^2=9a^2\vdots 3$
$r=1:x=3a+1$
$x^2=9a^2+6a+1$ chia $3$ dư $1$.
$r=2:x=3a+2$
$x^2=9a^2+12a+4$ chia $3$ dư $1$.
Vậy khi $r$ lần lượt là $0,1,2$ ta tính được số dư khi chia $x^2$ cho $3$ là $0,1,1$.
Tương tự đối với $y^2$.
Vậy để $x^2+y^2$ chia hết cho $3$ thì $x^2$ và $y^2$ phải đồng thời chia hết cho $3$, tương ứng với $x$ và $y$ đồng thời chia hết cho $3$.
Vậy ta có đpcm.
2. Phương pháp biểu thức bị chia thành tích hoặc tổng các tích:
Ý tưởng: Để chứng minh biểu thức $A(n)$ với $n$ nguyên chia hết cho một số nguyên $k$ khác $0$, ta phân tích $A(n)$ thành nhân tử và chứng minh có ít nhất một nhân tử chia hết cho $k$, hoặc phân tích $A(n)$ thành tổng các hạng tử đều chia hết cho $k$.
Một tính chất hay dùng: Tích của $n$ số nguyên liên tiếp luôn chia hết cho $n!$ ($n!=1\cdot 2\cdot 3\cdot … \cdot n$)
Tích của $2$ số nguyên liên tiếp chia hết cho $2$.
Tích của $3$ số nguyên liên tiếp chia hết cho $6$.
Ví dụ 1: Chứng minh rằng tích của 3 số chẵn liên tiếp chia hết cho 48.
Giải:
Gọi 3 số chẵn liên tiếp là $2k;2k+2;2k+4(k\in\mathbb{Z})$
Ta có:
$2k(2k+2)(2k+4)=8k(k+1)(k+2)$
Vì $k;k+1;k+2$ là 3 số nguyên liên tiếp nên $k(k+1)(k+2)\vdots 6$
Suy ra $8k(k+1)(k+2)\vdots 48$ hay ta có đpcm.
Ví dụ 2: Chứng minh rằng với số tự nhiên $x$ lẻ thì biểu thức $A=x^2+4x-5$ luôn chia hết cho $8$.
Giải:
Vì $x$ là số lẻ nên đặt $x=2k+1(k\in \mathbb{N})$
$A=(2k+1)^2+4(2k+1)-5=4k^2+4k+1+8k+4-5=4k(k+1)+8k$
Vì $k;k+1$ là 2 số nguyên liên tiếp nên $k(k+1)\vdots 2\Rightarrow 4k(k+1)\vdots 8$
Và $8k\vdots 8$
Do đó $A\vdots 8$
Vậy ta có đpcm.

 

[Blue Plus]

Tiếp tục nhé ^^
3. Phương pháp dùng hằng đẳng thức mở rộng:
Ý tưởng:
Xét hằng đẳng thức: $a^n-b^n=(a-b)(a^{n-1}+a^{n-2}b+…+ab^{n-2}+b^{n-1})$
Từ hằng đẳng thức trên suy ra: Nếu $a\ne b$ thì $(a^n-b^n)\vdots (a-b)(1)$
Thay $b$ bởi $-b$ ta có:
- Nếu $n$ lẻ: $a^n+b^n=(a+b)(a^{n-1}-a^{n-2}b+…+a^2b^{n-3}-ab^{n-2}+b^{n-1})$
Do đó $(a^n+b^n)\vdots (a+b)$ với $n$ lẻ $(2)$.
- Nếu $n$ chẵn: $a^n-b^n=(a+b)(a^{n-1}-a^{n-2}b+…+ab^{n-2}-b^{n-1})$
Do đó $(a^n-b^n)\vdots (a+b)$ với $n$ chẵn $(3)$.
Ví dụ 1: Chứng minh rằng $2^{4k}-1$ chia hết cho $15$ với $k\in\mathbb{N}$
Giải:
Ta có: $2^{4k}-1=16^k-1^k$
Áp dụng $(1)$ ta có $16^k-1^k\vdots (16-1)$ hay $16^k-1^k\vdots 15$
Suy ra $2^{4k}-1\vdots 15$
Vậy ta có đpcm.
Ví dụ 2: Chứng minh rằng với mọi số nguyên $n$ lẻ, số $N=118^n-101^n-16^n-1$ chia hết cho $3978$
Giải:
Để ý $3978=39\cdots 102$
Ta có: $N=(118^n-16^n)-(101^n+1)$
Áp dụng $(1)$ ta có: $118^n-16^n\vdots 102$
Với $n$ lẻ, áp dụng $(2)$ ta có: $101^n+1\vdots 102$
Suy ra $N\vdots 102$.
Lại có: $N=(118^n-1)-(101^n+16^n)$
Áp dụng $(1)$ ta có $118^n-1\vdots 117$
Với $n$ lẻ, áp dụng $(2)$ ta có: $101^n+16^n\vdots 117$
Suy ra $N\vdots 117$, mà $117\vdots 39$ nên $N\vdots 39$
Vì $(39,102)=1$ nên $N\vdots (39\cdot 102)$ hay $N\vdots 3978$
Ta có đpcm.