Fun math problem

cmhardw · Aug 6, 2008

A friend of mine is really interested in math competitions and problem solving in general. I gave him the circle math problem with the 15-gon that was just on here recently and he liked it.

He gave me one to post here. He already told me how to solve, so I don't want to give it away, but here goes:

What are the last 3 digits of 2009^2009 ; or 2009 raised to the exponent 2009?

Chris

rubiksfriend · Aug 6, 2008

489? Hopefully?

blah · Aug 6, 2008

511. I think. Binomial.

Edit: Wait, that's definitely wrong. 2009 is an odd power, it has to end with a 9. I just tried using mod and I got 489 too. But I don't know what went wrong with my previous method

Edit 2: I'll just post it here so hopefully someone can point out my mistake...

Dammit, why isn't LaTeX supported?

2009^2009
= (2000+9)^2009
= blah blah blah [expand using binomial theorem]
= 1000k + 9^2009 (for some integer k) how do you type the "equivalent" sign? [because the first 2009 terms are multiples of 2000, so they must end with 000]
= 1000k + (10-1)^2009
= 1000n - (2009C2)*100 + 2009*10 - 1 (for some integer n, n!=k) [again, expand the thing, and you'll get multiples of 1000 except for the last three terms]
= work that out and you'll get 1000n - xxxxxx511
= 489 (mod 1000) [This is the (edited) correct working!]

Oh wait, I know why, 1000-511 = 489 -.-" (it was -511 (mod 1000), not 511 (mod 1000))

Less efficient than modular arithmetic, but it serves as an alternative for those who don't know what modular arithmetic is

(they don't teach that stuff in school where I come from)

Lucas Garron · Aug 6, 2008

The best I can do for intuitive powermod:

9^10 ≡ 81^5 ≡ 401 (mod 1000)
Find it however your want; Excel, Mathematica, 81^5, powermod...

Now, take the powers of 401. They look very nice, and it's not hard to understand why:
9^10 ≡ 401
9^20 ≡ 801
9^30 ≡ 201
9^40 ≡ 601
9^50 ≡ 001

2009^2009 ≡ 9^(2000)*9^8 ≡ 9^(2000)*9^8 ≡ (9^(50))^40*9^9 ≡ 9^9

Very reasonable to do: 9^9 ≡ 489
(Or just do PowerMod[2009, 2009, 1000])

nitrocan · Aug 6, 2008

it can be solved using mods.
2009 = 9 mod 1000
9^2 = 81
9^4 = 561
9^5 = 49 so 9^10 = 9^5 * 9^5 = 401 mod 1000
if we continue,
401*401 = 801 mod 1000 (9^20)
401*801 = 201 mod 1000 (9^30)
401*201 = 601 mod 1000 (9^40)
401*601 = 001 mod 1000 (9^50)
so 2009^(50n) = 1 mod 1000
we can write 2009^2009 as 2009^(50*40) * 2009^9
2009*2000 is 1 so we don't care about that.
2009^9 = 9^9 and thats 9^4 * 9^5 = 561 * 49 = 489 mod 1000

(all the = are supposed to be the triple one)

Dene · Aug 6, 2008

I'm sure a powerful enough program could do all the working for me

Johannes91 · Aug 6, 2008

Dene said:
I'm sure a powerful enough program could do all the working for me

I often use the GHCi Haskell interpreter as a calculator. It gave this instantly:

Code:

Prelude> 2009^2009
48606340759767415508733180903816503236119335109156487489250825458681535144372550
03077878933959342648028048688226971267488483657431207075988285549799982512891143
00199104554731581939974076166040044898616366571717429934346339880899748354998033
21267114568763888337599807837826254149993835331522926248523380612016027369819514
04471695371631369996783643612581162223994760939593969710107835068026468701085352
95879764526317755061188052430815659054911850939251605834528584416956792135229263
82957572466273616017072288554417909560919581346539236170196955289808227451760910
35049454560806043735320715248226543590728365245703011967479035944520535446465007
75622077842447239010482781597602184359055076181001878554983165786658530718963917
05021029146785165602169377753627508108869846711012076871889204480808600742722426
26394767620763571326663386266419330687469908292902165192440194361036292996204113
80743259566053518578886274519747384906871788288397432625459523432412273426682759
80324921389805005741451310286074877334318163904973453604406488442842725438871464
91929038621265535142855063688378072063894852169471973732405367718541769515422202
54484552884733932234345379497870970258597657073493613359498452702297234874801655
32917284370181789923035559761465554633033175209248910922042207965366206926935139
46164574036469155653353972285945216016381670586935602303932070389701086036706959
63997252779705608641775269269890191665959804983616945678587347478626330632293526
37956085855218574777205316315068425592392159217351731813195253974310776479520216
92205001008019177413729283176461602863783791931274261647963204478784745474581730
51173788767303181738872029980490284449951278898649428503040439914326636686311413
30346475849128452413819899142092527020148505958106690926324353931181434143490564
03013194454963363395319891475938986538789956512209698229814253241356186928833893
04491682626396004314012823224139440214620445785992420599477297053121599689805303
68564680026577883365608845354010207979238843378378353093713496157273557543193846
40527892027282004393755486199622923482489599634258000808022067072761313009432702
13188614293631115938329004460329628732637786154974121645968846319447699630547188
31440259768691547185531340518676497331493881026617556383812156066565286044972278
54179570847779424526927933042980492199580290706139516354560500527480973821890935
46708119368132811972304242632972729735327917991981154165928553757129933024437309
90357041199892132595213726889603838639661201137347464807005277955868852916544353
53942690231528991014044946975253196528118216714419973336688328336692337194963806
26417484450924274069081676128319084672150683824169412928943640007302984946202966
84079117684064566690969983010659144755112067546351483926208031595359690589695997
85967962564408508809350371401401469703290534426551229638717646171407262907773769
11402842135288362099295761959654302822698575842167293859669677547462019908984849
39671531830300063413546133494967034974977475863317838307058311827367800133000468
79710144391402001035673236202595261434753199123533473167059319133078939760618739
39522221568911954551351015752915722155846363596028360268320489085706328826885106
68020214746290973620007872413876058406852156796455725804547777278432785837008838
88513946791209057472205933056739295124589105189666199379547032599451546034505879
00338481415341377236298165742808339515067993721007865674909075076338266625702270
83335942825168532239212861330421342046828803123472640563771025272518894053479111
23455449935541351208070149375625279419862090502498412686585709294282934153056068
39193242021550611646117087180311668284389094555828655844690900262966831353864495
50360246282172998807180265825149391968370228981454143668694188863879727709392868
26231796115507145688564027743802274062449487538424080064226853157040620437188653
90595185604023753454953804383689676195406457802284608934617241985367684577688823
34426279948642903501906649468701050397613032835500257849747118258138693315060618
55498139464399151188130188083074884441959371201103117216371931946934241657651464
56238995633997916517135635030423384181614286062477409147405563586683744066226477
36481968037757761528213770364277502223902968973460638621164902879355584548743784
40725546943223946775459543192437974677197847578914389164550004012014226965871605
71749858974228743735843889334417333317969456573122772922532710317348185206477043
91232115784968851721918346795158537238383853049095619530325474939566926673594300
71630703629882026536397936199026601871025901588260920467445914303263351912244995
82789460927039446070284141694786375164507176045264035740676295691228237580947245
72022270406264019278666590592497969059243655592075994929854844651085169134545225
01346385065174887829466097020564713396787636381514786432399828014431990188464230
96964843442573475364423067012822792090980252435339231971088383715254776137539917
71557687402989957458250502594057871071411802469990803390994561534357460184590387
45701325855337285002986410688899981396441028751325444471600789940626091810340982
31468697552616881373117091095183261226913720672591638904966274780742379638894747
54054284291785480572640290200376432442169537678052991596556723918516089198541628
60969485899346209708023350430506321181981560188966391643340948656674769359357863
15029011929045853844257373085780598096394856382071609298484711468255133982058347
24538771787945669103479259876375794429601363464550350544978723311070731205179513
43985194126865936751466407804441652439059614659930494273000806827512217655420530
52148936984546327289292153579680554677880783520356629547821736711454879201309133
79303355430596603921051903702337695059283091030863342280589586377173275421271056
38827385306853125740649682960284896294026700897243564287092290344349176866613839
32853811661780752371966666346639077341736420674271703577061819932397462672741848
77273049355442607375467307234794597819787194323651873619021329622417583217625855
70918866349017331901295053676002592000755956993835110382790868589899526906663819
43933894704451125986138479043842519191953034346561311611984203513982380208543998
73404132525730663662922061185035990377059403560969213241936581038555076298636743
97183437142729977488762800666075721331059168866193702717948916046022494634221260
39105227467419311442735441108905671495935953283296457295108652179424113138501135
76007895076213032868942526511028539682328472919169797933323572510125870391448458
40923137132167149017361222640367043038375957891551846307823427596460084566346736
83370252567267116207878170409944190771230427757492724232253780173860071839523436
83203852661352062028997632016669527018658103948209872667364696628576078016766171
3741416796498326143119083008990434118391030167873859556140916123694298718489

rubiksfriend · Aug 6, 2008

Wow. I don't even know what modular arithmetic is. Could someone please give me a concise explanation?

blah · Aug 6, 2008

Look at your watch (if you don't have one then stare at your wrist and visualize a watch there staring back at you).

1 o' clock ≡ 13 o' clock ≡ 25 o' clock (if it exists) ≡ ...
2 o' clock ≡ 14 o' clock ≡ 26 o' clock (if it exists) ≡ ...
3 o' clock ≡ 15 o' clock ≡ 27 o' clock (if it exists) ≡ ...

That's modular arithmetic.

1 ≡ 13 ≡ 25 ≡ -11 ≡ -23 ≡ 12k+1 for all integers k (mod 12)

Generally, if a ≡ b (mod m), then a = km + b for some integer k. (or b = lm + a for some integer l.)

Does that give you an idea?

brunson · Aug 6, 2008

X mod Y is equal to the remainder of X / Y.

As blah says, a = km + b for some integer k, is the definition of division in mathematical lingo, which isn't always the most clear to non-mathematicians.

I did it the same way nitrocan did, but there has to be a cleaner, non-computational solution. I know multiples of 3 do interesting things in number theory. I'll have to think on this for a while.

rubiksfriend · Aug 6, 2008

Thanks for clearing that up for me. I'll have to investigate further!

nitrocan · Aug 6, 2008

we are using mod 10 in our lives.
mod 2 is binary. i dont think that solution was not clean. i've solved(sometimes just tried solving) many unclean math problems

. this isnt one of the hardest.

x = y (mod z) means that when the number x gets divided into z, y is the remainder.

lets say this is our number : 4152
this is equal to 4*1000 + 1*100 + 5*10 + 2*1 which is actually
4*10^3 + 1*10^2 + 5*10^1 + 2*10^0.(this is in mod 10, which we use in our daily life) this is how the modular system works so 423 (mod 5) can be written like this:
4*5^3 + 2*5^2 + 3*5 = 500 + 50 + 15 = 575 (mod 10)

calculating a power of a number is very useful when trying to find the last digit of a number etc.
for example we're trying to find the last digit of 9^16
if we start calculating,
9^2 = 1 mod 10
so every even power of 9 will have 1 as the last digit, and so will 9^16

brunson · Aug 6, 2008

nitrocan said:
we are using mod 10 in our lives.
mod 2 is binary. i dont think that solution was not clean. i've solved(sometimes just tried solving) many unclean math problems . this isnt one of the hardest.

By unclean, I meant that I wasn't willing to calculate the order of the congruence ring by hand and resorted to a computer. I'd prefer if it required no calculations that couldn't be peformed in my head. It looks like you did it on paper, so I consider your answer better than mine.

JBCM627 · Aug 6, 2008

nitrocan said:
we are using mod 10 in our lives.
mod 2 is binary.

By mod 10, you mean base 10? They are very different. mod 2 is not binary, base 2 is binary.

nitrocan · Aug 6, 2008

no i mean mod 10. we write numbers as if they are in mod 10.

JBCM627 · Aug 6, 2008

nitrocan said:
no i mean mod 10. we write numbers as if they are in mod 10.

Mod isn't even a way to "write numbers"... it is an operation.

See:
wiki on mods
wiki on bases

We do not write numbers mod 10. If you constructed everything mod 10, you wouldn't be able to come up with an expression resulting in a defined
value greater than 10. By definition, n%10 < 10.

pcharles93 · Aug 7, 2008

Jim, you just love linking to wikipedia don't you?

JBCM627 · Aug 7, 2008

pcharles93 said:
Jim, you just love linking to wikipedia don't you?

I'll cite another source then:
mathworld on mods
mathworld on bases

(note the base 2 example... binary! not mod 2...)

blah · Aug 7, 2008

brunson said:
I did it the same way nitrocan did, but there has to be a cleaner, non-computational solution. I know multiples of 3 do interesting things in number theory. I'll have to think on this for a while.

Hey! What about my solution? It's the only non-mod solution around, because I figured most people would use mod to solve it, so I wanted to be "different"

And my solution doesn't require the use of a calculator at all. 2009C2 can be very easily calculated by hand, and it's even easier when you only want the last digit of it!

This is all the calculation that's involved:
Last three digits of [ - (2009C2)*100 + 2009*10 - 1 ]
= -[last digit of 2009C2]*100 + 90 -1
= -[2009!/2!2007!]*100 + 89
= -[2009*2008/2]*100 + 89
= -[last digit of 9*8/2]*100 + 89
= -511

1000-511 = 489

hawkmp4 · Aug 7, 2008

Binomial theorem could be used. But I was lazy-
2009**2009 =
blahblahblah....489

EDIT: Scratch that. Dunno how binomial theorem would help >.> I'm tired.

Thread starter	Similar threads	Forum	Replies	Date
	Cubing Task 4 Fun: Make a Tier List Ranking the Official WCA Puzzles	General Speedcubing Discussion	92	Apr 3, 2024
	Yiheng Wang Having Fun	General Speedcubing Discussion	1	Aug 24, 2023
	Fun 3x3 mini game idea	General Speedcubing Discussion	1	Aug 22, 2023
	Virtual Rubik's Cube on Scratch! (ZBLL Trainer soon?)	General Speedcubing Discussion	3	May 13, 2023
L	Fun math problem with groups...	Off-Topic Discussion	4	Feb 9, 2009

Fun math problem

Premium Member

Member

brah

Administrator

nitrocan

Guest

Premium Member

Member

Member

brah

Member

Member

nitrocan

Guest

Member

Member

nitrocan

Guest

Member

Member

Member

brah

Member