Một câu đố phân số
Đây là một câu đố có cả thẻ câu đố máy tính và thẻ không máy tính .
Chúng tôi có danh sách năm phân số sau:
$$11/5, 30/77, 1/11, 21/2, 5/7.$$
Bắt đầu bằng một số nguyên $x$, chúng tôi thực hiện thao tác sau: ở mỗi bước, nhân $x$ bởi phân số đầu tiên (từ trái sang phải) trong danh sách trên cho kết quả là số nguyên.
Nếu không có phân số như vậy trong danh sách, thì thủ tục kết thúc và giá trị của $x$ là kết quả cuối cùng.
Ví dụ: bắt đầu bằng $x = 2$
bước đầu tiên: nhân nó với $21/2$, mang lại $21$.
bước thứ hai: nhân nó với $5/7$, mang lại $15$.
bước thứ ba: nhân nó với $11/5$, mang lại $33$.
bước thứ tư: nhân nó với $1/11$, mang lại $3$.
Chúng ta thấy rằng $x = 3$ là kết quả cuối cùng, như là nhân $3$ bởi bất kỳ phân số nào trong số năm phân số sẽ cho kết quả không phải là số nguyên.
Câu hỏi: nếu chúng ta bắt đầu với $x = 2^{1234567}$, thì ba chữ số cuối cùng của kết quả cuối cùng sẽ là bao nhiêu?
Nhận xét:
Điều này ở một mức độ nào đó nổi tiếng, và tôi cố ý không đề cập đến tên, vì nó phải đơn giản đến mức không cần thêm kiến thức để giải quyết nó.
Tất nhiên, bạn có thể chỉ ra tên trong câu trả lời của mình!
Trả lời
Chúng tôi quan sát rằng
chỉ một phân số có mẫu số là 2
Vì chúng ta có x = 2 ^ 1234567, chúng ta có thể thử cắm nó vào. Chúng ta sẽ sử dụng thừa số nguyên tố của các số để làm cho mọi thứ dễ dàng hơn.
Đầu tiên chúng ta nhân với 21/2, nhận được 2 ^ 1234566 * 3 * 7. Bởi vì tất cả các phân số trước 21/2 đều có thừa số nguyên tố khác với 2, 3 hoặc 7, chúng ta biết rằng hàm sẽ tiếp tục nhân với 21/2 cho đến khi không còn thừa số nào của 2. Điều này khiến chúng ta có 3 ^ 1234567 * 7 ^ 1234567.
Kế tiếp,
chúng ta nhân với 5/7. Vì phân số đầu tiên trong danh sách có mẫu số là 5 nên chúng ta biết rằng bất cứ lúc nào chúng ta nhân với 5/7 về cơ bản chúng ta sẽ nhân với 11/7. Chúng tôi nhân và nhận được 3 ^ 1234567 * 7 ^ 1234566 * 11. 30/77 là phân số tiếp theo để nhân với. Chúng tôi kết thúc bằng 2 * 3 ^ 1234568 * 5 * 7 ^ 1234565. Nhân với 11/5 cho chúng ta 2 * 3 ^ 1234568 * 7 ^ 1234565 * 11.
Chúng tôi nhận thấy rằng
bởi vì chúng ta có một số lượng lớn các số 7, chúng tôi sẽ tiếp tục nhân với 30/77 và 11/5 cho đến khi hết số 7. Ta nhận thấy rằng mỗi khi số 7 giảm 1 thì số 2 tăng 1 và số 3 tăng 1. Ta tăng số thừa của 2 và 3 thêm 1234565 và loại bỏ tất cả thừa số của 7 để được 2 ^ 1234566 * 3 ^ 2469133 * 11. Chúng ta nhân với 1/11 để loại bỏ thừa số của 11 và được 2 ^ 1234566 * 3 ^ 2469133.
Điều này khiến chúng ta ở đúng vị trí ban đầu, ngoại trừ
chúng ta có một loạt thừa số là 3 và số thừa số của 2 giảm đi 1.
Vì không mẫu số nào có hệ số là 3,
chúng ta sẽ làm điều tương tự như trước đây, chỉ là một số lần nhỏ hơn. Loại bỏ tất cả 2s cho chúng ta 3 ^ 3703699 * 7 ^ 1234566. Chúng ta nhân với 5/7 và sau đó là 11/5 để được 3 ^ 3703699 * 7 ^ 1234565 * 11. Chúng ta cộng lại các lũy thừa của 2 và 3 và loại bỏ tất cả các lũy thừa của 7 và một lũy thừa của 11 để được 2 ^ 1234565 * 3 ^ 4938264.
Chúng tôi nhận thấy rằng
lần đầu tiên lũy thừa của 3 tăng (1234567 + 1234566), và lần này lũy thừa của 3 tăng (1234566 + 1234565). Điều này có nghĩa là với lũy thừa của 2, nó sẽ tăng lũy thừa của 3 lên (2x-1). Điều này có nghĩa là sức mạnh của 3 sẽ là$\sum_{i=1}^{1234567} 2i-1$ Chúng ta có thể sử dụng các thuộc tính tổng kết để lấy $2*\sum_{i=1}^{1234567} i - 1234567$. Chúng tôi biết rằng tổng của$n$ số nguyên dương là $\frac{n*(n+1)}{2}$, vì thế $\sum_{i=1}^{1234567} i = 1234567*1234568/2 = 762078456028$, vì thế $2*\sum_{i=1}^{1234567} i - 1234567 = 1524155677489$
Chúng ta thấy rằng
câu trả lời cuối cùng là 3 ^ 1524155677489, và bởi vì 3 chữ số cuối cùng của 3 ^ x lặp lại sau mỗi 100 lần, chúng ta chỉ cần lấy lũy thừa của 3 (mod 100), là 89.
Điều này có nghĩa là chúng ta chỉ cần tìm 3 chữ số cuối cùng của
3 ^ 89.
Chúng tôi biết rằng 3 chữ số cuối cùng của
3 ^ 10 là 049,
có nghĩa là 3 chữ số cuối cùng của
3 ^ 20 chỉ là 3 chữ số cuối cùng của 49 ^ 2, hoặc 401,
có nghĩa là 3 chữ số cuối cùng của
3 ^ 40 chỉ là 3 chữ số cuối cùng của 401 ^ 2 hoặc 801,
có nghĩa là 3 chữ số cuối cùng của
3 ^ 80 chỉ là 3 chữ số cuối cùng của 801 ^ 2 hoặc 601,
có nghĩa là 3 chữ số cuối cùng của
3 ^ 89 chỉ là 3 chữ số cuối của 601 * (3 chữ số cuối của 3 ^ 9).
Chúng tôi biết rằng 3 chữ số cuối cùng của
3 ^ 9 chỉ là 683, có nghĩa là 3 chữ số cuối của 3 ^ 89 là 3 chữ số cuối của 601 * 683, là 483.
Điều này có nghĩa là câu trả lời cuối cùng của chúng tôi là
483.
Tuyên bố từ chối trách nhiệm: Các phép tính của tôi hơi lộn xộn và một phép tính sai duy nhất sẽ làm sai toàn bộ câu trả lời, nhưng giải pháp chung vẫn phải đúng.
Tôi không muốn trở thành kẻ hợm hĩnh nhưng có giá trị trong việc chứng minh / tính toán điều gì đó một cách kinh tế. Vì vậy, hãy thực hiện nửa sau (tính toán ba chữ số cuối cùng của một lũy thừa số nguyên cực kỳ cao) của bằng chứng đúng cách. Đầu tiên, chúng tôi lấy$3^{100}\equiv 1 \mod 1000$ (không sử dụng Euler $\phi$):
bắt đầu từ $3^5 = 243$ chúng ta hãy lấy lũy thừa thứ năm hai lần nữa: Vì chúng ta chỉ cần ba chữ số cuối cùng nên việc sử dụng định lý nhị thức khá đơn giản vì dễ dàng thấy rằng số hạng thứ ba và tất cả các số hạng sau đều chia hết cho 1000 và do đó có thể bỏ qua. $3^{25} \equiv (240+3)^5 \equiv 243 + 5\times 81\times 240 + 10\times 27\times 240^2 + ... \equiv 443 \mod 1000$ $3^{125} \equiv (440+3)^5 \equiv 243 + 5\times 81\times 440 \equiv 443 \mod 1000$
Vì vậy, đó là giá trị như nhau trong cả hai trường hợp. Vì 3 và 1000 là tương đối nguyên tố, chúng tôi kết luận$3^{100} \equiv 1 \mod 1000$
Với điều đó đã được thiết lập, hãy để chúng tôi tìm ra một cách tính toán không đau
$3^{89}$. Bằng những gì chúng tôi vừa trình bày, chúng tôi có$3^{89}\equiv \frac 1 {3^{11}} \mod 1000$. Bây giờ, có thể dễ dàng đoán rằng nghịch đảo của$3$ modulo $1000$ Là $-333$, của $9$ Là $-111$. Như vậy:$3^{89}\equiv 3^{-11} \equiv 333\times 111^5 \equiv 333\times \left ( 1 + 5 \times 110 \right ) \equiv 333 \times 551 \equiv 333 + 650 + 500 \equiv 483 \mod 1000$