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. By using primitive roots how does one solve $x^2 \equiv -1 \pmod p$ for $x$, given prime $p$. Please read more carefully. You could pick the candidates randomly. If a piece of software does not specify whether it is licenced under GPL 3.0 "only" or "or-later", which variant does it "default to"? 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$). How to find a primitive root modulo $5^{10}$? You're not just testing primes, though, as you find one at 6.. @Joost Yes, being a perfect power prevents an integer from being the smallest(!) Once you have found one primitive root, you can easily find all the others. Copyright © 2005-2020 Math Help Forum. I say that if \(\displaystyle (p-1)/2\) is also a prime then \(\displaystyle 2\) is a primitive root of \(\displaystyle p\). Right. 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. Is There (or Can There Be) a General Algorithm to Solve Rubik's Cubes of Any Dimension? There are methods which make it faster. JavaScript is disabled. The obvious question: Does every prime $p \ge 3$ have a prime number as a primitive root? Finding primitive roots is generally difficult. 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 . 25 = 5^5. 1 decade ago. 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. For 11 you can use a simple fact that if \(\displaystyle p\) is a odd prime and \(\displaystyle (p-1)/2\) is also a prime then \(\displaystyle 2\) is a primitive root for \(\displaystyle p\). That removes $1, 4, 8, 9$ and others. You do not raise $a$ to the power of all prime factors of $\phi(p)$. 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. 1 Answer. Since you can store quite large powers of small primes in a table, calculating their powers will be a little bit faster. Let N have primitive roots .Which the way does find all primitive roots generally ? Relevance. Stack Exchange network consists of 176 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers. Why does Chrome need access to Bluetooth? How do you pick the primitive roots to test? what are the eight primitive roots of 25, how can you tell? By the way, this is exactly why you have $\phi(p-1)$ primitive roots when $p$ is prime. Does it have to do with the fact that it's $2^2$? How would you find a primitive root of a prime number such as 761? 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. Just because it is a tiny bit faster. maybe i am not smart enough to know your advice.YOu can tell clearly . Say \(\displaystyle p=11\) then \(\displaystyle (11-1)/2=5\) is prime, which means \(\displaystyle 2\) is primitive root of \(\displaystyle 11\). Let us find the lowest primitive root of $761$: So, the least primitive root of 761 is 6. 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. 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$. 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})$. If $2^2$ was one, then 2 would've been one as well. 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. For example, take \(\displaystyle n=4\). 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.. If $p$ is prime, then $s=p-1$. Favorite Answer. What are some methods to align switches in a multi-gang box? I think if testing all i ,(i,N)=1, is so long. 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). Typically, what you do is you pick a number and test. No simple general formula to compute primitive roots … Let $p$ be an odd prime number. What is the minimum viable ecological pyramid a terrafoming project would introduce to world with no life to make it suitable for humans?