Mrthdrb

Is there a word to describe the feeling of being transfixed out of horror?

Some numbers are more equivalent than others

Folder comparison

A Permanent Norse Presence in America

Is it improper etiquette to ask your opponent what his/her rating is before the game?

Why in book's example is used 言葉(ことば) instead of 言語(げんご)?

How do I implement a file system driver driver in Linux?

THT: What is a squared annular “ring”?

When quoting, must I also copy hyphens used to divide words that continue on the next line?

Is possible to search in vim history?

How do I repair my stair bannister?

Can I rely on this github repository files?

What is the gram­mat­i­cal term for “‑ed” words like these?

Query about absorption line spectra

Fly on a jet pack vs fly with a jet pack?

Bob has never been a M before

How will losing mobility of one hand affect my career as a programmer?

How can Trident be so inexpensive? Will it orbit Triton or just do a (slow) flyby?

Can I sign legal documents with a smiley face?

Is it possible to have a strip of cold climate in the middle of a planet?

What does this horizontal bar at the first measure mean?

MAXDOP Settings for SQL Server 2014

If a character with the Alert feat rolls a crit fail on their Perception check, are they surprised?

Using a siddur to Daven from in a seforim store

Find the Primitive Roots $mod 31$

Finding 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$.

2

$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

share|cite|improve this question

edited yesterday

Asaf Karagila♦

307k33438770

asked yesterday

Bryden CBryden C

31919

$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
  yesterday
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  yesterday
  

  
  
  
  

add a comment | 

2

$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

share|cite|improve this question

edited yesterday

Asaf Karagila♦

307k33438770

asked yesterday

Bryden CBryden C

31919

$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
  yesterday
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  yesterday
  

  
  
  
  

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

share|cite|improve this question

edited yesterday

Asaf Karagila♦

307k33438770

asked yesterday

Bryden CBryden C

31919

$endgroup$

share|cite|improve this question

edited yesterday

Asaf Karagila♦

307k33438770

asked yesterday

Bryden CBryden C

31919

share|cite|improve this question

edited yesterday

Asaf Karagila♦

307k33438770

asked yesterday

Bryden CBryden C

31919

edited yesterday

Asaf Karagila♦

307k33438770

edited yesterday

Asaf Karagila♦

307k33438770

asked yesterday

Bryden CBryden C

31919

asked yesterday

Bryden CBryden C

31919

3 Answers
3

active

oldest

votes

3

$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$.

share|cite|improve this answer

answered yesterday

Dietrich BurdeDietrich Burde

81.2k648106

$endgroup$

add a comment | 

2

$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))$.

share|cite|improve this answer

answered yesterday

MarkMark

10.4k1622

$endgroup$

add a comment | 

2

$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.

share|cite|improve this answer

answered yesterday

fleabloodfleablood

73.1k22790

$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
);



);

draft saved

draft discarded

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

Name

Email

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

Name

Email

Required, but never shown

3

$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$.

share|cite|improve this answer

answered yesterday

Dietrich BurdeDietrich Burde

81.2k648106

$endgroup$

add a comment | 

3

$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$.

share|cite|improve this answer

answered yesterday

Dietrich BurdeDietrich Burde

81.2k648106

$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$.

share|cite|improve this answer

answered yesterday

Dietrich BurdeDietrich Burde

81.2k648106

$endgroup$

share|cite|improve this answer

answered yesterday

Dietrich BurdeDietrich Burde

81.2k648106

answered yesterday

Dietrich BurdeDietrich Burde

81.2k648106

answered yesterday

Dietrich BurdeDietrich Burde

81.2k648106

2

$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))$.

share|cite|improve this answer

answered yesterday

MarkMark

10.4k1622

$endgroup$

add a comment | 

2

$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))$.

share|cite|improve this answer

answered yesterday

MarkMark

10.4k1622

$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))$.

share|cite|improve this answer

answered yesterday

MarkMark

10.4k1622

$endgroup$

share|cite|improve this answer

answered yesterday

MarkMark

10.4k1622

answered yesterday

MarkMark

10.4k1622

answered yesterday

MarkMark

10.4k1622

2

$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.

share|cite|improve this answer

answered yesterday

fleabloodfleablood

73.1k22790

$endgroup$

add a comment | 

2

$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.

share|cite|improve this answer

answered yesterday

fleabloodfleablood

73.1k22790

$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.

share|cite|improve this answer

answered yesterday

fleabloodfleablood

73.1k22790

$endgroup$

share|cite|improve this answer

answered yesterday

fleabloodfleablood

73.1k22790

answered yesterday

fleabloodfleablood

73.1k22790

answered yesterday

fleabloodfleablood

73.1k22790