2017 ! 2017!

2017 ! \large 2017!

Find the last two non-zero digits in the number above.


The answer is 68.

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.

4 solutions

Ivo Zerkov
Dec 3, 2017

Since there are fewer powers of 5 5 than of 2 2 in n ! n! for each n > 1 n>1 , the number of zeroes at the end of n ! n! is n 5 + n 25 + n 125 + . . . \large\lfloor \frac{n}{5}\rfloor+\lfloor \frac{n}{25}\rfloor+\lfloor \frac{n}{125}\rfloor+... . For n = 2017 n=2017 this gives 502 502 zeroes.

We then need to find 2017 ! 2 502 5 502 ( m o d 100 ) \large \frac{2017!}{2^{502}\cdot5^{502}} \pmod{100} . We do this by finding the expression’s value ( m o d 4 ) \pmod{4} and ( m o d 25 ) \pmod{25} and applying the Chinese Remainder Theorem on the results.

Note 2017 ! 2 502 5 502 ( m o d 4 ) \large\frac{2017!}{2^{502}\cdot5^{502}} \pmod{4} is obviously 0 0 [ 1 ] \large[1] , since we have a lot more powers of 2 2 in the numerator.

For convenience, let f ( x ) f(x) be x ! 5 k ( m o d 25 ) \large\frac{x!}{5^{k}}\pmod{25} , where 5 k 5^{k} is the largest power of 5 5 dividing x ! x! , found by the formula above.

Noting that ( 5 k + 1 ) ( 5 k + 2 ) ( 5 k + 3 ) ( 5 k + 4 ) = 250 k + 24 ( m o d 25 ) = 1 ( m o d 25 ) (5k+1)\cdot(5k+2)\cdot(5k+3)\cdot(5k+4)=250k+24\pmod{25}=-1\pmod{25} , we have:

f ( 2017 ) = 2017 ! 5 502 ( m o d 25 ) = ( 1 2 3 4 ) 1 ( 6 7 8 9 ) 2 . . . ( 2011 2012 2013 2014 ) 403 ( 2016 2017 ) 5 99 ( m o d 25 ) = ( 1 ) 403 22 f ( 403 ) ( m o d 25 ) f(2017)=\frac{2017!}{5^{502}}\pmod{25}=\frac{(1\cdot2\cdot3\cdot4)\cdot1\cdot(6\cdot7\cdot8\cdot9)\cdot2\cdot...\cdot(2011\cdot2012\cdot2013\cdot2014)\cdot403\cdot(2016\cdot2017)}{5^{99}}\pmod{25}=(-1)^{403}\cdot22\cdot f(403)\pmod{25}

Repeating this gives f ( 2017 ) = ( 1 ) 502 22 6 1 16 6 ( m o d 25 ) = 22 ( m o d 25 ) \large f(2017)=(-1)^{502}\cdot22\cdot6\cdot1\cdot16\cdot6\pmod{25}=22\pmod{25} . So, 2017 ! 5 502 = 22 ( m o d 25 ) \large \frac{2017!}{5^{502}}=22\pmod{25} .

On the other hand, since 2 φ ( 25 ) = 1 ( m o d 25 ) \large2^{\varphi(25)}=1\pmod{25} , we have 2 502 = 1 25 4 = 4 ( m o d 25 ) \large2^{502}=1^{25}*4=4\pmod{25} . By the Extended Euclidean Algorithm, 2017 ! 2 502 5 502 = 18 ( m o d 25 ) \frac{2017!}{2^{502}\cdot5^{502}}=18\pmod{25} . [ 2 ] \large[2]

Using the Chinese Remainder Theorem on [ 1 ] \large [1] and [ 2 ] \large [2] , we get 2017 ! 2 502 5 502 = 68 ( m o d 100 ) \large \frac{2017!}{2^{502}\cdot5^{502}} = 68\pmod{100} .

Nice solution! I used a very similar method, though I went straight ( m o d 100 ) \pmod{100} , 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 ( 2017 ) f(2017) , the last two factors are ( 1 2 ) (1\cdot2) , which you then equate to 2 ( m o d 25 ) 2\pmod {25} , which I don't think is quite true. After all, ( 5 k + 1 ) ( 5 k + 2 ) 15 k + 2 ( m o d 25 ) (5k+1)\cdot(5k+2)\equiv15k + 2\pmod {25} , so the residues could be any of 2, 7, 12, 17 or 22. In fact, in this particular case, the actual values are 2016 2017 22 ( m o d 25 ) 2016\cdot 2017\equiv 22\pmod {25} .

