Đến nội dung

Hình ảnh

Từ $2^{100} \equiv 1\pmod{125}$ suy ra $2^{100} \equiv 376\pmod{1000}$


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

#1
Nesbit

Nesbit

    ...let it be...

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

Ngày xưa mình không thích Số Học nên học rất kém môn này, để lại hậu quả đến bây giờ.

 

Đang đọc một cuốn sách trong đó có đoạn như sau: Vì $2^{100} \equiv 1\pmod{125}$, mà $2^{100}$ lại chia hết cho $8$, suy ra $2^{100} \equiv 376\pmod{1000}$.

 

Nếu chứng minh thì cũng khá dễ như sau: Ta có $2^{100} = 125k+1$. Nếu chia $k$ cho $8$ được $q$ dư $r$ thì $2^{100} = 125(8q + r) + 1 = 1000q + 120r + 5r + 1$. Vì $8\mid 2^{100}$ nên suy ra $8\mid 5r+1$, vậy $r=3$, nghĩa là $2^{100} = 1000q + 376$.

 

Điều Nesbit thắc mắc là đối với những bạn giỏi Số Học, cái đoạn suy ra ở trên có hiển nhiên không và tại sao? Cảm ơn các bạn.


Không đọc tin nhắn nhờ giải toán.

 

Góp ý về cách điều hành của mod

 

 


#2
Hoang72

Hoang72

    Thiếu úy

  • Điều hành viên OLYMPIC
  • 539 Bài viết

Em nghĩ khi đã tìm được con số $376$ là kết quả của $2^{100}$ mod $1000$ thì có thể xem là hiển nhiên.

Tuy nhiên tìm ra con số $376$ thì không phải qua một phép toán mà chỉ ra được.

Chẳng hạn, xét hệ đồng dư $\begin{cases} x\equiv a_1 \pmod {b_1} \\ x\equiv a_2\pmod {b_2}\end{cases}$, với $(b_1,b_2) = 1; a_1 < b_1; a_2 < b_2; b_1 > b_2$.

Ta tìm số dư của $x$ khi chia cho $b_1b_2$.

Đặt $x = b_1k + a_1$, gọi số dư của $k$ khi chia cho $b_2$ là $r$.

Thế thì $b_1k + a_1 \equiv b_1r + a_1\pmod {b_1b_2}$

$\Rightarrow b_1r + a_1 \equiv a_2\pmod {b_2}$

$\Rightarrow b_1r\equiv a_2 - a_1\pmod {b_2}$.

Phương trình này có duy nhất một nghiệm do $0\leq r < b_2$.

Muốn tìm $r$ thuật toán tối ưu nhất chắc cũng có lẽ là tìm nghịch đảo module của $b_1$, bằng việc tìm $x,y$ thoả mãn $xb_1 + yb_2 = 1$ thông qua giải thuật Euclid mở rộng, mất thời gian $O(\log_2 (\min\{b_1, b_2\}))$. Cho nên việc tìm ra số dư của $x$ khi chia cho $b_1b_2$ với các số cho trước không thuận lợi thì nó không phải là điều hiển nhiên  :D


Bài viết đã được chỉnh sửa nội dung bởi Hoang72: 14-09-2022 - 00:28


#3
Nesbit

Nesbit

    ...let it be...

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

Em nghĩ khi đã tìm được con số $376$ là kết quả của $2^{100}$ mod $1000$ thì có thể xem là hiển nhiên.

Tuy nhiên tìm ra con số $376$ thì không phải qua một phép toán mà chỉ ra được.

Tại sao khi biết kết quả là $376$ rồi thì hiển nhiên ấy em nhỉ?

Lưu ý là cách anh làm ở trên không biết trước kết quả mà tìm được số $376$ luôn.


Không đọc tin nhắn nhờ giải toán.

 

Góp ý về cách điều hành của mod

 

 


#4
Hoang72

Hoang72

    Thiếu úy

  • Điều hành viên OLYMPIC
  • 539 Bài viết

Tại sao khi biết kết quả là $376$ rồi thì hiển nhiên ấy em nhỉ?

Lưu ý là cách anh làm ở trên không biết trước kết quả mà tìm được số $376$ luôn.

$2^{100} \equiv 376\pmod {1000}$ thì sẽ có $2^{100} \equiv 376 \pmod {125}$ và $2^{100}\equiv 376\pmod 8$ ạ. Hoặc ngược lại.


Bài viết đã được chỉnh sửa nội dung bởi Hoang72: 14-09-2022 - 17:11


#5
Nesbit

Nesbit

    ...let it be...

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

$2^{100} \equiv 376\pmod {1000}$ thì sẽ có $2^{100} \equiv 376 \pmod {125}$ và $2^{100}\equiv 376\pmod 8$ ạ. Hoặc ngược lại.

Đúng là nếu biết kết quả là $376$ thì có thể kiểm chứng lại như vậy. Ở đây dùng tính chất nếu $a\equiv b\pmod {m}$ và $a\equiv b\pmod {n}$ với $(m,n) = 1$ thì $a\equiv b\pmod {mn}$.

 

Không biết có cách nào tìm ra được số $376$ nhanh hơn cách Nesbit đã làm ở trên không. Đọc sách thấy ghi là hiển nhiên nên chắc những người giỏi họ nhìn ra ngay được :D 


Không đọc tin nhắn nhờ giải toán.

 

Góp ý về cách điều hành của mod

 

 


#6
vutuanhien

vutuanhien

    Thiếu úy

  • ĐHV Toán Cao cấp
  • 690 Bài viết

