Find the Primitive Roots $mod 31$ The 2019 Stack Overflow Developer Survey Results Are InFinding a primitive root of a prime numberExactly $phi(phi(n))$ primitive roots modulo $n$What does “maximum order elements to mod n” mean for a number n without primitive roots modulo n?Number Theory: Modular Arithmetic Orders and Primitive RootsHow to find complete set of incongruent primitive roots mod 17Probability of Primitive Root (Mod 43)Primitive Roots mod a prime numberFind all primitive 8th roots of unity modulo 41.Primitive Roots and their ordersprimitive roots modulo 125Use primitive root to prove if $a^phi(m)/2equiv 1pmod m$ then $a$ is a quadratic residue modulo $m$.
What did it mean to "align" a radio?
Are there incongruent pythagorean triangles with the same perimeter and same area?
Shouldn't "much" here be used instead of "more"?
How technical should a Scrum Master be to effectively remove impediments?
One word riddle: Vowel in the middle
Is a "Democratic" Oligarchy-Style System Possible?
How come people say “Would of”?
Can you compress metal and what would be the consequences?
What is the meaning of the verb "bear" in this context?
Why do we hear so much about the Trump administration deciding to impose and then remove tariffs?
Is this app Icon Browser Safe/Legit?
Protecting Dualbooting Windows from dangerous code (like rm -rf)
A poker game description that does not feel gimmicky
What is the most effective way of iterating a std::vector and why?
Why can Shazam fly?
How to deal with fear of taking dependencies
Does the shape of a die affect the probability of a number being rolled?
Which Sci-Fi work first showed weapon of galactic-scale mass destruction?
Earliest use of the term "Galois extension"?
Output the Arecibo Message
What could be the right powersource for 15 seconds lifespan disposable giant chainsaw?
Can a flute soloist sit?
Have you ever entered Singapore using a different passport or name?
Do these rules for Critical Successes and Critical Failures seem Fair?
Find the Primitive Roots $mod 31$
The 2019 Stack Overflow Developer Survey Results Are InFinding a primitive root of a prime numberExactly $phi(phi(n))$ primitive roots modulo $n$What does “maximum order elements to mod n” mean for a number n without primitive roots modulo n?Number Theory: Modular Arithmetic Orders and Primitive RootsHow to find complete set of incongruent primitive roots mod 17Probability of Primitive Root (Mod 43)Primitive Roots mod a prime numberFind all primitive 8th roots of unity modulo 41.Primitive Roots and their ordersprimitive roots modulo 125Use primitive root to prove if $a^phi(m)/2equiv 1pmod m$ then $a$ is a quadratic residue modulo $m$.
$begingroup$
My approach:
There exist $phi(31-1) = phi(30) = 8$ primitive roots.
If $x^6 notequiv 1$,$x^10 notequiv 1$, and $x^15 notequiv 1$, then $x$ is a primitive root modulo $31$.
$x = 1, 2$ fails this but $x = 3$ passes this, thus $3$ is a primitive root.
I then know that $3^0, 3^1, 3^2, dots, 3^29$ is a residue system mod $31$.
How can I then determine which elements are the primitive roots of this set?
elementary-number-theory
edited Mar 23 at 21:47
Asaf Karagila♦
308k33441775
asked Mar 23 at 16:48
Bryden CBryden C
32619
$endgroup$
add a comment |
$begingroup$
My approach:
There exist $phi(31-1) = phi(30) = 8$ primitive roots.
If $x^6 notequiv 1$,$x^10 notequiv 1$, and $x^15 notequiv 1$, then $x$ is a primitive root modulo $31$.
$x = 1, 2$ fails this but $x = 3$ passes this, thus $3$ is a primitive root.
I then know that $3^0, 3^1, 3^2, dots, 3^29$ is a residue system mod $31$.
How can I then determine which elements are the primitive roots of this set?
elementary-number-theory
edited Mar 23 at 21:47
Asaf Karagila♦
308k33441775
asked Mar 23 at 16:48
Bryden CBryden C
32619
$endgroup$
$begingroup$
Well, $g=3^2$ isn't a primitive root because $gcd(2,30)=2$ and $g^15=1$, noting that $15=frac 302$. Do you see the pattern?
$endgroup$
– lulu
Mar 23 at 16:57
$begingroup$
Phrased differently, you say that you know that there are $varphi(30)=8$ primitive roots. How do you know that? The proof of that tells you how to find all the others, given one.
$endgroup$
– lulu
Mar 23 at 16:58
add a comment |
$begingroup$
My approach:
There exist $phi(31-1) = phi(30) = 8$ primitive roots.
If $x^6 notequiv 1$,$x^10 notequiv 1$, and $x^15 notequiv 1$, then $x$ is a primitive root modulo $31$.
$x = 1, 2$ fails this but $x = 3$ passes this, thus $3$ is a primitive root.
I then know that $3^0, 3^1, 3^2, dots, 3^29$ is a residue system mod $31$.
How can I then determine which elements are the primitive roots of this set?
elementary-number-theory
edited Mar 23 at 21:47
Asaf Karagila♦
308k33441775
asked Mar 23 at 16:48
Bryden CBryden C
32619
$endgroup$
My approach:
There exist $phi(31-1) = phi(30) = 8$ primitive roots.
If $x^6 notequiv 1$,$x^10 notequiv 1$, and $x^15 notequiv 1$, then $x$ is a primitive root modulo $31$.
$x = 1, 2$ fails this but $x = 3$ passes this, thus $3$ is a primitive root.
I then know that $3^0, 3^1, 3^2, dots, 3^29$ is a residue system mod $31$.
How can I then determine which elements are the primitive roots of this set?
elementary-number-theory
elementary-number-theory
edited Mar 23 at 21:47
Asaf Karagila♦
308k33441775
asked Mar 23 at 16:48
Bryden CBryden C
32619
edited Mar 23 at 21:47
Asaf Karagila♦
308k33441775
asked Mar 23 at 16:48
Bryden CBryden C
32619
edited Mar 23 at 21:47
Asaf Karagila♦
308k33441775
edited Mar 23 at 21:47
Asaf Karagila♦
308k33441775
edited Mar 23 at 21:47
Asaf Karagila♦
308k33441775
308k33441775
asked Mar 23 at 16:48
Bryden CBryden C
32619
asked Mar 23 at 16:48
Bryden CBryden C
32619
asked Mar 23 at 16:48
Bryden CBryden C
32619
32619
$begingroup$
Well, $g=3^2$ isn't a primitive root because $gcd(2,30)=2$ and $g^15=1$, noting that $15=frac 302$. Do you see the pattern?
$endgroup$
– lulu
Mar 23 at 16:57
$begingroup$
Phrased differently, you say that you know that there are $varphi(30)=8$ primitive roots. How do you know that? The proof of that tells you how to find all the others, given one.
$endgroup$
– lulu
Mar 23 at 16:58
add a comment |
$begingroup$
Well, $g=3^2$ isn't a primitive root because $gcd(2,30)=2$ and $g^15=1$, noting that $15=frac 302$. Do you see the pattern?
$endgroup$
– lulu
Mar 23 at 16:57
$begingroup$
Phrased differently, you say that you know that there are $varphi(30)=8$ primitive roots. How do you know that? The proof of that tells you how to find all the others, given one.
$endgroup$
– lulu
Mar 23 at 16:58
$begingroup$
Well, $g=3^2$ isn't a primitive root because $gcd(2,30)=2$ and $g^15=1$, noting that $15=frac 302$. Do you see the pattern?
$endgroup$
– lulu
Mar 23 at 16:57
$begingroup$
Well, $g=3^2$ isn't a primitive root because $gcd(2,30)=2$ and $g^15=1$, noting that $15=frac 302$. Do you see the pattern?
$endgroup$
– lulu
Mar 23 at 16:57
$begingroup$
Phrased differently, you say that you know that there are $varphi(30)=8$ primitive roots. How do you know that? The proof of that tells you how to find all the others, given one.
$endgroup$
– lulu
Mar 23 at 16:58
$begingroup$
Phrased differently, you say that you know that there are $varphi(30)=8$ primitive roots. How do you know that? The proof of that tells you how to find all the others, given one.
$endgroup$
– lulu
Mar 23 at 16:58
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
There are indeed $phi(phi (31))=8$ primitive roots modulo $31$ and you can find them as described here:
Finding a primitive root of a prime number
For example, $3^kequiv 1bmod 31$ only holds for $k=30$, if $1le kle 30$. Hence $3$ is a primitive root modulo $31$. Now compute the orders of powers of $3$.
answered Mar 23 at 16:57
Dietrich BurdeDietrich Burde
81.9k649107
$endgroup$
add a comment |
$begingroup$
Once you found one primitive root, the others are its powers which are relatively prime to $phi(31)=30$. The numbers in $0,1,2,...,29$ which are relatively prime to $30$ are $1,7,11,13,17,19,23,29$ and hence the primitive roots are $3,3^7,3^11,...,3^29$.
The reason why this is the case is the general formula $ord_n(a^k)=fracord_n(a)gcd(k,ord_n(a))$.
answered Mar 23 at 16:57
MarkMark
10.5k1622
$endgroup$
add a comment |
$begingroup$
I then know that $3^0,3^1,3^2,…,3^29$ is a residue system $mod 31$.
And you are sooo close.
$(3^k)^m = 3^mk$. So for $3^k$ to be a primitive root we need $mk$ to not be a multiple of $30$ for any natural $m < 30$.
In other words if $k$ is relatively prime to $30$.
In fact, that is precisely why we know there are $phi(30)$ primitive roots.
answered Mar 23 at 17:31
fleabloodfleablood
74k22891
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3159551%2ffind-the-primitive-roots-mod-31%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
There are indeed $phi(phi (31))=8$ primitive roots modulo $31$ and you can find them as described here:
Finding a primitive root of a prime number
For example, $3^kequiv 1bmod 31$ only holds for $k=30$, if $1le kle 30$. Hence $3$ is a primitive root modulo $31$. Now compute the orders of powers of $3$.
answered Mar 23 at 16:57
Dietrich BurdeDietrich Burde
81.9k649107
$endgroup$
add a comment |
$begingroup$
There are indeed $phi(phi (31))=8$ primitive roots modulo $31$ and you can find them as described here:
Finding a primitive root of a prime number
For example, $3^kequiv 1bmod 31$ only holds for $k=30$, if $1le kle 30$. Hence $3$ is a primitive root modulo $31$. Now compute the orders of powers of $3$.
answered Mar 23 at 16:57
Dietrich BurdeDietrich Burde
81.9k649107
$endgroup$
add a comment |
$begingroup$
There are indeed $phi(phi (31))=8$ primitive roots modulo $31$ and you can find them as described here:
Finding a primitive root of a prime number
For example, $3^kequiv 1bmod 31$ only holds for $k=30$, if $1le kle 30$. Hence $3$ is a primitive root modulo $31$. Now compute the orders of powers of $3$.
answered Mar 23 at 16:57
Dietrich BurdeDietrich Burde
81.9k649107
$endgroup$
There are indeed $phi(phi (31))=8$ primitive roots modulo $31$ and you can find them as described here:
Finding a primitive root of a prime number
For example, $3^kequiv 1bmod 31$ only holds for $k=30$, if $1le kle 30$. Hence $3$ is a primitive root modulo $31$. Now compute the orders of powers of $3$.
answered Mar 23 at 16:57
Dietrich BurdeDietrich Burde
81.9k649107
answered Mar 23 at 16:57
Dietrich BurdeDietrich Burde
81.9k649107
answered Mar 23 at 16:57
Dietrich BurdeDietrich Burde
81.9k649107
answered Mar 23 at 16:57
Dietrich BurdeDietrich Burde
81.9k649107
81.9k649107
add a comment |
add a comment |
$begingroup$
Once you found one primitive root, the others are its powers which are relatively prime to $phi(31)=30$. The numbers in $0,1,2,...,29$ which are relatively prime to $30$ are $1,7,11,13,17,19,23,29$ and hence the primitive roots are $3,3^7,3^11,...,3^29$.
The reason why this is the case is the general formula $ord_n(a^k)=fracord_n(a)gcd(k,ord_n(a))$.
answered Mar 23 at 16:57
MarkMark
10.5k1622
$endgroup$
add a comment |
$begingroup$
Once you found one primitive root, the others are its powers which are relatively prime to $phi(31)=30$. The numbers in $0,1,2,...,29$ which are relatively prime to $30$ are $1,7,11,13,17,19,23,29$ and hence the primitive roots are $3,3^7,3^11,...,3^29$.
The reason why this is the case is the general formula $ord_n(a^k)=fracord_n(a)gcd(k,ord_n(a))$.
answered Mar 23 at 16:57
MarkMark
10.5k1622
$endgroup$
add a comment |
$begingroup$
Once you found one primitive root, the others are its powers which are relatively prime to $phi(31)=30$. The numbers in $0,1,2,...,29$ which are relatively prime to $30$ are $1,7,11,13,17,19,23,29$ and hence the primitive roots are $3,3^7,3^11,...,3^29$.
The reason why this is the case is the general formula $ord_n(a^k)=fracord_n(a)gcd(k,ord_n(a))$.
answered Mar 23 at 16:57
MarkMark
10.5k1622
$endgroup$
Once you found one primitive root, the others are its powers which are relatively prime to $phi(31)=30$. The numbers in $0,1,2,...,29$ which are relatively prime to $30$ are $1,7,11,13,17,19,23,29$ and hence the primitive roots are $3,3^7,3^11,...,3^29$.
The reason why this is the case is the general formula $ord_n(a^k)=fracord_n(a)gcd(k,ord_n(a))$.
answered Mar 23 at 16:57
MarkMark
10.5k1622
answered Mar 23 at 16:57
MarkMark
10.5k1622
answered Mar 23 at 16:57
MarkMark
10.5k1622
answered Mar 23 at 16:57
MarkMark
10.5k1622
10.5k1622
add a comment |
add a comment |
$begingroup$
I then know that $3^0,3^1,3^2,…,3^29$ is a residue system $mod 31$.
And you are sooo close.
$(3^k)^m = 3^mk$. So for $3^k$ to be a primitive root we need $mk$ to not be a multiple of $30$ for any natural $m < 30$.
In other words if $k$ is relatively prime to $30$.
In fact, that is precisely why we know there are $phi(30)$ primitive roots.
answered Mar 23 at 17:31
fleabloodfleablood
74k22891
$endgroup$
add a comment |
$begingroup$
I then know that $3^0,3^1,3^2,…,3^29$ is a residue system $mod 31$.
And you are sooo close.
$(3^k)^m = 3^mk$. So for $3^k$ to be a primitive root we need $mk$ to not be a multiple of $30$ for any natural $m < 30$.
In other words if $k$ is relatively prime to $30$.
In fact, that is precisely why we know there are $phi(30)$ primitive roots.
answered Mar 23 at 17:31
fleabloodfleablood
74k22891
$endgroup$
add a comment |
$begingroup$
I then know that $3^0,3^1,3^2,…,3^29$ is a residue system $mod 31$.
And you are sooo close.
$(3^k)^m = 3^mk$. So for $3^k$ to be a primitive root we need $mk$ to not be a multiple of $30$ for any natural $m < 30$.
In other words if $k$ is relatively prime to $30$.
In fact, that is precisely why we know there are $phi(30)$ primitive roots.
answered Mar 23 at 17:31
fleabloodfleablood
74k22891
$endgroup$
I then know that $3^0,3^1,3^2,…,3^29$ is a residue system $mod 31$.
And you are sooo close.
$(3^k)^m = 3^mk$. So for $3^k$ to be a primitive root we need $mk$ to not be a multiple of $30$ for any natural $m < 30$.
In other words if $k$ is relatively prime to $30$.
In fact, that is precisely why we know there are $phi(30)$ primitive roots.
answered Mar 23 at 17:31
fleabloodfleablood
74k22891
answered Mar 23 at 17:31
fleabloodfleablood
74k22891
answered Mar 23 at 17:31
fleabloodfleablood
74k22891
answered Mar 23 at 17:31
fleabloodfleablood
74k22891
74k22891
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3159551%2ffind-the-primitive-roots-mod-31%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
Well, $g=3^2$ isn't a primitive root because $gcd(2,30)=2$ and $g^15=1$, noting that $15=frac 302$. Do you see the pattern?
$endgroup$
– lulu
Mar 23 at 16:57
$begingroup$
Phrased differently, you say that you know that there are $varphi(30)=8$ primitive roots. How do you know that? The proof of that tells you how to find all the others, given one.
$endgroup$
– lulu
Mar 23 at 16:58