I believe your final line for f ( 2017 ) f(2017) should read

f ( 2017 ) ( 1 ) 502 22 6 1 16 6 ( m o d 25 ) 22 ( m o d 25 ) f(2017)\equiv(-1)^{502}\cdot22\cdot6\cdot1\cdot16\cdot6\pmod{25}\equiv 22\pmod{25} .

zico quintina - 3 years, 6 months ago

Log in to reply

Yeah, you're right. Thanks for pointing that out!

Ivo Zerkov - 3 years, 5 months ago

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.

Akash Hossain - 3 years, 3 months ago

Log in to reply

Like I showed in the solution, ( 5 k + 1 ) ( 5 k + 2 ) ( 5 k + 3 ) ( 5 k + 4 ) = 250 k + 24 = 1 ( m o d 25 ) (5k+1)\cdot(5k+2)\cdot(5k+3)\cdot(5k+4)=250k+24=-1\pmod{25} regardless of k k . This means that every 4 consecutive numbers not divisible by 5 (for example, 31,32,33,34) make a contribution of 1 -1 to the product ( m o d 25 ) \pmod{25} , so the total contribution from these numbers, namely (1,2,3,4),(6,7,8,9),...(2011,2012,2013,2014), is equal to 1 403 -1^{403} . The 16 17 16\cdot17 is simply 2016 and 2017's contributions. 403 ! 403! 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 502 403 = 99 502-403=99 5's in the denominator. So in total we have f ( 2017 ) = ( 1 ) 403 22 403 ! 5 99 = 1 403 22 f ( 403 ) \displaystyle f(2017)=(-1)^{403}\cdot22\cdot\frac{403!}{5^{99}}=-1^{403}\cdot22\cdot f(403) .

Ivo Zerkov - 3 years, 3 months ago

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.

Akash Hossain - 3 years, 3 months ago

Log in to reply

@Akash Hossain Whether I write 1 2 3 4 ( m o d 25 ) 1\cdot2\cdot3\cdot4\pmod{25} or 6 7 8 9 ( m o d 25 ) 6\cdot7\cdot8\cdot9\pmod{25} or 1 ( m o d 25 ) -1\pmod{25} 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 ( 2017 ) = 2017 ! 5 502 ( m o d 25 ) = ( 1 ) 1 ( 1 ) 2 ( 1 ) ( 1 ) 403 16 17 5 99 ( m o d 25 ) \displaystyle f(2017)=\frac{2017!}{5^{502}}\pmod{25}=\frac{(-1)\cdot1\cdot(-1)\cdot2\cdot(-1)\cdots(-1)\cdot403\cdot16\cdot17}{5^{99}}\pmod{25} .

Note that I can't convert 16 17 ( m o d 25 ) 16\cdot17\pmod{25} into 1 2 ( m o d 25 ) 1\cdot2\pmod{25} because they aren't congruent, as you can check: 16 17 = 22 ( m o d 25 ) 16\cdot17=22\pmod{25} and 1 2 = 2 ( m o d 25 ) 1\cdot2=2\pmod{25} . I can only replace groups of 4 consecutive numbers, because they are always congruent to 1 ( m o d 25 ) -1\pmod{25} .

If you're still confused, just consider the following:

1 2 3 4 = 24 = ( 1 ) ( m o d 25 ) 1\cdot2\cdot3\cdot4=24=(-1)\pmod{25}

6 7 8 9 = 3024 = ( 1 ) ( m o d 25 ) 6\cdot7\cdot8\cdot9=3024=(-1)\pmod{25}

11 12 13 14 = 24024 = ( 1 ) ( m o d 25 ) 11\cdot12\cdot13\cdot14=24024=(-1)\pmod{25}

16 17 18 19 = 93024 = ( 1 ) ( m o d 25 ) 16\cdot17\cdot18\cdot19=93024=(-1)\pmod{25}

21 22 23 24 = 255024 = ( 1 ) ( m o d 25 ) 21\cdot22\cdot23\cdot24=255024=(-1)\pmod{25}

So any 4 consecutive numbers not divisible by 5 will make a contribution of 1 ( m o d 25 ) -1\pmod{25} to the product, as we meant to show.

