Đến nội dung

Hình ảnh

[TOPIC] Số học hướng tới kỳ thi Olympic

* * * - - 10 Bình chọn

  • Please log in to reply
Chủ đề này có 90 trả lời

#1
nguyenhuybao06

nguyenhuybao06

    Trung sĩ

  • Hái lộc VMF 2024
  • 168 Bài viết

Chào mọi người, 

 

Như các bạn đã biết, Số học đã, đang và luôn là một chủ đề nóng hổi, mà hầu như các bạn học sinh ôn thi những cuộc thi Olympic Toán học đều quan tâm. Để tiện cho các bạn trao đổi các vấn đề liên quan tới Số học, được sự cho phép và ủng hộ của đàn anh perfectstrong, mình xin phép tạo một topic mới với tên gọi là "Số học hướng tới kỳ thi Olympic".

 

Topic này là nơi các bạn sẽ thảo luận và đưa ra lời giải cho những bài toán Số học được đăng. Mục tiêu của topic là tạo ra sân chơi, để mọi người có thể thoải mái trao đổi và cùng giúp nhau phát triển, ngoài ra, khi cần ôn tập để chuẩn bị thi các kì thi Olympic, các bạn có thể xem đây như một nguồn tài liệu tham khảo.

 

Mình xin cảm ơn và mong các bạn sẽ ủng hộ topic này. 

 

Thân ái, 

Nguyễn Huy Gia Bảo


Bài viết đã được chỉnh sửa nội dung bởi nguyenhuybao06: 22-12-2024 - 22:42

Ngài có thể trói cơ thể tôi, buộc tay tôi, điều khiển hành động của tôi: ngài mạnh nhất, và xã hội cho ngài thêm quyền lực; nhưng với ý chí của tôi, thưa ngài, ngài không thể làm gì được.


#2
nguyenhuybao06

nguyenhuybao06

    Trung sĩ

  • Hái lộc VMF 2024
  • 168 Bài viết

Đầu tiên, mình xin khởi động topic bằng một bài toán nho nhỏ. 

 

Bài 1. Cho số nguyên dương $n>1$ thỏa mãn $n\mid 3^n-1.$ Chứng minh rằng $n$ là số chẵn. 


Ngài có thể trói cơ thể tôi, buộc tay tôi, điều khiển hành động của tôi: ngài mạnh nhất, và xã hội cho ngài thêm quyền lực; nhưng với ý chí của tôi, thưa ngài, ngài không thể làm gì được.


#3
MHN

MHN

    Sĩ quan

  • Thành viên
  • 438 Bài viết

Bài 1. Cho số nguyên dương $n>1$ thỏa mãn $n\mid 3^n-1.$ Chứng minh rằng $n$ là số chẵn. 

Gọi $p$ là ước nguyên tố nhỏ nhất của $n$, ta có $3^n \equiv 1 \pmod{p}$. Cũng có $3^{p-1} \equiv 1 \pmod{p}$. Gọi $k$ là số nguyên dương nhỏ nhất thoả mãn $3^k \equiv 1 \pmod{p}$. Vậy $k|p-1$ và $k|n$.

Nếu $k,n$ có cùng ước nguyên tố $r$ thì $r|k$ nên $k>r$ mà $k|p-1$ nên $p>k$, vậy $p>r$, mâu thuẫn điều kiện $p$ là ước nguyên tố nhỏ nhất của $n$. Do đó $\gcd (k,n)=1$. Tuy ra $k=1$ hay $p|3^1-1=2$. Vậy $p=2$ nên $2|n$.(Jinbe)

 

Bài 2: Tìm tất cả các bộ số nguyên dương \((a; b)\) thỏa mãn:$(b^2 + 3a) \vdots a^2b$

P/s:Vì để tạo sự sôi nổi cho topic nên mình sẽ thay đổi câu hỏi dẽ hơn so với câu ban đầu, sorry các bạn.


Bài viết đã được chỉnh sửa nội dung bởi MHN: 22-12-2024 - 23:35

$\textup{My mind is}$ :wacko: .

 


#4
dinhvu

dinhvu

    Trung sĩ

  • Thành viên
  • 118 Bài viết

