Math Is Fun Forum

parthenos

Member

Registered: 2008-08-25

Posts: 9

Need Help with Abstract Algebra (graduate level)

I am looking for someone to help talk me through some Abstract homework.

-integers and modulo n problems. Euler's function...

1.  compute the remainder when 37^100 is divide by 29.

2.  compute the last 2 digits of 9^1500

Last edited by parthenos (2008-08-25 12:27:08)

parthenos

Member

Registered: 2008-08-25

Posts: 9

Re: Need Help with Abstract Algebra (graduate level)

^ exponent

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Need Help with Abstract Algebra (graduate level)

1. The key here is of course everything (as you seem to know) is modulo 29.  What can you immediately reduce the problem to? 

2. Same as above, but you would be calculating mod 100.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: Need Help with Abstract Algebra (graduate level)

I can’t make head or tail of Ricky’s hint, so I doubt if Parthenos can either. Here are my own hints instead.

#1
By Fermat’s little theorem, if x is not divisible by 29,

.

Now

.

etc. Continue this way until

.

#2
Keep taking powers of 9 until you get to a number whose last two digits are 01.

should be it, i.e.

. The rest is a doddle.

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

Re: Need Help with Abstract Algebra (graduate level)

I'm pretty sure Ricky's hint was just saying that 37 could be changed into 8.

---

Why did the vector cross the road?
It wanted to be normal.

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: Need Help with Abstract Algebra (graduate level)

Okay, maybe you don’t need to calculate

directly in the second one. You can stop at

.

Notice that

, where N is an integer.

parthenos

Member

Registered: 2008-08-25

Posts: 9

Re: Need Help with Abstract Algebra (graduate level)

Thanks for you help Jane.  I still don't quite understand how I find the last 2 digits in #2.

krassi_holmz

Real Member

Registered: 2005-12-02

Posts: 1,905

Re: Need Help with Abstract Algebra (graduate level)

To get the last 2 digits you need the remainder modulo 100. First find the phi of 100:

Now, Euler theorem gives you:

, and 4|150, so the last two digits are 01.

And if you don't beleive, the number is actually
2310809578111909272693109431184832846484968454396283812529115413319435556973292122101720139716262409469889717513948376726158501486182636383531313869623735751595188198743086350673413093292498741784795660389148326466211372843337723144590341000538769498117226562808444716579845071408688720747381120135479199680471885180482121554984483377022066232113498842614313541610752653690490275184816645775562870080222550532658199952189433551842563700110684899935346509404097452154895288699360903786484615575470777362920177718027703180305669825349020152868844727956235156059960772077214312800556301983539901820176796454299860300131486822074451633519214994291242241850066416567586776526981799888092096865174444248800546127994730384671200620078154936387315118122040519117349396356198197315367766646921156257797160661163192060277301722871797101013527586327674333920080776435765228230385762165404932957246335621254520607306174400378047735376342518713628466946614321497738427647167939078993913147690702992638955965837451910388196619417991842556404018337740923222175380153877003983519741457506625666074023573361964063311318755920947209571433341645962479076131201964416276406387762072361807631460445372486964777059883706070699922193176468574966898852772974365576953262531708962699524486008324366541931862849776343129934761158587798436540362085500749517170402734545433993099089688531543345393342814833105525138762128016370025483881594201769798453765660001

---

IPBLE:  Increasing Performance By Lowering Expectations.

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: Need Help with Abstract Algebra (graduate level)

4|150

It does???!!!

Last edited by JaneFairfax (2008-08-26 11:08:32)

krassi_holmz

Real Member

Registered: 2005-12-02

Posts: 1,905

Re: Need Help with Abstract Algebra (graduate level)

4|150

It does???!!!

You got me!
So... Since 1500 = 37.40 + 20, then

Blah, and since i don't want to multiply by 9 3times, I'll use not Euler, but Carmichael theorem, first find:

And by Carmichael's theorem, that is:

Hence, the last 2 digits are 01, because 2|150.
Jane, you ruined my first proof. Happy now!;)
It would've been just fine if 100 were a prime...

Last edited by krassi_holmz (2008-08-26 10:53:19)

---

IPBLE:  Increasing Performance By Lowering Expectations.