Fdtxjr

How do you justify more code being written by following clean code practices?

is this saw blade faulty?

Imaginary part of expression too difficult to calculate

Isn't the word "experience" wrongly used in this context?

Does convergence of polynomials imply that of its coefficients?

PTIJ: Which Dr. Seuss books should one obtain?

How to test the sharpness of a knife?

Do people actually use the word "kaputt" in conversation?

Justification failure in beamer enumerate list

Why doesn't the chatan sign the ketubah?

What are the rules for concealing thieves' tools (or items in general)?

How are passwords stolen from companies if they only store hashes?

Turning a hard to access nut?

How can an organ that provides biological immortality be unable to regenerate?

How to find the largest number(s) in a list of elements, possibly non-unique?

Does the Shadow Magic sorcerer's Eyes of the Dark feature work on all Darkness spells or just his/her own?

TDE Master Key Rotation

Emojional cryptic crossword

CLI: Get information Ubuntu releases

Exit shell with shortcut (not typing exit) that closes session properly

Why are there no stars visible in cislunar space?

Have the tides ever turned twice on any open problem?

Is this Pascal's Matrix?

Why is this tree refusing to shed its dead leaves?

Let $p$ be a prime of the form $3k+2$. Show that if $x^3 equiv 1 pmod p$ then $x equiv 1 pmod p$.

Prove that $x^2 equiv -1 pmod p$ has no solutions if prime $p equiv 3 pmod 4$.Show that if $R_n$ is prime then $n$ must be prime.Show that $16$ is a perfect $8$th power modulo $p$ for any prime number $p$Show that $10^n(p-1)equiv 1pmod! 9p$ for $pge 7$Number Theory: $m^2equiv 1pmodp^n$If $a^p-1 equiv 1 pmod p$ and then $a^fracp-12 equiv 1$ or $p-1 pmod p$?Show that $a^i equiv a^j pmodm$ iff $i equiv j pmodd$Find solution of $x^p+1equiv1pmodp^q$, where p and q are primeProve that if $aequiv b pmod p^2-p$, then $a^aequiv b^b pmodp$ where $p$ is any prime and $a$ and $b$ are nonzero integers.Elementary Number Theory: Show that $3^10equiv 1 pmod11^2$.

3

$begingroup$

Let $p$ be a prime of the form $3k+2$. Show that if $x^3 equiv 1 pmod p$ then $x equiv 1 pmod p$.

What seems like and is probably an incredibly easy question and I'm struggling to get anywhere.

I've tried showing that since $p$ is prime and $p|x^3-1$ then either $p|x-1$ or $p|x^2+x+1$ so we're done if we can show that the latter case can never come about, however I'm struggling to show this. I'm doubtful this is the correct approach but I can't see anything else.

Any help is appreciated.

Thank you.

number-theory prime-numbers modular-arithmetic

share|cite|improve this question

edited Mar 13 at 4:33

Rócherz

2,9863821

asked Aug 27 '16 at 19:20

Aka_aka_aka_akAka_aka_aka_ak

935415

$endgroup$

add a comment | 

3

$begingroup$

Let $p$ be a prime of the form $3k+2$. Show that if $x^3 equiv 1 pmod p$ then $x equiv 1 pmod p$.

What seems like and is probably an incredibly easy question and I'm struggling to get anywhere.

I've tried showing that since $p$ is prime and $p|x^3-1$ then either $p|x-1$ or $p|x^2+x+1$ so we're done if we can show that the latter case can never come about, however I'm struggling to show this. I'm doubtful this is the correct approach but I can't see anything else.

Any help is appreciated.

Thank you.

number-theory prime-numbers modular-arithmetic

share|cite|improve this question

edited Mar 13 at 4:33

Rócherz

2,9863821

asked Aug 27 '16 at 19:20

Aka_aka_aka_akAka_aka_aka_ak

935415

$endgroup$

add a comment | 

$begingroup$

Let $p$ be a prime of the form $3k+2$. Show that if $x^3 equiv 1 pmod p$ then $x equiv 1 pmod p$.

What seems like and is probably an incredibly easy question and I'm struggling to get anywhere.

I've tried showing that since $p$ is prime and $p|x^3-1$ then either $p|x-1$ or $p|x^2+x+1$ so we're done if we can show that the latter case can never come about, however I'm struggling to show this. I'm doubtful this is the correct approach but I can't see anything else.

Any help is appreciated.

Thank you.

number-theory prime-numbers modular-arithmetic

share|cite|improve this question

edited Mar 13 at 4:33

Rócherz

2,9863821

asked Aug 27 '16 at 19:20

Aka_aka_aka_akAka_aka_aka_ak

935415

$endgroup$

share|cite|improve this question

edited Mar 13 at 4:33

Rócherz

2,9863821

asked Aug 27 '16 at 19:20

Aka_aka_aka_akAka_aka_aka_ak

935415

share|cite|improve this question

edited Mar 13 at 4:33

Rócherz

2,9863821

asked Aug 27 '16 at 19:20