Gọi $p$ là ước nguyên tố nhỏ nhất của $n$, ta có $3^n \equiv 1 \pmod{p}$. Cũng có $3^{p-1} \equiv 1 \pmod{p}$. Gọi $k$ là số nguyên dương nhỏ nhất thoả mãn $3^k \equiv 1 \pmod{p}$. Vậy $k|p-1$ và $k|n$.

Nếu $k,n$ có cùng ước nguyên tố $r$ thì $r|k$ nên $k>r$ mà $k|p-1$ nên $p>k$, vậy $p>r$, mâu thuẫn điều kiện $p$ là ước nguyên tố nhỏ nhất của $n$. Do đó $\gcd (k,n)=1$. Tuy ra $k=1$ hay $p|3^1-1=2$. Vậy $p=2$ nên $2|n$.(Jinbe)

 

Bài 2: Tìm tất cả các bộ số nguyên dương \((a; b)\) thỏa mãn:$(b^2 + 3a) : a^2 \cdot b$

P/s:Vì để tạo sự sôi nổi cho topic nên mình sẽ thay đổi câu hỏi dẽ hơn so với câu ban đầu, sorry các bạn.

mình chưa hiểu bạn viết gì lắm, : là sao nhỉ


  • Kng yêu thích

#5
nguyenhuybao06

nguyenhuybao06

    Trung sĩ

  • Hái lộc VMF 2024
  • 168 Bài viết

Bài 2: Tìm tất cả các bộ số nguyên dương \((a; b)\) thỏa mãn: $a^2b\mid (b^2 + 3a)$

Ta đặt $$k=\frac{b^2+3a}{a^2b}\in\mathbb{Z^+}.$$

Xét tập $S=\lbrace{(a,b)\in\mathbb{Z^+}\times\mathbb{Z^+}\mid k=\frac{b^2+3a}{a^2b}\rbrace}.$ Ta dễ thấy $S\ne \emptyset.$ Do đó tồn tại một cặp $(a_0, b_0)$ trong $S$ mà $a_0+b_0$ đạt giá trị nhỏ nhất. 

Xét phương trình $$\frac{x^2+3a_0}{a_0^2x}=k\Leftrightarrow x^2-ka_0^2x+3a_0=0.$$ 

Đây là phương trình bậc hai ẩn $x.$ Ta biết rằng phương trình trên có một nghiệm là $b_0.$ Như vậy theo định lý Viete, tồn tại nghiệm $b_1$ thỏa mãn phương trình trên sao cho $$b_1=ka_0^2-b_0=\frac{3a_0}{b_0}.$$

Từ đây ta được $b_1$ cũng là số nguyên dương. Ta có $$b_0^2\le b_1b_0=3a_0.$$

Từ đây ta được $$b_0ka_0^2=3a_0+b_0^2\le 6a_0.$$ Hay ta có $$a_0b_0k\le6.$$

Đến đây xét các trường hợp có thể của $k$ thì dễ rồi. 


Ngài có thể trói cơ thể tôi, buộc tay tôi, điều khiển hành động của tôi: ngài mạnh nhất, và xã hội cho ngài thêm quyền lực; nhưng với ý chí của tôi, thưa ngài, ngài không thể làm gì được.


#6
nguyenhuybao06

nguyenhuybao06

    Trung sĩ

  • Hái lộc VMF 2024
  • 168 Bài viết

Bài 3. Cho $n$ là một số nguyên dương. Chứng minh rằng $$n=\sum_{d>0, d\mid n}\varphi(d).$$


Ngài có thể trói cơ thể tôi, buộc tay tôi, điều khiển hành động của tôi: ngài mạnh nhất, và xã hội cho ngài thêm quyền lực; nhưng với ý chí của tôi, thưa ngài, ngài không thể làm gì được.


#7
Hahahahahahahaha

Hahahahahahahaha

    Trung sĩ

  • Thành viên
  • 170 Bài viết

Bài 3:

