If $m, n>0$ and $gcd(m, n) =d$, then $gcd(a^m-1, a^n-1) =a^d-1$.
$begingroup$
This question has already answered here in other topics, but all answers that I read have some techniques like congruence and fermat numbers and the book which I am reading shows this question in chapter about divisibility. So I have been looking for a way of resolving this problem just using divisibility.
I found a document that brings an answer considering just divisibility, but there are two parts of the solution that I haven't already understood yet. I have read it many times but no success. Here they are
1) why can't $x$ and $y$ be both positive?
2) why did he consider the power $a^{-ny}$, instead of $a^{ny}$, since it is well-known that $t$ divides $a^{ny}-1$?
See remarks on the attached picture in
https://photos.app.goo.gl/RyjPbLkYzJiMpWoG9
elementary-number-theory divisibility greatest-common-divisor
asked Dec 7 '18 at 2:32
user621908user621908
82
$endgroup$
add a comment |
$begingroup$
This question has already answered here in other topics, but all answers that I read have some techniques like congruence and fermat numbers and the book which I am reading shows this question in chapter about divisibility. So I have been looking for a way of resolving this problem just using divisibility.
I found a document that brings an answer considering just divisibility, but there are two parts of the solution that I haven't already understood yet. I have read it many times but no success. Here they are
1) why can't $x$ and $y$ be both positive?
2) why did he consider the power $a^{-ny}$, instead of $a^{ny}$, since it is well-known that $t$ divides $a^{ny}-1$?
See remarks on the attached picture in
https://photos.app.goo.gl/RyjPbLkYzJiMpWoG9
elementary-number-theory divisibility greatest-common-divisor
asked Dec 7 '18 at 2:32
user621908user621908
82
$endgroup$
1
$begingroup$
math.stackexchange.com/questions/7473/…
$endgroup$
– lab bhattacharjee
Dec 7 '18 at 2:37
$begingroup$
I actually would like to understand the argument of the picture too, because as I told above, I am assuming nothing has been told about congruences and fermat numbers
$endgroup$
– user621908
Dec 7 '18 at 2:57
add a comment |
$begingroup$
This question has already answered here in other topics, but all answers that I read have some techniques like congruence and fermat numbers and the book which I am reading shows this question in chapter about divisibility. So I have been looking for a way of resolving this problem just using divisibility.
I found a document that brings an answer considering just divisibility, but there are two parts of the solution that I haven't already understood yet. I have read it many times but no success. Here they are
1) why can't $x$ and $y$ be both positive?
2) why did he consider the power $a^{-ny}$, instead of $a^{ny}$, since it is well-known that $t$ divides $a^{ny}-1$?
See remarks on the attached picture in
https://photos.app.goo.gl/RyjPbLkYzJiMpWoG9
elementary-number-theory divisibility greatest-common-divisor
asked Dec 7 '18 at 2:32
user621908user621908
82
$endgroup$
This question has already answered here in other topics, but all answers that I read have some techniques like congruence and fermat numbers and the book which I am reading shows this question in chapter about divisibility. So I have been looking for a way of resolving this problem just using divisibility.
I found a document that brings an answer considering just divisibility, but there are two parts of the solution that I haven't already understood yet. I have read it many times but no success. Here they are
1) why can't $x$ and $y$ be both positive?
2) why did he consider the power $a^{-ny}$, instead of $a^{ny}$, since it is well-known that $t$ divides $a^{ny}-1$?
See remarks on the attached picture in
https://photos.app.goo.gl/RyjPbLkYzJiMpWoG9
elementary-number-theory divisibility greatest-common-divisor
elementary-number-theory divisibility greatest-common-divisor
asked Dec 7 '18 at 2:32
user621908user621908
82
asked Dec 7 '18 at 2:32
user621908user621908
82
asked Dec 7 '18 at 2:32
user621908user621908
82
asked Dec 7 '18 at 2:32
user621908user621908
82
asked Dec 7 '18 at 2:32
user621908user621908
82
82
1
$begingroup$
math.stackexchange.com/questions/7473/…
$endgroup$
– lab bhattacharjee
Dec 7 '18 at 2:37
$begingroup$
I actually would like to understand the argument of the picture too, because as I told above, I am assuming nothing has been told about congruences and fermat numbers
$endgroup$
– user621908
Dec 7 '18 at 2:57
add a comment |
1
$begingroup$
math.stackexchange.com/questions/7473/…
$endgroup$
– lab bhattacharjee
Dec 7 '18 at 2:37
$begingroup$
I actually would like to understand the argument of the picture too, because as I told above, I am assuming nothing has been told about congruences and fermat numbers
$endgroup$
– user621908
Dec 7 '18 at 2:57
1
1
$begingroup$
math.stackexchange.com/questions/7473/…
$endgroup$
– lab bhattacharjee
Dec 7 '18 at 2:37
$begingroup$
math.stackexchange.com/questions/7473/…
$endgroup$
– lab bhattacharjee
Dec 7 '18 at 2:37
$begingroup$
I actually would like to understand the argument of the picture too, because as I told above, I am assuming nothing has been told about congruences and fermat numbers
$endgroup$
– user621908
Dec 7 '18 at 2:57
$begingroup$
I actually would like to understand the argument of the picture too, because as I told above, I am assuming nothing has been told about congruences and fermat numbers
$endgroup$
– user621908
Dec 7 '18 at 2:57
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Regarding your first part, $x,y$ cannot be both positive. If so, then $dgeq m+n$. But this is impossible, since $d|a implies d leq a$. Do not forget that $m,n$ are both positive by the hypothesis.
Regarding your second part, we have assumed, by the first part, Without Loss of Generality, that $y$ is negative. Now, the term $(a^{ny}-1)$ is not an integer since $a^{ny}$ is a fraction. Hence, we need to negate it to make the power positive. i.e. $(a^{-ny}-1)$.
I hope now it is clear.
answered Dec 7 '18 at 12:29
Maged SaeedMaged Saeed
8471417
$endgroup$
$begingroup$
Very clear about part 2...but no so much about the first because in that solution it is written $d leq m$ which I understand because $d$ divides $m$. Now you said that $d$ divides $a$ and I got more confused. Could you please give me more details about the fact that if $x, y >0$ implies $dgeq m+n$?
$endgroup$
– user621908
Dec 7 '18 at 12:49
$begingroup$
Oh I see. I was trying to give the property that if a number$d$ divides another number $a$ then $d$ must be less than or equal to $a$. In our case, it follows that $d$ shall be less than or equal to $m$ and less than or equal to $n$ because it divides them.
$endgroup$
– Maged Saeed
Dec 7 '18 at 13:03
$begingroup$
Hope I was clear.
$endgroup$
– Maged Saeed
Dec 7 '18 at 13:03
1
$begingroup$
Now I understand your point, but $dgeq m+n$ is still freaking me out. Please
$endgroup$
– user621908
Dec 7 '18 at 14:14
1
$begingroup$
It is ok now. This specific example was very helpful... I appreciate your time and patience
$endgroup$
– user621908
Dec 7 '18 at 15:24
|
show 2 more comments
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%2f3029392%2fif-m-n0-and-gcdm-n-d-then-gcdam-1-an-1-ad-1%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$
Regarding your first part, $x,y$ cannot be both positive. If so, then $dgeq m+n$. But this is impossible, since $d|a implies d leq a$. Do not forget that $m,n$ are both positive by the hypothesis.
Regarding your second part, we have assumed, by the first part, Without Loss of Generality, that $y$ is negative. Now, the term $(a^{ny}-1)$ is not an integer since $a^{ny}$ is a fraction. Hence, we need to negate it to make the power positive. i.e. $(a^{-ny}-1)$.
I hope now it is clear.
answered Dec 7 '18 at 12:29
Maged SaeedMaged Saeed
8471417
$endgroup$
$begingroup$
Very clear about part 2...but no so much about the first because in that solution it is written $d leq m$ which I understand because $d$ divides $m$. Now you said that $d$ divides $a$ and I got more confused. Could you please give me more details about the fact that if $x, y >0$ implies $dgeq m+n$?
$endgroup$
– user621908
Dec 7 '18 at 12:49
$begingroup$
Oh I see. I was trying to give the property that if a number$d$ divides another number $a$ then $d$ must be less than or equal to $a$. In our case, it follows that $d$ shall be less than or equal to $m$ and less than or equal to $n$ because it divides them.
$endgroup$
– Maged Saeed
Dec 7 '18 at 13:03
$begingroup$
Hope I was clear.
$endgroup$
– Maged Saeed
Dec 7 '18 at 13:03
1
$begingroup$
Now I understand your point, but $dgeq m+n$ is still freaking me out. Please
$endgroup$
– user621908
Dec 7 '18 at 14:14
1
$begingroup$
It is ok now. This specific example was very helpful... I appreciate your time and patience
$endgroup$
– user621908
Dec 7 '18 at 15:24
|
show 2 more comments
$begingroup$
Regarding your first part, $x,y$ cannot be both positive. If so, then $dgeq m+n$. But this is impossible, since $d|a implies d leq a$. Do not forget that $m,n$ are both positive by the hypothesis.
Regarding your second part, we have assumed, by the first part, Without Loss of Generality, that $y$ is negative. Now, the term $(a^{ny}-1)$ is not an integer since $a^{ny}$ is a fraction. Hence, we need to negate it to make the power positive. i.e. $(a^{-ny}-1)$.
I hope now it is clear.
answered Dec 7 '18 at 12:29
Maged SaeedMaged Saeed
8471417
$endgroup$
$begingroup$
Very clear about part 2...but no so much about the first because in that solution it is written $d leq m$ which I understand because $d$ divides $m$. Now you said that $d$ divides $a$ and I got more confused. Could you please give me more details about the fact that if $x, y >0$ implies $dgeq m+n$?
$endgroup$
– user621908
Dec 7 '18 at 12:49
$begingroup$
Oh I see. I was trying to give the property that if a number$d$ divides another number $a$ then $d$ must be less than or equal to $a$. In our case, it follows that $d$ shall be less than or equal to $m$ and less than or equal to $n$ because it divides them.
$endgroup$
– Maged Saeed
Dec 7 '18 at 13:03
$begingroup$
Hope I was clear.
$endgroup$
– Maged Saeed
Dec 7 '18 at 13:03
1
$begingroup$
Now I understand your point, but $dgeq m+n$ is still freaking me out. Please
$endgroup$
– user621908
Dec 7 '18 at 14:14
1
$begingroup$
It is ok now. This specific example was very helpful... I appreciate your time and patience
$endgroup$
– user621908
Dec 7 '18 at 15:24
|
show 2 more comments
$begingroup$
Regarding your first part, $x,y$ cannot be both positive. If so, then $dgeq m+n$. But this is impossible, since $d|a implies d leq a$. Do not forget that $m,n$ are both positive by the hypothesis.
Regarding your second part, we have assumed, by the first part, Without Loss of Generality, that $y$ is negative. Now, the term $(a^{ny}-1)$ is not an integer since $a^{ny}$ is a fraction. Hence, we need to negate it to make the power positive. i.e. $(a^{-ny}-1)$.
I hope now it is clear.
answered Dec 7 '18 at 12:29
Maged SaeedMaged Saeed
8471417
$endgroup$
Regarding your first part, $x,y$ cannot be both positive. If so, then $dgeq m+n$. But this is impossible, since $d|a implies d leq a$. Do not forget that $m,n$ are both positive by the hypothesis.
Regarding your second part, we have assumed, by the first part, Without Loss of Generality, that $y$ is negative. Now, the term $(a^{ny}-1)$ is not an integer since $a^{ny}$ is a fraction. Hence, we need to negate it to make the power positive. i.e. $(a^{-ny}-1)$.
I hope now it is clear.
answered Dec 7 '18 at 12:29
Maged SaeedMaged Saeed
8471417
answered Dec 7 '18 at 12:29
Maged SaeedMaged Saeed
8471417
answered Dec 7 '18 at 12:29
Maged SaeedMaged Saeed
8471417
answered Dec 7 '18 at 12:29
Maged SaeedMaged Saeed
8471417
8471417
$begingroup$
Very clear about part 2...but no so much about the first because in that solution it is written $d leq m$ which I understand because $d$ divides $m$. Now you said that $d$ divides $a$ and I got more confused. Could you please give me more details about the fact that if $x, y >0$ implies $dgeq m+n$?
$endgroup$
– user621908
Dec 7 '18 at 12:49
$begingroup$
Oh I see. I was trying to give the property that if a number$d$ divides another number $a$ then $d$ must be less than or equal to $a$. In our case, it follows that $d$ shall be less than or equal to $m$ and less than or equal to $n$ because it divides them.
$endgroup$
– Maged Saeed
Dec 7 '18 at 13:03
$begingroup$
Hope I was clear.
$endgroup$
– Maged Saeed
Dec 7 '18 at 13:03
1
$begingroup$
Now I understand your point, but $dgeq m+n$ is still freaking me out. Please
$endgroup$
– user621908
Dec 7 '18 at 14:14
1
$begingroup$
It is ok now. This specific example was very helpful... I appreciate your time and patience
$endgroup$
– user621908
Dec 7 '18 at 15:24
|
show 2 more comments
$begingroup$
Very clear about part 2...but no so much about the first because in that solution it is written $d leq m$ which I understand because $d$ divides $m$. Now you said that $d$ divides $a$ and I got more confused. Could you please give me more details about the fact that if $x, y >0$ implies $dgeq m+n$?
$endgroup$
– user621908
Dec 7 '18 at 12:49
$begingroup$
Oh I see. I was trying to give the property that if a number$d$ divides another number $a$ then $d$ must be less than or equal to $a$. In our case, it follows that $d$ shall be less than or equal to $m$ and less than or equal to $n$ because it divides them.
$endgroup$
– Maged Saeed
Dec 7 '18 at 13:03
$begingroup$
Hope I was clear.
$endgroup$
– Maged Saeed
Dec 7 '18 at 13:03
1
$begingroup$
Now I understand your point, but $dgeq m+n$ is still freaking me out. Please
$endgroup$
– user621908
Dec 7 '18 at 14:14
1
$begingroup$
It is ok now. This specific example was very helpful... I appreciate your time and patience
$endgroup$
– user621908
Dec 7 '18 at 15:24
$begingroup$
Very clear about part 2...but no so much about the first because in that solution it is written $d leq m$ which I understand because $d$ divides $m$. Now you said that $d$ divides $a$ and I got more confused. Could you please give me more details about the fact that if $x, y >0$ implies $dgeq m+n$?
$endgroup$
– user621908
Dec 7 '18 at 12:49
$begingroup$
Very clear about part 2...but no so much about the first because in that solution it is written $d leq m$ which I understand because $d$ divides $m$. Now you said that $d$ divides $a$ and I got more confused. Could you please give me more details about the fact that if $x, y >0$ implies $dgeq m+n$?
$endgroup$
– user621908
Dec 7 '18 at 12:49
$begingroup$
Oh I see. I was trying to give the property that if a number$d$ divides another number $a$ then $d$ must be less than or equal to $a$. In our case, it follows that $d$ shall be less than or equal to $m$ and less than or equal to $n$ because it divides them.
$endgroup$
– Maged Saeed
Dec 7 '18 at 13:03
$begingroup$
Oh I see. I was trying to give the property that if a number$d$ divides another number $a$ then $d$ must be less than or equal to $a$. In our case, it follows that $d$ shall be less than or equal to $m$ and less than or equal to $n$ because it divides them.
$endgroup$
– Maged Saeed
Dec 7 '18 at 13:03
$begingroup$
Hope I was clear.
$endgroup$
– Maged Saeed
Dec 7 '18 at 13:03
$begingroup$
Hope I was clear.
$endgroup$
– Maged Saeed
Dec 7 '18 at 13:03
1
1
$begingroup$
Now I understand your point, but $dgeq m+n$ is still freaking me out. Please
$endgroup$
– user621908
Dec 7 '18 at 14:14
$begingroup$
Now I understand your point, but $dgeq m+n$ is still freaking me out. Please
$endgroup$
– user621908
Dec 7 '18 at 14:14
1
1
$begingroup$
It is ok now. This specific example was very helpful... I appreciate your time and patience
$endgroup$
– user621908
Dec 7 '18 at 15:24
$begingroup$
It is ok now. This specific example was very helpful... I appreciate your time and patience
$endgroup$
– user621908
Dec 7 '18 at 15:24
|
show 2 more comments
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%2f3029392%2fif-m-n0-and-gcdm-n-d-then-gcdam-1-an-1-ad-1%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$
math.stackexchange.com/questions/7473/…
$endgroup$
– lab bhattacharjee
Dec 7 '18 at 2:37
$begingroup$
I actually would like to understand the argument of the picture too, because as I told above, I am assuming nothing has been told about congruences and fermat numbers
$endgroup$
– user621908
Dec 7 '18 at 2:57