if i don't misunderstand ,the way you say is if i replace 2 by another number i and \(\displaystyle (p-1)/i\) is prime ,then i is primitive root of n . For a better experience, please enable JavaScript in your browser before proceeding. There is no general formula to find a primitive root. Has anyone seriously considered a space-based time capsule? And $a^m \mod p$ is another primitive root if and only if $m$ and $p-1$ are coprime (if $\gcd(m,p-1)=d$ then $(a^m)^{(p-1)/d}\equiv (a^{p-1})^{m/d}\equiv 1\mod p$, so we need $d=1$). Remember order means the. The obvious question: Does every prime $p \ge 3$ have a prime number as a primitive root? @Arturo I have posted my answer below, and among other things, I have an example of why just testing $a^{380}$ is not enough to say that $a$ is a primitive root. To test that $a$ is a primitive root of $p$ you need to do the following. For example, take \(\displaystyle n=4\). Copyright © 2005-2020 Math Help Forum. Then it turns out for any integer relatively prime to 59-1, let's call it b, then $2^b (mod 59)$ is also a primitive root of 59.. rev 2020.11.24.38066, The best answers are voted up and rise to the top, Mathematics Stack Exchange works best with JavaScript enabled, Start here for a quick overview of the site, Detailed answers to any questions you might have, Discuss the workings and policies of this site, Learn more about Stack Overflow the company, Learn more about hiring developers or posting ads with us. Why do internal forces not affect the conservation of momentum, the powers to test are: $760/2=380$, $760/5=152$ and $760/19=40$ (just 3 instead of testing all of them). Smallest prime $p$ which every integer $< n$ is a primitive root $\mod p$. You do not raise $a$ to the power of all prime factors of $\phi(p)$. Indeed, if $a$ is a primitive root mod $p$, and $p$ is prime (for simplicity), then $a$ can generate all other remainders $1\ldots(p-1)$ as powers: $a^1\equiv a,a^2,\ldots,a^{p-1}\equiv 1$. I think if testing all i ,(i,N)=1, is so long. JavaScript is disabled. Finding Other Primitive Roots (mod p) Suppose that we have a primitive root, g. For example, 2 is a primitive root of 59. When you learn True Polymorph, do you learn about every creature in existence? Say \(\displaystyle p=11\) then \(\displaystyle (11-1)/2=5\) is prime, which means \(\displaystyle 2\) is primitive root of \(\displaystyle 11\). Relevance. The direct way with to deal with \(\displaystyle 11\) is to list all \(\displaystyle n\) with \(\displaystyle \gcd (n,11)=1\) so \(\displaystyle n=1,2,...,10\). I leave that for you to prove. For example, $6^2=36$ or $6^{15}\equiv 686$ are not primitive roots of $761$ because $\gcd(2,760)=2>1$ and $\gcd(15,760)=5>1$, but, for example, $6^3=216$ is another primitive root of 761. The prime $ p = 71$ has $7$ as a primitive root. Also, there will be more powers to test. How to find generator in a finite group?what is generator? Finally, calculate $a^{s/p_i}\mod p$ for all $i=1\ldots k$, and if you find $1$ among residuals then it is NOT a primitive root, otherwise it is. Just because it is a tiny bit faster. Although there can be multiple primitive root for a prime number but we are only concerned for smallest one.If you want to find all roots then continue the process till p-1 instead of breaking up on finding first primitive root. Let us find the lowest primitive root of $761$: So, the least primitive root of 761 is 6. How you find all the other primitive roots. You find those factors $p_i$ and raise $a$ to the powers $s/p_i$. What is this part which is mounted on the wing of Embraer ERJ-145? Is There (or Can There Be) a General Algorithm to Solve Rubik's Cubes of Any Dimension? In my other posts. Founded in 2005, Math Help Forum is dedicated to free math help and math discussions, and our math community welcomes students, teachers, educators, professors, mathematicians, engineers, and scientists. :(. For example $761-6=755$ is primitive because $760$ is divisible by $4$. In Star Trek TNG Episode 11 "The Big Goodbye", why would the people inside of the holodeck "vanish" if the program aborts? Since you can store quite large powers of small primes in a table, calculating their powers will be a little bit faster. 4- If it is 1 then 'i' is not a primitive root of n. 5- If it is never 1 then return i;. Why does Chrome need access to Bluetooth? primitive root. Does it have to do with the fact that it's $2^2$? All rights reserved. How to find a primitive root modulo $5^{10}$? Mathematics is concerned with numbers, data, quantity, structure, space, models, and change. But if you are looking for primitive roots of, say, $2311$ then the probability of finding one at random is about 20% and there are 5 powers to test. By using primitive roots how does one solve $x^2 \equiv -1 \pmod p$ for $x$, given prime $p$. Randomly? This is precisely why you need to test all the powers: $760/2$, $760/5$ and $760/19$. 1 Answer. If $p \ge 3$ and $p-1$ is therefore even, $x^2 (\text{mod } p)$ cannot be a primitive root, and if $x^3 (\text{mod } p)$ is a primitive root then so is $x$. If $2^2$ was one, then 2 would've been one as well. You could pick the candidates randomly. Does every prime > 2 have a primitive root that is a prime? If a person is dressed up as non-human, and is killed by someone who sincerely believes the victim was not human, who is responsible? There are primitive roots mod n n n if and only if n = 1, 2, 4, p k, n = 1,2,4,p^k, n = 1, 2, 4, p k, or 2 p k, 2p^k, 2 p k, where p p p is an odd prime. By the way, this is exactly why you have $\phi(p-1)$ primitive roots when $p$ is prime. How you find all the other primitive roots. Do all threads share the same instance of a heap variable, or have different instances of a heap variable? I think if testing all i ,(i,N)=1, is so long THanks I was wondering - why did you skip 4 when looking for a primitive root? Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. From wiki... psi(25) = 20. Meaning of the Term "Heavy Metals" in CofA? So pick one at random and check to see if $a^{380}\equiv -1\pmod{761}$; if yes, then $a$ is a primitive root; if not, then pick something else. If $p-1$ is divisible by $4$ and $a$ is a primitive element then $p-a$ is also primitive. Let $p$ be a prime with $p\equiv 1\pmod4$, and let $g$ be a primitive root modulo $p.$ Then $-1\equiv g^{\frac{p-1}{2}}\pmod p,$ so $-g\equiv g^{\frac{p+1}{2}}\pmod p.$ Since $\frac{p+1}{2}$ is prime to $p-1,$ $-g$ is also a primitive root modulo $p.$, Finding a primitive root of a prime number, “Question closed” notifications experiment results and graduation, MAINTENANCE WARNING: Possible downtime early morning Dec 2/4/9 UTC (8:30PM…, Generator of multiplicative group of $\mathbb{Z}/p\mathbb{Z}$, Efficient algorithms for Primitive roots where time-complexity is $\leq O(\sqrt{n})$. Lucas' primality test == finding a primitive root? I say that if \(\displaystyle (p-1)/2\) is also a prime then \(\displaystyle 2\) is a primitive root of \(\displaystyle p\). 1 decade ago. Let $p$ be an odd prime number. Answer Save. For example, if you pick a random number to test for being a primitive root of $761$, then the probability of finding one is roughly $\frac{1}{2}\times\frac{4}{5}\times\frac{18}{19}$ or 38%, and there are 3 powers to test. First, let $s=\phi(p)$ where $\phi()$ is the Euler's totient function.