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
November 28th, 2017, 07:16 PM   #1
Newbie
 
Joined: Sep 2017
From: San Diego

Posts: 8
Thanks: 0

What does this mean

If the GCD(a, m) =1, show that any x such that

$\displaystyle x \equiv ca^{\phi(m)-1}\mod m $ satisfies $\displaystyle ax\equiv c\mod m$

I put

Suppose $\displaystyle x \equiv ca^{\phi(m)-1}\mod m $ for any x.
Then by multiplying both side of congruence by a we get,

$\displaystyle ax \equiv ca^{\phi(m)}\mod m $

Since the GCD(a, m) =1, by Euler's theorem it follows that

$\displaystyle a^{\phi(m)} = 1\mod m $


Thus,

$\displaystyle ax \equiv ca^{\phi(m)}\equiv c \cdot 1 \mod m $

Hence $\displaystyle ax \equiv c \mod m $


Is this what I need to do? To me the word satisfies means is a solution to, but I have no idea how to show that. This all I came up with.
Shadow89 is offline  
 
December 1st, 2017, 03:58 AM   #2
Math Team
 
Joined: Jan 2015
From: Alabama

Posts: 2,875
Thanks: 766

The last thing you write is
Quote:
Originally Posted by Shadow89 View Post
Hence $\displaystyle ax \equiv c \mod m $
so you have shown that this "x" is a solution to the equation!
Country Boy is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
congruence, euler, phi



Thread Tools
Display Modes






Copyright © 2017 My Math Forum. All rights reserved.