My Math Forum n=?

 Algebra Pre-Algebra and Basic Algebra Math Forum

 October 22nd, 2018, 11:55 AM #11 Member   Joined: Jan 2016 From: Athens, OH Posts: 92 Thanks: 47 This may be more information than you want, but here goes. Given positive integers a and m, find all positive integers n with $a^n$ congruent to 1 mod m. First a and m must be relatively prime; otherwise, no such n exists. So for a prime to m, $a^n$ is 1 mod m for $n=\phi(m)$ -- here $\phi$ is Euler's totient function. Let k be the smallest positive integer with $a^k=1$ mod m; k is called the order of a modulo m. Then k divides $\phi(m)$ and any solution n is a multiple of k. For your specific problem, $\phi(53)=52$. As was noted in the last post, the order of 5 turns out to be 52. This is a lot of arithmetic to do by hand. I have a little computer program that computes the order of a mod m; if you're interested, post again. Lastly, for m a prime, the problem of finding a with the order of a being m-1 is a hard problem. Such an a is called a primitive root. As far as I know, there is no easy way to find primitive roots.

 Thread Tools Display Modes Linear Mode

 Contact - Home - Forums - Cryptocurrency Forum - Top