Đến nội dung

Hình ảnh

Cho n là số nguyên dương lẻ, u là 1 ước nguyên dương lẻ của $3^{n}+1$. Tìm số dư của u khi chia cho 3.


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

#1
phamvanha92

phamvanha92

    Trung sĩ

  • Thành viên
  • 164 Bài viết
Cho n là số nguyên dương lẻ, u là 1 ước nguyên dương lẻ của $3^{n}+1$. Tìm số dư của u khi chia cho 3.

#2
nhuquynhdinh

nhuquynhdinh

    Binh nhì

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

Cho n là số nguyên dương lẻ, u là 1 ước nguyên dương lẻ của $3^{n}+1$. Tìm số dư của u khi chia cho 3.

Vì n lẻ nên ta có :
$3^{n} + 1$ = $(3 + 1).(3^{n-1} + 3^{n-2} + ... + 3 + 1)$ = $4.(3^{n-1} + 3^{n-2} + ... + 3 + 1)$ = 2.k.u ( Vì u là ước lẻ ) (k > 0)
Nếu u = 1 thì u chia 3 dư 1
Nếu u $\neq$ 1 thì 4 không chia hết cho u
$\Rightarrow$ $3^{n} + 1 = 4. (3^{n-1} + 3^{n-2} + ... +3 + 1) = 4. u$
$\Rightarrow$ $3^{n-1} + 3^{n-2} + ...+ 1 = u$
Mà $3^{n-1} + 3^{n-2} + ...+ 1$ chia 3 dư 1
$\Rightarrow$ u chia 3 dư 1
Vậy số dư của u khi chia cho 3 là 1

3698


#3
famas1stvn98

famas1stvn98

    Binh nhì

  • Thành viên
  • 14 Bài viết
hình như mình thấy lời giải bạn có vấn đề rồi lúc mình làm bài này cũng đến đoạn $3^{n-1}+....+1$ chia 3 dư 1 nhưng mà có phải cứ số nào chia 3 dư 1 thì ước của nó cũng chia 3 dư 1 đâu? ví dụ như 4=2*2 đó. Khẳng định của bạn chỉ đúng khi số chia 3 dư 2 thôi, khi ấy chắc chắn có ước của số đó chia 3 dư 2.
P/s: bài bạn Nguyên chuẩn đó :D

Bài viết đã được chỉnh sửa nội dung bởi famas1stvn98: 13-07-2012 - 22:33


#4
nguyenta98

nguyenta98

    Thượng úy

  • Hiệp sỹ
  • 1259 Bài viết

Cho n là số nguyên dương lẻ, u là 1 ước nguyên dương lẻ của $3^{n}+1$. Tìm số dư của u khi chia cho 3.

