All Questions
Tagged with primitive-roots totient-function
24
questions
0
votes
0
answers
33
views
Question about a proof of $\phi(r)$ incongruent integers
Hello I have a particular question, about the proof of the following theorem:
Theorem: If $r|p-1$, with $p$ an odd prime, there are $\phi(r)$ incongruent integers which have order $r$ modulo $p$.
...
- 51
0
votes
1
answer
1k
views
which Numbers can have primitive roots? [duplicate]
I know that if $(a,n)=1,n>0$ and $a^{ϕ(n)}≡1\pmod n$, i.e, order of a $\bmod n$ is $ϕ(n)$, then $a$ is called the primitive root modulo $n$.
I want to know what are the possible values of $n$,
i....
0
votes
1
answer
119
views
Do primitive roots mod m always satisfy $\gcd(r^t,m)=1$?
I am confused about primitive roots. My text defines primitive roots as the solutions for $a$ of the equation $\operatorname{ord}_m a = \phi(m)$ where $\operatorname{ord}_m a$ is defined as the ...
- 426
1
vote
3
answers
95
views
If r is a primitive root mod m, then r is a primitive root $\pmod{\phi(m)}$?
Gerstein's Introduction to Mathematical Structures and Proofs offers the following proposition and corollary:
Suppose r is a primitive root mod m:
Prop 6.80: $log_r xy \equiv log_r x + log_r y$
...
- 426
1
vote
2
answers
384
views
If r is a primitive root, then the residue of $r^t$ is also a primitive root if $\gcd(t,\phi(m))=1$ where $\phi$ is Euler's totient
This is part ii of the proof of Proposition 6.77 of Gerstein's Introduction to Mathematical Structures and Proofs. I don't understand it. Here is how the discussion, and my understanding of it, go:
$r$...
- 426
0
votes
4
answers
49
views
For every $k \in \Bbb Z$ there is $0 \le x \le p-1$ such as $x^3\equiv k \pmod {p}$
This question is looking like an easy one but I have been trying to solve it for the last couple days and I haven't been able to prove it - so I need some help.
The question:
Let $p$ be a prime number,...
- 364
0
votes
1
answer
852
views
Primitive root modulo $2p$
The question: Let $a,p \in \Bbb N$,$ \ $ $p$ is an odd prime, $a$ is a primitive root modulo $p$. prove that:
if $a$ is odd, $a$ is primitive root modulo $2p$.
if $a$ is even, $a+p$ is primitive root ...
- 364
1
vote
1
answer
319
views
Prove that $a$ is primitive root modulo $p^2$
I really need to answer this question quickly for my homework due tomorrow:
Let $a,p \in \Bbb N$, $p$ is prime, $a$ is a primitive root modulo $p$ that $p^2\nmid (a^{p-1}-1)$.
Prove that $a$ is ...
- 364
0
votes
2
answers
399
views
Intro Number Theory—show gcd$(\phi(m), \phi(n)) > 1$ unless either $m$ or $n$ is $1$ or $2$
Problem:
Show gcd$(\phi(m), \phi(n)) > 1$ unless either $m$ or $n$ is $1$ or $2$, where
$\phi(x)$ is the Euler-phi function.
Hint: Use the fact that $\phi(a)$ is even for $a > 2$
...
- 379
1
vote
0
answers
192
views
Prove that numbers relatively prime to $n$ are congruent modulo $n$ to powers of primitive root of $n$
Suppose that we have $\gcd(a,n) = 1$ where $a$ is primitive root of $n$ and $\{a_1, a_2 .. a_{\phi(n)} \}$ are numbers less than $n$ which are relative prime to it. Show that this set of numbers is ...
- 1,334
0
votes
1
answer
47
views
Why is it sufficient to only check ${s/p_i}$ powers in finding primitive root?
In an answer to Finding a primitive root of a prime number,
Vadim only checks $\,a^{\large s/p_i}\bmod p\,$ to check a primitive root. It works but why it is sufficient just to check only the powers ${...
- 27
1
vote
0
answers
102
views
Is this a valid proof of Euler's product formula for the totient function?
I will attempt the proof using induction. But first, a lemma:
Lemma 1: If $ n = p^{\alpha} $, where $ p $ is prime and $ \alpha\in\mathbb{N} $, then $ \phi(n) = n(1-\frac{1}{p}) $.
$ \underline{...
- 71
-1
votes
1
answer
141
views
Does a number have a primitive root if and only if φ(n)=λ(n)?
From the Wikipedia article on root primitives:
In particular, for a to be a primitive root modulo n, φ(n) has to be the smallest power of a which is congruent to 1 modulo n.
Am I correct if I say ...
- 151
0
votes
1
answer
158
views
Primitive Roots and their orders
For this question, suppose $p = 659$, where $p$ is prime. I have found that, through computing $\phi(p-1)$, where $\phi ()$ is the Euler Tiotent Function. Here, there are a total of 276 primitive ...
- 1,597
1
vote
1
answer
131
views
Need some help with a proof about primitive roots.
I'm having trouble understanding this theorem:
If $g$ is a primitive root of $m$, then the remainders modulo $m$ of $g,g^2,...,g^{\varphi (m)}$ are the $\varphi (m)$ natural numbers that are ...
- 474