Questions tagged [primitive-roots]

For questions about primitive roots in modular arithmetic, index calculus, and applications in cryptography. For questions about primitive roots of unity, use the (roots-of-unity) tag instead.

Filter by
Sorted by
Tagged with
2
votes
4answers
392 views

Understanding Primitive roots

I am trying to find a single primitive root modulo $11$. The definition in my textbook says "Let $a$ and $n$ be relatively prime integers with ($a \neq 0$) and $n$ positive. Then the least ...
2
votes
1answer
36 views

Understanding the following lemma

While studying primitive roots, I came across the following lemma: Lemma: Let $p$ and $q$ be primes and suppose that $q^\alpha\mid p-1$, where $\alpha\geq 1$. Then there are precisely $q^\alpha - q^{\...
5
votes
1answer
209 views

Chinese reminder Theorem and primitive roots

The problem I am working on is "Let $p$ be a prime such that $p\equiv 1\pmod{105}$. Show that there exist integers $n, x, y, z$ such that $p$ does not divide $n$ and $n \equiv 3x^3 \equiv 5y^5 \equiv ...
0
votes
1answer
29 views

Let $g$ be a primitive root modulo $p^e$ for some $p$ prime, $e\geq 1$, show that gcd$(g,p)=1$

So far I've got: Suppose gcd$(p,g)\neq 1$, so $p\mid g$ and hence $p^e\mid g^e$ so $g^e\equiv 0 $ (mod $p^e$) Also $g^{p^{e-1}(p-1)}\equiv 1$ (mod $p^e)$ because $g$ is a primitive root. Not sure ...
5
votes
1answer
73 views

Is there a counterexample? $\forall p \in \Bbb P\ ,\ p\gt 61\ ,\ \exists\ r1,r2\ \in \{\ Primitive\ Roots\ Modulo\ p\ \}\ /\ r1+r2 = NextPrime(p)$

This is the weirdest thing I have observed so far! Take the set of Primitive Roots Modulo p (link to definition here) of a prime number $p$, $Pr(p)$. For those primes $p \gt 61$ there is always a pair ...
1
vote
2answers
771 views

What does “maximum order elements to mod n” mean for a number n without primitive roots modulo n?

I apologize because probably this is trivial, but I do not understand the concept: "maximum order elements to mod n for n". This is the context: in the Wikipedia in the primitive roots modulo n ...
5
votes
1answer
350 views

Conjecture about the product of the primitive roots modulo a prime number ($\prod Pr_p$)

While I was learning about the primitive roots modulo $p \in \Bbb P$ (I will call $Pr_p$ to the complete list of the primitive roots module $p$) and having in mind the conjecture explained in this ...
3
votes
2answers
656 views

Online primitive root modulo n list or tool?

Please does somebody know of an online list or tool (if possible server side, not a Java applet running in my computer) to calculate the primitive roots modulo n, for instance $n \in [1,1000]$ (apart ...
0
votes
1answer
210 views

Proof of primitive roots in $F_{128}$

What would be the simplest way to prove that every element in $F_{128}$ is a primitive root except zero $(0)$ and the identity. Well, clearly 0 can not be a primitive root, and i also know that $...
1
vote
0answers
65 views

Proof for primality based on exponents and primitive roots

I'm trying to prove the following statement: Suppose $n > 1$. The number $n$ is prime if and only if there exists a number $b$ such that gcd$(b, n) = 1$ and $b^{n−1} ≡ 1$ (mod $n$) and $b^{(n−1)/d}...
2
votes
0answers
64 views

A multivalued function $ f(x) = 0 $ with integer solutions $ x_1=p(n) $ and $x_2=q(n) $

Please help me to define a multivalued function $ f(x) = 0 $ with integer solutions : $ x_1 = p(n)$ and $ x_2 = q(n) $ such that $\dfrac{ p(n) + q(n) } { 2 } = 2 n + 1 $ and $ \...
3
votes
1answer
77 views

Why is $c+q$ still a primitive root modulo $q$?

Question: Let $p$ and $q$ be distinct odd prime numbers. By considering primitive roots, we need to show $\exists c\in\mathbb{Z}$ with the property that: $\bullet$ $c^n\equiv 1\pmod{p}$ whenever $n$ ...
1
vote
1answer
95 views

If $p$ is an odd prime with $(p - 1)/2$ primitive roots, is $p$ a Fermat prime?

If $p$ is an odd prime and there are $(p - 1)/2$ primitive roots modulo $p$, then is $p = 2^k + 1$ for some nonnegative integer $k$? This is the converse of a statement that I have already proved.
1
vote
4answers
446 views

How is $3$ not a primitive root mod 8?

Sources are telling me that there are no primitive roots $\mod 8$, yet $\phi (8) = 4$ and $3^{\phi(8)} = 1 \mod 8$. Thus $1, 3$ form a reduced residue system.
0
votes
0answers
96 views

Prove that if $3^\frac{F_n-1}{2} \equiv -1 \pmod {F_n}$, then $F_n$ is prime [duplicate]

$F_n = 2^{2^n} + 1$ is a Fermat Number. Here is my attempt. We square each side of the congruences we get $$3^{F_n-1} \equiv 1 \pmod {F_n}$$ Now I already know that whenever $m \neq n$ then $ \gcd(...
2
votes
1answer
64 views

$g^q-q$ and $g^q-gq$ are primitive roots modulo $q^2$

Let $g$ be a primitive root modulo an odd prime $q$. Then, both $g^q-q$ and $g^q-gq$ are primitive roots modulo $q^2$. I read this question somewhere and the first thing that came to my mind as a ...
3
votes
1answer
150 views

Proving $\frac{p-1}{2}$ is a primitive root modulo $p$ if and only if $2(-1)^{(p-1)/2}$ is a primitive root modulo $p$

Let $p$ be an odd prime. Prove that $\frac{p-1}{2}$ is a primitive root modulo $p$ if and only if $2(-1)^{(p-1)/2}$ is a primitive root modulo $p$. I was thinking that since $\frac{p-1}{2}$ is a ...
1
vote
1answer
368 views

primitive roots and quadratic residues

prove that if p congruent to 3 (mod 4) is a prime and g is a primitive root mod p, then p - g is not a primitive root mod p. p-g must be congruent to g^m mod p for some m, and if i want to show p - g ...
0
votes
2answers
2k views

Finding order of an integer with (mod 9)?

I am trying to solve a problem to find the order of some integers with (mod 9). I understand the concept I also have the solution to the problem. My calculations are also correct except for a few ...
1
vote
1answer
925 views

Prove that $a$ is a primitive root $\bmod{p}$ if and only if $-a$ has order $\frac{p-1}{2}$

Consider a prime $p$ $\in\mathbb{N}$ of the form $4t+3$, with $t$ $\in\mathbb{N}$. Prove that a $\in\mathbb{Z}$ is a primitive root $\mod p$ if and only if $-a$ has order $\frac{(p-1)}{2}$. I showed ...
0
votes
1answer
79 views

How do I prove this statement about $n^\text{th}$-power residues?

I am studying A Classical Introduction to Modern Number Theory by Ireland and Rosen, and the authors leave the proof of the following proposition (4.2.2) as "an exercise" ... Suppose that $a$ is ...
5
votes
1answer
243 views

Determine the number of solutions of $x^p\equiv 1\mod p^h$ using primitive roots

So the problem is to determine the number of solutions of the congruence $x^p\equiv 1\mod p^h$, where $p$ is an odd prime and $h\geq2$. We are asked to establish the result using primitive roots. We ...
4
votes
3answers
203 views

primitive roots problem. that integer n can never have exactly 26 primitive roots.

Show that no integer $n$ can have exactly 26 primitive roots. I know that if $n$ has primitive roots then it has exactly $\phi(\phi(n))$ primitive roots. I think the proof has to use contradiction. ...
4
votes
1answer
182 views

Count of lower and upper primitive roots of prime $p \equiv 3 \bmod 4$

I was exploring the layout of primitive roots of primes over a reasonable range and this question concerns the number of primitive roots either side of $p/2$. Many primes have an exact match between ...
1
vote
2answers
157 views

Let $p$ be a prime of the form $p=2^k+1$. Prove that $\mathbb{Z}_p$ has $2^{k-1}$ primitive roots.

Let $p$ be a prime of the form $p=2^k+1$. Prove that $\mathbb{Z}_p$ has $2^{k-1}$ primitive roots. Let $g_0$ be a primitive root. Which powers of $g_0$ are primitive roots? Prove! Since $p$ is a ...
4
votes
1answer
49 views

Show that $[-a^2]$ generates Up

I'm trying to show that $[-a^2]$ generates $U_p$, given that $1<a<p-1$ and p is an odd prime, $p=2q+1$ and q is also an odd prime. I know that $[-a^2]$ is a primitive root iff 1. $[-a^2]^{\phi(...
1
vote
1answer
106 views

Properties of square roots

Forgive me if this question is very basic, I don't know much about the properties of square roots. My goal is to compute the square root of a very large number (around 1024 bits). While toying around ...
0
votes
1answer
33 views

Primitive roots in $\mathbb{F}_7[x]/(x^2+1)$

Are $2+x$ and $1+x$ primitive roots in $\mathbb{F}_7[x]/(x^2+1)$? I'm having trouble with the arithmetic associated with finding primitive roots.
4
votes
1answer
111 views

Primitive roots modulo primes congruent to n!

for $N \ge 4$. Show for prime numbers, $p \equiv 1$ mod $(N!)$ that none of the numbers $1,2,...,N$ are primitive roots modulo $p$ I can't figure out where to start with this question, all I can ...
2
votes
1answer
41 views

Long division to primitive roots?

In this long divsion: ...
0
votes
1answer
194 views

The primitive root of modulo 109

While trying to find the first primitive root of modulo 109, I've ran across a very weird problem. Firstly I used Euler Criterion to try to find a number that would satisfy $a^{(p-1)/2}≡-1$ mod($p$). ...
1
vote
1answer
90 views

Concerning Primitive roots and exponents.

If for any $u$,such that 1 < u < p; given $\bmod p$; if $m^u \equiv u V \pmod{p}$ where $p$ does not divide $(V - 1)$ for any $V$ then $m$ is not a primitive root. Is this true?
1
vote
1answer
202 views

Discrete Logarithm Problem

Question: Discrete Logarithm Problem: Let $g$ be a primitive root for $F_{p}$. Suppose that $x = a$ and $x = b$ are both integer solutions to the congruence $g^{x} \equiv h \pmod{p}$. Prove that $a \...
3
votes
1answer
770 views

If $r$ is a primitive root of odd prime $p$, prove that $\text{ind}_r (-1) = \frac{p-1}{2}$

If $r$ is a primitive root of odd prime $p$, prove that $\text{ind}_r (-1) = \frac{p-1}{2}$ I know $r^{p-1}\equiv 1 \pmod {p} \implies r^{(p-1)/2}\equiv -1 \pmod{p}$ But some how I feel the ...
2
votes
1answer
74 views

Primitive roots and 'equivalent exponents'.

If M is a primitive root mod p and M = $\ N^T$ mod p , then the order of N mod p is also (p-1) is this true?
0
votes
1answer
203 views

My proof that there are primitive roots modulo $p^2$

Let $p$ be a prime number. I'd like to prove that there are primitive roots modulo $p^2$. Could someone check this argument? Note that if $r\in\mathbb Z$ is a primitive root modulo $p^2$, it must be ...
0
votes
2answers
1k views

If $p$ and $q = 2p + 1$ are both odd primes, show that $-4$ and $2(-1)^{(1/2)(p-1)}$ are both primitive roots modulo $q$.

If $p$ and $q = 2p + 1$ are both odd primes, show that $-4$ and $2(-1)^{(1/2)(p-1)}$ are both primitive roots modulo $q$. I cannot get heads nor tails of how to even start this let alone finish it
0
votes
1answer
319 views

How do I find a primitive element in $Z_7$?

I understand the definition of a primitive element. I also know that 3 is primitive element of $Z_7$. I was shown that 2 is not primitive element of $Z_7$ because $2^{3}$ = 8= 1. I do not understand ...
0
votes
1answer
65 views

primitive roots $g^a \mod{p}$

$p$ prime, $g$ primitive root $\mod{p}$, $0 \leq a \leq p-2$ Show: $g^a \mod{p}$ is a primitive root $\mod{p}$ $\Leftrightarrow$ gcd($a,p-1) = 1$ Ideas: $g^a \mod{p}$ is a primitive root if $ord(...
0
votes
0answers
63 views

About a variation of the primitive root idea.

Let $n $ be called a half primitive root mod ($m$) if $n^{\phi(m)/2} = 1$ mod($m$) and for any $t $ with $1 < t < \phi(m)/2$, $m$ does not divide $(n^t - 1)$. So the order of $n$ mod($m$) is $\...
0
votes
0answers
52 views

About primitive roots of $p$ less than $\frac{p-1}2$.

If all the residues of $p$, from $2$ to $\dfrac{p-1}2$ can be expressed as $(2^A)(3^B)(5^C) \pmod p$ for some integers $A$, $B$, $C$ then is it true at least one of $2$ or $3$ or $5$ is a primitive ...
2
votes
0answers
45 views

About primitive roots and ways of expressing them.

If $q$ is a primitive root mod $p$ and $q = (2^a)(3^b)(5^c)\pmod p$ for some $a,b,c$ all elements of integers then say that this $q$ has the 'form' $\{2,3,5\}(p)$. Then is it true all the residues $\...
4
votes
0answers
91 views

About primitive roots and primes.

For any odd prime $p$ there exists at least one prime $q < p$ such that $q$ is a primitive root $\text{mod } p$ ; is this true?
1
vote
1answer
1k views

Primitive Root mod 26 and 25?

I would live to calculate the primitive roots modulo 26 and modulo 25. My approach: 26 is not a prime number. But 26=2*13 are Prime numbers. So I calculated the primitive roots of them: Result for ...
2
votes
1answer
60 views

Discrete logarithm when $\alpha$ is not a primitve root

When a number $\alpha$ is a primitive root for a prime number $n$ then $\beta \equiv \alpha^{x} \mod n$ can be written as $x = \log_\alpha(\beta) \mod n-1 $. If $n$ is not a prime, the equation ...
0
votes
1answer
44 views

Primitive roots of $2^{16} + 1$ [duplicate]

I have a primitive root $ \alpha $ of a number $ p = 2^{16} + 1$. How can I show if $ \alpha^{3} $ and $\alpha^{14}$ are primitive roots as well?
7
votes
1answer
197 views

Find the last digit of the exponent $x$.

Let \begin{align} p&=396543857870745963499374527519378569849832249490600276007703072957912\cdots\\ &\phantom{=}8049490077183813353745228056691 \end{align} This number is a 100-digit prime ...
1
vote
1answer
55 views

Fermat's Little Theorem - Prim. Root - Find x

So I am studying for finals and I am not able to solve the problem: Let $p=3∗2^{11484018}−1$ be a prime with 3457035 digits. Find a positive integer $x$ so that $2^x \equiv 3 \mod p$ Any guidance ...
2
votes
1answer
48 views

Primitive roots for a number

I want to show if a number a is a primitive root$\pmod{n}$ Is there a way to show this without raising a to all the powers between 1 and n-1?
3
votes
2answers
2k views

Proving a number has no primitive roots

How do you prove an arbitrary number $n$ has no primitive roots without finding all numbers less than $n$ which are also coprime to $n$ and exhausting that none of the order of these numbers modulo $n$...