May 4th, 2010, 06:34 AM  #1 
Newbie Joined: Apr 2010 From: kenya Posts: 28 Thanks: 0  How can this be solved.
for an integer m>1 show that a^m is congruent to a^(mphi(m))modulo(m) for all integers a.I tried to solve this by induction but failed.Help.

May 4th, 2010, 06:47 AM  #2 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: How can this be solved.
The order of a mod m divides the order of the group (this is called Lagrange's theorem), which is phi(m). Thus a^phi(m) = 1, which gives you the result you need.

May 4th, 2010, 07:38 AM  #3 
Newbie Joined: Apr 2010 From: kenya Posts: 28 Thanks: 0  Re: How can this be solved.
Isn't there any elementary approach apart from using Lang range's theorem because I got this from an exercise of number theory book before the theorem was discussed.

May 4th, 2010, 08:11 AM  #4 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: How can this be solved.
Do you know Fermat's little theorem? It, together with the CRT, can probably be used... but that's still a lot of machinery. I'll be honest, I can't think of a more elementary method off the top of my head. What results do you have so far?

May 4th, 2010, 08:24 AM  #5 
Newbie Joined: Apr 2010 From: kenya Posts: 28 Thanks: 0  Re: How can this be solved.
By induction I reached a point where I had to show that m divides (mphi(m);1)a^(mphi(m)1)+..........+(mphi(m);mphi(m)1)a.Am using (a;b) to mean combination of b objects from a objects.This is where I got stuck.


Tags 
solved 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
How was this solved?  noatom  Algebra  1  December 27th, 2013 06:47 AM 
Solved an equation. I don't think this is the end though.  hamburgertime  Algebra  1  February 21st, 2013 01:36 PM 
[Solved] there should be a plus right?  peaceofmind  Algebra  3  April 23rd, 2011 06:38 PM 
solved  vjelmy  Calculus  7  May 25th, 2010 09:44 AM 
Please Help! Can this be solved at all?  cluelessinmath  Algebra  16  January 15th, 2010 09:04 AM 