$ord_p(a)=2 iff aequiv -1 mod p$ The 2019 Stack Overflow Developer Survey Results Are InSuppose $p$ is an odd prime. Show that $x^4 equiv-1$ (mod $p$) has a solution if and only if $p equiv1$ (mod $8$).Why are the congruences $p^2-1 equiv 0(mod 8)$ and $p^e equiv 1 + e(p-1) (mod 4)$ for odd prime $p$ and $e ge 1$ true?Let $p > 3$ be a prime number. Show that $x^2 equiv −3mod p$ is solvable iff $pequiv 1mod 6$.Show that if $ab equiv 1 mod m$ then $textord(a) = textord(b)$Suppose that $gcd(a,n)= 1$. Prove that $a^m equiv 1 pmod n$ iff $ord(a,n) mid m$Applying Fermat’s Little Theorem to $g^fracp-12$ (mod $p$).$x^2 equiv a mod p$, $ x^2 equiv b mod p$, and $x^2 equiv ab mod p$, prove either all three are solvable or exactly one$gcd(a, 63) = 1$ implies $a^7 equiv a mod 63$?Is $x^2 equiv 1 pmodp^k iff x equiv pm 1 pmod p^k$ for odd prime $p$?Let $p$ be an odd prime and let $i ≥ 0$. Show that $2^i$ $notequiv$ $2^p+i$ (mod p).
How do PCB vias affect signal quality?
How to display lines in a file like ls displays files in a directory?
How to obtain a position of last non-zero element
If I score a critical hit on an 18 or higher, what are my chances of getting a critical hit if I roll 3d20?
Inverse Relationship Between Precision and Recall
What is this sharp, curved notch on my knife for?
Output the Arecibo Message
What is the motivation for a law requiring 2 parties to consent for recording a conversation
How to charge AirPods to keep battery healthy?
The difference between dialogue marks
Likelihood that a superbug or lethal virus could come from a landfill
APIPA and LAN Broadcast Domain
Are there any other methods to apply to solving simultaneous equations?
Star Trek - X-shaped Item on Regula/Orbital Office Starbases
How much of the clove should I use when using big garlic heads?
What does もの mean in this sentence?
Can an undergraduate be advised by a professor who is very far away?
Cooking pasta in a water boiler
Is it a good practice to use a static variable in a Test Class and use that in the actual class instead of Test.isRunningTest()?
What could be the right powersource for 15 seconds lifespan disposable giant chainsaw?
How did passengers keep warm on sail ships?
Deal with toxic manager when you can't quit
Geography at the pixel level
Is an up-to-date browser secure on an out-of-date OS?
$ord_p(a)=2 iff aequiv -1 mod p$
The 2019 Stack Overflow Developer Survey Results Are InSuppose $p$ is an odd prime. Show that $x^4 equiv-1$ (mod $p$) has a solution if and only if $p equiv1$ (mod $8$).Why are the congruences $p^2-1 equiv 0(mod 8)$ and $p^e equiv 1 + e(p-1) (mod 4)$ for odd prime $p$ and $e ge 1$ true?Let $p > 3$ be a prime number. Show that $x^2 equiv −3mod p$ is solvable iff $pequiv 1mod 6$.Show that if $ab equiv 1 mod m$ then $textord(a) = textord(b)$Suppose that $gcd(a,n)= 1$. Prove that $a^m equiv 1 pmod n$ iff $ord(a,n) mid m$Applying Fermat’s Little Theorem to $g^fracp-12$ (mod $p$).$x^2 equiv a mod p$, $ x^2 equiv b mod p$, and $x^2 equiv ab mod p$, prove either all three are solvable or exactly one$gcd(a, 63) = 1$ implies $a^7 equiv a mod 63$?Is $x^2 equiv 1 pmodp^k iff x equiv pm 1 pmod p^k$ for odd prime $p$?Let $p$ be an odd prime and let $i ≥ 0$. Show that $2^i$ $notequiv$ $2^p+i$ (mod p).
$begingroup$
a) Let $p$ be an odd prime. Prove that:
$$textord_p(a)=2 iff aequiv -1 mod p$$
My attempt:
Assume that $textord_p(a)=2$, then
$a^2equiv 1 mod p$
$pmid a^2-1$
$pmid(a-1)(a+1)$
$pmid a-1$ or $pmid a+1$
If $pmid a-1$ then $aequiv 1 mod p$
Which contradicts that $textord_p(a)=2$
Therefore, we must have $aequiv -1 mod p$.
Now, assume that $aequiv -1 mod p$
Then $a^2 equiv 1 mod p$. Now, I think we must show that $2$, is the least positive integer satisfying the last congruence. This is equivalent to showing, that $anot equiv 1 mod p$. Since $aequiv -1 mod p$, then $anot equiv 1 mod p$. Is that true, please?
b) Suppose that $textord_n (a)=n-1$, prove that n is a prime number.
My attempt:
$textord_n (a)=n-1 implies a^n-1 equiv 1 mod n$
Then and by the converse of the Fermat’s little theorem, we have that $n$ is a prime number. [notice that $(a,n)=1$].
Is that true, please?
Thank you.
abstract-algebra number-theory modular-arithmetic
edited Mar 31 at 0:09
Roddy MacPhee
767118
asked Mar 30 at 22:51
DimaDima
873616
$endgroup$
|
show 3 more comments
$begingroup$
a) Let $p$ be an odd prime. Prove that:
$$textord_p(a)=2 iff aequiv -1 mod p$$
My attempt:
Assume that $textord_p(a)=2$, then
$a^2equiv 1 mod p$
$pmid a^2-1$
$pmid(a-1)(a+1)$
$pmid a-1$ or $pmid a+1$
If $pmid a-1$ then $aequiv 1 mod p$
Which contradicts that $textord_p(a)=2$
Therefore, we must have $aequiv -1 mod p$.
Now, assume that $aequiv -1 mod p$
Then $a^2 equiv 1 mod p$. Now, I think we must show that $2$, is the least positive integer satisfying the last congruence. This is equivalent to showing, that $anot equiv 1 mod p$. Since $aequiv -1 mod p$, then $anot equiv 1 mod p$. Is that true, please?
b) Suppose that $textord_n (a)=n-1$, prove that n is a prime number.
My attempt:
$textord_n (a)=n-1 implies a^n-1 equiv 1 mod n$
Then and by the converse of the Fermat’s little theorem, we have that $n$ is a prime number. [notice that $(a,n)=1$].
Is that true, please?
Thank you.
abstract-algebra number-theory modular-arithmetic
edited Mar 31 at 0:09
Roddy MacPhee
767118
asked Mar 30 at 22:51
DimaDima
873616
$endgroup$
1
$begingroup$
Yes, it could be possible only with $p=2$, and you suppose $p$ is odd.
$endgroup$
– Bernard
Mar 30 at 22:54
$begingroup$
@Bernard Thank you so much.
$endgroup$
– Dima
Mar 30 at 22:59
$begingroup$
You're welcome! Always glad to help!
$endgroup$
– Bernard
Mar 30 at 23:00
1
$begingroup$
B.t.w., non-prime numbers which satisfy that $a^n-1equiv 1$ for all $a$ coprime to $n$ are called *Carmichael numbers. The smallest Carmichael number is $561=3cdot 11cdot 17$.
$endgroup$
– Bernard
Mar 30 at 23:10
$begingroup$
" Now, I think we must show that 2, is the least positive integer satisfying the last congruence." uh.... he only positive integer smaller is $1$.... Sometimes one of the directions in an if and only if proof is self evident. This is one of those times.
$endgroup$
– fleablood
Mar 31 at 1:10
|
show 3 more comments
$begingroup$
a) Let $p$ be an odd prime. Prove that:
$$textord_p(a)=2 iff aequiv -1 mod p$$
My attempt:
Assume that $textord_p(a)=2$, then
$a^2equiv 1 mod p$
$pmid a^2-1$
$pmid(a-1)(a+1)$
$pmid a-1$ or $pmid a+1$
If $pmid a-1$ then $aequiv 1 mod p$
Which contradicts that $textord_p(a)=2$
Therefore, we must have $aequiv -1 mod p$.
Now, assume that $aequiv -1 mod p$
Then $a^2 equiv 1 mod p$. Now, I think we must show that $2$, is the least positive integer satisfying the last congruence. This is equivalent to showing, that $anot equiv 1 mod p$. Since $aequiv -1 mod p$, then $anot equiv 1 mod p$. Is that true, please?
b) Suppose that $textord_n (a)=n-1$, prove that n is a prime number.
My attempt:
$textord_n (a)=n-1 implies a^n-1 equiv 1 mod n$
Then and by the converse of the Fermat’s little theorem, we have that $n$ is a prime number. [notice that $(a,n)=1$].
Is that true, please?
Thank you.
abstract-algebra number-theory modular-arithmetic
edited Mar 31 at 0:09
Roddy MacPhee
767118
asked Mar 30 at 22:51
DimaDima
873616
$endgroup$
a) Let $p$ be an odd prime. Prove that:
$$textord_p(a)=2 iff aequiv -1 mod p$$
My attempt:
Assume that $textord_p(a)=2$, then
$a^2equiv 1 mod p$
$pmid a^2-1$
$pmid(a-1)(a+1)$
$pmid a-1$ or $pmid a+1$
If $pmid a-1$ then $aequiv 1 mod p$
Which contradicts that $textord_p(a)=2$
Therefore, we must have $aequiv -1 mod p$.
Now, assume that $aequiv -1 mod p$
Then $a^2 equiv 1 mod p$. Now, I think we must show that $2$, is the least positive integer satisfying the last congruence. This is equivalent to showing, that $anot equiv 1 mod p$. Since $aequiv -1 mod p$, then $anot equiv 1 mod p$. Is that true, please?
b) Suppose that $textord_n (a)=n-1$, prove that n is a prime number.
My attempt:
$textord_n (a)=n-1 implies a^n-1 equiv 1 mod n$
Then and by the converse of the Fermat’s little theorem, we have that $n$ is a prime number. [notice that $(a,n)=1$].
Is that true, please?
Thank you.
abstract-algebra number-theory modular-arithmetic
abstract-algebra number-theory modular-arithmetic
edited Mar 31 at 0:09
Roddy MacPhee
767118
asked Mar 30 at 22:51
DimaDima
873616
edited Mar 31 at 0:09
Roddy MacPhee
767118
asked Mar 30 at 22:51
DimaDima
873616
edited Mar 31 at 0:09
Roddy MacPhee
767118
edited Mar 31 at 0:09
Roddy MacPhee
767118
edited Mar 31 at 0:09
Roddy MacPhee
767118
767118
asked Mar 30 at 22:51
DimaDima
873616
asked Mar 30 at 22:51
DimaDima
873616
asked Mar 30 at 22:51
DimaDima
873616
873616
1
$begingroup$
Yes, it could be possible only with $p=2$, and you suppose $p$ is odd.
$endgroup$
– Bernard
Mar 30 at 22:54
$begingroup$
@Bernard Thank you so much.
$endgroup$
– Dima
Mar 30 at 22:59
$begingroup$
You're welcome! Always glad to help!
$endgroup$
– Bernard
Mar 30 at 23:00
1
$begingroup$
B.t.w., non-prime numbers which satisfy that $a^n-1equiv 1$ for all $a$ coprime to $n$ are called *Carmichael numbers. The smallest Carmichael number is $561=3cdot 11cdot 17$.
$endgroup$
– Bernard
Mar 30 at 23:10
$begingroup$
" Now, I think we must show that 2, is the least positive integer satisfying the last congruence." uh.... he only positive integer smaller is $1$.... Sometimes one of the directions in an if and only if proof is self evident. This is one of those times.
$endgroup$
– fleablood
Mar 31 at 1:10
|
show 3 more comments
1
$begingroup$
Yes, it could be possible only with $p=2$, and you suppose $p$ is odd.
$endgroup$
– Bernard
Mar 30 at 22:54
$begingroup$
@Bernard Thank you so much.
$endgroup$
– Dima
Mar 30 at 22:59
$begingroup$
You're welcome! Always glad to help!
$endgroup$
– Bernard
Mar 30 at 23:00
1
$begingroup$
B.t.w., non-prime numbers which satisfy that $a^n-1equiv 1$ for all $a$ coprime to $n$ are called *Carmichael numbers. The smallest Carmichael number is $561=3cdot 11cdot 17$.
$endgroup$
– Bernard
Mar 30 at 23:10
$begingroup$
" Now, I think we must show that 2, is the least positive integer satisfying the last congruence." uh.... he only positive integer smaller is $1$.... Sometimes one of the directions in an if and only if proof is self evident. This is one of those times.
$endgroup$
– fleablood
Mar 31 at 1:10
1
1
$begingroup$
Yes, it could be possible only with $p=2$, and you suppose $p$ is odd.
$endgroup$
– Bernard
Mar 30 at 22:54
$begingroup$
Yes, it could be possible only with $p=2$, and you suppose $p$ is odd.
$endgroup$
– Bernard
Mar 30 at 22:54
$begingroup$
@Bernard Thank you so much.
$endgroup$
– Dima
Mar 30 at 22:59
$begingroup$
@Bernard Thank you so much.
$endgroup$
– Dima
Mar 30 at 22:59
$begingroup$
You're welcome! Always glad to help!
$endgroup$
– Bernard
Mar 30 at 23:00
$begingroup$
You're welcome! Always glad to help!
$endgroup$
– Bernard
Mar 30 at 23:00
1
1
$begingroup$
B.t.w., non-prime numbers which satisfy that $a^n-1equiv 1$ for all $a$ coprime to $n$ are called *Carmichael numbers. The smallest Carmichael number is $561=3cdot 11cdot 17$.
$endgroup$
– Bernard
Mar 30 at 23:10
$begingroup$
B.t.w., non-prime numbers which satisfy that $a^n-1equiv 1$ for all $a$ coprime to $n$ are called *Carmichael numbers. The smallest Carmichael number is $561=3cdot 11cdot 17$.
$endgroup$
– Bernard
Mar 30 at 23:10
$begingroup$
" Now, I think we must show that 2, is the least positive integer satisfying the last congruence." uh.... he only positive integer smaller is $1$.... Sometimes one of the directions in an if and only if proof is self evident. This is one of those times.
$endgroup$
– fleablood
Mar 31 at 1:10
$begingroup$
" Now, I think we must show that 2, is the least positive integer satisfying the last congruence." uh.... he only positive integer smaller is $1$.... Sometimes one of the directions in an if and only if proof is self evident. This is one of those times.
$endgroup$
– fleablood
Mar 31 at 1:10
|
show 3 more comments
1 Answer
1
active
oldest
votes
$begingroup$
Hint For $b)$ your approoach is not working since the converse to FLT is not true.
Try instead the following:
$textord_n (a)=n-1$ implies that $a, a^2,... , a^n-1$ are distinct elements modulo n, in the set $1, 2, .., n-1 pmodn$.
Deduce that $1, 2,.., n-1$ are all invertible modulo n
answered Mar 30 at 23:05
N. S.N. S.
105k7115210
$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%2f3168857%2ford-pa-2-iff-a-equiv-1-mod-p%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Hint For $b)$ your approoach is not working since the converse to FLT is not true.
Try instead the following:
$textord_n (a)=n-1$ implies that $a, a^2,... , a^n-1$ are distinct elements modulo n, in the set $1, 2, .., n-1 pmodn$.
Deduce that $1, 2,.., n-1$ are all invertible modulo n
answered Mar 30 at 23:05
N. S.N. S.
105k7115210
$endgroup$
add a comment |
$begingroup$
Hint For $b)$ your approoach is not working since the converse to FLT is not true.
Try instead the following:
$textord_n (a)=n-1$ implies that $a, a^2,... , a^n-1$ are distinct elements modulo n, in the set $1, 2, .., n-1 pmodn$.
Deduce that $1, 2,.., n-1$ are all invertible modulo n
answered Mar 30 at 23:05
N. S.N. S.
105k7115210
$endgroup$
add a comment |
$begingroup$
Hint For $b)$ your approoach is not working since the converse to FLT is not true.
Try instead the following:
$textord_n (a)=n-1$ implies that $a, a^2,... , a^n-1$ are distinct elements modulo n, in the set $1, 2, .., n-1 pmodn$.
Deduce that $1, 2,.., n-1$ are all invertible modulo n
answered Mar 30 at 23:05
N. S.N. S.
105k7115210
$endgroup$
Hint For $b)$ your approoach is not working since the converse to FLT is not true.
Try instead the following:
$textord_n (a)=n-1$ implies that $a, a^2,... , a^n-1$ are distinct elements modulo n, in the set $1, 2, .., n-1 pmodn$.
Deduce that $1, 2,.., n-1$ are all invertible modulo n
answered Mar 30 at 23:05
N. S.N. S.
105k7115210
answered Mar 30 at 23:05
N. S.N. S.
105k7115210
answered Mar 30 at 23:05
N. S.N. S.
105k7115210
answered Mar 30 at 23:05
N. S.N. S.
105k7115210
105k7115210
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%2f3168857%2ford-pa-2-iff-a-equiv-1-mod-p%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
1
$begingroup$
Yes, it could be possible only with $p=2$, and you suppose $p$ is odd.
$endgroup$
– Bernard
Mar 30 at 22:54
$begingroup$
@Bernard Thank you so much.
$endgroup$
– Dima
Mar 30 at 22:59
$begingroup$
You're welcome! Always glad to help!
$endgroup$
– Bernard
Mar 30 at 23:00
1
$begingroup$
B.t.w., non-prime numbers which satisfy that $a^n-1equiv 1$ for all $a$ coprime to $n$ are called *Carmichael numbers. The smallest Carmichael number is $561=3cdot 11cdot 17$.
$endgroup$
– Bernard
Mar 30 at 23:10
$begingroup$
" Now, I think we must show that 2, is the least positive integer satisfying the last congruence." uh.... he only positive integer smaller is $1$.... Sometimes one of the directions in an if and only if proof is self evident. This is one of those times.
$endgroup$
– fleablood
Mar 31 at 1:10