Number Theory Number Theory Math Forum

 November 28th, 2017, 06: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. 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
Quote:
 Originally Posted by Shadow89 Hence $\displaystyle ax \equiv c \mod m$
so you have shown that this "x" is a solution to the equation! Tags congruence, euler, phi Thread Tools Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

 Contact - Home - Forums - Cryptocurrency Forum - Top      