Ygtjki

What does the Rambam mean when he says that the planets have souls?

How do I repair my stair bannister?

Generating adjacency matrices from isomorphic graphs

Open a doc from terminal, but not by its name

Difference between -| and |- in TikZ

How should I respond when I lied about my education and the company finds out through background check?

Could the E-bike drivetrain wear down till needing replacement after 400 km?

Why does the integral domain "being trapped between a finite field extension" implies that it is a field?

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

Does the Mind Blank spell prevent the target from being frightened?

Can somebody explain Brexit in a few child-proof sentences?

What linear sensor for a keyboard?

Engineer refusing to file/disclose patents

My friend sent me a screenshot of a transaction hash, but when I search for it I find divergent data. What happened?

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

Could solar power be utilized and substitute coal in the 19th century?

Why did the EU agree to delay the Brexit deadline?

Is XSS in canonical link possible?

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

Is it possible to use .desktop files to open local pdf files on specific pages with a browser?

Varistor? Purpose and principle

THT: What is a squared annular “ring”?

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

Can I Retrieve Email Addresses from BCC?

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.5k1622

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

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

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

share|cite|improve this answer

answered yesterday

MarkMark

10.5k1622

$endgroup$

share|cite|improve this answer

answered yesterday

MarkMark

10.5k1622

answered yesterday

MarkMark

10.5k1622

answered yesterday

MarkMark

10.5k1622

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.2k22790

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

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

$endgroup$

share|cite|improve this answer

answered yesterday

fleabloodfleablood

73.2k22790

answered yesterday

fleabloodfleablood

73.2k22790

answered yesterday

fleabloodfleablood

73.2k22790