Đến nội dung

Hình ảnh

tồn tại một bội $a(n)$ của $2^n+1$


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

#1
pnt

pnt

    Thượng sĩ

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

Chứng minh với mọi số nguyên dương $n$, luôn tồn tại một bội $a(n)$ của $2^n+1$ sao cho: $a(n)$ có đúng $n$ số $1$, và $n$ số $1$ này đứng liên tiếp.

Ví dụ: Có thể chọn

$$a(1)=12; a(2)=110; a(3)=456111$$


độc lập ,tự do muôn năm!!!!!!!!!!!!!

#2
nguyenta98

nguyenta98

    Thượng úy

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

Chứng minh với mọi số nguyên dương $n$, luôn tồn tại một bội $a(n)$ của $2^n+1$ sao cho: $a(n)$ có đúng $n$ số $1$, và $n$ số $1$ này đứng liên tiếp.

Ví dụ: Có thể chọn

$$a(1)=12; a(2)=110; a(3)=456111$$

Bài này tuy lời giải ngắn gọn, nhưng ý tưởng và kĩ năng ko phù hợp THCS  lắm :D Nên chuyển nó vào mục Olympiad

Giải như sau:

Ta có một chú ý nhỏ là nếu $2^n+1=5^x.y$ với $gcd(5,y)=1$ thì trong bội của $a(n)$ ta chỉ việc thêm $x$ số $0$ vào sau là xong, do đó để thuận tiện ta chỉ cm bài toán trong TH $gcd(2^n+1,5)=1$ là đủ

Xét số có dạng sau: $A=\overline{200..00200..00200..200...011111....1}$ với $n$ số 1 với $l$ chữ số 2, các chữ số $0$ ko quan tâm

Hay ta viết $A$ dạng sau:

$$A=2.10^{m_1}+2.10^{m_2}+...+2.10^{m_l}+11...11$$ (với $n$ cs $1$)

Chú ý $gcd(10,2^n+1)=1$ do đó chọn $m_i=\phi(2^n+1).s_i$ với $s_i \in Z+$ và $s_1>s_2>...>s_l$

Khi đó theo định lý Euler

$A \equiv 2+2+...+2+11...11 \pmod{2^n+1}$ (n cs 1 và $l$ cs 2)
Hay $A \equiv 2l+11...11 \pmod{2^n+1}$

Đến đây do $gcd(2,2^n+1)$ theo bổ đề Bezout, tồn tại $l$ để $2l+11..11 \vdots 2^n+1$ nên bài toán được cm, số $A \vdots 2^n+1$ và có đúng n cs 1

P/S bài có ý tưởng khá giống một bài Shorlist với cách chọn phi hàm Euler (bài $S(n) \vdots k$ gì đó mình ko nhớ lắm), nhắc lại hệ quả của bổ đề Bezout (thực ra gọi thế cho oai chứ nó là hệ thặng dư) Cho a,b,c nguyên dương, $gcd(a,c)=1$ khi đó tồn tại duy nhất số tự nhiên $x$ theo $\pmod{c}$ để $ax+b \vdots c$


Bài viết đã được chỉnh sửa nội dung bởi nguyenta98: 06-10-2013 - 14:50





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

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