Find the Primitive Roots $mod 31$
$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
$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
$endgroup$
$begingroup$
Well, $g=3^2$ isn't a primitive root because $gcd(2,30)=2$ and $g^{15}=1$, noting that $15=frac {30}2$. Do you see the pattern?
$endgroup$
– lulu
2 days ago
$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
2 days ago
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
$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 2 days ago
Asaf Karagila♦
307k33439770
307k33439770
asked 2 days ago
Bryden CBryden C
31919
31919
$begingroup$
Well, $g=3^2$ isn't a primitive root because $gcd(2,30)=2$ and $g^{15}=1$, noting that $15=frac {30}2$. Do you see the pattern?
$endgroup$
– lulu
2 days ago
$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
2 days ago
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 {30}2$. Do you see the pattern?
$endgroup$
– lulu
2 days ago
$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
2 days ago
$begingroup$
Well, $g=3^2$ isn't a primitive root because $gcd(2,30)=2$ and $g^{15}=1$, noting that $15=frac {30}2$. Do you see the pattern?
$endgroup$
– lulu
2 days ago
$begingroup$
Well, $g=3^2$ isn't a primitive root because $gcd(2,30)=2$ and $g^{15}=1$, noting that $15=frac {30}2$. Do you see the pattern?
$endgroup$
– lulu
2 days ago
$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
2 days ago
$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
2 days ago
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$.
$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)=frac{ord_n(a)}{gcd(k,ord_n(a))}$.
$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.
$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$.
$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$.
$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$.
$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 2 days ago
Dietrich BurdeDietrich Burde
81.3k648106
81.3k648106
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)=frac{ord_n(a)}{gcd(k,ord_n(a))}$.
$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)=frac{ord_n(a)}{gcd(k,ord_n(a))}$.
$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)=frac{ord_n(a)}{gcd(k,ord_n(a))}$.
$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)=frac{ord_n(a)}{gcd(k,ord_n(a))}$.
answered 2 days ago
MarkMark
10.4k1622
10.4k1622
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.
$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.
$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.
$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 2 days ago
fleabloodfleablood
73.4k22791
73.4k22791
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 {30}2$. Do you see the pattern?
$endgroup$
– lulu
2 days ago
$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
2 days ago