Giải như sau:
Bổ đề 1: Nếu $p$ là số nguyên tố lẻ $>3$ (hay khi đó $p=6q\pm1$) khi ấy $3^{\frac{p-1}{2}} \equiv (-1)^q \pmod{p}$
Bổ đề 2: $3^x-1 \vdots p$ và $3^y-1 \vdots p$ với $x$ min thì $y \vdots x$
Chứng minh bổ đề này chắc dễ rồi
Áp dụng bài toán
Thử $n=1$ thì thấy hiển nhiên là đúng
Giả sử đúng đến $n=m$ như vậy suy ra $n=3,5,...,m$ đều đúng hay tất cả các ước của $3^3+1,3^5+1,...,3^m+1$ đều chia $3$ dư $1$
Ta sẽ chứng minh $n=m+2$ cũng đúng hay mọi ước $3^{m+2}+1$ chia $3$ dư $1$
Thật vậy ta có, giả sử $p$ là một ước của $3^{m+2}+1$ suy ra $3^{2(m+2)}-1 \vdots p$ ($p>1$ vì $p=1$ là điều hiển nhiên và $p$ lẻ)
Gọi $k$ là số nhỏ nhất thỏa mãn $3^{k}-1$
TH1: $k$ lẻ suy ra áp dụng bổ đề ta có $2(m+2) \vdots k$ nhưng $gcd(k,2)=1 \Rightarrow m+2 \vdots k$
Suy ra $3^{m+2}-1 \vdots p$ mà $p$ là ước $3^{m+2}+1 \Rightarrow 2 \vdots p$ vô lý
TH2: $k$ chẵn suy ra $k=2t$ áp dụng bồ đề có $2(m+2) \vdots 2t \Rightarrow m+2 \vdots t$ suy ra $t$ lẻ do $m+2$ lẻ $(1)$
Mặt khác $3^k-1 \vdots p \Rightarrow (3^t-1)(3^t+1) \vdots p$
Nếu $3^t-1 \vdots p$ mà $m+2 \vdots t \Rightarrow 3^{m+2}-1 \vdots p$ mà $p$ là ước của $3^{m+2}+1$ nên $2 \vdots p$ vô lý
Suy ra $3^t+1 \vdots p$ mà dễ thấy
$\blacksquare$ Nếu $t<m+2$ mà $t$ lẻ (theo $(1)$)
Nên theo quy nạp thì đúng với mọi $n=3,5,...,m$ nên đúng với $t$ hay mọi ước của $3^t+1$ chia $3$ dư $1$
Suy ra $p \equiv 1 \pmod{3}$ mà $p$ là ước $3^{m+2}+1$ nên có đpcm
$\blacksquare$ Nếu $t=m+2$ khi đó $3^{2(m+2)}-1$ là số nhỏ nhất chia hết cho $p$
Mặt khác theo Fermat nhỏ suy ra $3^{p-1}-1 \vdots p \Rightarrow \left(3^{\frac{p-1}{2}}-1\right).\left(3^{\frac{p-1}{2}}+1\right) \vdots p$
Theo bổ đề 2 suy ra $p-1 \vdots 2(m+2) \Rightarrow \frac{p-1}{2} \vdots (m+2)$
$\boxed{\rightarrow}$ Khi $\frac{p-1}{2}$ lẻ suy ra $\frac{p-1}{2}=(m+2).l$ với $l$ lẻ suy ra $\left(3^{\frac{p-1}{2}}+1\right)$
Theo bổ đề 1 suy ra $p=6q\pm 1$ và $(-1)^q \equiv -1 \pmod{p} \Rightarrow q=2u+1$
Nhưng khi $p=6q-1 \Rightarrow p=6(2u+1)-1=12u+5 \Rightarrow \frac{p-1}{2}=6u+2$ vô lý vì ta đã giả sử $\frac{p-1}{2}$ lẻ
Suy ra $p=6(2u+1)+1 \Rightarrow p \equiv 1 \pmod{3}$ suy ra đpcm
$\boxed{\rightarrow}$ Khi $\frac{p-1}{2}$ chẵn suy ra $\left(3^{\frac{p-1}{2}}-1\right) \vdots p$
Suy ra $\frac{p-1}{2}=(m+2).z$ với $z$ chẵn (theo bổ đề 2)
Theo bổ đề 1 suy ra $p=6q\pm 1$ và $(-1)^q \equiv 1 \pmod{p} \Rightarrow q=2g$
Nhưng khi $p=6(2g)-1 \Rightarrow \frac{p-1}{2}=6q-1$ là số lẻ vô lý do ta đã giả sử $\frac{p-1}{2}$ chẵn
Do đó $p=6(2g)+1 \Rightarrow p \equiv 1 \pmod{3}$ suy ra đpcm
Vậy bài toán được chứng minh hoàn toàn

Bài viết đã được chỉnh sửa nội dung bởi nguyenta98: 14-07-2012 - 13:09


#5
perfectstrong

perfectstrong

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

  • Quản lý Toán Ứng dụng
  • 4990 Bài viết
Ý tưởng chung là sử dụng cấp của số. Nhưng cách sau ngắn gọn hơn :)
Lời giải:
Nếu $n=1$ thì dễ thấy $1 \equiv 1 \pmod 3$.
Nếu $n>1 \Rightarrow \dfrac{n-1}{2}>0$
Gọi $p$ là 1 ước nguyên tố lẻ của $3^n+1$. Dễ thấy $p>3$.
Đặt $3^{\frac{n-1}{2}}=2q+1(q \in \mathbb{N})$
$\Rightarrow p|3^n+1=3(2q+1)^2+1=4(3q^2+3q+1) \Rightarrow p|3q^2+3q+1$
$\Rightarrow q \not \equiv 0 \pmod p$
Nếu $q \equiv 1 \pmod p \Rightarrow 3q^2+3q+1 \equiv 7 \pmod p \Rightarrow p=7 \equiv 1 \pmod 3$
Ta xét $q \not \equiv 1 \pmod p$. Dễ suy ra $p|q^2+q+1$
Mặt khác $q^3 \equiv 1 \pmod p \Rightarrow q^{3k+1} \not \equiv 0;1 \pmod p,\forall k \in \mathbb{N},(1)$
Mà $(q;p)=1 \Rightarrow q^{p-1} \equiv 1 \pmod p$. Kết hợp với $(1)$ suy ra $p-1 \not \equiv 0;1 \pmod 3 \Rightarrow p \equiv 1 \pmod 3$.
Do đó, mọi ước dương lẻ của $3^n+1$ đều chia $3$ dư $1$.

Bài viết đã được chỉnh sửa nội dung bởi perfectstrong: 15-07-2012 - 21:42

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.




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

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