This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Since g c d ( 5 7 9 9 9 , 1 0 0 0 0 0 ) = 1 , we will use CRT.
Obviously, 5 7 9 9 9 ≡ 0 ( mod 3125)
We must find 5 7 9 9 9 (mod 32)
We know that ϕ ( 3 2 ) = 1 6 ⟹ 5 1 6 ≡ 1 (mod 32)
⟹ 5 7 9 9 9 ≡ 5 1 5 (mod 32)
Let x = 5 7 9 9 9 .
Since x ≡ 5 1 5 this implies that 5 x ≡ 5 1 6 ≡ 1 (mod 32)
5 x ≡ 1 (mod 32) - Multiply 13 on both sides.
x ≡ 1 3 (mod 32)
Use CRT on
x ≡ 1 3 (mod 32) x ≡ 0 (mod 3125)
To get that x ≡ 7 8 1 2 5 ( mod 100000)
5^8=...90625, now 90625^2=...890625 so,90625^(2*500)=.....890625, then 5^8000=...890625 now,5^7999=890625/5=78125
If you don't come up with any solution, I suggest researching the way it repeats the last digits. For example, we find out that 5 6 = . . . 1 5 6 2 5 5 7 = . . . 7 8 1 2 5 5 8 = . . . 9 0 6 2 5 5 9 = . . 5 3 1 2 5 5 1 0 = . . . 6 5 6 2 5 5 1 1 = . . . 2 8 1 2 5 5 1 2 = . . . 4 0 6 2 5 5 1 3 = . . . 0 3 1 2 5 5 1 4 = . . . 1 5 6 2 5 5 1 5 = . . . 7 8 1 2 5 ... We could observe that the repeating round has 8 elements, and 7 9 9 9 = 9 9 9 × 8 + 7 . Hence, the last five digits of 5 7 9 9 9 are 7 8 1 2 5 .
This solution is based on the lemma below. First we note that 5 7 = 7 8 1 2 5 , and 5 8 = . . . 9 0 6 2 5 . Further, 5 7 5 8 = . . . . 7 8 1 2 5 and 9 0 6 2 5 2 = . . . 9 0 6 2 5 . Thus 5 8 k = . . . 9 0 6 2 5 for any whole number k. Hence 5 7 9 9 9 = 5 7 ( 5 8 ) 9 9 9 = . . . . 7 8 1 2 5 × . . . 9 0 6 2 5 = . . . 7 8 1 2 5 . In conclusion 5 k will end in 78125 when ever k mod 8 = 7.
Lemma. Let A and B be whole numbers with n digits each. Further, let P be a large whole number whose last n digits are A, and let Q be a large whole number whose last n digits are B. Then the last n digits of the product PQ will be the same as the last n digits of the product AB.
Proof: Let t be the number of digits of P and u be the number of digits of Q, naturally t>n and u>n. Then P = 1 0 t + A and Q = 1 0 u + B . Distributing, we get PQ = 1 0 t + u + 1 0 t B + 1 0 u A + A B , a number whose last n digits are precisely the last n digits of AB.
Problem Loading...
Note Loading...
Set Loading...
Using the Carmichael function, we find that 5 8 ≡ 1 ( m o d 3 2 ) . Thus 5 7 9 9 4 = 5 8 ∗ 9 9 9 + 2 ≡ 5 2 ( m o d 2 5 ) . Multiplying through with 5 5 we find that 5 7 9 9 9 ≡ 5 7 = 7 8 1 2 5 ( m o d 1 0 5 ) .