Đến nội dung


Chú ý

Nếu các bạn đăng kí thành viên mà không nhận được email kích hoạt thì hãy kiểm tra thùng thư rác (spam). Nếu không biết cách truy cập vào thùng thư rác thì các bạn chịu khó Google hoặc đăng câu hỏi vào mục Hướng dẫn - Trợ giúp để thành viên khác có thể hỗ trợ.


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
  • Giới tính:Nam
  • Đến từ:TP.hcm
  • Sở thích:Giải tích, Đại số, Hình học, Số học, Lượng giác, Topo, Toán rời rạc, Toán thông kê.

Đã gửi 31-03-2005 - 21:43

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
  • Giới tính:Nam
  • Đến từ:THPT chuyên KHTN
  • Sở thích:Number theory, Combinatorics-number theory problems

Đã gửi 06-10-2013 - 14:34

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