Mixing
Prove that $text{gcd}(a, p) = 1 implies pnmid a $ is true.
$begingroup$
This is one direction of the biconditional in part b of this proposition:
Prove that for every prime, $p$, and for all natural numbers $a$,
(a) $text{gcd}(a,p)=p$ iff $pmid a$
(b) $text{gcd}(a,p)=1$ iff $pnmid a$.
So far for my proof of part b, I have that:
Proposition Part (b): $text{gcd}(a, p) = 1 implies pnmid a$.
Proof: Let us consider one direction of the bi-conditional proposition:
$pnmid a implies text{gcd}(a, p) = 1$.
Let $b$ be a common divisor of $a$ and $p$. It is enough to show that $b = 1$.
We know that $p$ is prime, so if $b mid p, b = 1$ or $b = p$.
If $b = p$, then $pmid a$ because $b$ is a common divisor of both $a$ and $p$. This is a contradiction, because we assumed that $p nmid a$.
Therefore, $b = 1$.
Now I just need the proof of the other direction; please help me out!
elementary-number-theory divisibility greatest-common-divisor
edited Jan 3 at 19:58
Martin Sleziak
44.7k9117272
asked Jan 3 at 0:54
ChiminChimin
111
$endgroup$
add a comment |
$begingroup$
This is one direction of the biconditional in part b of this proposition:
Prove that for every prime, $p$, and for all natural numbers $a$,
(a) $text{gcd}(a,p)=p$ iff $pmid a$
(b) $text{gcd}(a,p)=1$ iff $pnmid a$.
So far for my proof of part b, I have that:
Proposition Part (b): $text{gcd}(a, p) = 1 implies pnmid a$.
Proof: Let us consider one direction of the bi-conditional proposition:
$pnmid a implies text{gcd}(a, p) = 1$.
Let $b$ be a common divisor of $a$ and $p$. It is enough to show that $b = 1$.
We know that $p$ is prime, so if $b mid p, b = 1$ or $b = p$.
If $b = p$, then $pmid a$ because $b$ is a common divisor of both $a$ and $p$. This is a contradiction, because we assumed that $p nmid a$.
Therefore, $b = 1$.
Now I just need the proof of the other direction; please help me out!
elementary-number-theory divisibility greatest-common-divisor
edited Jan 3 at 19:58
Martin Sleziak
44.7k9117272
asked Jan 3 at 0:54
ChiminChimin
111
$endgroup$
$begingroup$
The other direction is trivial. If $gcd(a,p) =1$ then no factor of $p$ divides $a$. In particular $pnot mid a$.
$endgroup$
– fleablood
Jan 3 at 1:39
add a comment |
$begingroup$
This is one direction of the biconditional in part b of this proposition:
Prove that for every prime, $p$, and for all natural numbers $a$,
(a) $text{gcd}(a,p)=p$ iff $pmid a$
(b) $text{gcd}(a,p)=1$ iff $pnmid a$.
So far for my proof of part b, I have that:
Proposition Part (b): $text{gcd}(a, p) = 1 implies pnmid a$.
Proof: Let us consider one direction of the bi-conditional proposition:
$pnmid a implies text{gcd}(a, p) = 1$.
Let $b$ be a common divisor of $a$ and $p$. It is enough to show that $b = 1$.
We know that $p$ is prime, so if $b mid p, b = 1$ or $b = p$.
If $b = p$, then $pmid a$ because $b$ is a common divisor of both $a$ and $p$. This is a contradiction, because we assumed that $p nmid a$.
Therefore, $b = 1$.
Now I just need the proof of the other direction; please help me out!
elementary-number-theory divisibility greatest-common-divisor
edited Jan 3 at 19:58
Martin Sleziak
44.7k9117272
asked Jan 3 at 0:54
ChiminChimin
111
$endgroup$
This is one direction of the biconditional in part b of this proposition:
Prove that for every prime, $p$, and for all natural numbers $a$,
(a) $text{gcd}(a,p)=p$ iff $pmid a$
(b) $text{gcd}(a,p)=1$ iff $pnmid a$.
So far for my proof of part b, I have that:
Proposition Part (b): $text{gcd}(a, p) = 1 implies pnmid a$.
Proof: Let us consider one direction of the bi-conditional proposition:
$pnmid a implies text{gcd}(a, p) = 1$.
Let $b$ be a common divisor of $a$ and $p$. It is enough to show that $b = 1$.
We know that $p$ is prime, so if $b mid p, b = 1$ or $b = p$.
If $b = p$, then $pmid a$ because $b$ is a common divisor of both $a$ and $p$. This is a contradiction, because we assumed that $p nmid a$.
Therefore, $b = 1$.
Now I just need the proof of the other direction; please help me out!
elementary-number-theory divisibility greatest-common-divisor
elementary-number-theory divisibility greatest-common-divisor
edited Jan 3 at 19:58
Martin Sleziak
44.7k9117272
asked Jan 3 at 0:54
ChiminChimin
111
edited Jan 3 at 19:58
Martin Sleziak
44.7k9117272
asked Jan 3 at 0:54
ChiminChimin
111
edited Jan 3 at 19:58
Martin Sleziak
44.7k9117272
edited Jan 3 at 19:58
Martin Sleziak
44.7k9117272
edited Jan 3 at 19:58
Martin Sleziak
44.7k9117272
44.7k9117272
asked Jan 3 at 0:54
ChiminChimin
111
asked Jan 3 at 0:54
ChiminChimin
111
asked Jan 3 at 0:54
ChiminChimin
111
111
$begingroup$
The other direction is trivial. If $gcd(a,p) =1$ then no factor of $p$ divides $a$. In particular $pnot mid a$.
$endgroup$
– fleablood
Jan 3 at 1:39
add a comment |
$begingroup$
The other direction is trivial. If $gcd(a,p) =1$ then no factor of $p$ divides $a$. In particular $pnot mid a$.
$endgroup$
– fleablood
Jan 3 at 1:39
$begingroup$
The other direction is trivial. If $gcd(a,p) =1$ then no factor of $p$ divides $a$. In particular $pnot mid a$.
$endgroup$
– fleablood
Jan 3 at 1:39
$begingroup$
The other direction is trivial. If $gcd(a,p) =1$ then no factor of $p$ divides $a$. In particular $pnot mid a$.
$endgroup$
– fleablood
Jan 3 at 1:39
add a comment |
4 Answers
4
active
oldest
votes
$begingroup$
If you wish to prove that $[gcd(a,p)=1]Rightarrow [pnmid a]$ you could equivalently prove $[pmid a]Rightarrow [gcd(a,p)neq1]$, which I think you will find easier. If you know that $pmid a$ then both $p$ and $a$ are divisible by $p$, so the $gcd(a,p)=p$.
answered Jan 3 at 1:04
ItsJustASeriesBroItsJustASeriesBro
1563
$endgroup$
$begingroup$
So basically, I should use the contrapositive to prove this statement?
$endgroup$
– Chimin
Jan 3 at 1:10
$begingroup$
@Chimin You do not have to, but it should be a reflex to check the contrapositive to see if it is easier whenever you are working on if and only if statements.
$endgroup$
– ItsJustASeriesBro
Jan 3 at 1:12
$begingroup$
not exactly following how this proves that [gcd(a,p)=1]⇒[p∤a]
$endgroup$
– Chimin
Jan 3 at 1:27
$begingroup$
@Chimin So you are familiar with the logical equivalence between a statement and its contrapositive? If I prove the contrapositive then the original statement has also been proven. And the point is that if you get to assume that $pmid a$ (which is exactly the hypothesis of the contrapositive) then it is immediately apparent that $gcd(a,p)neq 1$. The fact that we can further show the exact value of $gcd(a,p)$ is sort of just icing on the cake.
$endgroup$
– ItsJustASeriesBro
Jan 3 at 1:31
$begingroup$
Yes; is it enough to say:
$endgroup$
– Chimin
Jan 3 at 1:32
|
show 2 more comments
$begingroup$
$p|p$ and if $p|a$ then $p$ is a common divisor of $a$ and $p$. But the greatest common factor is $1$ so this is impossible.
This direction was meant to be trivial. For positive integers $a|b iff gcd(a,b) = a$. If $a|b$ then its a common divisor but nothing larger than $a$ divides $a$. If $gcd(a,b) = a$ then $a|b$.
answered Jan 3 at 1:43
fleabloodfleablood
68.8k22685
$endgroup$
add a comment |
$begingroup$
If $p|a$ and also $p|p$ $Rightarrow p|gcd(a,p)$ as $gcd(a,p)=ax+py, x,yin mathbb{Z}$ $rightarrow leftarrow $ because $pnot mid 1$
answered Jan 3 at 1:20
Julio Trujillo GonzalezJulio Trujillo Gonzalez
856
$endgroup$
$begingroup$
unless it is $p=pm1$
$endgroup$
– Julio Trujillo Gonzalez
Jan 3 at 1:21
$begingroup$
where did x and y come from
$endgroup$
– Chimin
Jan 3 at 1:25
$begingroup$
$x$ and $y$ both are integre numbers. I recommend reading en.wikipedia.org/wiki/Bézout%27s_identity
$endgroup$
– Julio Trujillo Gonzalez
Jan 3 at 1:29
add a comment |
$begingroup$
Hint $ $ note that $ p = (a,p) iff pmid (a,p) iff pmid a,p iff pmid a,, $ so $(a)$ is true.
Negating above $,pnmid aiff (a,p)neq piff (a,p)=1,, $ by $, (a,p)mid p,, $ so $(b)$ is true.
answered Jan 3 at 2:15
Bill DubuqueBill Dubuque
209k29191633
$endgroup$
$begingroup$
Note $,(a,b)$ denotes $,gcd(a,b),,$ standard notation in number theory.
$endgroup$
– Bill Dubuque
Jan 3 at 2:21
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%2f3060155%2fprove-that-textgcda-p-1-implies-p-nmid-a-is-true%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
If you wish to prove that $[gcd(a,p)=1]Rightarrow [pnmid a]$ you could equivalently prove $[pmid a]Rightarrow [gcd(a,p)neq1]$, which I think you will find easier. If you know that $pmid a$ then both $p$ and $a$ are divisible by $p$, so the $gcd(a,p)=p$.
answered Jan 3 at 1:04
ItsJustASeriesBroItsJustASeriesBro
1563
$endgroup$
$begingroup$
So basically, I should use the contrapositive to prove this statement?
$endgroup$
– Chimin
Jan 3 at 1:10
$begingroup$
@Chimin You do not have to, but it should be a reflex to check the contrapositive to see if it is easier whenever you are working on if and only if statements.
$endgroup$
– ItsJustASeriesBro
Jan 3 at 1:12
$begingroup$
not exactly following how this proves that [gcd(a,p)=1]⇒[p∤a]
$endgroup$
– Chimin
Jan 3 at 1:27
$begingroup$
@Chimin So you are familiar with the logical equivalence between a statement and its contrapositive? If I prove the contrapositive then the original statement has also been proven. And the point is that if you get to assume that $pmid a$ (which is exactly the hypothesis of the contrapositive) then it is immediately apparent that $gcd(a,p)neq 1$. The fact that we can further show the exact value of $gcd(a,p)$ is sort of just icing on the cake.
$endgroup$
– ItsJustASeriesBro
Jan 3 at 1:31
$begingroup$
Yes; is it enough to say:
$endgroup$
– Chimin
Jan 3 at 1:32
|
show 2 more comments
$begingroup$
If you wish to prove that $[gcd(a,p)=1]Rightarrow [pnmid a]$ you could equivalently prove $[pmid a]Rightarrow [gcd(a,p)neq1]$, which I think you will find easier. If you know that $pmid a$ then both $p$ and $a$ are divisible by $p$, so the $gcd(a,p)=p$.
answered Jan 3 at 1:04
ItsJustASeriesBroItsJustASeriesBro
1563
$endgroup$
$begingroup$
So basically, I should use the contrapositive to prove this statement?
$endgroup$
– Chimin
Jan 3 at 1:10
$begingroup$
@Chimin You do not have to, but it should be a reflex to check the contrapositive to see if it is easier whenever you are working on if and only if statements.
$endgroup$
– ItsJustASeriesBro
Jan 3 at 1:12
$begingroup$
not exactly following how this proves that [gcd(a,p)=1]⇒[p∤a]
$endgroup$
– Chimin
Jan 3 at 1:27
$begingroup$
@Chimin So you are familiar with the logical equivalence between a statement and its contrapositive? If I prove the contrapositive then the original statement has also been proven. And the point is that if you get to assume that $pmid a$ (which is exactly the hypothesis of the contrapositive) then it is immediately apparent that $gcd(a,p)neq 1$. The fact that we can further show the exact value of $gcd(a,p)$ is sort of just icing on the cake.
$endgroup$
– ItsJustASeriesBro
Jan 3 at 1:31
$begingroup$
Yes; is it enough to say:
$endgroup$
– Chimin
Jan 3 at 1:32
|
show 2 more comments
$begingroup$
If you wish to prove that $[gcd(a,p)=1]Rightarrow [pnmid a]$ you could equivalently prove $[pmid a]Rightarrow [gcd(a,p)neq1]$, which I think you will find easier. If you know that $pmid a$ then both $p$ and $a$ are divisible by $p$, so the $gcd(a,p)=p$.
answered Jan 3 at 1:04
ItsJustASeriesBroItsJustASeriesBro
1563
$endgroup$
If you wish to prove that $[gcd(a,p)=1]Rightarrow [pnmid a]$ you could equivalently prove $[pmid a]Rightarrow [gcd(a,p)neq1]$, which I think you will find easier. If you know that $pmid a$ then both $p$ and $a$ are divisible by $p$, so the $gcd(a,p)=p$.
answered Jan 3 at 1:04
ItsJustASeriesBroItsJustASeriesBro
1563
answered Jan 3 at 1:04
ItsJustASeriesBroItsJustASeriesBro
1563
answered Jan 3 at 1:04
ItsJustASeriesBroItsJustASeriesBro
1563
answered Jan 3 at 1:04
ItsJustASeriesBroItsJustASeriesBro
1563
1563
$begingroup$
So basically, I should use the contrapositive to prove this statement?
$endgroup$
– Chimin
Jan 3 at 1:10
$begingroup$
@Chimin You do not have to, but it should be a reflex to check the contrapositive to see if it is easier whenever you are working on if and only if statements.
$endgroup$
– ItsJustASeriesBro
Jan 3 at 1:12
$begingroup$
not exactly following how this proves that [gcd(a,p)=1]⇒[p∤a]
$endgroup$
– Chimin
Jan 3 at 1:27
$begingroup$
@Chimin So you are familiar with the logical equivalence between a statement and its contrapositive? If I prove the contrapositive then the original statement has also been proven. And the point is that if you get to assume that $pmid a$ (which is exactly the hypothesis of the contrapositive) then it is immediately apparent that $gcd(a,p)neq 1$. The fact that we can further show the exact value of $gcd(a,p)$ is sort of just icing on the cake.
$endgroup$
– ItsJustASeriesBro
Jan 3 at 1:31
$begingroup$
Yes; is it enough to say:
$endgroup$
– Chimin
Jan 3 at 1:32
|
show 2 more comments
$begingroup$
So basically, I should use the contrapositive to prove this statement?
$endgroup$
– Chimin
Jan 3 at 1:10
$begingroup$
@Chimin You do not have to, but it should be a reflex to check the contrapositive to see if it is easier whenever you are working on if and only if statements.
$endgroup$
– ItsJustASeriesBro
Jan 3 at 1:12
$begingroup$
not exactly following how this proves that [gcd(a,p)=1]⇒[p∤a]
$endgroup$
– Chimin
Jan 3 at 1:27
$begingroup$
@Chimin So you are familiar with the logical equivalence between a statement and its contrapositive? If I prove the contrapositive then the original statement has also been proven. And the point is that if you get to assume that $pmid a$ (which is exactly the hypothesis of the contrapositive) then it is immediately apparent that $gcd(a,p)neq 1$. The fact that we can further show the exact value of $gcd(a,p)$ is sort of just icing on the cake.
$endgroup$
– ItsJustASeriesBro
Jan 3 at 1:31
$begingroup$
Yes; is it enough to say:
$endgroup$
– Chimin
Jan 3 at 1:32
$begingroup$
So basically, I should use the contrapositive to prove this statement?
$endgroup$
– Chimin
Jan 3 at 1:10
$begingroup$
So basically, I should use the contrapositive to prove this statement?
$endgroup$
– Chimin
Jan 3 at 1:10
$begingroup$
@Chimin You do not have to, but it should be a reflex to check the contrapositive to see if it is easier whenever you are working on if and only if statements.
$endgroup$
– ItsJustASeriesBro
Jan 3 at 1:12
$begingroup$
@Chimin You do not have to, but it should be a reflex to check the contrapositive to see if it is easier whenever you are working on if and only if statements.
$endgroup$
– ItsJustASeriesBro
Jan 3 at 1:12
$begingroup$
not exactly following how this proves that [gcd(a,p)=1]⇒[p∤a]
$endgroup$
– Chimin
Jan 3 at 1:27
$begingroup$
not exactly following how this proves that [gcd(a,p)=1]⇒[p∤a]
$endgroup$
– Chimin
Jan 3 at 1:27
$begingroup$
@Chimin So you are familiar with the logical equivalence between a statement and its contrapositive? If I prove the contrapositive then the original statement has also been proven. And the point is that if you get to assume that $pmid a$ (which is exactly the hypothesis of the contrapositive) then it is immediately apparent that $gcd(a,p)neq 1$. The fact that we can further show the exact value of $gcd(a,p)$ is sort of just icing on the cake.
$endgroup$
– ItsJustASeriesBro
Jan 3 at 1:31
$begingroup$
@Chimin So you are familiar with the logical equivalence between a statement and its contrapositive? If I prove the contrapositive then the original statement has also been proven. And the point is that if you get to assume that $pmid a$ (which is exactly the hypothesis of the contrapositive) then it is immediately apparent that $gcd(a,p)neq 1$. The fact that we can further show the exact value of $gcd(a,p)$ is sort of just icing on the cake.
$endgroup$
– ItsJustASeriesBro
Jan 3 at 1:31
$begingroup$
Yes; is it enough to say:
$endgroup$
– Chimin
Jan 3 at 1:32
$begingroup$
Yes; is it enough to say:
$endgroup$
– Chimin
Jan 3 at 1:32
|
show 2 more comments
$begingroup$
$p|p$ and if $p|a$ then $p$ is a common divisor of $a$ and $p$. But the greatest common factor is $1$ so this is impossible.
This direction was meant to be trivial. For positive integers $a|b iff gcd(a,b) = a$. If $a|b$ then its a common divisor but nothing larger than $a$ divides $a$. If $gcd(a,b) = a$ then $a|b$.
answered Jan 3 at 1:43
fleabloodfleablood
68.8k22685
$endgroup$
add a comment |
$begingroup$
$p|p$ and if $p|a$ then $p$ is a common divisor of $a$ and $p$. But the greatest common factor is $1$ so this is impossible.
This direction was meant to be trivial. For positive integers $a|b iff gcd(a,b) = a$. If $a|b$ then its a common divisor but nothing larger than $a$ divides $a$. If $gcd(a,b) = a$ then $a|b$.
answered Jan 3 at 1:43
fleabloodfleablood
68.8k22685
$endgroup$
add a comment |
$begingroup$
$p|p$ and if $p|a$ then $p$ is a common divisor of $a$ and $p$. But the greatest common factor is $1$ so this is impossible.
This direction was meant to be trivial. For positive integers $a|b iff gcd(a,b) = a$. If $a|b$ then its a common divisor but nothing larger than $a$ divides $a$. If $gcd(a,b) = a$ then $a|b$.
answered Jan 3 at 1:43
fleabloodfleablood
68.8k22685
$endgroup$
$p|p$ and if $p|a$ then $p$ is a common divisor of $a$ and $p$. But the greatest common factor is $1$ so this is impossible.
This direction was meant to be trivial. For positive integers $a|b iff gcd(a,b) = a$. If $a|b$ then its a common divisor but nothing larger than $a$ divides $a$. If $gcd(a,b) = a$ then $a|b$.
answered Jan 3 at 1:43
fleabloodfleablood
68.8k22685
edited Jan 3 at 1:49
answered Jan 3 at 1:43
fleabloodfleablood
68.8k22685
answered Jan 3 at 1:43
fleabloodfleablood
68.8k22685
answered Jan 3 at 1:43
fleabloodfleablood
68.8k22685
68.8k22685
add a comment |
add a comment |
$begingroup$
If $p|a$ and also $p|p$ $Rightarrow p|gcd(a,p)$ as $gcd(a,p)=ax+py, x,yin mathbb{Z}$ $rightarrow leftarrow $ because $pnot mid 1$
answered Jan 3 at 1:20
Julio Trujillo GonzalezJulio Trujillo Gonzalez
856
$endgroup$
$begingroup$
unless it is $p=pm1$
$endgroup$
– Julio Trujillo Gonzalez
Jan 3 at 1:21
$begingroup$
where did x and y come from
$endgroup$
– Chimin
Jan 3 at 1:25
$begingroup$
$x$ and $y$ both are integre numbers. I recommend reading en.wikipedia.org/wiki/Bézout%27s_identity
$endgroup$
– Julio Trujillo Gonzalez
Jan 3 at 1:29
add a comment |
$begingroup$
If $p|a$ and also $p|p$ $Rightarrow p|gcd(a,p)$ as $gcd(a,p)=ax+py, x,yin mathbb{Z}$ $rightarrow leftarrow $ because $pnot mid 1$
answered Jan 3 at 1:20
Julio Trujillo GonzalezJulio Trujillo Gonzalez
856
$endgroup$
$begingroup$
unless it is $p=pm1$
$endgroup$
– Julio Trujillo Gonzalez
Jan 3 at 1:21
$begingroup$
where did x and y come from
$endgroup$
– Chimin
Jan 3 at 1:25
$begingroup$
$x$ and $y$ both are integre numbers. I recommend reading en.wikipedia.org/wiki/Bézout%27s_identity
$endgroup$
– Julio Trujillo Gonzalez
Jan 3 at 1:29
add a comment |
$begingroup$
If $p|a$ and also $p|p$ $Rightarrow p|gcd(a,p)$ as $gcd(a,p)=ax+py, x,yin mathbb{Z}$ $rightarrow leftarrow $ because $pnot mid 1$
answered Jan 3 at 1:20
Julio Trujillo GonzalezJulio Trujillo Gonzalez
856
$endgroup$
If $p|a$ and also $p|p$ $Rightarrow p|gcd(a,p)$ as $gcd(a,p)=ax+py, x,yin mathbb{Z}$ $rightarrow leftarrow $ because $pnot mid 1$
answered Jan 3 at 1:20
Julio Trujillo GonzalezJulio Trujillo Gonzalez
856
answered Jan 3 at 1:20
Julio Trujillo GonzalezJulio Trujillo Gonzalez
856
answered Jan 3 at 1:20
Julio Trujillo GonzalezJulio Trujillo Gonzalez
856
answered Jan 3 at 1:20
Julio Trujillo GonzalezJulio Trujillo Gonzalez
856
856
$begingroup$
unless it is $p=pm1$
$endgroup$
– Julio Trujillo Gonzalez
Jan 3 at 1:21
$begingroup$
where did x and y come from
$endgroup$
– Chimin
Jan 3 at 1:25
$begingroup$
$x$ and $y$ both are integre numbers. I recommend reading en.wikipedia.org/wiki/Bézout%27s_identity
$endgroup$
– Julio Trujillo Gonzalez
Jan 3 at 1:29
add a comment |
$begingroup$
unless it is $p=pm1$
$endgroup$
– Julio Trujillo Gonzalez
Jan 3 at 1:21
$begingroup$
where did x and y come from
$endgroup$
– Chimin
Jan 3 at 1:25
$begingroup$
$x$ and $y$ both are integre numbers. I recommend reading en.wikipedia.org/wiki/Bézout%27s_identity
$endgroup$
– Julio Trujillo Gonzalez
Jan 3 at 1:29
$begingroup$
unless it is $p=pm1$
$endgroup$
– Julio Trujillo Gonzalez
Jan 3 at 1:21
$begingroup$
unless it is $p=pm1$
$endgroup$
– Julio Trujillo Gonzalez
Jan 3 at 1:21
$begingroup$
where did x and y come from
$endgroup$
– Chimin
Jan 3 at 1:25
$begingroup$
where did x and y come from
$endgroup$
– Chimin
Jan 3 at 1:25
$begingroup$
$x$ and $y$ both are integre numbers. I recommend reading en.wikipedia.org/wiki/Bézout%27s_identity
$endgroup$
– Julio Trujillo Gonzalez
Jan 3 at 1:29
$begingroup$
$x$ and $y$ both are integre numbers. I recommend reading en.wikipedia.org/wiki/Bézout%27s_identity
$endgroup$
– Julio Trujillo Gonzalez
Jan 3 at 1:29
add a comment |
$begingroup$
Hint $ $ note that $ p = (a,p) iff pmid (a,p) iff pmid a,p iff pmid a,, $ so $(a)$ is true.
Negating above $,pnmid aiff (a,p)neq piff (a,p)=1,, $ by $, (a,p)mid p,, $ so $(b)$ is true.
answered Jan 3 at 2:15
Bill DubuqueBill Dubuque
209k29191633
$endgroup$
$begingroup$
Note $,(a,b)$ denotes $,gcd(a,b),,$ standard notation in number theory.
$endgroup$
– Bill Dubuque
Jan 3 at 2:21
add a comment |
$begingroup$
Hint $ $ note that $ p = (a,p) iff pmid (a,p) iff pmid a,p iff pmid a,, $ so $(a)$ is true.
Negating above $,pnmid aiff (a,p)neq piff (a,p)=1,, $ by $, (a,p)mid p,, $ so $(b)$ is true.
answered Jan 3 at 2:15
Bill DubuqueBill Dubuque
209k29191633
$endgroup$
$begingroup$
Note $,(a,b)$ denotes $,gcd(a,b),,$ standard notation in number theory.
$endgroup$
– Bill Dubuque
Jan 3 at 2:21
add a comment |
$begingroup$
Hint $ $ note that $ p = (a,p) iff pmid (a,p) iff pmid a,p iff pmid a,, $ so $(a)$ is true.
Negating above $,pnmid aiff (a,p)neq piff (a,p)=1,, $ by $, (a,p)mid p,, $ so $(b)$ is true.
answered Jan 3 at 2:15
Bill DubuqueBill Dubuque
209k29191633
$endgroup$
Hint $ $ note that $ p = (a,p) iff pmid (a,p) iff pmid a,p iff pmid a,, $ so $(a)$ is true.
Negating above $,pnmid aiff (a,p)neq piff (a,p)=1,, $ by $, (a,p)mid p,, $ so $(b)$ is true.
answered Jan 3 at 2:15
Bill DubuqueBill Dubuque
209k29191633
answered Jan 3 at 2:15
Bill DubuqueBill Dubuque
209k29191633
answered Jan 3 at 2:15
Bill DubuqueBill Dubuque
209k29191633
answered Jan 3 at 2:15
Bill DubuqueBill Dubuque
209k29191633
209k29191633
$begingroup$
Note $,(a,b)$ denotes $,gcd(a,b),,$ standard notation in number theory.
$endgroup$
– Bill Dubuque
Jan 3 at 2:21
add a comment |
$begingroup$
Note $,(a,b)$ denotes $,gcd(a,b),,$ standard notation in number theory.
$endgroup$
– Bill Dubuque
Jan 3 at 2:21
$begingroup$
Note $,(a,b)$ denotes $,gcd(a,b),,$ standard notation in number theory.
$endgroup$
– Bill Dubuque
Jan 3 at 2:21
$begingroup$
Note $,(a,b)$ denotes $,gcd(a,b),,$ standard notation in number theory.
$endgroup$
– Bill Dubuque
Jan 3 at 2:21
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%2f3060155%2fprove-that-textgcda-p-1-implies-p-nmid-a-is-true%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$
The other direction is trivial. If $gcd(a,p) =1$ then no factor of $p$ divides $a$. In particular $pnot mid a$.
$endgroup$
– fleablood
Jan 3 at 1:39