Ivo Zerkov - 3 years, 3 months ago

Oh I got it ! Indeed this was a great solution.

Akash Hossain - 3 years, 3 months ago

Log in to reply

Glad you liked it!

Ivo Zerkov - 3 years, 3 months ago

5^k should be largest power of 5 dividing x!

Vincent Chen - 1 year, 2 months ago

Log in to reply

Right you are, thanks!

Ivo Zerkov - 1 year, 1 month ago

By the Extended Euclidean Algorithm, the expression=18(mod 25)..... Could someone explain how was it calculated?

Pro raks - 1 year, 1 month ago

Log in to reply

Let’s review what we had found up until that point:

2017 ! 5 502 22 ( m o d 25 ) \large\frac{2017!}{5^{502}}\equiv22\pmod{25}

2 502 4 ( m o d 25 ) 2^{502}\equiv4\pmod{25}

We’re trying to find x : = 2017 ! 5 502 2 502 ( m o d 25 ) x:=\large\frac{2017!}{5^{502}\cdot2^{502}}\pmod{25} . Note, using the above, that this comes down to solving 4 x 22 ( m o d 25 ) . 4x\equiv22\pmod{25}. There’s a couple of ways to proceed, but perhaps the most straightforward is to simply find the inverse of 4 ( m o d 25 ) . 4\pmod{25}. (We know this exists since gcd ( 4 , 25 ) = 1 \text{gcd}(4,25)=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 19 = 76 1 ( m o d 25 ) 4\cdot19=76\equiv1\pmod{25} , so the inverse of 4 4 is 19 19 .

So 4 x 22 ( m o d 25 ) 19 4 x 19 22 ( m o d 25 ) x 418 ( m o d 25 ) 4x\equiv22\pmod{25} \iff 19\cdot4x\equiv19\cdot22\pmod{25}\iff x\equiv418\pmod{25} , and the result follows.

Ivo Zerkov - 1 year, 1 month ago

What does 2^phi(25) mean?

Hunter Bien - 1 year, 1 month ago

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?

Hunter Bien - 1 year, 1 month ago

Log in to reply

φ ( n ) \varphi(n) is standard notation for Euler’s totient function, which in a nutshell counts the number of integers in [ 1 , n ] [1,n] that are coprime to n n .

In particular, φ ( 25 ) = 20 \varphi(25)=20 .

The way I use it is an application of Euler-Fermat’s theorem, which you can look up.

Ivo Zerkov - 1 year, 1 month ago
Michel Gelders
Dec 12, 2017

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.

Nicholas Palevsky - 3 years, 6 months ago

Log in to reply

I did something even a little more complicated, separating different cases so I only had to do r % 1000.

Nicholas Palevsky - 3 years, 6 months ago

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?

Bobby McBobson - 3 years, 5 months ago
Nicholas Palevsky
Dec 11, 2017

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
y = 1
for x in range(1,2017 + 1):
     y *= x
     if x % 5 == 0:
             while y % 10 == 0: y /= 10
     else:
             y = y % 1000

print y

=> 368

No need to optimize with nowadays computers. Simply type in python console: And you get the answer quite immediately.

Laurent Shorts - 3 years, 5 months ago

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
# computes primes to 2017 with your usual method
primes = [2,3,5,7,11, ..., 2011,2017]

def powerOfPrime(p, n):
    """ gives the highest power of p that divides n! """
    tot = 0
    n /= p
    while n > 0:
        tot += n
        n /= p
    return tot

reminder = 1
for p in primes:
    if p == 5:
        continue
    if p == 2:
        power = powerOfPrime(2, 2017) - powerOfPrime(5, 2017)
    else:
        power = powerOfPrime(p, 2017)
    reminder = (reminder * pow(p, power, 100)) % 100

print reminder

Laurent Shorts - 3 years, 5 months ago
Wage Mareto
Dec 28, 2017

2017 ! = 4691238606496835154123334763112339349393782860577132281066577713980512516012595872736662937486975615719068118574190055039684498675016335003486162084260814761936137639047147271527784853779168811344440411502275027939415991050284157960514391050429475098827771237860907782270989037431286770001289516610383668883751646289412330746956815078042608777118222417259012153980868059189895322104049920435204499428363782008857646844794331477446552700363905702447931049935526990328994490694834126180948970023199172810067395046387793443712182391229219141687509190169997165999105288234444670380120617845879593015284508182584848776684279192254603481304600761216814359067834700038896121094977112923410962161418760309207304615733033326727689158349196467757174893859766801715038084375406786777201848477381182129928116880468153556380029571594920063448616612270689115465556603807296977350904563171598064124640240795281657800715197562809154611267143627993898729090340625493463471663745464985721404846214479364873455384129755801230728707810565808647033184518995772144586077141286786177949226389412945372413540392151701293281250838958756204163153837443964453600486720525221825699088143204208118159382337325622283474901349749989056015096898103223335186038827380470465855370458598510140857945193760553765566916216709215106775443866275595435116576341611353980221291125608324043415381004668553190615437157153144821431480370310543042783569050552737043116004994954272775368470764353370803652770732775526778496839802549986424954318847883120660842680603299869559738011029563059230656203749758222710387950100134891559949958723716275890640228708151085357244397665962022834876780146100560512504988998836742348623069371030898938525177617865001742687981600631586959407138965695323632627582223327734312982749235859004749859820735685899594668431537644800541514368040344176176871270086881698584165850874718736564614982727941423552997936342261554439093473056598764044455291361446853536071879502080865517129251077344519437553709062740354462849634579031074097030090415955130357923058501875372582622884021698670656041436261732966452366064644993976880037902187704158601140537630618248770944199866376356318213934187140937944723767137643700654528459195195870410092649904500950150741780597441186356193377786517167550891565215014904237613372887196461738112043786909597464188014518671615413369416993155923548619596200244415185235027780256827504921463686375263927146832013739733415790635841012359904207052183025587443484665025845733366318129941870346401189406288528256990010448417262687753689461184135884873596655519352212138152496381261014329391097090581430508962461100475283350105229948713390825455487827973667971985291465417905486215172870422301958038670218271093889911404311340238241609384343471602929057828974212042244985363208139358533532337559620998927693055804700310038772624446222618219985988967483535703342907786830586550412451337390710334238880526922825937662360085910367631733130172048842073097345680732945902792793332602829831845881342607078837770695471847474028645570634513090972739717979821287937915209593755850559390239803377994615251327227174327755382490249111620217682173878162162368797175337613745369408658593635035473721545394209788842820950933730406083012674994776121989133156733827404744726748044985198906318427531927588536843727892922947355179619602102690782250139101505978540203414052107301051746822947826304829786653351633610602523331292516144524374962268687594622651825216895041157061523552903994840389230933302192748488225683327770790601013144883729541833901586537523470811689055307435096846064346921499381593517325591025389942864701907235909325734122252895747126436141382880240115307644605555254795726058174432734944885747513367092411207845289920993484840412169833114859172481675382739585633060075505398416824826637899992393052624550803277726440793041386608456953818518441402496626859430745097801624770601458310257577930955189080930852961325387165055670636172022092056680286777744128449880505172550038920723702055686533489714713321798350249939965601436895513674944952168241082575495811367515595096330432271046353895205411804199350759552430572807491053780317175962789732176752890422249381261747471558765362979518576858038286381500691797637880862587479641943345062089726278051148066707261568289375724636165316963754384143472362440091498928647735569982393814607142507836489799113783892092063008651213950313832972443580359340414193637461478015077548426735742668611239198740585188937133450982506926842126346793965234199388283528961078015173330846502684734302408593410631909164727998098917986980921431211107826500708862552644141524239667145577071378173752771347193464009770531830999814152199488575714185928418720360079792801761757006757097490242923020770556717818013909156071885723319407648776920520010565939892248813275105856499046150143147665052164478648187447721379170746647929936329145435222594106666649552275331070240439673074167099980122644637640284417100774248445182853374733197933146793468983508634721673972146851297139861678861077768481253669544221538764874099003166696286928164699610348065888459891241658772123430238500485897397468489877872689921767403573267503765148377466327454196861314273969113805020243343025595042875536913012078693869653125039075877651453962939257721386318556439989971480675169799103315968 × 1 0 5791 2017!=4691238606496835154123334763112339349393782860577132281066577713980512516012595872736662937486975615719068118574190055039684498675016335003486162084260814761936137639047147271527784853779168811344440411502275027939415991050284157960514391050429475098827771237860907782270989037431286770001289516610383668883751646289412330746956815078042608777118222417259012153980868059189895322104049920435204499428363782008857646844794331477446552700363905702447931049935526990328994490694834126180948970023199172810067395046387793443712182391229219141687509190169997165999105288234444670380120617845879593015284508182584848776684279192254603481304600761216814359067834700038896121094977112923410962161418760309207304615733033326727689158349196467757174893859766801715038084375406786777201848477381182129928116880468153556380029571594920063448616612270689115465556603807296977350904563171598064124640240795281657800715197562809154611267143627993898729090340625493463471663745464985721404846214479364873455384129755801230728707810565808647033184518995772144586077141286786177949226389412945372413540392151701293281250838958756204163153837443964453600486720525221825699088143204208118159382337325622283474901349749989056015096898103223335186038827380470465855370458598510140857945193760553765566916216709215106775443866275595435116576341611353980221291125608324043415381004668553190615437157153144821431480370310543042783569050552737043116004994954272775368470764353370803652770732775526778496839802549986424954318847883120660842680603299869559738011029563059230656203749758222710387950100134891559949958723716275890640228708151085357244397665962022834876780146100560512504988998836742348623069371030898938525177617865001742687981600631586959407138965695323632627582223327734312982749235859004749859820735685899594668431537644800541514368040344176176871270086881698584165850874718736564614982727941423552997936342261554439093473056598764044455291361446853536071879502080865517129251077344519437553709062740354462849634579031074097030090415955130357923058501875372582622884021698670656041436261732966452366064644993976880037902187704158601140537630618248770944199866376356318213934187140937944723767137643700654528459195195870410092649904500950150741780597441186356193377786517167550891565215014904237613372887196461738112043786909597464188014518671615413369416993155923548619596200244415185235027780256827504921463686375263927146832013739733415790635841012359904207052183025587443484665025845733366318129941870346401189406288528256990010448417262687753689461184135884873596655519352212138152496381261014329391097090581430508962461100475283350105229948713390825455487827973667971985291465417905486215172870422301958038670218271093889911404311340238241609384343471602929057828974212042244985363208139358533532337559620998927693055804700310038772624446222618219985988967483535703342907786830586550412451337390710334238880526922825937662360085910367631733130172048842073097345680732945902792793332602829831845881342607078837770695471847474028645570634513090972739717979821287937915209593755850559390239803377994615251327227174327755382490249111620217682173878162162368797175337613745369408658593635035473721545394209788842820950933730406083012674994776121989133156733827404744726748044985198906318427531927588536843727892922947355179619602102690782250139101505978540203414052107301051746822947826304829786653351633610602523331292516144524374962268687594622651825216895041157061523552903994840389230933302192748488225683327770790601013144883729541833901586537523470811689055307435096846064346921499381593517325591025389942864701907235909325734122252895747126436141382880240115307644605555254795726058174432734944885747513367092411207845289920993484840412169833114859172481675382739585633060075505398416824826637899992393052624550803277726440793041386608456953818518441402496626859430745097801624770601458310257577930955189080930852961325387165055670636172022092056680286777744128449880505172550038920723702055686533489714713321798350249939965601436895513674944952168241082575495811367515595096330432271046353895205411804199350759552430572807491053780317175962789732176752890422249381261747471558765362979518576858038286381500691797637880862587479641943345062089726278051148066707261568289375724636165316963754384143472362440091498928647735569982393814607142507836489799113783892092063008651213950313832972443580359340414193637461478015077548426735742668611239198740585188937133450982506926842126346793965234199388283528961078015173330846502684734302408593410631909164727998098917986980921431211107826500708862552644141524239667145577071378173752771347193464009770531830999814152199488575714185928418720360079792801761757006757097490242923020770556717818013909156071885723319407648776920520010565939892248813275105856499046150143147665052164478648187447721379170746647929936329145435222594106666649552275331070240439673074167099980122644637640284417100774248445182853374733197933146793468983508634721673972146851297139861678861077768481253669544221538764874099003166696286928164699610348065888459891241658772123430238500485897397468489877872689921767403573267503765148377466327454196861314273969113805020243343025595042875536913012078693869653125039075877651453962939257721386318556439989971480675169799103315968 \times 10^{5791}

Are You Stirred up? You are asked to give a more mathematical solution than this... NOTED!

James Bacon - 2 years, 10 months ago

By the Extended Euclidean Algorithm, the expression=18(mod 25)..... Could someone explain how was it calculated?

Debraj Datta - 1 year, 2 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...