Mixing
Definition of prime numbers and equivalence
$begingroup$
A prime number $p$ is a positive integer that has exactly two different dividers ($1$ and itself). This is a very clear and universal definition.
My notes say that this definition is equivalent to the previous one: $p$ is a prime number if from $p mid ab$ follows that $p mid a$ or $p mid b$ for $a,b in mathbb{Z}$. I was wondering why this is an equivalent definition for a prime number.
Thanks in advance!
number-theory elementary-number-theory discrete-mathematics prime-numbers divisibility
edited Jan 26 at 11:30
Maria Mazur
47.9k1260120
asked Jan 26 at 10:59
ZacharyZachary
1919
$endgroup$
add a comment |
$begingroup$
A prime number $p$ is a positive integer that has exactly two different dividers ($1$ and itself). This is a very clear and universal definition.
My notes say that this definition is equivalent to the previous one: $p$ is a prime number if from $p mid ab$ follows that $p mid a$ or $p mid b$ for $a,b in mathbb{Z}$. I was wondering why this is an equivalent definition for a prime number.
Thanks in advance!
number-theory elementary-number-theory discrete-mathematics prime-numbers divisibility
edited Jan 26 at 11:30
Maria Mazur
47.9k1260120
asked Jan 26 at 10:59
ZacharyZachary
1919
$endgroup$
2
$begingroup$
Formally the first definition states that $p$ is irreducible and the second that $p$ is prime. Every prime $p$ is irreducible and in the special case of the ring of integers the concepts irreducible and prime coincide. But in a more general setting an irreducible element of a ring is not necessarily prime. So actually prime is stronger than irreducible.
$endgroup$
– drhab
Jan 26 at 11:16
add a comment |
$begingroup$
A prime number $p$ is a positive integer that has exactly two different dividers ($1$ and itself). This is a very clear and universal definition.
My notes say that this definition is equivalent to the previous one: $p$ is a prime number if from $p mid ab$ follows that $p mid a$ or $p mid b$ for $a,b in mathbb{Z}$. I was wondering why this is an equivalent definition for a prime number.
Thanks in advance!
number-theory elementary-number-theory discrete-mathematics prime-numbers divisibility
edited Jan 26 at 11:30
Maria Mazur
47.9k1260120
asked Jan 26 at 10:59
ZacharyZachary
1919
$endgroup$
A prime number $p$ is a positive integer that has exactly two different dividers ($1$ and itself). This is a very clear and universal definition.
My notes say that this definition is equivalent to the previous one: $p$ is a prime number if from $p mid ab$ follows that $p mid a$ or $p mid b$ for $a,b in mathbb{Z}$. I was wondering why this is an equivalent definition for a prime number.
Thanks in advance!
number-theory elementary-number-theory discrete-mathematics prime-numbers divisibility
number-theory elementary-number-theory discrete-mathematics prime-numbers divisibility
edited Jan 26 at 11:30
Maria Mazur
47.9k1260120
asked Jan 26 at 10:59
ZacharyZachary
1919
edited Jan 26 at 11:30
Maria Mazur
47.9k1260120
asked Jan 26 at 10:59
ZacharyZachary
1919
edited Jan 26 at 11:30
Maria Mazur
47.9k1260120
edited Jan 26 at 11:30
Maria Mazur
47.9k1260120
edited Jan 26 at 11:30
Maria Mazur
47.9k1260120
47.9k1260120
asked Jan 26 at 10:59
ZacharyZachary
1919
asked Jan 26 at 10:59
ZacharyZachary
1919
asked Jan 26 at 10:59
ZacharyZachary
1919
1919
2
$begingroup$
Formally the first definition states that $p$ is irreducible and the second that $p$ is prime. Every prime $p$ is irreducible and in the special case of the ring of integers the concepts irreducible and prime coincide. But in a more general setting an irreducible element of a ring is not necessarily prime. So actually prime is stronger than irreducible.
$endgroup$
– drhab
Jan 26 at 11:16
add a comment |
2
$begingroup$
Formally the first definition states that $p$ is irreducible and the second that $p$ is prime. Every prime $p$ is irreducible and in the special case of the ring of integers the concepts irreducible and prime coincide. But in a more general setting an irreducible element of a ring is not necessarily prime. So actually prime is stronger than irreducible.
$endgroup$
– drhab
Jan 26 at 11:16
2
2
$begingroup$
Formally the first definition states that $p$ is irreducible and the second that $p$ is prime. Every prime $p$ is irreducible and in the special case of the ring of integers the concepts irreducible and prime coincide. But in a more general setting an irreducible element of a ring is not necessarily prime. So actually prime is stronger than irreducible.
$endgroup$
– drhab
Jan 26 at 11:16
$begingroup$
Formally the first definition states that $p$ is irreducible and the second that $p$ is prime. Every prime $p$ is irreducible and in the special case of the ring of integers the concepts irreducible and prime coincide. But in a more general setting an irreducible element of a ring is not necessarily prime. So actually prime is stronger than irreducible.
$endgroup$
– drhab
Jan 26 at 11:16
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Let $p$ be prime according to the first definition and let $pnmid a$ and $pnmid b$ where $a$ and $b$ are positive integers.
It is well known that there are unique expressions $a=r_1^{u_1}cdots r_n^{u_n}$ and $b=s_1^{v_1}cdots s_m^{v_m}$ where the $s_i$ and $r_j$ are primes according to the first definition and the $u_i$ and $v_j$ are positive integers.
Then from $pnmid a$ and $pnmid b$ it follows that $pnotin{r_1,dots, r_n,s_1,dots, s_n}$ which is evidently the set of prime factors of $ab$. So we conclude that $pnmid ab$.
Proved is now that a prime according to the first definition is also a prime according to the second definition.
For the converse see the answer of greedoid.
Formally the first definition states that $p$ is irreducible and the second that $p$ is prime. Every prime $p$ is irreducible and in the special case of the ring of integers the concepts irreducible and prime coincide. But in a more general setting an irreducible element of a ring is not necessarily prime. So actually prime is stronger than irreducible.
answered Jan 26 at 11:32
drhabdrhab
103k545136
$endgroup$
add a comment |
$begingroup$
Suppose there is positive not prime $n$ such that $$n mid abimplies n mid a ;;;{rm or};;; n mid b$$ for $a,b in mathbb{Z}$.
Then $n= xcdot y$ and $xyne 1$, so $nmid xy$ and thus $nmid x$ or $nmid y$.
But $x,y<n$ so we have a cotnradiction.
The other way is well known fact in number theory.
answered Jan 26 at 11:07
Maria MazurMaria Mazur
47.9k1260120
$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%2f3088120%2fdefinition-of-prime-numbers-and-equivalence%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$
Let $p$ be prime according to the first definition and let $pnmid a$ and $pnmid b$ where $a$ and $b$ are positive integers.
It is well known that there are unique expressions $a=r_1^{u_1}cdots r_n^{u_n}$ and $b=s_1^{v_1}cdots s_m^{v_m}$ where the $s_i$ and $r_j$ are primes according to the first definition and the $u_i$ and $v_j$ are positive integers.
Then from $pnmid a$ and $pnmid b$ it follows that $pnotin{r_1,dots, r_n,s_1,dots, s_n}$ which is evidently the set of prime factors of $ab$. So we conclude that $pnmid ab$.
Proved is now that a prime according to the first definition is also a prime according to the second definition.
For the converse see the answer of greedoid.
Formally the first definition states that $p$ is irreducible and the second that $p$ is prime. Every prime $p$ is irreducible and in the special case of the ring of integers the concepts irreducible and prime coincide. But in a more general setting an irreducible element of a ring is not necessarily prime. So actually prime is stronger than irreducible.
answered Jan 26 at 11:32
drhabdrhab
103k545136
$endgroup$
add a comment |
$begingroup$
Let $p$ be prime according to the first definition and let $pnmid a$ and $pnmid b$ where $a$ and $b$ are positive integers.
It is well known that there are unique expressions $a=r_1^{u_1}cdots r_n^{u_n}$ and $b=s_1^{v_1}cdots s_m^{v_m}$ where the $s_i$ and $r_j$ are primes according to the first definition and the $u_i$ and $v_j$ are positive integers.
Then from $pnmid a$ and $pnmid b$ it follows that $pnotin{r_1,dots, r_n,s_1,dots, s_n}$ which is evidently the set of prime factors of $ab$. So we conclude that $pnmid ab$.
Proved is now that a prime according to the first definition is also a prime according to the second definition.
For the converse see the answer of greedoid.
Formally the first definition states that $p$ is irreducible and the second that $p$ is prime. Every prime $p$ is irreducible and in the special case of the ring of integers the concepts irreducible and prime coincide. But in a more general setting an irreducible element of a ring is not necessarily prime. So actually prime is stronger than irreducible.
answered Jan 26 at 11:32
drhabdrhab
103k545136
$endgroup$
add a comment |
$begingroup$
Let $p$ be prime according to the first definition and let $pnmid a$ and $pnmid b$ where $a$ and $b$ are positive integers.
It is well known that there are unique expressions $a=r_1^{u_1}cdots r_n^{u_n}$ and $b=s_1^{v_1}cdots s_m^{v_m}$ where the $s_i$ and $r_j$ are primes according to the first definition and the $u_i$ and $v_j$ are positive integers.
Then from $pnmid a$ and $pnmid b$ it follows that $pnotin{r_1,dots, r_n,s_1,dots, s_n}$ which is evidently the set of prime factors of $ab$. So we conclude that $pnmid ab$.
Proved is now that a prime according to the first definition is also a prime according to the second definition.
For the converse see the answer of greedoid.
Formally the first definition states that $p$ is irreducible and the second that $p$ is prime. Every prime $p$ is irreducible and in the special case of the ring of integers the concepts irreducible and prime coincide. But in a more general setting an irreducible element of a ring is not necessarily prime. So actually prime is stronger than irreducible.
answered Jan 26 at 11:32
drhabdrhab
103k545136
$endgroup$
Let $p$ be prime according to the first definition and let $pnmid a$ and $pnmid b$ where $a$ and $b$ are positive integers.
It is well known that there are unique expressions $a=r_1^{u_1}cdots r_n^{u_n}$ and $b=s_1^{v_1}cdots s_m^{v_m}$ where the $s_i$ and $r_j$ are primes according to the first definition and the $u_i$ and $v_j$ are positive integers.
Then from $pnmid a$ and $pnmid b$ it follows that $pnotin{r_1,dots, r_n,s_1,dots, s_n}$ which is evidently the set of prime factors of $ab$. So we conclude that $pnmid ab$.
Proved is now that a prime according to the first definition is also a prime according to the second definition.
For the converse see the answer of greedoid.
Formally the first definition states that $p$ is irreducible and the second that $p$ is prime. Every prime $p$ is irreducible and in the special case of the ring of integers the concepts irreducible and prime coincide. But in a more general setting an irreducible element of a ring is not necessarily prime. So actually prime is stronger than irreducible.
answered Jan 26 at 11:32
drhabdrhab
103k545136
answered Jan 26 at 11:32
drhabdrhab
103k545136
answered Jan 26 at 11:32
drhabdrhab
103k545136
answered Jan 26 at 11:32
drhabdrhab
103k545136
103k545136
add a comment |
add a comment |
$begingroup$
Suppose there is positive not prime $n$ such that $$n mid abimplies n mid a ;;;{rm or};;; n mid b$$ for $a,b in mathbb{Z}$.
Then $n= xcdot y$ and $xyne 1$, so $nmid xy$ and thus $nmid x$ or $nmid y$.
But $x,y<n$ so we have a cotnradiction.
The other way is well known fact in number theory.
answered Jan 26 at 11:07
Maria MazurMaria Mazur
47.9k1260120
$endgroup$
add a comment |
$begingroup$
Suppose there is positive not prime $n$ such that $$n mid abimplies n mid a ;;;{rm or};;; n mid b$$ for $a,b in mathbb{Z}$.
Then $n= xcdot y$ and $xyne 1$, so $nmid xy$ and thus $nmid x$ or $nmid y$.
But $x,y<n$ so we have a cotnradiction.
The other way is well known fact in number theory.
answered Jan 26 at 11:07
Maria MazurMaria Mazur
47.9k1260120
$endgroup$
add a comment |
$begingroup$
Suppose there is positive not prime $n$ such that $$n mid abimplies n mid a ;;;{rm or};;; n mid b$$ for $a,b in mathbb{Z}$.
Then $n= xcdot y$ and $xyne 1$, so $nmid xy$ and thus $nmid x$ or $nmid y$.
But $x,y<n$ so we have a cotnradiction.
The other way is well known fact in number theory.
answered Jan 26 at 11:07
Maria MazurMaria Mazur
47.9k1260120
$endgroup$
Suppose there is positive not prime $n$ such that $$n mid abimplies n mid a ;;;{rm or};;; n mid b$$ for $a,b in mathbb{Z}$.
Then $n= xcdot y$ and $xyne 1$, so $nmid xy$ and thus $nmid x$ or $nmid y$.
But $x,y<n$ so we have a cotnradiction.
The other way is well known fact in number theory.
answered Jan 26 at 11:07
Maria MazurMaria Mazur
47.9k1260120
answered Jan 26 at 11:07
Maria MazurMaria Mazur
47.9k1260120
answered Jan 26 at 11:07
Maria MazurMaria Mazur
47.9k1260120
answered Jan 26 at 11:07
Maria MazurMaria Mazur
47.9k1260120
47.9k1260120
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%2f3088120%2fdefinition-of-prime-numbers-and-equivalence%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$
Formally the first definition states that $p$ is irreducible and the second that $p$ is prime. Every prime $p$ is irreducible and in the special case of the ring of integers the concepts irreducible and prime coincide. But in a more general setting an irreducible element of a ring is not necessarily prime. So actually prime is stronger than irreducible.
$endgroup$
– drhab
Jan 26 at 11:16