All Questions
Tagged with primitive-roots quadratic-residues
34
questions
1
vote
1
answer
952
views
A primitive root modulo p is a primitive root modulo $p^2$ if and only if $g^{p-1} \not\equiv 1 \mod{p^2}$
$p$ is an odd prime. I'm starting with number theory and I'm completly stuck with this question. In general, I don't really know how to approach the proves. Then I'm also supposed to prove that either ...
- 283
0
votes
1
answer
761
views
Showing that $p$ is a Fermat prime if and only if every quadratic non-residue mod $p$ is also a primitive root mod $p$ [duplicate]
I want to show that $p$ is a Fermat prime $\iff$ every quadratic non-residue of $p$ is also a primitive root mod $p$
These are some facts that I know:
$F_n = 2^{2^n} + 1$
Every prime divisor $p$ of $...
- 578
2
votes
1
answer
57
views
Given a prime number a of the form 29 (mod 40) or 40k + 29. Show that the prime a cannot divide any integer of the form n^2 + 10.
Not sure how to approach this problem. First idea was proof by contradiction. Assume a divides n^2 + 10 and proceed from there. I couldn't reach a substantial conclusion from this approach.
- 21
0
votes
1
answer
61
views
Testing for primitive roots using quadratic non residue and Jacobi symbol
Is this always true for all cases??
$a$ is a primitive root $modulo$ $n$ $⇒$ $\left(\dfrac{a}{n}\right) = -1$
Is the converse also always true?
$\left(\dfrac{a}{n}\right)$ $= -1$ $⇒$ $a$ is a ...
- 109
0
votes
1
answer
183
views
Find the number of integer pairs 0 ≤ a, b ≤ 100 such that a^20 ≡ b^50 (mod 101). Need help with understanding solution
Find the number of integer pairs 0 ≤ a, b ≤ 100 such that $a^{20}$ ≡ $b^{50} \pmod {101}$.
Here is the solution: "Since is prime, there exists a primitive
root g in modulo 101. For some integers x ...
- 11
1
vote
1
answer
77
views
What is the size of the set $\{ 0^{42}\pmod{101}, 1^{42}\pmod{101}, 2^{42} \pmod{101},...,100^{42}\pmod{101}\}$
What is the size of the set $\{ 0^{42}\pmod{101}, 1^{42}\pmod{101}, 2^{42} \pmod{101},...,100^{42}\pmod{101}\}$? How would you even start the problem? By the way, I got this problem from my number ...
- 147
2
votes
1
answer
310
views
Find the sum of quadratic residues modulo $101$
Given that $2$ is a primitive root (mod $101$), find the remainder when the sum of all the quadratic residues (mod $101$) is divided by $101$. A quadratic residue $r$ is a residue (mod $101$) such ...
- 147
0
votes
0
answers
117
views
Quadratic residue and cubic polynomials
The question is simple: Can
$\sum_{x=0}^{p-1} (\frac{ax^3 +bx^2 +cx +d}{p} )$
be expressed as a closed form ?
(It's a Legendre Symbol)
- 39
1
vote
0
answers
36
views
Quadratic residue of composite numbers [duplicate]
If $a$ is a quadratic residue modulo $m$ and $ab \equiv 1 \;(\bmod\;m)$. Prove that $b$ is also quadratic residue modulo $m$.
The above question is from Niven & Zuckerman " Introduction to the ...
1
vote
1
answer
794
views
The product of both quadratic residues and non residues in a residue system modulo prime p
Compute the product of all the quadratic residues $a$ where $(a, p) = 1$ in a residue system modulo $p$ where $p$ is prime. Similarly, compute the product of all the quadratic nonresidues in a residue ...
- 33
1
vote
2
answers
422
views
a) and b) Suppose a = primitive root mod p for an odd prime p. Show that $\left(\frac{a}{p}\right)$ = -1
I understand how to evaluate Legendre symbols when given discrete numbers.
For example the Legendre symbol for the following:
$\left(\frac{3}{105953}\right)=\left(\frac{105953}{3}\right)=\left(\frac{2}...
- 131
1
vote
1
answer
35
views
Can at least one primitive root $w$ of $N$ be expressed as $a^2-b$, where $(b|N)=-1$
I am stuck on a thought experiment: can any (or for that matter, at least one) primitive root $w$ of $N$, $N$ prime, be expressed as $w=a^2-b$, where $(b|N)=-1$, and $a,b\in\mathbb{N}$.
We know that ...
- 1,950
1
vote
1
answer
602
views
Use primitive root to prove if $a^{\phi(m)/2}\equiv 1\pmod m$ then $a$ is a quadratic residue modulo $m$.
This is trivial in arguments of quadratic residues, but I couldn't solve it using primitive root. The problem seeks to use primitive root to be proved.
Problem: Let $m>2$ be an integer having a ...
- 1,867
0
votes
0
answers
88
views
Relation between residues and primitive roots modulo $p$
I got a very satisfiying answer to my question on the relation between primeness and co-primeness of numbers which can be defined in a somehow symmetric way:
$n$ is prime iff
$$(\forall xy)\ n\ |\ ...
- 18.2k
3
votes
1
answer
767
views
A question about a primitive root mod $p=2^{2^k}+1$, where $p$ is prime.
Let $p=2^{2^k}+1$ be a prime where $k\ge1$. Prove that the set of quadratic non-residues mod $p$ is the same as the set of primitive roots mod $p$. Use this to show that $7$ is a primitive root mod $p$...
