My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
LinkBack Thread Tools Display Modes
May 4th, 2010, 05: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^(m-phi(m))modulo(m) for all integers a.I tried to solve this by induction but failed.Help.
ogajajames is offline  
 
May 4th, 2010, 05:47 AM   #2
Global Moderator
 
CRGreathouse's Avatar
 
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.
CRGreathouse is offline  
May 4th, 2010, 06: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.
ogajajames is offline  
May 4th, 2010, 07:11 AM   #4
Global Moderator
 
CRGreathouse's Avatar
 
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?
CRGreathouse is offline  
May 4th, 2010, 07: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 (m-phi(m);1)a^(m-phi(m)-1)+..........+(m-phi(m);m-phi(m)-1)a.Am using (a;b) to mean combination of b objects from a objects.This is where I got stuck.
ogajajames is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

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 05:47 AM
Solved an equation. I don't think this is the end though. hamburgertime Algebra 1 February 21st, 2013 12:36 PM
[Solved] there should be a plus right? peaceofmind Algebra 3 April 23rd, 2011 05:38 PM
solved vjelmy Calculus 7 May 25th, 2010 08:44 AM
Please Help! Can this be solved at all? cluelessinmath Algebra 16 January 15th, 2010 08:04 AM





Copyright © 2019 My Math Forum. All rights reserved.