Giả sử $n$ có phân tích tiêu chuẩn: $n=p_{1}^{a_{1}}.p_{2}^{a_{2}}...p_{k}^{a_{k}}$
Nhận xét hàm phi Euler là hàm nhân tính. Khi đó áp dụng công thức tổng trải ta được:
$\sum_{d|n}\varphi(d)=\prod_{i=1}^{k}(\sum_{j=0}^{a_{i}}\varphi(p_{i}^{j}))=[\varphi(p_{1}^{0})+\varphi(p_{1}^{1})+...+\varphi(p_{1}^{a_{1}})]...[\varphi(p_{k}^{0})+\varphi(p_{k}^{1})+...+\varphi(p_{k}^{a_{k}})]=n$
Chú ý: $\varphi(p^{x})=p^{x}-p^{x-1}$


Bài viết đã được chỉnh sửa nội dung bởi Hahahahahahahaha: 23-12-2024 - 17:48

WHO'S THAT POKÉMON?!

 

:icon14:  :icon14:  :icon14:  :icon14:  :icon14:  :icon14:  :icon14:  :icon14:  :icon14:  :icon14:  :icon14:  :icon14:  :icon14:


#8
perfectstrong

perfectstrong

    $LOVE(x)|_{x =\alpha}^\Omega=+\infty$

  • Quản lý Toán Ứng dụng
  • 5118 Bài viết

Bài 3:

$\sum_{d|n}\varphi(d)=\prod_{i=1}^{k}(\sum_{j=0}^{a_{i}}\varphi(p_{i}^{j}))$

Quan trọng là giải thích cái này :D


Luôn yêu để sống, luôn sống để học toán, luôn học toán để yêu!!! :D
$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$
I'm still there everywhere.

#9
MHN

MHN

    Sĩ quan

  • Thành viên
  • 438 Bài viết

Bài 4: Chứng minh rằng với mọi số thực $\delta\in [0,1]$ và với mọi $\varepsilon>0$, bất đẳng thức 

$$\left| \frac{\varphi(n)}{n}-\delta \right|<\varepsilon$$

đúng với số tự nhiên n nào đó


$\textup{My mind is}$ :wacko: .

 


#10
Hahahahahahahaha

Hahahahahahahaha

    Trung sĩ

  • Thành viên
  • 170 Bài viết

Bài 3: :))

. hmmmm em nghĩ đến $d=p_{1}^{b_{1}}.p_{2}^{b_{2}}...p_{k}^{b_{k}}$

với $0\leq b_{i}\leq a_{i}$ cho nên là kiểu gì $\varphi(d)=\varphi(?).\varphi(?)....$

sau một hồi liệt kệ đầy đủ các ước thì sẽ nhóm thành nhân tử như vậy :))

 

*** chứng minh hàm phi Euler là hàm nhân tính:

ta sẽ chứng minh: $\varphi(mn)=\varphi(m).\varphi(n)$ với $(m,n)=1$

+) để ý $\varphi(mn)$ là số các số không vượt quá $mn$ và nguyên tố cùng nhau với $mn$ 

Ta viết các số nguyên dương không vượt quá $mn$ thành các hàng (từ trái sang phải) và cột (từ trên xuống) sau:

File gửi kèm  Screenshot (737).png   13.96K   0 Số lần tải

$\star $: Gọi $r$ là $1$ số nguyên dương không vượt quá $m$ sao cho $(m,r)=d>1$

Khi đó: không có số nào trong cột thứ $r(1\leq r \leq m)$ nguyên tố cùng nhau với $m$ thì cũng sẽ không nguyên tố cùng nhau với $mn$

Vì: một phần tử của cột $r$ đó đều có dạng $km+r(0<k<n)$. Do đó: theo thuật toán Euclid thì $(km+r,m)=(r,m)=d>1$

$\star$: Như vậy để tìm các số trong bảng mà nguyên tố cùng nhau với $m$ thì ta xét các cột $r$ sao cho $(m,r)=1$. Khi này có $\varphi(m)$ cột như vậy.

$\star$: tiếp theo ta đếm xem trong mỗi cột như vậy có bao nhiêu số nguyên tố cùng nhau với $m$

để ý: mỗi cột như vậy gồm các số $r,m+r,2m+r,...,(n-1)m+r$

và ta thấy $\{0;1;2;...;n-1\}$ là hệ thặng dư đầy đủ modulo $n$

