My Math Forum  

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

Number Theory Number Theory Math Forum

LinkBack Thread Tools Display Modes
November 28th, 2017, 06:16 PM   #1
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 $


$\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, 02:58 AM   #2
Math Team
Joined: Jan 2015
From: Alabama

Posts: 3,264
Thanks: 902

The last thing you write is
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  

  My Math Forum > College Math Forum > Number Theory

congruence, euler, phi

Thread Tools
Display Modes

Copyright © 2019 My Math Forum. All rights reserved.