Prove that $text{gcd}(a, p) = 1 implies pnmid a $ is true.
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.7k8115271
asked Jan 3 at 0:54
Chimin
111
New contributor
Chimin is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
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.7k8115271
asked Jan 3 at 0:54
Chimin
111
New contributor
Chimin is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Welcome to MSE. For some basic information about writing mathematics at this site see, e.g., basic help on mathjax notation, mathjax tutorial and quick reference, main meta site math tutorial and equation editing how-to.
– José Carlos Santos
Jan 3 at 0:59
The other direction is trivial. If $gcd(a,p) =1$ then no factor of $p$ divides $a$. In particular $pnot mid a$.
– fleablood
Jan 3 at 1:39
add a comment |
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.7k8115271
asked Jan 3 at 0:54
Chimin
111
New contributor
Chimin is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
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.7k8115271
asked Jan 3 at 0:54
Chimin
111
New contributor
Chimin is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited Jan 3 at 19:58
Martin Sleziak
44.7k8115271
asked Jan 3 at 0:54
Chimin
111
New contributor
Chimin is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited Jan 3 at 19:58
Martin Sleziak
44.7k8115271
edited Jan 3 at 19:58
Martin Sleziak
44.7k8115271
edited Jan 3 at 19:58
Martin Sleziak
44.7k8115271
44.7k8115271
asked Jan 3 at 0:54
Chimin
111
New contributor
Chimin is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Jan 3 at 0:54
Chimin
111
asked Jan 3 at 0:54
Chimin
111
111
New contributor
Chimin is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Chimin is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Chimin is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Welcome to MSE. For some basic information about writing mathematics at this site see, e.g., basic help on mathjax notation, mathjax tutorial and quick reference, main meta site math tutorial and equation editing how-to.
– José Carlos Santos
Jan 3 at 0:59
The other direction is trivial. If $gcd(a,p) =1$ then no factor of $p$ divides $a$. In particular $pnot mid a$.
– fleablood
Jan 3 at 1:39
add a comment |
Welcome to MSE. For some basic information about writing mathematics at this site see, e.g., basic help on mathjax notation, mathjax tutorial and quick reference, main meta site math tutorial and equation editing how-to.
– José Carlos Santos
Jan 3 at 0:59
The other direction is trivial. If $gcd(a,p) =1$ then no factor of $p$ divides $a$. In particular $pnot mid a$.
– fleablood
Jan 3 at 1:39
Welcome to MSE. For some basic information about writing mathematics at this site see, e.g., basic help on mathjax notation, mathjax tutorial and quick reference, main meta site math tutorial and equation editing how-to.
– José Carlos Santos
Jan 3 at 0:59
Welcome to MSE. For some basic information about writing mathematics at this site see, e.g., basic help on mathjax notation, mathjax tutorial and quick reference, main meta site math tutorial and equation editing how-to.
– José Carlos Santos
Jan 3 at 0:59
The other direction is trivial. If $gcd(a,p) =1$ then no factor of $p$ divides $a$. In particular $pnot mid a$.
– fleablood
Jan 3 at 1:39
The other direction is trivial. If $gcd(a,p) =1$ then no factor of $p$ divides $a$. In particular $pnot mid a$.
– fleablood
Jan 3 at 1:39
add a comment |
4 Answers
4
active
oldest
votes
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
ItsJustASeriesBro
1563
New contributor
ItsJustASeriesBro is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
So basically, I should use the contrapositive to prove this statement?
– Chimin
Jan 3 at 1:10
@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.
– ItsJustASeriesBro
Jan 3 at 1:12
not exactly following how this proves that [gcd(a,p)=1]⇒[p∤a]
– Chimin
Jan 3 at 1:27
@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.
– ItsJustASeriesBro
Jan 3 at 1:31
Yes; is it enough to say:
– Chimin
Jan 3 at 1:32
|
show 2 more comments
$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
fleablood
68.4k22685
add a comment |
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 Gonzalez
856
unless it is $p=pm1$
– Julio Trujillo Gonzalez
Jan 3 at 1:21
where did x and y come from
– Chimin
Jan 3 at 1:25
$x$ and $y$ both are integre numbers. I recommend reading en.wikipedia.org/wiki/Bézout%27s_identity
– Julio Trujillo Gonzalez
Jan 3 at 1:29
add a comment |
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 Dubuque
209k29190629
Note $,(a,b)$ denotes $,gcd(a,b),,$ standard notation in number theory.
– 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
});
}
});
Chimin is a new contributor. Be nice, and check out our Code of Conduct.
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
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
ItsJustASeriesBro
1563
New contributor
ItsJustASeriesBro is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
So basically, I should use the contrapositive to prove this statement?
– Chimin
Jan 3 at 1:10
@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.
– ItsJustASeriesBro
Jan 3 at 1:12
not exactly following how this proves that [gcd(a,p)=1]⇒[p∤a]
– Chimin
Jan 3 at 1:27
@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.
– ItsJustASeriesBro
Jan 3 at 1:31
Yes; is it enough to say:
– Chimin
Jan 3 at 1:32
|
show 2 more comments
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
ItsJustASeriesBro
1563
New contributor
ItsJustASeriesBro is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
So basically, I should use the contrapositive to prove this statement?
– Chimin
Jan 3 at 1:10
@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.
– ItsJustASeriesBro
Jan 3 at 1:12
not exactly following how this proves that [gcd(a,p)=1]⇒[p∤a]
– Chimin
Jan 3 at 1:27
@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.
– ItsJustASeriesBro
Jan 3 at 1:31
Yes; is it enough to say:
– Chimin
Jan 3 at 1:32
|
show 2 more comments
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
ItsJustASeriesBro
1563
New contributor
ItsJustASeriesBro is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
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
ItsJustASeriesBro
1563
New contributor
ItsJustASeriesBro is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered Jan 3 at 1:04
ItsJustASeriesBro
1563
New contributor
ItsJustASeriesBro is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered Jan 3 at 1:04
ItsJustASeriesBro
1563
answered Jan 3 at 1:04
ItsJustASeriesBro
1563
1563
New contributor
ItsJustASeriesBro is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
ItsJustASeriesBro is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
ItsJustASeriesBro is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
So basically, I should use the contrapositive to prove this statement?
– Chimin
Jan 3 at 1:10
@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.
– ItsJustASeriesBro
Jan 3 at 1:12
not exactly following how this proves that [gcd(a,p)=1]⇒[p∤a]
– Chimin
Jan 3 at 1:27
@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.
– ItsJustASeriesBro
Jan 3 at 1:31
Yes; is it enough to say:
– Chimin
Jan 3 at 1:32
|
show 2 more comments
So basically, I should use the contrapositive to prove this statement?
– Chimin
Jan 3 at 1:10
@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.
– ItsJustASeriesBro
Jan 3 at 1:12
not exactly following how this proves that [gcd(a,p)=1]⇒[p∤a]
– Chimin
Jan 3 at 1:27
@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.
– ItsJustASeriesBro
Jan 3 at 1:31
Yes; is it enough to say:
– Chimin
Jan 3 at 1:32
So basically, I should use the contrapositive to prove this statement?
– Chimin
Jan 3 at 1:10
So basically, I should use the contrapositive to prove this statement?
– Chimin
Jan 3 at 1:10
@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.
– ItsJustASeriesBro
Jan 3 at 1:12
@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.
– ItsJustASeriesBro
Jan 3 at 1:12
not exactly following how this proves that [gcd(a,p)=1]⇒[p∤a]
– Chimin
Jan 3 at 1:27
not exactly following how this proves that [gcd(a,p)=1]⇒[p∤a]
– Chimin
Jan 3 at 1:27
@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.
– ItsJustASeriesBro
Jan 3 at 1:31
@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.
– ItsJustASeriesBro
Jan 3 at 1:31
Yes; is it enough to say:
– Chimin
Jan 3 at 1:32
Yes; is it enough to say:
– Chimin
Jan 3 at 1:32
|
show 2 more comments
$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
fleablood
68.4k22685
add a comment |
$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
fleablood
68.4k22685
add a comment |
$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
fleablood
68.4k22685
$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
fleablood
68.4k22685
edited Jan 3 at 1:49
answered Jan 3 at 1:43
fleablood
68.4k22685
answered Jan 3 at 1:43
fleablood
68.4k22685
answered Jan 3 at 1:43
fleablood
68.4k22685
68.4k22685
add a comment |
add a comment |
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 Gonzalez
856
unless it is $p=pm1$
– Julio Trujillo Gonzalez
Jan 3 at 1:21
where did x and y come from
– Chimin
Jan 3 at 1:25
$x$ and $y$ both are integre numbers. I recommend reading en.wikipedia.org/wiki/Bézout%27s_identity
– Julio Trujillo Gonzalez
Jan 3 at 1:29
add a comment |
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 Gonzalez
856
unless it is $p=pm1$
– Julio Trujillo Gonzalez
Jan 3 at 1:21
where did x and y come from
– Chimin
Jan 3 at 1:25
$x$ and $y$ both are integre numbers. I recommend reading en.wikipedia.org/wiki/Bézout%27s_identity
– Julio Trujillo Gonzalez
Jan 3 at 1:29
add a comment |
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 Gonzalez
856
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 Gonzalez
856
answered Jan 3 at 1:20
Julio Trujillo Gonzalez
856
answered Jan 3 at 1:20
Julio Trujillo Gonzalez
856
answered Jan 3 at 1:20
Julio Trujillo Gonzalez
856
856
unless it is $p=pm1$
– Julio Trujillo Gonzalez
Jan 3 at 1:21
where did x and y come from
– Chimin
Jan 3 at 1:25
$x$ and $y$ both are integre numbers. I recommend reading en.wikipedia.org/wiki/Bézout%27s_identity
– Julio Trujillo Gonzalez
Jan 3 at 1:29
add a comment |
unless it is $p=pm1$
– Julio Trujillo Gonzalez
Jan 3 at 1:21
where did x and y come from
– Chimin
Jan 3 at 1:25
$x$ and $y$ both are integre numbers. I recommend reading en.wikipedia.org/wiki/Bézout%27s_identity
– Julio Trujillo Gonzalez
Jan 3 at 1:29
unless it is $p=pm1$
– Julio Trujillo Gonzalez
Jan 3 at 1:21
unless it is $p=pm1$
– Julio Trujillo Gonzalez
Jan 3 at 1:21
where did x and y come from
– Chimin
Jan 3 at 1:25
where did x and y come from
– Chimin
Jan 3 at 1:25
$x$ and $y$ both are integre numbers. I recommend reading en.wikipedia.org/wiki/Bézout%27s_identity
– Julio Trujillo Gonzalez
Jan 3 at 1:29
$x$ and $y$ both are integre numbers. I recommend reading en.wikipedia.org/wiki/Bézout%27s_identity
– Julio Trujillo Gonzalez
Jan 3 at 1:29
add a comment |
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 Dubuque
209k29190629
Note $,(a,b)$ denotes $,gcd(a,b),,$ standard notation in number theory.
– Bill Dubuque
Jan 3 at 2:21
add a comment |
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 Dubuque
209k29190629
Note $,(a,b)$ denotes $,gcd(a,b),,$ standard notation in number theory.
– Bill Dubuque
Jan 3 at 2:21
add a comment |
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 Dubuque
209k29190629
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 Dubuque
209k29190629
answered Jan 3 at 2:15
Bill Dubuque
209k29190629
answered Jan 3 at 2:15
Bill Dubuque
209k29190629
answered Jan 3 at 2:15
Bill Dubuque
209k29190629
209k29190629
Note $,(a,b)$ denotes $,gcd(a,b),,$ standard notation in number theory.
– Bill Dubuque
Jan 3 at 2:21
add a comment |
Note $,(a,b)$ denotes $,gcd(a,b),,$ standard notation in number theory.
– Bill Dubuque
Jan 3 at 2:21
Note $,(a,b)$ denotes $,gcd(a,b),,$ standard notation in number theory.
– Bill Dubuque
Jan 3 at 2:21
Note $,(a,b)$ denotes $,gcd(a,b),,$ standard notation in number theory.
– Bill Dubuque
Jan 3 at 2:21
add a comment |
Chimin is a new contributor. Be nice, and check out our Code of Conduct.
Chimin is a new contributor. Be nice, and check out our Code of Conduct.
Chimin is a new contributor. Be nice, and check out our Code of Conduct.
Chimin is a new contributor. Be nice, and check out our Code of Conduct.
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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
Welcome to MSE. For some basic information about writing mathematics at this site see, e.g., basic help on mathjax notation, mathjax tutorial and quick reference, main meta site math tutorial and equation editing how-to.
– José Carlos Santos
Jan 3 at 0:59
The other direction is trivial. If $gcd(a,p) =1$ then no factor of $p$ divides $a$. In particular $pnot mid a$.
– fleablood
Jan 3 at 1:39