분수 퍼즐
이것은 컴퓨터 퍼즐 태그와 컴퓨터 없음 태그 가 모두있는 퍼즐입니다 .
다음과 같은 다섯 가지 분수 목록이 있습니다.
$$11/5, 30/77, 1/11, 21/2, 5/7.$$
정수로 시작 $x$, 우리는 다음 작업을 수행합니다. 각 단계에서 곱하기 $x$ 정수 결과를 제공하는 위 목록의 첫 번째 분수 (왼쪽에서 오른쪽으로)로.
목록에 그러한 분수가 없으면 절차가 종료되고 값이 $x$ 최종 결과입니다.
예 : 시작 $x = 2$
첫 번째 단계 : 곱하기 $21/2$, 제공 $21$.
두 번째 단계 : 곱하기 $5/7$, 제공 $15$.
세 번째 단계 : 곱하기 $11/5$, 제공 $33$.
네 번째 단계 : 곱하기 $1/11$, 제공 $3$.
우리는 그것을 본다 $x = 3$ 곱하기로 최종 결과입니다 $3$ 5 개의 분수 중 하나는 정수가 아닌 결과를 제공합니다.
질문 : 다음으로 시작하면 $x = 2^{1234567}$, 그러면 최종 결과의 마지막 세 자리는 무엇입니까?
말:
이것은 어느 정도 잘 알려져 있으며,이를 해결하는 데 추가 지식이 필요하지 않을 정도로 간단해야하기 때문에 의도적으로 이름을 언급하지 않습니다.
물론 답변에서 이름을 지적 할 수 있습니다!
답변
우리는
분수 하나만 분모가 2입니다.
x = 2 ^ 1234567이므로 연결을 시도 할 수 있습니다. 숫자의 소인수 분해를 사용하여 일을 더 쉽게 할 것입니다.
먼저 21/2를 곱하여 2 ^ 1234566 * 3 * 7을 얻습니다. 21/2 이전의 모든 분수는 2, 3 또는 7이 아닌 소인수를 갖기 때문에 함수가 21/2로 계속 곱한다는 것을 알고 있습니다. 2의 인수가 남지 않을 때까지. 3 ^ 1234567 * 7 ^ 1234567이 남습니다.
다음,
우리는 5/7을 곱합니다. 목록의 첫 번째 분수는 분모가 5이기 때문에 5/7을 곱할 때마다 본질적으로 11/7을 곱할 것임을 알고 있습니다. 우리는 곱하고 3 ^ 1234567 * 7 ^ 1234566 * 11을 얻습니다. 30/77은 곱할 다음 분수입니다. 2 * 3 ^ 1234568 * 5 * 7 ^ 1234565로 끝납니다. 11/5를 곱하면 2 * 3 ^ 1234568 * 7 ^ 1234565 * 11이됩니다.
우리는
7이 너무 많기 때문에 7이 다 떨어질 때까지 30/77과 11/5를 계속 곱할 것입니다. 우리는 7의 수가 1 감소 할 때마다 2의 수가 1 씩 증가하고 3의 수가 1만큼 증가한다는 것을 알고 있습니다. 우리는 2와 3의 수를 1234565만큼 증가시키고 7의 모든 요소를 제거하여 2 ^ 1234566 * 3 ^ 2469133 * 11. 1/11을 곱하여 11의 인수를 제거하고 2 ^ 1234566 * 3 ^ 2469133을 얻습니다.
이것은 우리를 처음과 같은 위치에 남겨 둡니다.
우리는 3 개의 요인을 가지고 있고 2 개의 요인의 수는 1만큼 감소했습니다.
분모가 3의 인수가 없기 때문에
이전과 똑같은 작업을 몇 번만 수행합니다. 2를 모두 제거하면 3 ^ 3703699 * 7 ^ 1234566이됩니다. 우리는 5/7을 곱한 다음 11/5를 곱하여 3 ^ 3703699 * 7 ^ 1234565 * 11을 얻습니다. 2와 3의 거듭 제곱을 다시 더하고 7의 거듭 제곱과 11의 거듭 제곱을 모두 제거하여 2 ^ 1234565를 얻습니다. * 3 ^ 4938264.
우리는
처음에는 3의 거듭 제곱이 (1234567 + 1234566)만큼 증가했고 이번에는 3의 거듭 제곱이 (1234566 + 1234565)만큼 증가했습니다. 즉, 2의 거듭 제곱에 대해 3의 거듭 제곱이 (2x-1)만큼 증가합니다. 이것은 3의 거듭 제곱이$\sum_{i=1}^{1234567} 2i-1$ 합계 속성을 사용하여 $2*\sum_{i=1}^{1234567} i - 1234567$. 우리는 첫 번째의 합이$n$ 양의 정수는 $\frac{n*(n+1)}{2}$, 그래서 $\sum_{i=1}^{1234567} i = 1234567*1234568/2 = 762078456028$, 그래서 $2*\sum_{i=1}^{1234567} i - 1234567 = 1524155677489$
우리는 그것을 본다
최종 답은 3 ^ 1524155677489이고 3 ^ x의 마지막 3 자리가 100 번마다 반복되기 때문에 3의 거듭 제곱 (mod 100), 즉 89 만 취하면됩니다.
즉, 마지막 3 자리를 찾아야합니다.
3 ^ 89.
마지막 3 자리는
3 ^ 10은 049이고
이는 마지막 3 자리 숫자를 의미합니다.
3 ^ 20은 49 ^ 2 또는 401의 마지막 3 자리입니다.
이는 마지막 3 자리 숫자를 의미합니다.
3 ^ 40은 401 ^ 2 또는 801의 마지막 3 자리입니다.
이는 마지막 3 자리 숫자를 의미합니다.
3 ^ 80은 801 ^ 2 또는 601의 마지막 3 자리입니다.
이는 마지막 3 자리 숫자를 의미합니다.
3 ^ 89는 601 *의 마지막 3 자리입니다 (3 ^ 9의 마지막 3 자리).
마지막 3 자리는
3 ^ 9는 683에 불과합니다. 즉, 3 ^ 89의 마지막 3 자리는 601 * 683의 마지막 3 자리 인 483입니다.
이것은 우리의 최종 답변이
483.
면책 조항 : 내 계산은 약간 지저분하며 한 번의 오산으로 전체 답변이 잘못 될 수 있지만 일반적인 솔루션은 여전히 옳습니다.
나는 속물처럼 보이고 싶지 않지만 경제적으로 무언가를 증명 / 계산하는 데 가치가 있습니다. 따라서 증명의 후반부 (정말 높은 정수 거듭 제곱의 마지막 세 자리 계산)를 올바르게 수행해 봅시다. 첫째, 우리는$3^{100}\equiv 1 \mod 1000$ (오일러를 사용하지 않고 $\phi$) :
에서 시작 $3^5 = 243$ 다섯 번째 거듭 제곱을 두 번 더 취해 봅시다. 마지막 세 자리 만 필요하기 때문에 이항 정리를 사용하면 매우 간단합니다. 세 번째 및 모든 후속 항이 1000으로 나눌 수 있으므로 무시할 수 있다는 것을 쉽게 알 수 있기 때문입니다. $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$
두 경우 모두 동일한 값입니다. 3과 1000은 상대적으로 소수이므로$3^{100} \equiv 1 \mod 1000$
이를 통해 고통없는 컴퓨팅 방법을 찾아 보겠습니다.
$3^{89}$. 우리가 방금 보여준 것에 의해$3^{89}\equiv \frac 1 {3^{11}} \mod 1000$. 자, 그 역이$3$ 모듈로 $1000$ 이다 $-333$,의 $9$ 이다 $-111$. 그러므로:$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$