Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2007-09-11 23:40:29

Identity
Member
Registered: 2007-04-18
Posts: 934

Number Theory solution help

I neeed help with the 2nd solution to question 4 in the link.

http://www.mathscomp.ms.unimelb.edu.au/ … 2004SS.pdf

It looks like a variant of fermat's little theorem but I can't for the life of me work out how it's supposed to work. How do you know n and the exponents are coprime etc??? Thanks

Offline

#2 2007-09-12 00:30:44

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

Re: Number Theory solution help

Coprime?  You don't need anything like that.  Modular arithmetic is preserved through addition and multiplication.  That is:

If a = a' (mod n) and b = b' (mod n) then a + b = a' + b' (mod n) and ab = a'b' (mod n)

Use the later and induction to prove that if a = b (mod n), then a^k = b^k (mod n).  Now simply apply the addition part and you're done.  In general, if you mod an equation out by n, you can mod all of it's parts out by n.  It's when you are going from one mod to another mod that you have to worry about more complex things.


"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..."

Offline

Board footer

Powered by FluxBB