If $p$ is a prime and $p|ab$, then $p|a$ or $p|b$.
$begingroup$
I'm just starting to write proof and I was asked to prove the above statement. I came up with the following proof by contrapositive:
Assume $p$ does not divide $a$ or $p$ does not divide $b$, then $p$ does not divide $ab$.
Let $a=pk$ & $b=pm$ for some integers $k$ and $m$.
So, $ab=(pk)(pm)$, then $ab=p(km)$. This is a contradiction.
I'm not sure if that is correct proof. Any help is appreciated. Thank you.
elementary-number-theory proof-verification prime-numbers
edited Dec 12 '18 at 4:02
Shaun
9,065113683
asked Dec 12 '18 at 3:46
MettalMettal
257
$endgroup$
add a comment |
$begingroup$
I'm just starting to write proof and I was asked to prove the above statement. I came up with the following proof by contrapositive:
Assume $p$ does not divide $a$ or $p$ does not divide $b$, then $p$ does not divide $ab$.
Let $a=pk$ & $b=pm$ for some integers $k$ and $m$.
So, $ab=(pk)(pm)$, then $ab=p(km)$. This is a contradiction.
I'm not sure if that is correct proof. Any help is appreciated. Thank you.
elementary-number-theory proof-verification prime-numbers
edited Dec 12 '18 at 4:02
Shaun
9,065113683
asked Dec 12 '18 at 3:46
MettalMettal
257
$endgroup$
2
$begingroup$
No, it is not correct. You are using that $p$ divides $a$, which is the opposite of what you assumed.
$endgroup$
– Andrés E. Caicedo
Dec 12 '18 at 3:50
1
$begingroup$
If you are doing your proof by contrapositive, you need to assume that $p$ does not divide $a $ and does not divide $b $.
$endgroup$
– AnyAD
Dec 12 '18 at 3:52
$begingroup$
Some courses of algebra provide this property (also known as Euclid's lemma) as the definition for prime numbers, some explanations provided here
$endgroup$
– rtybase
Dec 12 '18 at 9:28
add a comment |
$begingroup$
I'm just starting to write proof and I was asked to prove the above statement. I came up with the following proof by contrapositive:
Assume $p$ does not divide $a$ or $p$ does not divide $b$, then $p$ does not divide $ab$.
Let $a=pk$ & $b=pm$ for some integers $k$ and $m$.
So, $ab=(pk)(pm)$, then $ab=p(km)$. This is a contradiction.
I'm not sure if that is correct proof. Any help is appreciated. Thank you.
elementary-number-theory proof-verification prime-numbers
edited Dec 12 '18 at 4:02
Shaun
9,065113683
asked Dec 12 '18 at 3:46
MettalMettal
257
$endgroup$
I'm just starting to write proof and I was asked to prove the above statement. I came up with the following proof by contrapositive:
Assume $p$ does not divide $a$ or $p$ does not divide $b$, then $p$ does not divide $ab$.
Let $a=pk$ & $b=pm$ for some integers $k$ and $m$.
So, $ab=(pk)(pm)$, then $ab=p(km)$. This is a contradiction.
I'm not sure if that is correct proof. Any help is appreciated. Thank you.
elementary-number-theory proof-verification prime-numbers
elementary-number-theory proof-verification prime-numbers
edited Dec 12 '18 at 4:02
Shaun
9,065113683
asked Dec 12 '18 at 3:46
MettalMettal
257
edited Dec 12 '18 at 4:02
Shaun
9,065113683
asked Dec 12 '18 at 3:46
MettalMettal
257
edited Dec 12 '18 at 4:02
Shaun
9,065113683
edited Dec 12 '18 at 4:02
Shaun
9,065113683
edited Dec 12 '18 at 4:02
Shaun
9,065113683
9,065113683
asked Dec 12 '18 at 3:46
MettalMettal
257
asked Dec 12 '18 at 3:46
MettalMettal
257
asked Dec 12 '18 at 3:46
MettalMettal
257
257
2
$begingroup$
No, it is not correct. You are using that $p$ divides $a$, which is the opposite of what you assumed.
$endgroup$
– Andrés E. Caicedo
Dec 12 '18 at 3:50
1
$begingroup$
If you are doing your proof by contrapositive, you need to assume that $p$ does not divide $a $ and does not divide $b $.
$endgroup$
– AnyAD
Dec 12 '18 at 3:52
$begingroup$
Some courses of algebra provide this property (also known as Euclid's lemma) as the definition for prime numbers, some explanations provided here
$endgroup$
– rtybase
Dec 12 '18 at 9:28
add a comment |
2
$begingroup$
No, it is not correct. You are using that $p$ divides $a$, which is the opposite of what you assumed.
$endgroup$
– Andrés E. Caicedo
Dec 12 '18 at 3:50
1
$begingroup$
If you are doing your proof by contrapositive, you need to assume that $p$ does not divide $a $ and does not divide $b $.
$endgroup$
– AnyAD
Dec 12 '18 at 3:52
$begingroup$
Some courses of algebra provide this property (also known as Euclid's lemma) as the definition for prime numbers, some explanations provided here
$endgroup$
– rtybase
Dec 12 '18 at 9:28
2
2
$begingroup$
No, it is not correct. You are using that $p$ divides $a$, which is the opposite of what you assumed.
$endgroup$
– Andrés E. Caicedo
Dec 12 '18 at 3:50
$begingroup$
No, it is not correct. You are using that $p$ divides $a$, which is the opposite of what you assumed.
$endgroup$
– Andrés E. Caicedo
Dec 12 '18 at 3:50
1
1
$begingroup$
If you are doing your proof by contrapositive, you need to assume that $p$ does not divide $a $ and does not divide $b $.
$endgroup$
– AnyAD
Dec 12 '18 at 3:52
$begingroup$
If you are doing your proof by contrapositive, you need to assume that $p$ does not divide $a $ and does not divide $b $.
$endgroup$
– AnyAD
Dec 12 '18 at 3:52
$begingroup$
Some courses of algebra provide this property (also known as Euclid's lemma) as the definition for prime numbers, some explanations provided here
$endgroup$
– rtybase
Dec 12 '18 at 9:28
$begingroup$
Some courses of algebra provide this property (also known as Euclid's lemma) as the definition for prime numbers, some explanations provided here
$endgroup$
– rtybase
Dec 12 '18 at 9:28
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
The proof is not valid.
First, let's review the contrapositive statement:
Assume $p$ does not divide $a color{red}{text{ and }} p$ does not divide $b$, then $p$ does not divide $ab$.
In the very next line, we have assumed that $p$ doesn't divide $a$, hence we can't write $a=pk$.
One possible way to solve the problem is by prime factorization of $a$ and $b$.
answered Dec 12 '18 at 3:51
Siong Thye GohSiong Thye Goh
101k1466118
$endgroup$
add a comment |
$begingroup$
This is Euclid's lemma.
You could, as one approach, use the fundamental theorem of arithmetic (FTA), to write $a$ and $b$ uniquely as products of powers of primes. Then note that if $p$ isn't in one prime factorization it would have to be in the other (or else it won't be a factor of the product).
Or i found the following proof on Wikipedia. You could use Bezout's identity: if $pmid ab$ and $pnotmid a$, then $a$ and $p$ are relatively prime. So $exists s,r: sa+rp=1$. So $bsa+brp=b$. So $pmid b$ (since it divides both terms of the LHS).
answered Dec 12 '18 at 4:45
Chris CusterChris Custer
12.6k3825
$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%2f3036200%2fif-p-is-a-prime-and-pab-then-pa-or-pb%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The proof is not valid.
First, let's review the contrapositive statement:
Assume $p$ does not divide $a color{red}{text{ and }} p$ does not divide $b$, then $p$ does not divide $ab$.
In the very next line, we have assumed that $p$ doesn't divide $a$, hence we can't write $a=pk$.
One possible way to solve the problem is by prime factorization of $a$ and $b$.
answered Dec 12 '18 at 3:51
Siong Thye GohSiong Thye Goh
101k1466118
$endgroup$
add a comment |
$begingroup$
The proof is not valid.
First, let's review the contrapositive statement:
Assume $p$ does not divide $a color{red}{text{ and }} p$ does not divide $b$, then $p$ does not divide $ab$.
In the very next line, we have assumed that $p$ doesn't divide $a$, hence we can't write $a=pk$.
One possible way to solve the problem is by prime factorization of $a$ and $b$.
answered Dec 12 '18 at 3:51
Siong Thye GohSiong Thye Goh
101k1466118
$endgroup$
add a comment |
$begingroup$
The proof is not valid.
First, let's review the contrapositive statement:
Assume $p$ does not divide $a color{red}{text{ and }} p$ does not divide $b$, then $p$ does not divide $ab$.
In the very next line, we have assumed that $p$ doesn't divide $a$, hence we can't write $a=pk$.
One possible way to solve the problem is by prime factorization of $a$ and $b$.
answered Dec 12 '18 at 3:51
Siong Thye GohSiong Thye Goh
101k1466118
$endgroup$
The proof is not valid.
First, let's review the contrapositive statement:
Assume $p$ does not divide $a color{red}{text{ and }} p$ does not divide $b$, then $p$ does not divide $ab$.
In the very next line, we have assumed that $p$ doesn't divide $a$, hence we can't write $a=pk$.
One possible way to solve the problem is by prime factorization of $a$ and $b$.
answered Dec 12 '18 at 3:51
Siong Thye GohSiong Thye Goh
101k1466118
answered Dec 12 '18 at 3:51
Siong Thye GohSiong Thye Goh
101k1466118
answered Dec 12 '18 at 3:51
Siong Thye GohSiong Thye Goh
101k1466118
answered Dec 12 '18 at 3:51
Siong Thye GohSiong Thye Goh
101k1466118
101k1466118
add a comment |
add a comment |
$begingroup$
This is Euclid's lemma.
You could, as one approach, use the fundamental theorem of arithmetic (FTA), to write $a$ and $b$ uniquely as products of powers of primes. Then note that if $p$ isn't in one prime factorization it would have to be in the other (or else it won't be a factor of the product).
Or i found the following proof on Wikipedia. You could use Bezout's identity: if $pmid ab$ and $pnotmid a$, then $a$ and $p$ are relatively prime. So $exists s,r: sa+rp=1$. So $bsa+brp=b$. So $pmid b$ (since it divides both terms of the LHS).
answered Dec 12 '18 at 4:45
Chris CusterChris Custer
12.6k3825
$endgroup$
add a comment |
$begingroup$
This is Euclid's lemma.
You could, as one approach, use the fundamental theorem of arithmetic (FTA), to write $a$ and $b$ uniquely as products of powers of primes. Then note that if $p$ isn't in one prime factorization it would have to be in the other (or else it won't be a factor of the product).
Or i found the following proof on Wikipedia. You could use Bezout's identity: if $pmid ab$ and $pnotmid a$, then $a$ and $p$ are relatively prime. So $exists s,r: sa+rp=1$. So $bsa+brp=b$. So $pmid b$ (since it divides both terms of the LHS).
answered Dec 12 '18 at 4:45
Chris CusterChris Custer
12.6k3825
$endgroup$
add a comment |
$begingroup$
This is Euclid's lemma.
You could, as one approach, use the fundamental theorem of arithmetic (FTA), to write $a$ and $b$ uniquely as products of powers of primes. Then note that if $p$ isn't in one prime factorization it would have to be in the other (or else it won't be a factor of the product).
Or i found the following proof on Wikipedia. You could use Bezout's identity: if $pmid ab$ and $pnotmid a$, then $a$ and $p$ are relatively prime. So $exists s,r: sa+rp=1$. So $bsa+brp=b$. So $pmid b$ (since it divides both terms of the LHS).
answered Dec 12 '18 at 4:45
Chris CusterChris Custer
12.6k3825
$endgroup$
This is Euclid's lemma.
You could, as one approach, use the fundamental theorem of arithmetic (FTA), to write $a$ and $b$ uniquely as products of powers of primes. Then note that if $p$ isn't in one prime factorization it would have to be in the other (or else it won't be a factor of the product).
Or i found the following proof on Wikipedia. You could use Bezout's identity: if $pmid ab$ and $pnotmid a$, then $a$ and $p$ are relatively prime. So $exists s,r: sa+rp=1$. So $bsa+brp=b$. So $pmid b$ (since it divides both terms of the LHS).
answered Dec 12 '18 at 4:45
Chris CusterChris Custer
12.6k3825
answered Dec 12 '18 at 4:45
Chris CusterChris Custer
12.6k3825
answered Dec 12 '18 at 4:45
Chris CusterChris Custer
12.6k3825
answered Dec 12 '18 at 4:45
Chris CusterChris Custer
12.6k3825
12.6k3825
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%2f3036200%2fif-p-is-a-prime-and-pab-then-pa-or-pb%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
2
$begingroup$
No, it is not correct. You are using that $p$ divides $a$, which is the opposite of what you assumed.
$endgroup$
– Andrés E. Caicedo
Dec 12 '18 at 3:50
1
$begingroup$
If you are doing your proof by contrapositive, you need to assume that $p$ does not divide $a $ and does not divide $b $.
$endgroup$
– AnyAD
Dec 12 '18 at 3:52
$begingroup$
Some courses of algebra provide this property (also known as Euclid's lemma) as the definition for prime numbers, some explanations provided here
$endgroup$
– rtybase
Dec 12 '18 at 9:28