mà $(m,n)=1$ nên $\{0.m+r;1.m+r;2m+r;...;(n-1)m+r\}$ cũng là 1 hệ thặng dư đầy đủ theo modulo $n$

tương ứng có $1$ hệ thặng dư thu gọn theo modulo $n$

do đó  mỗi cột như vậy có $\varphi(n)$ số nguyên tố cùng nhau với $n$

lai do $(m,r)=1$ nên $\varphi(n)$ số ấy trong cột đó cũng nguyên tố cùng nhau với $m$

khi đó theo bổ đề này: $(a,b)=1$ và $(a,c)=1$ thì $(a,bc)=1$

ta có: $\varphi(n)$ số này cũng nguyên tố cùng nhau với $mn$

và có $\varphi(m)$ cột như vậy

SUY RA: $\varphi(mn)=\varphi(m).\varphi(n)$


Bài viết đã được chỉnh sửa nội dung bởi Hahahahahahahaha: 23-12-2024 - 19:54

WHO'S THAT POKÉMON?!

 

:icon14:  :icon14:  :icon14:  :icon14:  :icon14:  :icon14:  :icon14:  :icon14:  :icon14:  :icon14:  :icon14:  :icon14:  :icon14:


#11
Hahahahahahahaha

Hahahahahahahaha

    Trung sĩ

  • Thành viên
  • 170 Bài viết

bài 5

Cho $n$ là số nguyên dương, $n\geq 2$

Gọi $S(n)$ là tổng các số không nguyên tố cùng nhau với $n$ và không vượt quá $n$

Chứng minh rằng:  $S(n)=\frac{n}{2}(n+1-\varphi(n))$

 

Bài 6: CMR: $\varphi(n)+\sigma(n) \geq 2n$


Bài viết đã được chỉnh sửa nội dung bởi Hahahahahahahaha: 23-12-2024 - 20:40

WHO'S THAT POKÉMON?!

 

:icon14:  :icon14:  :icon14:  :icon14:  :icon14:  :icon14:  :icon14:  :icon14:  :icon14:  :icon14:  :icon14:  :icon14:  :icon14:


#12
MHN

MHN

    Sĩ quan

  • Thành viên
  • 438 Bài viết

Bài 6: CMR: $\varphi(n)+\sigma(n) \geq 2n$

Giả sử các ước của $n$ là $1 = d_1 < d_2 < ... < d_k = n$.

Trong các số tự nhiên không vượt quá $n$, có $\frac{n}{d_i}$ số là bội của $d_i$. Mỗi số không vượt quá $n$ và không nguyên tố cùng nhau với $n$ phải là bội của một ước nào đó (lớn hơn $1$) của $n$. 

$\Rightarrow$ Ta có:

$$n - \varphi(n) \leq \frac{n}{d_2} + \frac{n}{d_3} + ... + \frac{n}{d_k}.$$

Mặt khác, $\frac{n}{d_2} + \frac{n}{d_3} + ... + \frac{n}{d_k} = d_{k-1} + d_{k-2} + ... + d_1 = \sigma(n) - n.$

$\Rightarrow n - \varphi(n) \leq \sigma(n) - n$ hay $\sigma(n) + \varphi(n) \geq 2n.$

Vậy đẳng thức xảy ra khi $n$ nguyên tố


$\textup{My mind is}$ :wacko: .

 


#13
tru0ng khanh chi

tru0ng khanh chi

    Lính mới

  • Thành viên mới
  • 8 Bài viết

Bài 7(JBMO Shortlist 2023). Cho $p$ là số nguyên tố khác $5$ thoả mãn $\frac{p+1}{2}$ cũng là số nguyên tố. Giả sử tồn tại hai số nguyên dương $a<b$ sao cho $\frac{p^2+a}{p+a^2}$ và $\frac{p^2+b}{p+b^2}$ đều là số nguyên. Chứng minh rằng $b=(a-1)^2+1$.



#14
ohmuhgawd

ohmuhgawd

    Binh nhì

  • Thành viên mới
  • 18 Bài viết

Bài 4: Chứng minh rằng với mọi số thực $\delta\in [0,1]$ và với mọi $\varepsilon>0$, bất đẳng thức 