Đúng là nếu biết kết quả là $376$ thì có thể kiểm chứng lại như vậy. Ở đây dùng tính chất nếu $a\equiv b\pmod {m}$ và $a\equiv b\pmod {n}$ với $(m,n) = 1$ thì $a\equiv b\pmod {mn}$.

 

Không biết có cách nào tìm ra được số $376$ nhanh hơn cách Nesbit đã làm ở trên không. Đọc sách thấy ghi là hiển nhiên nên chắc những người giỏi họ nhìn ra ngay được :D

Em cũng cảm thấy là không có cách nào để nhìn ra ngay được con số 376 trừ khi đã biết trước thì có thể nói là 'hiển nhiên'. Tất nhiên ở trường hợp này số cũng khá nhỏ nên có thể tính nhẩm nhanh được ($125\equiv 5$ mod 8 nên cần nhân 3 lên để cộng 1 chia hết cho 8, ra được 376).


"The first analogy that came to my mind is of immersing the nut in some softening liquid, and why not simply water? From time to time you rub so the liquid penetrates better, and otherwise you let time pass. The shell becomes more flexible through weeks and months—when the time is ripe, hand pressure is enough, the shell opens like a perfectly ripened avocado!" - Grothendieck


#7
Nesbit

Nesbit

    ...let it be...

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

Em cũng cảm thấy là không có cách nào để nhìn ra ngay được con số 376 trừ khi đã biết trước thì có thể nói là 'hiển nhiên'. Tất nhiên ở trường hợp này số cũng khá nhỏ nên có thể tính nhẩm nhanh được ($125\equiv 5$ mod 8 nên cần nhân 3 lên để cộng 1 chia hết cho 8, ra được 376).

Rất có thể cách tính nhẩm như em nói chính là cách "hiển nhiên" của tác giả. Em có thể chia sẻ thêm tại sao lại nhìn ra ngay được là bài toán ban đầu có thể đưa về việc tìm một hệ số để nhân với $5$ cộng $1$ chia hết cho $8$ không? Theo cách anh làm ở trên thì tất nhiên là đúng như vậy, nhưng anh cần phải đặt bút xuống mới tới được bước đó, và anh đang cố gắng hiểu suy nghĩ trong đầu của những người nhìn ngay ra được. Anh đưa một ví dụ bên dưới để em hiểu ý anh là gì.

 

Nếu ai hay áp dụng định lý phần dư Trung Hoa thì rất có thể họ sẽ xử lí trong đầu như sau:

 

Ta cần tìm $x$ sao cho $x \equiv 1\pmod{125}$ và $x \equiv 0\pmod{8}$, vì khi đó ta sẽ có $2^{100}\equiv x\pmod{1000} $ theo định lý phần dư Trung Hoa. Muốn tìm $x$ ta nhẩm để tìm $r$ sao cho $8\mid 125\times r + 1$. Vì $8\mid 120$ nên $8\mid 5r + 1$, suy ra $r=3$.


Không đọc tin nhắn nhờ giải toán.

 

Góp ý về cách điều hành của mod

 

 


#8
vutuanhien

vutuanhien

    Thiếu úy

  • ĐHV Toán Cao cấp
  • 690 Bài viết

Rất có thể cách tính nhẩm như em nói chính là cách "hiển nhiên" của tác giả. Em có thể chia sẻ thêm tại sao lại nhìn ra ngay được là bài toán ban đầu có thể đưa về việc tìm một hệ số để nhân với $5$ cộng $1$ chia hết cho $8$ không? Theo cách anh làm ở trên thì tất nhiên là đúng như vậy, nhưng anh cần phải đặt bút xuống mới tới được bước đó, và anh đang cố gắng hiểu suy nghĩ trong đầu của những người nhìn ngay ra được. Anh đưa một ví dụ bên dưới để em hiểu ý anh là gì.

 

Nếu ai hay áp dụng định lý phần dư Trung Hoa thì rất có thể họ sẽ xử lí trong đầu như sau:

 

Ta cần tìm $x$ sao cho $x \equiv 1\pmod{125}$ và $x \equiv 0\pmod{8}$, vì khi đó ta sẽ có $2^{100}\equiv x\pmod{1000} $ theo định lý phần dư Trung Hoa. Muốn tìm $x$ ta nhẩm để tìm $r$ sao cho $8\mid 125\times r + 1$. Vì $8\mid 120$ nên $8\mid 5r + 1$, suy ra $r=3$.

À cách nghĩ của em cũng giống điều mà anh viết thôi ạ, có thể là em "quen" các bài này nên nhẩm nhanh hơn thôi ạ. Em nhớ là hồi lớp 6 em đọc sách Nâng cao phát triển của thầy Vũ Hữu Bình cũng có những bài kiểu tìm $x$ mà $x\equiv 3$ mod $4$, $x\equiv 6$ mod 11... mà hồi đó không biết định lý phần dư Trung Hoa nên phải học cách nhẩm: Tìm $y$ chia hết cho $4$ để $y+3\equiv 6$ mod $11$...

 

Còn những bài này về cơ bản đúng là phải dùng định lý phần dư Trung Hoa và đưa về giải phương trình $xb_{1}+yb_{2}=1$ như Hoang72 đã bình luận ở trên nên em nghĩ là không có cách nào hiển nhiên để nhìn ra được số 376.


Bài viết đã được chỉnh sửa nội dung bởi vutuanhien: 16-09-2022 - 20:36

"The first analogy that came to my mind is of immersing the nut in some softening liquid, and why not simply water? From time to time you rub so the liquid penetrates better, and otherwise you let time pass. The shell becomes more flexible through weeks and months—when the time is ripe, hand pressure is enough, the shell opens like a perfectly ripened avocado!" - Grothendieck





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

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