Aka_aka_aka_akAka_aka_aka_ak

935415

edited Mar 13 at 4:33

Rócherz

2,9863821

edited Mar 13 at 4:33

Rócherz

2,9863821

asked Aug 27 '16 at 19:20

Aka_aka_aka_akAka_aka_aka_ak

935415

asked Aug 27 '16 at 19:20

Aka_aka_aka_akAka_aka_aka_ak

935415

3 Answers
3

active

oldest

votes

2

$begingroup$

Hint $, rm mod, p!:, 1 equiv x^largecolor#0a0 p-1 equiv x^large 1+3kequiv x(color#c00x^large 3)^large k equiv x, $ by $,color#c00x^large 3equiv 1. $ QED

Said conceptually: $ $ the order of $,x,$ is $,1,$ since it divides the coprimes $,color#c003,$ and $,color#0a0p!-!1 = 1+3k$

share|cite|improve this answer

edited Aug 27 '16 at 21:34

answered Aug 27 '16 at 21:19

Bill DubuqueBill Dubuque

212k29195654

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  That's a nice way to solve it.
  $endgroup$
  – quid♦
  Aug 28 '16 at 0:43
  

  
  
  
  

add a comment | 

1

$begingroup$

The approach is fine.

You can exclude the latter if you can show that $x^2 + x + 1 $ has no root modulo $p$. This is equivalent to its discriminant not being a quadratic residue modulo $p$. And this in turn follows by the congruence condition on $p$.

share|cite|improve this answer

answered Aug 27 '16 at 19:26

quid♦quid

37.2k95193

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Let me know if you want more computational details.
  $endgroup$
  – quid♦
  Aug 27 '16 at 19:26
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Ok thanks, I'll take another look in a minute, this will likely be enough, thank you.
  $endgroup$
  – Aka_aka_aka_ak
  Aug 27 '16 at 19:28
  

  
  
  
  

add a comment | 

1

$begingroup$

If $p$ is prime and $pmid x^3-1=(x-1)left(x^2+x+1right)$, then by Euclid's lemma either $pmid x-1$ or $pmid x^2+x+1$.

For contradiction, let $pmid x^2+x+1$ and $pequiv 2pmod 3$.

If $p=2$, then $2=pmid x^2+x+1=x(x+1)+1$, which is odd for all $xinmathbb Z$, contradiction.

If $p$ is odd, then $pmid 4left(x^2+x+1right)=(2x+1)^2+3$, so $(2x+1)^2equiv -3pmod p$, so $-3$ is a quadratic residue mod $p$, but this contradicts Quadratic Reciprocity.

share|cite|improve this answer

answered Aug 27 '16 at 19:34

user236182user236182

12k11333

$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%2f1905547%2flet-p-be-a-prime-of-the-form-3k2-show-that-if-x3-equiv-1-pmod-p-then%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

2

$begingroup$

Hint $, rm mod, p!:, 1 equiv x^largecolor#0a0 p-1 equiv x^large 1+3kequiv x(color#c00x^large 3)^large k equiv x, $ by $,color#c00x^large 3equiv 1. $ QED

Said conceptually: $ $ the order of $,x,$ is $,1,$ since it divides the coprimes $,color#c003,$ and $,color#0a0p!-!1 = 1+3k$

share|cite|improve this answer

edited Aug 27 '16 at 21:34

answered Aug 27 '16 at 21:19

Bill DubuqueBill Dubuque

212k29195654

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  That's a nice way to solve it.
  $endgroup$
  – quid♦
  Aug 28 '16 at 0:43
  

  
  
  
  

add a comment | 

2

$begingroup$

Hint $, rm mod, p!:, 1 equiv x^largecolor#0a0 p-1 equiv x^large 1+3kequiv x(color#c00x^large 3)^large k equiv x, $ by $,color#c00x^large 3equiv 1. $ QED

Said conceptually: $ $ the order of $,x,$ is $,1,$ since it divides the coprimes $,color#c003,$ and $,color#0a0p!-!1 = 1+3k$

share|cite|improve this answer

edited Aug 27 '16 at 21:34

answered Aug 27 '16 at 21:19

Bill DubuqueBill Dubuque

212k29195654

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  That's a nice way to solve it.
  $endgroup$
  – quid♦
  Aug 28 '16 at 0:43
  

  
  
  
  

add a comment | 

$begingroup$

Hint $, rm mod, p!:, 1 equiv x^largecolor#0a0 p-1 equiv x^large 1+3kequiv x(color#c00x^large 3)^large k equiv x, $ by $,color#c00x^large 3equiv 1. $ QED

Said conceptually: $ $ the order of $,x,$ is $,1,$ since it divides the coprimes $,color#c003,$ and $,color#0a0p!-!1 = 1+3k$

share|cite|improve this answer

edited Aug 27 '16 at 21:34

answered Aug 27 '16 at 21:19

Bill DubuqueBill Dubuque

212k29195654

$endgroup$

share|cite|improve this answer

edited Aug 27 '16 at 21:34