$$\left| \frac{\varphi(n)}{n}-\delta \right|<\varepsilon$$

đúng với số tự nhiên n nào đó

Bài này chứng minh là mọi phân số dương <1 đều có thể viết dưới dạng phi(n)/n và c/m với 2 số bất kì luôn có 1 số hữu tỉ nằm ngay giữa 2 số ấy pk ạ? 


Bài viết đã được chỉnh sửa nội dung bởi ohmuhgawd: 23-12-2024 - 23:18


#15
nguyenhuybao06

nguyenhuybao06

    Trung sĩ

  • Hái lộc VMF 2024
  • 168 Bài viết

Bài 5. Cho $n$ là số nguyên dương, $n\geq 2.$ Gọi $S(n)$ là tổng các số không nguyên tố cùng nhau với $n$ và không vượt quá $n.$ Chứng minh rằng $$S(n)=\frac{n}{2}(n+1-\varphi(n)).$$

 

Với $n$ là số nguyên tố thì ta dễ có điều phải chứng minh.

Giả sử phân tích tiêu chuẩn của $n$ có dạng $p_1^{\alpha_1}p_2^{\alpha_2}...p_k^{\alpha_k}$ và $n$ thỏa mãn đẳng thức trên.

Bây giờ ta sẽ chứng minh $n'=p_{k+1}n=p_1^{\alpha_1}p_2^{\alpha_2}...p_{k+1}$ cũng sẽ có được đẳng thức trên. Ta có vế trái của đẳng thức được biến đổi thành $$\frac{p_{k+1}n}{2}(p_{k+1}n+1-\varphi(p_{k+1}n)).$$

Đặt $f(n)=\sum_{i=1}^ni.$ Vế phải của đẳng thức được biến đổi thành $$f(p_{k+1}n)-\frac{p_{k+1}n\varphi(p_{k+1}n)}{2}=\frac{p_{k+1}n(p_{k+1}n+1-\varphi(p_{k+1}n))}{2}.$$

Ơ làm xong mới biết còn chẳng cần quy nạp. :D

P/s. Ở lời giải trên mình có sử dụng công thức tổng các số nhỏ hơn $n$ và nguyên tố cùng nhau với $n$ là $\frac{n\varphi(n)}{2}.$


Ngài có thể trói cơ thể tôi, buộc tay tôi, điều khiển hành động của tôi: ngài mạnh nhất, và xã hội cho ngài thêm quyền lực; nhưng với ý chí của tôi, thưa ngài, ngài không thể làm gì được.


#16
nguyenhuybao06

nguyenhuybao06

    Trung sĩ

  • Hái lộc VMF 2024
  • 168 Bài viết

Bài 8. Tìm tất cả các số nguyên dương $n$ thỏa mãn $\frac{2^n+1}{n^2}$ là số nguyên. 


Ngài có thể trói cơ thể tôi, buộc tay tôi, điều khiển hành động của tôi: ngài mạnh nhất, và xã hội cho ngài thêm quyền lực; nhưng với ý chí của tôi, thưa ngài, ngài không thể làm gì được.


#17
dinhvu

dinhvu

    Trung sĩ

  • Thành viên
  • 118 Bài viết

 


Bài viết đã được chỉnh sửa nội dung bởi dinhvu: 24-12-2024 - 09:13


#18
MUVODICH

MUVODICH

    Binh nhất

  • Thành viên mới
  • 29 Bài viết

Bài 8. Tìm tất cả các số nguyên dương $n$ thỏa mãn $\frac{2^n+1}{n^2}$ là số nguyên. 

Đây là bài từ IMO 1900 và cũng hay xuất hiện trong các tài liệu về bổ đề LTE.
Sau đây là một lời giải mình sưu tầm trên diễn đàn:

File gửi kèm

  • File gửi kèm  Ảnh.png   72.31K   0 Số lần tải

Bài viết đã được chỉnh sửa nội dung bởi MUVODICH: 24-12-2024 - 08:58


#19
Hahahahahahahaha

Hahahahahahahaha

    Trung sĩ

  • Thành viên
  • 170 Bài viết

Bài 6

Cách 2: 

