[math-fun] Is this true?
x^x == k (mod n) is solvable for all k iff gcd(n, phi(n)) = 1.
Perhaps you left out some hypothesis? Let n = 3 then gcd(3,phi(3)) = 1 but mod 3: 0^0 = 1, 1^1 = 1, 2^2 = 4 = 1 so x^x = 2 mod 3 has no solution. On Sun, Mar 13, 2016 at 10:54 AM, David Wilson <davidwwilson@comcast.net> wrote:
x^x == k (mod n) is solvable for all k iff gcd(n, phi(n)) = 1.
What about 5^5 == 2 (mod 3)?
-----Original Message----- From: math-fun [mailto:math-fun-bounces@mailman.xmission.com] On Behalf Of W. Edwin Clark Sent: Sunday, March 13, 2016 12:49 PM To: math-fun Subject: Re: [math-fun] Is this true?
Perhaps you left out some hypothesis? Let n = 3 then gcd(3,phi(3)) = 1 but mod 3: 0^0 = 1, 1^1 = 1, 2^2 = 4 = 1 so x^x = 2 mod 3 has no solution.
On Sun, Mar 13, 2016 at 10:54 AM, David Wilson <davidwwilson@comcast.net> wrote:
x^x == k (mod n) is solvable for all k iff gcd(n, phi(n)) = 1.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Sun, Mar 13, 2016 at 7:54 AM, David Wilson <davidwwilson@comcast.net> wrote:
x^x == k (mod n) is solvable for all k iff gcd(n, phi(n)) = 1.
Yes; in particular, since n and phi(n) are coprime, there's a number m less than n*phi(n) such that m == k (mod n) and m == 1 (mod phi(n)). -- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
participants (3)
-
David Wilson -
Mike Stay -
W. Edwin Clark