answered Aug 27 '16 at 21:19

Bill DubuqueBill Dubuque

212k29195654

answered Aug 27 '16 at 21:19

Bill DubuqueBill Dubuque

212k29195654

answered Aug 27 '16 at 21:19

Bill DubuqueBill Dubuque

212k29195654

1

$begingroup$

The approach is fine.

You can exclude the latter if you can show that $x^2 + x + 1 $ has no root modulo $p$. This is equivalent to its discriminant not being a quadratic residue modulo $p$. And this in turn follows by the congruence condition on $p$.

share|cite|improve this answer

answered Aug 27 '16 at 19:26

quid♦quid

37.2k95193

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Let me know if you want more computational details.
  $endgroup$
  – quid♦
  Aug 27 '16 at 19:26
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Ok thanks, I'll take another look in a minute, this will likely be enough, thank you.
  $endgroup$
  – Aka_aka_aka_ak
  Aug 27 '16 at 19:28
  

  
  
  
  

add a comment | 

1

$begingroup$

The approach is fine.

You can exclude the latter if you can show that $x^2 + x + 1 $ has no root modulo $p$. This is equivalent to its discriminant not being a quadratic residue modulo $p$. And this in turn follows by the congruence condition on $p$.

share|cite|improve this answer

answered Aug 27 '16 at 19:26

quid♦quid

37.2k95193

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Let me know if you want more computational details.
  $endgroup$
  – quid♦
  Aug 27 '16 at 19:26
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Ok thanks, I'll take another look in a minute, this will likely be enough, thank you.
  $endgroup$
  – Aka_aka_aka_ak
  Aug 27 '16 at 19:28
  

  
  
  
  

add a comment | 

$begingroup$

The approach is fine.

You can exclude the latter if you can show that $x^2 + x + 1 $ has no root modulo $p$. This is equivalent to its discriminant not being a quadratic residue modulo $p$. And this in turn follows by the congruence condition on $p$.

share|cite|improve this answer

answered Aug 27 '16 at 19:26

quid♦quid

37.2k95193

$endgroup$

share|cite|improve this answer

answered Aug 27 '16 at 19:26

quid♦quid

37.2k95193

answered Aug 27 '16 at 19:26

quid♦quid

37.2k95193

answered Aug 27 '16 at 19:26

quid♦quid

37.2k95193

1

$begingroup$

If $p$ is prime and $pmid x^3-1=(x-1)left(x^2+x+1right)$, then by Euclid's lemma either $pmid x-1$ or $pmid x^2+x+1$.

For contradiction, let $pmid x^2+x+1$ and $pequiv 2pmod 3$.

If $p=2$, then $2=pmid x^2+x+1=x(x+1)+1$, which is odd for all $xinmathbb Z$, contradiction.

If $p$ is odd, then $pmid 4left(x^2+x+1right)=(2x+1)^2+3$, so $(2x+1)^2equiv -3pmod p$, so $-3$ is a quadratic residue mod $p$, but this contradicts Quadratic Reciprocity.

share|cite|improve this answer

answered Aug 27 '16 at 19:34

user236182user236182

12k11333

$endgroup$

add a comment | 

1

$begingroup$

If $p$ is prime and $pmid x^3-1=(x-1)left(x^2+x+1right)$, then by Euclid's lemma either $pmid x-1$ or $pmid x^2+x+1$.

For contradiction, let $pmid x^2+x+1$ and $pequiv 2pmod 3$.

If $p=2$, then $2=pmid x^2+x+1=x(x+1)+1$, which is odd for all $xinmathbb Z$, contradiction.

If $p$ is odd, then $pmid 4left(x^2+x+1right)=(2x+1)^2+3$, so $(2x+1)^2equiv -3pmod p$, so $-3$ is a quadratic residue mod $p$, but this contradicts Quadratic Reciprocity.

share|cite|improve this answer

answered Aug 27 '16 at 19:34

user236182user236182

12k11333

$endgroup$

add a comment | 

$begingroup$

If $p$ is prime and $pmid x^3-1=(x-1)left(x^2+x+1right)$, then by Euclid's lemma either $pmid x-1$ or $pmid x^2+x+1$.

For contradiction, let $pmid x^2+x+1$ and $pequiv 2pmod 3$.

If $p=2$, then $2=pmid x^2+x+1=x(x+1)+1$, which is odd for all $xinmathbb Z$, contradiction.

If $p$ is odd, then $pmid 4left(x^2+x+1right)=(2x+1)^2+3$, so $(2x+1)^2equiv -3pmod p$, so $-3$ is a quadratic residue mod $p$, but this contradicts Quadratic Reciprocity.

share|cite|improve this answer

answered Aug 27 '16 at 19:34

user236182user236182

12k11333

$endgroup$

share|cite|improve this answer

answered Aug 27 '16 at 19:34

user236182user236182

12k11333

answered Aug 27 '16 at 19:34

user236182user236182

12k11333

answered Aug 27 '16 at 19:34

user236182user236182

12k11333