2 0 1 7 !
Find the last two non-zero digits in the number above.
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.
Nice solution! I used a very similar method, though I went straight ( m o d 1 0 0 ) , which required a bit more "massaging" of powers of two and powers of three; your method is more efficient.
One minor quibble, though: When you first break down f ( 2 0 1 7 ) , the last two factors are ( 1 ⋅ 2 ) , which you then equate to 2 ( m o d 2 5 ) , which I don't think is quite true. After all, ( 5 k + 1 ) ⋅ ( 5 k + 2 ) ≡ 1 5 k + 2 ( m o d 2 5 ) , so the residues could be any of 2, 7, 12, 17 or 22. In fact, in this particular case, the actual values are 2 0 1 6 ⋅ 2 0 1 7 ≡ 2 2 ( m o d 2 5 ) .
I believe your final line for f ( 2 0 1 7 ) should read
f ( 2 0 1 7 ) ≡ ( − 1 ) 5 0 2 ⋅ 2 2 ⋅ 6 ⋅ 1 ⋅ 1 6 ⋅ 6 ( m o d 2 5 ) ≡ 2 2 ( m o d 2 5 ) .
Log in to reply
Yeah, you're right. Thanks for pointing that out!
How did you get that f(2017)=2017!/5^502(mod 25)=(1 2 3 4) 1 (1 2 3 4) 1 (1 2 3 4)...403 (16*17) (mod 25)?Please explain this.
Log in to reply
Like I showed in the solution, ( 5 k + 1 ) ⋅ ( 5 k + 2 ) ⋅ ( 5 k + 3 ) ⋅ ( 5 k + 4 ) = 2 5 0 k + 2 4 = − 1 ( m o d 2 5 ) regardless of k . This means that every 4 consecutive numbers not divisible by 5 (for example, 31,32,33,34) make a contribution of − 1 to the product ( m o d 2 5 ) , so the total contribution from these numbers, namely (1,2,3,4),(6,7,8,9),...(2011,2012,2013,2014), is equal to − 1 4 0 3 . The 1 6 ⋅ 1 7 is simply 2016 and 2017's contributions. 4 0 3 ! is just 5,10,15...2015's contributions, when we divide each of them by one of the 502 5's in the denominator. This leaves 5 0 2 − 4 0 3 = 9 9 5's in the denominator. So in total we have f ( 2 0 1 7 ) = ( − 1 ) 4 0 3 ⋅ 2 2 ⋅ 5 9 9 4 0 3 ! = − 1 4 0 3 ⋅ 2 2 ⋅ f ( 4 0 3 ) .
Log in to reply
In the sixth line of your solution,you wrote f(2017)=2017!/5^502 (mod 25) which means you are considering modulo 25 not 5.But you again wrote that 2017!/5^502 (mod 25) =(1 * 2 * 3 * 4) * (1 * 2 * 3 * 4) * ..... * (1 * 2 * 3 * 4) * 403 * (16 * 17)/5^99 and this time you are considering modulo 5 as 1,2,3,4,6,7 are congruent to 1,2,3,4,1 and 2 respectively.I totally can't understand your sixth and the following lines.Would you please give me a full(much detailed) details of these lines as I am unskilled in this sector.Thanks in advance.
Log in to reply
@Akash Hossain – Whether I write 1 ⋅ 2 ⋅ 3 ⋅ 4 ( m o d 2 5 ) or 6 ⋅ 7 ⋅ 8 ⋅ 9 ( m o d 2 5 ) or − 1 ( m o d 2 5 ) doesn't matter. If you prefer to think of it that way, the sixth line you're stuck on can be reformulated as follows:
f ( 2 0 1 7 ) = 5 5 0 2 2 0 1 7 ! ( m o d 2 5 ) = 5 9 9 ( − 1 ) ⋅ 1 ⋅ ( − 1 ) ⋅ 2 ⋅ ( − 1 ) ⋯ ( − 1 ) ⋅ 4 0 3 ⋅ 1 6 ⋅ 1 7 ( m o d 2 5 ) .
Note that I can't convert 1 6 ⋅ 1 7 ( m o d 2 5 ) into 1 ⋅ 2 ( m o d 2 5 ) because they aren't congruent, as you can check: 1 6 ⋅ 1 7 = 2 2 ( m o d 2 5 ) and 1 ⋅ 2 = 2 ( m o d 2 5 ) . I can only replace groups of 4 consecutive numbers, because they are always congruent to − 1 ( m o d 2 5 ) .
If you're still confused, just consider the following:
1 ⋅ 2 ⋅ 3 ⋅ 4 = 2 4 = ( − 1 ) ( m o d 2 5 )
6 ⋅ 7 ⋅ 8 ⋅ 9 = 3 0 2 4 = ( − 1 ) ( m o d 2 5 )
1 1 ⋅ 1 2 ⋅ 1 3 ⋅ 1 4 = 2 4 0 2 4 = ( − 1 ) ( m o d 2 5 )
1 6 ⋅ 1 7 ⋅ 1 8 ⋅ 1 9 = 9 3 0 2 4 = ( − 1 ) ( m o d 2 5 )
2 1 ⋅ 2 2 ⋅ 2 3 ⋅ 2 4 = 2 5 5 0 2 4 = ( − 1 ) ( m o d 2 5 )
So any 4 consecutive numbers not divisible by 5 will make a contribution of − 1 ( m o d 2 5 ) to the product, as we meant to show.
Oh I got it ! Indeed this was a great solution.
5^k should be largest power of 5 dividing x!
By the Extended Euclidean Algorithm, the expression=18(mod 25)..... Could someone explain how was it calculated?
Log in to reply
Let’s review what we had found up until that point:
5 5 0 2 2 0 1 7 ! ≡ 2 2 ( m o d 2 5 )
2 5 0 2 ≡ 4 ( m o d 2 5 )
We’re trying to find x : = 5 5 0 2 ⋅ 2 5 0 2 2 0 1 7 ! ( m o d 2 5 ) . Note, using the above, that this comes down to solving 4 x ≡ 2 2 ( m o d 2 5 ) . There’s a couple of ways to proceed, but perhaps the most straightforward is to simply find the inverse of 4 ( m o d 2 5 ) . (We know this exists since gcd ( 4 , 2 5 ) = 1 ).
Usually we do this type of problem using the Extended Euclidean Algorithm (which you can look up to see in use) but in this particular case it isn’t terribly difficult to spot 4 ⋅ 1 9 = 7 6 ≡ 1 ( m o d 2 5 ) , so the inverse of 4 is 1 9 .
So 4 x ≡ 2 2 ( m o d 2 5 ) ⟺ 1 9 ⋅ 4 x ≡ 1 9 ⋅ 2 2 ( m o d 2 5 ) ⟺ x ≡ 4 1 8 ( m o d 2 5 ) , and the result follows.
What does 2^phi(25) mean?
Log in to reply
I first thought phi(25) meant that it was a multiple of 25 so I tried 2^25 and saw that after mod 25, the result was 7. Is phi(25) a function?
Log in to reply
φ ( n ) is standard notation for Euler’s totient function, which in a nutshell counts the number of integers in [ 1 , n ] that are coprime to n .
In particular, φ ( 2 5 ) = 2 0 .
The way I use it is an application of Euler-Fermat’s theorem, which you can look up.
another brute-force calculation (C):
void CalcReste()
{
unsigned int r = 1;
for (int i = 1; i <= 2017; i++)
{
r = (r * i);
while (r % 10 == 0)
r /= 10;
r = r % 1000000;
}
printf("\r\nresult=%d", r % 100);
}
Less brute force than merely doing a factorial.
Log in to reply
I did something even a little more complicated, separating different cases so I only had to do r % 1000.
Oddly enough, this is exactly what I did in JavaScript. Same for loop set up. While in the middle. The % 1000000. Even writing r = r * i instead of r *= i, and r /= 10 instead of r = r / 10. Which is weird, as we both had the exact same inconsistency in our code, and the % 1000000 could have had any other count of 0s. What are the odds?
I was worried about the length and complexity of a straightforward factorial solution — some of the comments on that solution seem to express the same concerns— and since you only need the last two non-zero digits, I did something that would keep the numbers fairly small and the computations reasonably simple. I culdn't seem to get my ruby program to format properly, so I rewrote in python (which I've never used before):
1 2 3 4 5 6 7 8 9 |
|
=> 368
No need to optimize with nowadays computers. Simply type in python console:
And you get the answer quite immediately.Log in to reply
If you want to optimize further, you can use the pow method, which can very quickly compute reminders of big exponentials using modular exponentiation. You just have to compute prime numbers until 2017, and then how many times each prime is in 2017! (and that's easy).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|
2 0 1 7 ! = 4 6 9 1 2 3 8 6 0 6 4 9 6 8 3 5 1 5 4 1 2 3 3 3 4 7 6 3 1 1 2 3 3 9 3 4 9 3 9 3 7 8 2 8 6 0 5 7 7 1 3 2 2 8 1 0 6 6 5 7 7 7 1 3 9 8 0 5 1 2 5 1 6 0 1 2 5 9 5 8 7 2 7 3 6 6 6 2 9 3 7 4 8 6 9 7 5 6 1 5 7 1 9 0 6 8 1 1 8 5 7 4 1 9 0 0 5 5 0 3 9 6 8 4 4 9 8 6 7 5 0 1 6 3 3 5 0 0 3 4 8 6 1 6 2 0 8 4 2 6 0 8 1 4 7 6 1 9 3 6 1 3 7 6 3 9 0 4 7 1 4 7 2 7 1 5 2 7 7 8 4 8 5 3 7 7 9 1 6 8 8 1 1 3 4 4 4 4 0 4 1 1 5 0 2 2 7 5 0 2 7 9 3 9 4 1 5 9 9 1 0 5 0 2 8 4 1 5 7 9 6 0 5 1 4 3 9 1 0 5 0 4 2 9 4 7 5 0 9 8 8 2 7 7 7 1 2 3 7 8 6 0 9 0 7 7 8 2 2 7 0 9 8 9 0 3 7 4 3 1 2 8 6 7 7 0 0 0 1 2 8 9 5 1 6 6 1 0 3 8 3 6 6 8 8 8 3 7 5 1 6 4 6 2 8 9 4 1 2 3 3 0 7 4 6 9 5 6 8 1 5 0 7 8 0 4 2 6 0 8 7 7 7 1 1 8 2 2 2 4 1 7 2 5 9 0 1 2 1 5 3 9 8 0 8 6 8 0 5 9 1 8 9 8 9 5 3 2 2 1 0 4 0 4 9 9 2 0 4 3 5 2 0 4 4 9 9 4 2 8 3 6 3 7 8 2 0 0 8 8 5 7 6 4 6 8 4 4 7 9 4 3 3 1 4 7 7 4 4 6 5 5 2 7 0 0 3 6 3 9 0 5 7 0 2 4 4 7 9 3 1 0 4 9 9 3 5 5 2 6 9 9 0 3 2 8 9 9 4 4 9 0 6 9 4 8 3 4 1 2 6 1 8 0 9 4 8 9 7 0 0 2 3 1 9 9 1 7 2 8 1 0 0 6 7 3 9 5 0 4 6 3 8 7 7 9 3 4 4 3 7 1 2 1 8 2 3 9 1 2 2 9 2 1 9 1 4 1 6 8 7 5 0 9 1 9 0 1 6 9 9 9 7 1 6 5 9 9 9 1 0 5 2 8 8 2 3 4 4 4 4 6 7 0 3 8 0 1 2 0 6 1 7 8 4 5 8 7 9 5 9 3 0 1 5 2 8 4 5 0 8 1 8 2 5 8 4 8 4 8 7 7 6 6 8 4 2 7 9 1 9 2 2 5 4 6 0 3 4 8 1 3 0 4 6 0 0 7 6 1 2 1 6 8 1 4 3 5 9 0 6 7 8 3 4 7 0 0 0 3 8 8 9 6 1 2 1 0 9 4 9 7 7 1 1 2 9 2 3 4 1 0 9 6 2 1 6 1 4 1 8 7 6 0 3 0 9 2 0 7 3 0 4 6 1 5 7 3 3 0 3 3 3 2 6 7 2 7 6 8 9 1 5 8 3 4 9 1 9 6 4 6 7 7 5 7 1 7 4 8 9 3 8 5 9 7 6 6 8 0 1 7 1 5 0 3 8 0 8 4 3 7 5 4 0 6 7 8 6 7 7 7 2 0 1 8 4 8 4 7 7 3 8 1 1 8 2 1 2 9 9 2 8 1 1 6 8 8 0 4 6 8 1 5 3 5 5 6 3 8 0 0 2 9 5 7 1 5 9 4 9 2 0 0 6 3 4 4 8 6 1 6 6 1 2 2 7 0 6 8 9 1 1 5 4 6 5 5 5 6 6 0 3 8 0 7 2 9 6 9 7 7 3 5 0 9 0 4 5 6 3 1 7 1 5 9 8 0 6 4 1 2 4 6 4 0 2 4 0 7 9 5 2 8 1 6 5 7 8 0 0 7 1 5 1 9 7 5 6 2 8 0 9 1 5 4 6 1 1 2 6 7 1 4 3 6 2 7 9 9 3 8 9 8 7 2 9 0 9 0 3 4 0 6 2 5 4 9 3 4 6 3 4 7 1 6 6 3 7 4 5 4 6 4 9 8 5 7 2 1 4 0 4 8 4 6 2 1 4 4 7 9 3 6 4 8 7 3 4 5 5 3 8 4 1 2 9 7 5 5 8 0 1 2 3 0 7 2 8 7 0 7 8 1 0 5 6 5 8 0 8 6 4 7 0 3 3 1 8 4 5 1 8 9 9 5 7 7 2 1 4 4 5 8 6 0 7 7 1 4 1 2 8 6 7 8 6 1 7 7 9 4 9 2 2 6 3 8 9 4 1 2 9 4 5 3 7 2 4 1 3 5 4 0 3 9 2 1 5 1 7 0 1 2 9 3 2 8 1 2 5 0 8 3 8 9 5 8 7 5 6 2 0 4 1 6 3 1 5 3 8 3 7 4 4 3 9 6 4 4 5 3 6 0 0 4 8 6 7 2 0 5 2 5 2 2 1 8 2 5 6 9 9 0 8 8 1 4 3 2 0 4 2 0 8 1 1 8 1 5 9 3 8 2 3 3 7 3 2 5 6 2 2 2 8 3 4 7 4 9 0 1 3 4 9 7 4 9 9 8 9 0 5 6 0 1 5 0 9 6 8 9 8 1 0 3 2 2 3 3 3 5 1 8 6 0 3 8 8 2 7 3 8 0 4 7 0 4 6 5 8 5 5 3 7 0 4 5 8 5 9 8 5 1 0 1 4 0 8 5 7 9 4 5 1 9 3 7 6 0 5 5 3 7 6 5 5 6 6 9 1 6 2 1 6 7 0 9 2 1 5 1 0 6 7 7 5 4 4 3 8 6 6 2 7 5 5 9 5 4 3 5 1 1 6 5 7 6 3 4 1 6 1 1 3 5 3 9 8 0 2 2 1 2 9 1 1 2 5 6 0 8 3 2 4 0 4 3 4 1 5 3 8 1 0 0 4 6 6 8 5 5 3 1 9 0 6 1 5 4 3 7 1 5 7 1 5 3 1 4 4 8 2 1 4 3 1 4 8 0 3 7 0 3 1 0 5 4 3 0 4 2 7 8 3 5 6 9 0 5 0 5 5 2 7 3 7 0 4 3 1 1 6 0 0 4 9 9 4 9 5 4 2 7 2 7 7 5 3 6 8 4 7 0 7 6 4 3 5 3 3 7 0 8 0 3 6 5 2 7 7 0 7 3 2 7 7 5 5 2 6 7 7 8 4 9 6 8 3 9 8 0 2 5 4 9 9 8 6 4 2 4 9 5 4 3 1 8 8 4 7 8 8 3 1 2 0 6 6 0 8 4 2 6 8 0 6 0 3 2 9 9 8 6 9 5 5 9 7 3 8 0 1 1 0 2 9 5 6 3 0 5 9 2 3 0 6 5 6 2 0 3 7 4 9 7 5 8 2 2 2 7 1 0 3 8 7 9 5 0 1 0 0 1 3 4 8 9 1 5 5 9 9 4 9 9 5 8 7 2 3 7 1 6 2 7 5 8 9 0 6 4 0 2 2 8 7 0 8 1 5 1 0 8 5 3 5 7 2 4 4 3 9 7 6 6 5 9 6 2 0 2 2 8 3 4 8 7 6 7 8 0 1 4 6 1 0 0 5 6 0 5 1 2 5 0 4 9 8 8 9 9 8 8 3 6 7 4 2 3 4 8 6 2 3 0 6 9 3 7 1 0 3 0 8 9 8 9 3 8 5 2 5 1 7 7 6 1 7 8 6 5 0 0 1 7 4 2 6 8 7 9 8 1 6 0 0 6 3 1 5 8 6 9 5 9 4 0 7 1 3 8 9 6 5 6 9 5 3 2 3 6 3 2 6 2 7 5 8 2 2 2 3 3 2 7 7 3 4 3 1 2 9 8 2 7 4 9 2 3 5 8 5 9 0 0 4 7 4 9 8 5 9 8 2 0 7 3 5 6 8 5 8 9 9 5 9 4 6 6 8 4 3 1 5 3 7 6 4 4 8 0 0 5 4 1 5 1 4 3 6 8 0 4 0 3 4 4 1 7 6 1 7 6 8 7 1 2 7 0 0 8 6 8 8 1 6 9 8 5 8 4 1 6 5 8 5 0 8 7 4 7 1 8 7 3 6 5 6 4 6 1 4 9 8 2 7 2 7 9 4 1 4 2 3 5 5 2 9 9 7 9 3 6 3 4 2 2 6 1 5 5 4 4 3 9 0 9 3 4 7 3 0 5 6 5 9 8 7 6 4 0 4 4 4 5 5 2 9 1 3 6 1 4 4 6 8 5 3 5 3 6 0 7 1 8 7 9 5 0 2 0 8 0 8 6 5 5 1 7 1 2 9 2 5 1 0 7 7 3 4 4 5 1 9 4 3 7 5 5 3 7 0 9 0 6 2 7 4 0 3 5 4 4 6 2 8 4 9 6 3 4 5 7 9 0 3 1 0 7 4 0 9 7 0 3 0 0 9 0 4 1 5 9 5 5 1 3 0 3 5 7 9 2 3 0 5 8 5 0 1 8 7 5 3 7 2 5 8 2 6 2 2 8 8 4 0 2 1 6 9 8 6 7 0 6 5 6 0 4 1 4 3 6 2 6 1 7 3 2 9 6 6 4 5 2 3 6 6 0 6 4 6 4 4 9 9 3 9 7 6 8 8 0 0 3 7 9 0 2 1 8 7 7 0 4 1 5 8 6 0 1 1 4 0 5 3 7 6 3 0 6 1 8 2 4 8 7 7 0 9 4 4 1 9 9 8 6 6 3 7 6 3 5 6 3 1 8 2 1 3 9 3 4 1 8 7 1 4 0 9 3 7 9 4 4 7 2 3 7 6 7 1 3 7 6 4 3 7 0 0 6 5 4 5 2 8 4 5 9 1 9 5 1 9 5 8 7 0 4 1 0 0 9 2 6 4 9 9 0 4 5 0 0 9 5 0 1 5 0 7 4 1 7 8 0 5 9 7 4 4 1 1 8 6 3 5 6 1 9 3 3 7 7 7 8 6 5 1 7 1 6 7 5 5 0 8 9 1 5 6 5 2 1 5 0 1 4 9 0 4 2 3 7 6 1 3 3 7 2 8 8 7 1 9 6 4 6 1 7 3 8 1 1 2 0 4 3 7 8 6 9 0 9 5 9 7 4 6 4 1 8 8 0 1 4 5 1 8 6 7 1 6 1 5 4 1 3 3 6 9 4 1 6 9 9 3 1 5 5 9 2 3 5 4 8 6 1 9 5 9 6 2 0 0 2 4 4 4 1 5 1 8 5 2 3 5 0 2 7 7 8 0 2 5 6 8 2 7 5 0 4 9 2 1 4 6 3 6 8 6 3 7 5 2 6 3 9 2 7 1 4 6 8 3 2 0 1 3 7 3 9 7 3 3 4 1 5 7 9 0 6 3 5 8 4 1 0 1 2 3 5 9 9 0 4 2 0 7 0 5 2 1 8 3 0 2 5 5 8 7 4 4 3 4 8 4 6 6 5 0 2 5 8 4 5 7 3 3 3 6 6 3 1 8 1 2 9 9 4 1 8 7 0 3 4 6 4 0 1 1 8 9 4 0 6 2 8 8 5 2 8 2 5 6 9 9 0 0 1 0 4 4 8 4 1 7 2 6 2 6 8 7 7 5 3 6 8 9 4 6 1 1 8 4 1 3 5 8 8 4 8 7 3 5 9 6 6 5 5 5 1 9 3 5 2 2 1 2 1 3 8 1 5 2 4 9 6 3 8 1 2 6 1 0 1 4 3 2 9 3 9 1 0 9 7 0 9 0 5 8 1 4 3 0 5 0 8 9 6 2 4 6 1 1 0 0 4 7 5 2 8 3 3 5 0 1 0 5 2 2 9 9 4 8 7 1 3 3 9 0 8 2 5 4 5 5 4 8 7 8 2 7 9 7 3 6 6 7 9 7 1 9 8 5 2 9 1 4 6 5 4 1 7 9 0 5 4 8 6 2 1 5 1 7 2 8 7 0 4 2 2 3 0 1 9 5 8 0 3 8 6 7 0 2 1 8 2 7 1 0 9 3 8 8 9 9 1 1 4 0 4 3 1 1 3 4 0 2 3 8 2 4 1 6 0 9 3 8 4 3 4 3 4 7 1 6 0 2 9 2 9 0 5 7 8 2 8 9 7 4 2 1 2 0 4 2 2 4 4 9 8 5 3 6 3 2 0 8 1 3 9 3 5 8 5 3 3 5 3 2 3 3 7 5 5 9 6 2 0 9 9 8 9 2 7 6 9 3 0 5 5 8 0 4 7 0 0 3 1 0 0 3 8 7 7 2 6 2 4 4 4 6 2 2 2 6 1 8 2 1 9 9 8 5 9 8 8 9 6 7 4 8 3 5 3 5 7 0 3 3 4 2 9 0 7 7 8 6 8 3 0 5 8 6 5 5 0 4 1 2 4 5 1 3 3 7 3 9 0 7 1 0 3 3 4 2 3 8 8 8 0 5 2 6 9 2 2 8 2 5 9 3 7 6 6 2 3 6 0 0 8 5 9 1 0 3 6 7 6 3 1 7 3 3 1 3 0 1 7 2 0 4 8 8 4 2 0 7 3 0 9 7 3 4 5 6 8 0 7 3 2 9 4 5 9 0 2 7 9 2 7 9 3 3 3 2 6 0 2 8 2 9 8 3 1 8 4 5 8 8 1 3 4 2 6 0 7 0 7 8 8 3 7 7 7 0 6 9 5 4 7 1 8 4 7 4 7 4 0 2 8 6 4 5 5 7 0 6 3 4 5 1 3 0 9 0 9 7 2 7 3 9 7 1 7 9 7 9 8 2 1 2 8 7 9 3 7 9 1 5 2 0 9 5 9 3 7 5 5 8 5 0 5 5 9 3 9 0 2 3 9 8 0 3 3 7 7 9 9 4 6 1 5 2 5 1 3 2 7 2 2 7 1 7 4 3 2 7 7 5 5 3 8 2 4 9 0 2 4 9 1 1 1 6 2 0 2 1 7 6 8 2 1 7 3 8 7 8 1 6 2 1 6 2 3 6 8 7 9 7 1 7 5 3 3 7 6 1 3 7 4 5 3 6 9 4 0 8 6 5 8 5 9 3 6 3 5 0 3 5 4 7 3 7 2 1 5 4 5 3 9 4 2 0 9 7 8 8 8 4 2 8 2 0 9 5 0 9 3 3 7 3 0 4 0 6 0 8 3 0 1 2 6 7 4 9 9 4 7 7 6 1 2 1 9 8 9 1 3 3 1 5 6 7 3 3 8 2 7 4 0 4 7 4 4 7 2 6 7 4 8 0 4 4 9 8 5 1 9 8 9 0 6 3 1 8 4 2 7 5 3 1 9 2 7 5 8 8 5 3 6 8 4 3 7 2 7 8 9 2 9 2 2 9 4 7 3 5 5 1 7 9 6 1 9 6 0 2 1 0 2 6 9 0 7 8 2 2 5 0 1 3 9 1 0 1 5 0 5 9 7 8 5 4 0 2 0 3 4 1 4 0 5 2 1 0 7 3 0 1 0 5 1 7 4 6 8 2 2 9 4 7 8 2 6 3 0 4 8 2 9 7 8 6 6 5 3 3 5 1 6 3 3 6 1 0 6 0 2 5 2 3 3 3 1 2 9 2 5 1 6 1 4 4 5 2 4 3 7 4 9 6 2 2 6 8 6 8 7 5 9 4 6 2 2 6 5 1 8 2 5 2 1 6 8 9 5 0 4 1 1 5 7 0 6 1 5 2 3 5 5 2 9 0 3 9 9 4 8 4 0 3 8 9 2 3 0 9 3 3 3 0 2 1 9 2 7 4 8 4 8 8 2 2 5 6 8 3 3 2 7 7 7 0 7 9 0 6 0 1 0 1 3 1 4 4 8 8 3 7 2 9 5 4 1 8 3 3 9 0 1 5 8 6 5 3 7 5 2 3 4 7 0 8 1 1 6 8 9 0 5 5 3 0 7 4 3 5 0 9 6 8 4 6 0 6 4 3 4 6 9 2 1 4 9 9 3 8 1 5 9 3 5 1 7 3 2 5 5 9 1 0 2 5 3 8 9 9 4 2 8 6 4 7 0 1 9 0 7 2 3 5 9 0 9 3 2 5 7 3 4 1 2 2 2 5 2 8 9 5 7 4 7 1 2 6 4 3 6 1 4 1 3 8 2 8 8 0 2 4 0 1 1 5 3 0 7 6 4 4 6 0 5 5 5 5 2 5 4 7 9 5 7 2 6 0 5 8 1 7 4 4 3 2 7 3 4 9 4 4 8 8 5 7 4 7 5 1 3 3 6 7 0 9 2 4 1 1 2 0 7 8 4 5 2 8 9 9 2 0 9 9 3 4 8 4 8 4 0 4 1 2 1 6 9 8 3 3 1 1 4 8 5 9 1 7 2 4 8 1 6 7 5 3 8 2 7 3 9 5 8 5 6 3 3 0 6 0 0 7 5 5 0 5 3 9 8 4 1 6 8 2 4 8 2 6 6 3 7 8 9 9 9 9 2 3 9 3 0 5 2 6 2 4 5 5 0 8 0 3 2 7 7 7 2 6 4 4 0 7 9 3 0 4 1 3 8 6 6 0 8 4 5 6 9 5 3 8 1 8 5 1 8 4 4 1 4 0 2 4 9 6 6 2 6 8 5 9 4 3 0 7 4 5 0 9 7 8 0 1 6 2 4 7 7 0 6 0 1 4 5 8 3 1 0 2 5 7 5 7 7 9 3 0 9 5 5 1 8 9 0 8 0 9 3 0 8 5 2 9 6 1 3 2 5 3 8 7 1 6 5 0 5 5 6 7 0 6 3 6 1 7 2 0 2 2 0 9 2 0 5 6 6 8 0 2 8 6 7 7 7 7 4 4 1 2 8 4 4 9 8 8 0 5 0 5 1 7 2 5 5 0 0 3 8 9 2 0 7 2 3 7 0 2 0 5 5 6 8 6 5 3 3 4 8 9 7 1 4 7 1 3 3 2 1 7 9 8 3 5 0 2 4 9 9 3 9 9 6 5 6 0 1 4 3 6 8 9 5 5 1 3 6 7 4 9 4 4 9 5 2 1 6 8 2 4 1 0 8 2 5 7 5 4 9 5 8 1 1 3 6 7 5 1 5 5 9 5 0 9 6 3 3 0 4 3 2 2 7 1 0 4 6 3 5 3 8 9 5 2 0 5 4 1 1 8 0 4 1 9 9 3 5 0 7 5 9 5 5 2 4 3 0 5 7 2 8 0 7 4 9 1 0 5 3 7 8 0 3 1 7 1 7 5 9 6 2 7 8 9 7 3 2 1 7 6 7 5 2 8 9 0 4 2 2 2 4 9 3 8 1 2 6 1 7 4 7 4 7 1 5 5 8 7 6 5 3 6 2 9 7 9 5 1 8 5 7 6 8 5 8 0 3 8 2 8 6 3 8 1 5 0 0 6 9 1 7 9 7 6 3 7 8 8 0 8 6 2 5 8 7 4 7 9 6 4 1 9 4 3 3 4 5 0 6 2 0 8 9 7 2 6 2 7 8 0 5 1 1 4 8 0 6 6 7 0 7 2 6 1 5 6 8 2 8 9 3 7 5 7 2 4 6 3 6 1 6 5 3 1 6 9 6 3 7 5 4 3 8 4 1 4 3 4 7 2 3 6 2 4 4 0 0 9 1 4 9 8 9 2 8 6 4 7 7 3 5 5 6 9 9 8 2 3 9 3 8 1 4 6 0 7 1 4 2 5 0 7 8 3 6 4 8 9 7 9 9 1 1 3 7 8 3 8 9 2 0 9 2 0 6 3 0 0 8 6 5 1 2 1 3 9 5 0 3 1 3 8 3 2 9 7 2 4 4 3 5 8 0 3 5 9 3 4 0 4 1 4 1 9 3 6 3 7 4 6 1 4 7 8 0 1 5 0 7 7 5 4 8 4 2 6 7 3 5 7 4 2 6 6 8 6 1 1 2 3 9 1 9 8 7 4 0 5 8 5 1 8 8 9 3 7 1 3 3 4 5 0 9 8 2 5 0 6 9 2 6 8 4 2 1 2 6 3 4 6 7 9 3 9 6 5 2 3 4 1 9 9 3 8 8 2 8 3 5 2 8 9 6 1 0 7 8 0 1 5 1 7 3 3 3 0 8 4 6 5 0 2 6 8 4 7 3 4 3 0 2 4 0 8 5 9 3 4 1 0 6 3 1 9 0 9 1 6 4 7 2 7 9 9 8 0 9 8 9 1 7 9 8 6 9 8 0 9 2 1 4 3 1 2 1 1 1 0 7 8 2 6 5 0 0 7 0 8 8 6 2 5 5 2 6 4 4 1 4 1 5 2 4 2 3 9 6 6 7 1 4 5 5 7 7 0 7 1 3 7 8 1 7 3 7 5 2 7 7 1 3 4 7 1 9 3 4 6 4 0 0 9 7 7 0 5 3 1 8 3 0 9 9 9 8 1 4 1 5 2 1 9 9 4 8 8 5 7 5 7 1 4 1 8 5 9 2 8 4 1 8 7 2 0 3 6 0 0 7 9 7 9 2 8 0 1 7 6 1 7 5 7 0 0 6 7 5 7 0 9 7 4 9 0 2 4 2 9 2 3 0 2 0 7 7 0 5 5 6 7 1 7 8 1 8 0 1 3 9 0 9 1 5 6 0 7 1 8 8 5 7 2 3 3 1 9 4 0 7 6 4 8 7 7 6 9 2 0 5 2 0 0 1 0 5 6 5 9 3 9 8 9 2 2 4 8 8 1 3 2 7 5 1 0 5 8 5 6 4 9 9 0 4 6 1 5 0 1 4 3 1 4 7 6 6 5 0 5 2 1 6 4 4 7 8 6 4 8 1 8 7 4 4 7 7 2 1 3 7 9 1 7 0 7 4 6 6 4 7 9 2 9 9 3 6 3 2 9 1 4 5 4 3 5 2 2 2 5 9 4 1 0 6 6 6 6 6 4 9 5 5 2 2 7 5 3 3 1 0 7 0 2 4 0 4 3 9 6 7 3 0 7 4 1 6 7 0 9 9 9 8 0 1 2 2 6 4 4 6 3 7 6 4 0 2 8 4 4 1 7 1 0 0 7 7 4 2 4 8 4 4 5 1 8 2 8 5 3 3 7 4 7 3 3 1 9 7 9 3 3 1 4 6 7 9 3 4 6 8 9 8 3 5 0 8 6 3 4 7 2 1 6 7 3 9 7 2 1 4 6 8 5 1 2 9 7 1 3 9 8 6 1 6 7 8 8 6 1 0 7 7 7 6 8 4 8 1 2 5 3 6 6 9 5 4 4 2 2 1 5 3 8 7 6 4 8 7 4 0 9 9 0 0 3 1 6 6 6 9 6 2 8 6 9 2 8 1 6 4 6 9 9 6 1 0 3 4 8 0 6 5 8 8 8 4 5 9 8 9 1 2 4 1 6 5 8 7 7 2 1 2 3 4 3 0 2 3 8 5 0 0 4 8 5 8 9 7 3 9 7 4 6 8 4 8 9 8 7 7 8 7 2 6 8 9 9 2 1 7 6 7 4 0 3 5 7 3 2 6 7 5 0 3 7 6 5 1 4 8 3 7 7 4 6 6 3 2 7 4 5 4 1 9 6 8 6 1 3 1 4 2 7 3 9 6 9 1 1 3 8 0 5 0 2 0 2 4 3 3 4 3 0 2 5 5 9 5 0 4 2 8 7 5 5 3 6 9 1 3 0 1 2 0 7 8 6 9 3 8 6 9 6 5 3 1 2 5 0 3 9 0 7 5 8 7 7 6 5 1 4 5 3 9 6 2 9 3 9 2 5 7 7 2 1 3 8 6 3 1 8 5 5 6 4 3 9 9 8 9 9 7 1 4 8 0 6 7 5 1 6 9 7 9 9 1 0 3 3 1 5 9 6 8 × 1 0 5 7 9 1
Are You Stirred up? You are asked to give a more mathematical solution than this... NOTED!
By the Extended Euclidean Algorithm, the expression=18(mod 25)..... Could someone explain how was it calculated?
Problem Loading...
Note Loading...
Set Loading...
Since there are fewer powers of 5 than of 2 in n ! for each n > 1 , the number of zeroes at the end of n ! is ⌊ 5 n ⌋ + ⌊ 2 5 n ⌋ + ⌊ 1 2 5 n ⌋ + . . . . For n = 2 0 1 7 this gives 5 0 2 zeroes.
We then need to find 2 5 0 2 ⋅ 5 5 0 2 2 0 1 7 ! ( m o d 1 0 0 ) . We do this by finding the expression’s value ( m o d 4 ) and ( m o d 2 5 ) and applying the Chinese Remainder Theorem on the results.
Note 2 5 0 2 ⋅ 5 5 0 2 2 0 1 7 ! ( m o d 4 ) is obviously 0 [ 1 ] , since we have a lot more powers of 2 in the numerator.
For convenience, let f ( x ) be 5 k x ! ( m o d 2 5 ) , where 5 k is the largest power of 5 dividing x ! , found by the formula above.
Noting that ( 5 k + 1 ) ⋅ ( 5 k + 2 ) ⋅ ( 5 k + 3 ) ⋅ ( 5 k + 4 ) = 2 5 0 k + 2 4 ( m o d 2 5 ) = − 1 ( m o d 2 5 ) , we have:
f ( 2 0 1 7 ) = 5 5 0 2 2 0 1 7 ! ( m o d 2 5 ) = 5 9 9 ( 1 ⋅ 2 ⋅ 3 ⋅ 4 ) ⋅ 1 ⋅ ( 6 ⋅ 7 ⋅ 8 ⋅ 9 ) ⋅ 2 ⋅ . . . ⋅ ( 2 0 1 1 ⋅ 2 0 1 2 ⋅ 2 0 1 3 ⋅ 2 0 1 4 ) ⋅ 4 0 3 ⋅ ( 2 0 1 6 ⋅ 2 0 1 7 ) ( m o d 2 5 ) = ( − 1 ) 4 0 3 ⋅ 2 2 ⋅ f ( 4 0 3 ) ( m o d 2 5 )
Repeating this gives f ( 2 0 1 7 ) = ( − 1 ) 5 0 2 ⋅ 2 2 ⋅ 6 ⋅ 1 ⋅ 1 6 ⋅ 6 ( m o d 2 5 ) = 2 2 ( m o d 2 5 ) . So, 5 5 0 2 2 0 1 7 ! = 2 2 ( m o d 2 5 ) .
On the other hand, since 2 φ ( 2 5 ) = 1 ( m o d 2 5 ) , we have 2 5 0 2 = 1 2 5 ∗ 4 = 4 ( m o d 2 5 ) . By the Extended Euclidean Algorithm, 2 5 0 2 ⋅ 5 5 0 2 2 0 1 7 ! = 1 8 ( m o d 2 5 ) . [ 2 ]
Using the Chinese Remainder Theorem on [ 1 ] and [ 2 ] , we get 2 5 0 2 ⋅ 5 5 0 2 2 0 1 7 ! = 6 8 ( m o d 1 0 0 ) .