giả sử $n$ có phân tích chính tắc: 

$n=p_{1}^{a_{1}}.p_{2}^{a_{2}}...p_{k}^{a_{k}}$

ta sẽ chứng minh:

$\frac{\varphi(n)}{n}+\frac{\sigma(n)}{n}\geq 2$

$\star$: $ \frac{\varphi(n)}{n}=\prod_{i=1}^{k}(1-\frac{1}{p_{i}})=\prod_{i=1}^{k}(\frac{p_{i}-1}{p_{i}})$

$\star$:  $\frac{\sigma(n)}{n}=\prod_{i=1}^{k}(\frac{\frac{p_{i}^{a_{i}+1}-1}{p_{i}-1}}{p_{i}^{a_{i}}})=\prod_{i=1}^{k}(\frac{p_{i}-\frac{1}{p_{i}^{a_{i}}}}{p_{i}-1})\geq\prod_{i=1}^{k}(\frac{p_{i}-\frac{1}{p_{i}}}{p_{i}-1})=\prod_{i=1}^{k}(\frac{p_{i}+1}{p_{i}})$

ta chỉ cần chỉ ra:

$\prod_{i=1}^{k}(p_{i}-1)+\prod_{i=1}^{k}(p_{i}+1)\geq 2\prod_{i=1}^{k}p_{i}$

BỔ ĐỀ: $x_{j}$ nguyên dương

$\prod_{j=1}^{n}(x_{j}-1)+\prod_{j=1}^{n}(x_{j}+1)\geq 2\prod_{j=1}^{n}x_{j}$

+) $n=1$, đúng

+) $n=2$, đúng

...

+) giả sử bất đẳng thức đúng với $n-1$ tức là: $\prod_{j=1}^{n-1}(x_{j}-1)+\prod_{j=1}^{n-1}(x_{j}+1)\geq 2\prod_{j=1}^{n-1}x_{j}$

ta sẽ chứng mình bất đẳng thức đúng với $n$ hay là: $\prod_{j=1}^{n}(x_{j}-1)+\prod_{j=1}^{n}(x_{j}+1)\geq 2\prod_{j=1}^{n}x_{j}$

Thậy vậy $VT=(x_{n}-1)\prod_{j=1}^{n-1}(x_{j}-1)+(x_{n}+1)\prod_{j=1}^{n-1}(x_{j}+1)\geq2\prod_{j=1}^{n}x_{j} $ (hai số)

từ đây SUY RA ĐPCM :))


Bài viết đã được chỉnh sửa nội dung bởi Hahahahahahahaha: 24-12-2024 - 09:07

WHO'S THAT POKÉMON?!

 

:icon14:  :icon14:  :icon14:  :icon14:  :icon14:  :icon14:  :icon14:  :icon14:  :icon14:  :icon14:  :icon14:  :icon14:  :icon14:


#20
Hahahahahahahaha

Hahahahahahahaha

    Trung sĩ

  • Thành viên
  • 170 Bài viết

BÀI 5: 

mình thấy ae suy nghĩ hơi phức tạp rồi :))

với $n$ là số nguyên tố thì $\varphi(n)=n-1$ 

thì đẳng thức trên hiển nhiên đúng

với $n$ là hợp số 

Khi này $n>2$ nên $\varphi(n)$ chẵn

Gọi $m_{1},m_{2},...,m_{s}$ là các số nguyên tố cùng nhau với $n$

do đó theo thuật toán Euclid thì: $(m_{i},n)=(n-m_{i},n)=1$

nên sẽ tồn tại $m_{i}=m_{j}(i\ne j)$ ở dãy trên 

cũng vì đó $m_{1}+...+m_{s}=\frac{n.\varphi(n)}{2}$

SUY RA: $S(n)=\frac{n(n+1)}{2}-\frac{n.\varphi(n)}{2}$


WHO'S THAT POKÉMON?!

 

:icon14:  :icon14:  :icon14:  :icon14:  :icon14:  :icon14:  :icon14:  :icon14:  :icon14:  :icon14:  :icon14:  :icon14:  :icon14:





2 người đang xem chủ đề

0 thành viên, 2 khách, 0 thành viên ẩn danh