$x^a - 1$ divides $x^b - 1$ if and only if $a$ divides $b$ Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)number theory division of power for the case $(n^r −1)$ divides $(n^m −1)$ if and only if $r$ divides $m$.How to show that if p is prime and m,n are natural numbers then $p^m -1 | p^n -1$$a,r,min mathbbZ^+$ prove that $(a^r-1)mid (a^m-1)Leftrightarrow rmid m$Show that $x^p^m - x$ divides $x^p^n - x$ if and only if $m$ divides $n$.Let $a$ and $b$ be integers $ge 1$. prove that $(2^a-1) | (2^ab-1)$.Prove that $gcd(a^n - 1, a^m - 1) = a^gcd(n, m) - 1$Proving that $gcd(2^m - 1, 2^n - 1) = 2^gcd(m,n ) - 1$Factoring $a^10+a^5+1$Number theory fun problemProve that if $frac 10^n-19 | frac 10^m-19$, then $n|m$If $a^2$ divides $b^2$, then $a$ divides $b$Suppose $a, b$ and $n$ are positive integers. Prove that $a^n$ divides $b^n$ if and only if $a$ divides $b$.Prove that $a$ divides $b$ and $b$ divides $a$ if and only if $a = pm b$If $N$ divides $a$ and $N$ divides $b$ thennumber theory division of power for the case $(n^r −1)$ divides $(n^m −1)$ if and only if $r$ divides $m$.If $a^a$ divides $b^b$, then $a$ divides $b$?Prove: For a,b,c positive integers, ac divides bc if and only if a divides bLet $n,a_1,a_2,ldots,a_n$ be integers such that $a_1a_2a_3cdots a_n =n$ and $a_1+a_2+a_3+cdots+a_n=0$. Prove that 4 divides nProve that if 2 divides n and 7 divides n, then 14 divides nA problem on divisibility: If $c$ divides $ab$ and $gcd(b,c)=1$, then prove that $c$ divides $a$.
Can anything be seen from the center of the Boötes void? How dark would it be?
Do I really need to have a message in a novel to appeal to readers?
8 Prisoners wearing hats
Why aren't air breathing engines used as small first stages?
Is it cost-effective to upgrade an old-ish Giant Escape R3 commuter bike with entry-level branded parts (wheels, drivetrain)?
If a contract sometimes uses the wrong name, is it still valid?
Using et al. for a last / senior author rather than for a first author
First console to have temporary backward compatibility
Compare a given version number in the form major.minor.build.patch and see if one is less than the other
Most bit efficient text communication method?
Generate an RGB colour grid
Wu formula for manifolds with boundary
Why are there no cargo aircraft with "flying wing" design?
Is it common practice to audition new musicians one-on-one before rehearsing with the entire band?
What is the meaning of the simile “quick as silk”?
Circuit to "zoom in" on mV fluctuations of a DC signal?
Do wooden building fires get hotter than 600°C?
Is grep documentation wrong?
What does this Jacques Hadamard quote mean?
How to Make a Beautiful Stacked 3D Plot
How to react to hostile behavior from a senior developer?
How come Sam didn't become Lord of Horn Hill?
Is there such thing as an Availability Group failover trigger?
Is it ethical to give a final exam after the professor has quit before teaching the remaining chapters of the course?
$x^a - 1$ divides $x^b - 1$ if and only if $a$ divides $b$
Announcing the arrival of Valued Associate #679: Cesar Manara
Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)number theory division of power for the case $(n^r −1)$ divides $(n^m −1)$ if and only if $r$ divides $m$.How to show that if p is prime and m,n are natural numbers then $p^m -1 | p^n -1$$a,r,min mathbbZ^+$ prove that $(a^r-1)mid (a^m-1)Leftrightarrow rmid m$Show that $x^p^m - x$ divides $x^p^n - x$ if and only if $m$ divides $n$.Let $a$ and $b$ be integers $ge 1$. prove that $(2^a-1) | (2^ab-1)$.Prove that $gcd(a^n - 1, a^m - 1) = a^gcd(n, m) - 1$Proving that $gcd(2^m - 1, 2^n - 1) = 2^gcd(m,n ) - 1$Factoring $a^10+a^5+1$Number theory fun problemProve that if $frac 10^n-19 | frac 10^m-19$, then $n|m$If $a^2$ divides $b^2$, then $a$ divides $b$Suppose $a, b$ and $n$ are positive integers. Prove that $a^n$ divides $b^n$ if and only if $a$ divides $b$.Prove that $a$ divides $b$ and $b$ divides $a$ if and only if $a = pm b$If $N$ divides $a$ and $N$ divides $b$ thennumber theory division of power for the case $(n^r −1)$ divides $(n^m −1)$ if and only if $r$ divides $m$.If $a^a$ divides $b^b$, then $a$ divides $b$?Prove: For a,b,c positive integers, ac divides bc if and only if a divides bLet $n,a_1,a_2,ldots,a_n$ be integers such that $a_1a_2a_3cdots a_n =n$ and $a_1+a_2+a_3+cdots+a_n=0$. Prove that 4 divides nProve that if 2 divides n and 7 divides n, then 14 divides nA problem on divisibility: If $c$ divides $ab$ and $gcd(b,c)=1$, then prove that $c$ divides $a$.
$begingroup$
Let $x > 1$ and $a$, $b$ be positive integers. I know that $a$ divides $b$ implies that $x^a - 1$ divides $x^b - 1$. If $b = qa$, then
$x^b - 1 = (x^a)^q - 1^q = (x^a - 1)((x^a)^q-1 + ldots + x^a + 1)$
I'm interested in the converse of the statement. If $x^a - 1$ divides $x^b - 1$, does this imply that $a$ divides $b$?
elementary-number-theory
asked Apr 4 '12 at 14:39
spinspin
3,90512258
$endgroup$
add a comment |
$begingroup$
Let $x > 1$ and $a$, $b$ be positive integers. I know that $a$ divides $b$ implies that $x^a - 1$ divides $x^b - 1$. If $b = qa$, then
$x^b - 1 = (x^a)^q - 1^q = (x^a - 1)((x^a)^q-1 + ldots + x^a + 1)$
I'm interested in the converse of the statement. If $x^a - 1$ divides $x^b - 1$, does this imply that $a$ divides $b$?
elementary-number-theory
asked Apr 4 '12 at 14:39
spinspin
3,90512258
$endgroup$
5
$begingroup$
By the division algorithm, you can write $b=qa+r$ with $0 leq r < a$. When you do long division of $x^b - 1$ by $x^a - 1$, you will eventuall encounter the remainder $x^r - 1$, and the process stops. If $x^a - 1$ divides $x^b - 1$, the remainder must be $0$, whence $r=0$.
$endgroup$
– Chris Leary
Apr 4 '12 at 14:57
$begingroup$
Generalization : math.stackexchange.com/questions/7473/…
$endgroup$
– lab bhattacharjee
Mar 9 '14 at 7:13
add a comment |
$begingroup$
Let $x > 1$ and $a$, $b$ be positive integers. I know that $a$ divides $b$ implies that $x^a - 1$ divides $x^b - 1$. If $b = qa$, then
$x^b - 1 = (x^a)^q - 1^q = (x^a - 1)((x^a)^q-1 + ldots + x^a + 1)$
I'm interested in the converse of the statement. If $x^a - 1$ divides $x^b - 1$, does this imply that $a$ divides $b$?
elementary-number-theory
asked Apr 4 '12 at 14:39
spinspin
3,90512258
$endgroup$
Let $x > 1$ and $a$, $b$ be positive integers. I know that $a$ divides $b$ implies that $x^a - 1$ divides $x^b - 1$. If $b = qa$, then
$x^b - 1 = (x^a)^q - 1^q = (x^a - 1)((x^a)^q-1 + ldots + x^a + 1)$
I'm interested in the converse of the statement. If $x^a - 1$ divides $x^b - 1$, does this imply that $a$ divides $b$?
elementary-number-theory
elementary-number-theory
asked Apr 4 '12 at 14:39
spinspin
3,90512258
asked Apr 4 '12 at 14:39
spinspin
3,90512258
edited Apr 4 '12 at 14:50
spin
asked Apr 4 '12 at 14:39
spinspin
3,90512258
asked Apr 4 '12 at 14:39
spinspin
3,90512258
asked Apr 4 '12 at 14:39
spinspin
3,90512258
3,90512258
5
$begingroup$
By the division algorithm, you can write $b=qa+r$ with $0 leq r < a$. When you do long division of $x^b - 1$ by $x^a - 1$, you will eventuall encounter the remainder $x^r - 1$, and the process stops. If $x^a - 1$ divides $x^b - 1$, the remainder must be $0$, whence $r=0$.
$endgroup$
– Chris Leary
Apr 4 '12 at 14:57
$begingroup$
Generalization : math.stackexchange.com/questions/7473/…
$endgroup$
– lab bhattacharjee
Mar 9 '14 at 7:13
add a comment |
5
$begingroup$
By the division algorithm, you can write $b=qa+r$ with $0 leq r < a$. When you do long division of $x^b - 1$ by $x^a - 1$, you will eventuall encounter the remainder $x^r - 1$, and the process stops. If $x^a - 1$ divides $x^b - 1$, the remainder must be $0$, whence $r=0$.
$endgroup$
– Chris Leary
Apr 4 '12 at 14:57
$begingroup$
Generalization : math.stackexchange.com/questions/7473/…
$endgroup$
– lab bhattacharjee
Mar 9 '14 at 7:13
5
5
$begingroup$
By the division algorithm, you can write $b=qa+r$ with $0 leq r < a$. When you do long division of $x^b - 1$ by $x^a - 1$, you will eventuall encounter the remainder $x^r - 1$, and the process stops. If $x^a - 1$ divides $x^b - 1$, the remainder must be $0$, whence $r=0$.
$endgroup$
– Chris Leary
Apr 4 '12 at 14:57
$begingroup$
By the division algorithm, you can write $b=qa+r$ with $0 leq r < a$. When you do long division of $x^b - 1$ by $x^a - 1$, you will eventuall encounter the remainder $x^r - 1$, and the process stops. If $x^a - 1$ divides $x^b - 1$, the remainder must be $0$, whence $r=0$.
$endgroup$
– Chris Leary
Apr 4 '12 at 14:57
$begingroup$
Generalization : math.stackexchange.com/questions/7473/…
$endgroup$
– lab bhattacharjee
Mar 9 '14 at 7:13
$begingroup$
Generalization : math.stackexchange.com/questions/7473/…
$endgroup$
– lab bhattacharjee
Mar 9 '14 at 7:13
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Let $b=a cdot q+r$.
Then
$$x^b-1=x^b-x^r+x^r-1=x^r(x^aq-1)+x^r-1 ,.$$
Use that $x^a-1$ divides $x^aq-1$.
answered Apr 4 '12 at 14:51
N. S.N. S.
105k7115210
$endgroup$
$begingroup$
@N.S. Aren't you using recursion there? The last sentence.
$endgroup$
– TheRandomGuy
Mar 5 '16 at 14:47
$begingroup$
@DhruvSomani The last step is just the formula $$y^q-1^q=(y-1)(y^q-1+..+y+1)$$
$endgroup$
– N. S.
Mar 5 '16 at 19:52
1
$begingroup$
Notice that with the conditions of strict inequality in the Euclidean algorithm we cannot have dat $x^a-1$ divides $x^r-1$. So it is more precise !
$endgroup$
– Maman
Oct 16 '17 at 18:19
$begingroup$
I arrived that $x^a-1$ divides $x^r-1$, but how does that means $r=0$?
$endgroup$
– Ning Wang
Mar 18 '18 at 9:55
$begingroup$
It seems like that $0 le r <a$ is needed. @Maman: Is this what you meant?
$endgroup$
– Ning Wang
Mar 18 '18 at 9:58
|
show 1 more comment
$begingroup$
Hint $:$ By Theorem below $rm:(x^a!-1,x^b!-1) = x^(a,b)!-1$ $[ rm: =: x^a!-1!iff! (a,b)=a!iff! amid b,]$
when applied to $rm f_n = x^n!-1 = x^n-m : (x^m!-1) + x^n-m!-1 =: g f_m + f_n-mequiv f_n-mpmodf_m$
Theorem $: $ If $rm:f_n:$ is a sequence in a GCD domain (domain where gcds exist) satisfying $rm f_:0 =: 0: $ and $rm : f_nequiv f_n-m (mod f_m) $ for $rm: n > m $ then $rm: (f_n,f_m) = f_(n,:m) : $ where $rm (i,:j) = gcd(i,:j):$.
Proof $ $ By induction on $rm:n + m:$. The theorem is trivially true if $rm n = m $ or $rm n = 0 $ or $rm: m = 0:$.
So we may assume $rm:n > m > 0:$.$ $ Note $rm (f_n,f_m): = (f_n-m,f_m) $ follows from the hypothesis.
Since $rm: (n-m)+m < n+m: , $ induction yields $rm (f_n-m,f_m) = f_(n-m,:m) = f_(n,:m) $
See this post and its links for more on such divisibility sequences.
answered Apr 4 '12 at 16:45
Bill DubuqueBill Dubuque
214k29197659
$endgroup$
$begingroup$
Thanks for the answer, it's always interesting a more general approach
$endgroup$
– spin
Apr 8 '12 at 20:05
add a comment |
Your Answer
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%2f128007%2fxa-1-divides-xb-1-if-and-only-if-a-divides-b%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 $b=a cdot q+r$.
Then
$$x^b-1=x^b-x^r+x^r-1=x^r(x^aq-1)+x^r-1 ,.$$
Use that $x^a-1$ divides $x^aq-1$.
answered Apr 4 '12 at 14:51
N. S.N. S.
105k7115210
$endgroup$
$begingroup$
@N.S. Aren't you using recursion there? The last sentence.
$endgroup$
– TheRandomGuy
Mar 5 '16 at 14:47
$begingroup$
@DhruvSomani The last step is just the formula $$y^q-1^q=(y-1)(y^q-1+..+y+1)$$
$endgroup$
– N. S.
Mar 5 '16 at 19:52
1
$begingroup$
Notice that with the conditions of strict inequality in the Euclidean algorithm we cannot have dat $x^a-1$ divides $x^r-1$. So it is more precise !
$endgroup$
– Maman
Oct 16 '17 at 18:19
$begingroup$
I arrived that $x^a-1$ divides $x^r-1$, but how does that means $r=0$?
$endgroup$
– Ning Wang
Mar 18 '18 at 9:55
$begingroup$
It seems like that $0 le r <a$ is needed. @Maman: Is this what you meant?
$endgroup$
– Ning Wang
Mar 18 '18 at 9:58
|
show 1 more comment
$begingroup$
Let $b=a cdot q+r$.
Then
$$x^b-1=x^b-x^r+x^r-1=x^r(x^aq-1)+x^r-1 ,.$$
Use that $x^a-1$ divides $x^aq-1$.
answered Apr 4 '12 at 14:51
N. S.N. S.
105k7115210
$endgroup$
$begingroup$
@N.S. Aren't you using recursion there? The last sentence.
$endgroup$
– TheRandomGuy
Mar 5 '16 at 14:47
$begingroup$
@DhruvSomani The last step is just the formula $$y^q-1^q=(y-1)(y^q-1+..+y+1)$$
$endgroup$
– N. S.
Mar 5 '16 at 19:52
1
$begingroup$
Notice that with the conditions of strict inequality in the Euclidean algorithm we cannot have dat $x^a-1$ divides $x^r-1$. So it is more precise !
$endgroup$
– Maman
Oct 16 '17 at 18:19
$begingroup$
I arrived that $x^a-1$ divides $x^r-1$, but how does that means $r=0$?
$endgroup$
– Ning Wang
Mar 18 '18 at 9:55
$begingroup$
It seems like that $0 le r <a$ is needed. @Maman: Is this what you meant?
$endgroup$
– Ning Wang
Mar 18 '18 at 9:58
|
show 1 more comment
$begingroup$
Let $b=a cdot q+r$.
Then
$$x^b-1=x^b-x^r+x^r-1=x^r(x^aq-1)+x^r-1 ,.$$
Use that $x^a-1$ divides $x^aq-1$.
answered Apr 4 '12 at 14:51
N. S.N. S.
105k7115210
$endgroup$
Let $b=a cdot q+r$.
Then
$$x^b-1=x^b-x^r+x^r-1=x^r(x^aq-1)+x^r-1 ,.$$
Use that $x^a-1$ divides $x^aq-1$.
answered Apr 4 '12 at 14:51
N. S.N. S.
105k7115210
answered Apr 4 '12 at 14:51
N. S.N. S.
105k7115210
answered Apr 4 '12 at 14:51
N. S.N. S.
105k7115210
answered Apr 4 '12 at 14:51
N. S.N. S.
105k7115210
105k7115210
$begingroup$
@N.S. Aren't you using recursion there? The last sentence.
$endgroup$
– TheRandomGuy
Mar 5 '16 at 14:47
$begingroup$
@DhruvSomani The last step is just the formula $$y^q-1^q=(y-1)(y^q-1+..+y+1)$$
$endgroup$
– N. S.
Mar 5 '16 at 19:52
1
$begingroup$
Notice that with the conditions of strict inequality in the Euclidean algorithm we cannot have dat $x^a-1$ divides $x^r-1$. So it is more precise !
$endgroup$
– Maman
Oct 16 '17 at 18:19
$begingroup$
I arrived that $x^a-1$ divides $x^r-1$, but how does that means $r=0$?
$endgroup$
– Ning Wang
Mar 18 '18 at 9:55
$begingroup$
It seems like that $0 le r <a$ is needed. @Maman: Is this what you meant?
$endgroup$
– Ning Wang
Mar 18 '18 at 9:58
|
show 1 more comment
$begingroup$
@N.S. Aren't you using recursion there? The last sentence.
$endgroup$
– TheRandomGuy
Mar 5 '16 at 14:47
$begingroup$
@DhruvSomani The last step is just the formula $$y^q-1^q=(y-1)(y^q-1+..+y+1)$$
$endgroup$
– N. S.
Mar 5 '16 at 19:52
1
$begingroup$
Notice that with the conditions of strict inequality in the Euclidean algorithm we cannot have dat $x^a-1$ divides $x^r-1$. So it is more precise !
$endgroup$
– Maman
Oct 16 '17 at 18:19
$begingroup$
I arrived that $x^a-1$ divides $x^r-1$, but how does that means $r=0$?
$endgroup$
– Ning Wang
Mar 18 '18 at 9:55
$begingroup$
It seems like that $0 le r <a$ is needed. @Maman: Is this what you meant?
$endgroup$
– Ning Wang
Mar 18 '18 at 9:58
$begingroup$
@N.S. Aren't you using recursion there? The last sentence.
$endgroup$
– TheRandomGuy
Mar 5 '16 at 14:47
$begingroup$
@N.S. Aren't you using recursion there? The last sentence.
$endgroup$
– TheRandomGuy
Mar 5 '16 at 14:47
$begingroup$
@DhruvSomani The last step is just the formula $$y^q-1^q=(y-1)(y^q-1+..+y+1)$$
$endgroup$
– N. S.
Mar 5 '16 at 19:52
$begingroup$
@DhruvSomani The last step is just the formula $$y^q-1^q=(y-1)(y^q-1+..+y+1)$$
$endgroup$
– N. S.
Mar 5 '16 at 19:52
1
1
$begingroup$
Notice that with the conditions of strict inequality in the Euclidean algorithm we cannot have dat $x^a-1$ divides $x^r-1$. So it is more precise !
$endgroup$
– Maman
Oct 16 '17 at 18:19
$begingroup$
Notice that with the conditions of strict inequality in the Euclidean algorithm we cannot have dat $x^a-1$ divides $x^r-1$. So it is more precise !
$endgroup$
– Maman
Oct 16 '17 at 18:19
$begingroup$
I arrived that $x^a-1$ divides $x^r-1$, but how does that means $r=0$?
$endgroup$
– Ning Wang
Mar 18 '18 at 9:55
$begingroup$
I arrived that $x^a-1$ divides $x^r-1$, but how does that means $r=0$?
$endgroup$
– Ning Wang
Mar 18 '18 at 9:55
$begingroup$
It seems like that $0 le r <a$ is needed. @Maman: Is this what you meant?
$endgroup$
– Ning Wang
Mar 18 '18 at 9:58
$begingroup$
It seems like that $0 le r <a$ is needed. @Maman: Is this what you meant?
$endgroup$
– Ning Wang
Mar 18 '18 at 9:58
|
show 1 more comment
$begingroup$
Hint $:$ By Theorem below $rm:(x^a!-1,x^b!-1) = x^(a,b)!-1$ $[ rm: =: x^a!-1!iff! (a,b)=a!iff! amid b,]$
when applied to $rm f_n = x^n!-1 = x^n-m : (x^m!-1) + x^n-m!-1 =: g f_m + f_n-mequiv f_n-mpmodf_m$
Theorem $: $ If $rm:f_n:$ is a sequence in a GCD domain (domain where gcds exist) satisfying $rm f_:0 =: 0: $ and $rm : f_nequiv f_n-m (mod f_m) $ for $rm: n > m $ then $rm: (f_n,f_m) = f_(n,:m) : $ where $rm (i,:j) = gcd(i,:j):$.
Proof $ $ By induction on $rm:n + m:$. The theorem is trivially true if $rm n = m $ or $rm n = 0 $ or $rm: m = 0:$.
So we may assume $rm:n > m > 0:$.$ $ Note $rm (f_n,f_m): = (f_n-m,f_m) $ follows from the hypothesis.
Since $rm: (n-m)+m < n+m: , $ induction yields $rm (f_n-m,f_m) = f_(n-m,:m) = f_(n,:m) $
See this post and its links for more on such divisibility sequences.
answered Apr 4 '12 at 16:45
Bill DubuqueBill Dubuque
214k29197659
$endgroup$
$begingroup$
Thanks for the answer, it's always interesting a more general approach
$endgroup$
– spin
Apr 8 '12 at 20:05
add a comment |
$begingroup$
Hint $:$ By Theorem below $rm:(x^a!-1,x^b!-1) = x^(a,b)!-1$ $[ rm: =: x^a!-1!iff! (a,b)=a!iff! amid b,]$
when applied to $rm f_n = x^n!-1 = x^n-m : (x^m!-1) + x^n-m!-1 =: g f_m + f_n-mequiv f_n-mpmodf_m$
Theorem $: $ If $rm:f_n:$ is a sequence in a GCD domain (domain where gcds exist) satisfying $rm f_:0 =: 0: $ and $rm : f_nequiv f_n-m (mod f_m) $ for $rm: n > m $ then $rm: (f_n,f_m) = f_(n,:m) : $ where $rm (i,:j) = gcd(i,:j):$.
Proof $ $ By induction on $rm:n + m:$. The theorem is trivially true if $rm n = m $ or $rm n = 0 $ or $rm: m = 0:$.
So we may assume $rm:n > m > 0:$.$ $ Note $rm (f_n,f_m): = (f_n-m,f_m) $ follows from the hypothesis.
Since $rm: (n-m)+m < n+m: , $ induction yields $rm (f_n-m,f_m) = f_(n-m,:m) = f_(n,:m) $
See this post and its links for more on such divisibility sequences.
answered Apr 4 '12 at 16:45
Bill DubuqueBill Dubuque
214k29197659
$endgroup$
$begingroup$
Thanks for the answer, it's always interesting a more general approach
$endgroup$
– spin
Apr 8 '12 at 20:05
add a comment |
$begingroup$
Hint $:$ By Theorem below $rm:(x^a!-1,x^b!-1) = x^(a,b)!-1$ $[ rm: =: x^a!-1!iff! (a,b)=a!iff! amid b,]$
when applied to $rm f_n = x^n!-1 = x^n-m : (x^m!-1) + x^n-m!-1 =: g f_m + f_n-mequiv f_n-mpmodf_m$
Theorem $: $ If $rm:f_n:$ is a sequence in a GCD domain (domain where gcds exist) satisfying $rm f_:0 =: 0: $ and $rm : f_nequiv f_n-m (mod f_m) $ for $rm: n > m $ then $rm: (f_n,f_m) = f_(n,:m) : $ where $rm (i,:j) = gcd(i,:j):$.
Proof $ $ By induction on $rm:n + m:$. The theorem is trivially true if $rm n = m $ or $rm n = 0 $ or $rm: m = 0:$.
So we may assume $rm:n > m > 0:$.$ $ Note $rm (f_n,f_m): = (f_n-m,f_m) $ follows from the hypothesis.
Since $rm: (n-m)+m < n+m: , $ induction yields $rm (f_n-m,f_m) = f_(n-m,:m) = f_(n,:m) $
See this post and its links for more on such divisibility sequences.
answered Apr 4 '12 at 16:45
Bill DubuqueBill Dubuque
214k29197659
$endgroup$
Hint $:$ By Theorem below $rm:(x^a!-1,x^b!-1) = x^(a,b)!-1$ $[ rm: =: x^a!-1!iff! (a,b)=a!iff! amid b,]$
when applied to $rm f_n = x^n!-1 = x^n-m : (x^m!-1) + x^n-m!-1 =: g f_m + f_n-mequiv f_n-mpmodf_m$
Theorem $: $ If $rm:f_n:$ is a sequence in a GCD domain (domain where gcds exist) satisfying $rm f_:0 =: 0: $ and $rm : f_nequiv f_n-m (mod f_m) $ for $rm: n > m $ then $rm: (f_n,f_m) = f_(n,:m) : $ where $rm (i,:j) = gcd(i,:j):$.
Proof $ $ By induction on $rm:n + m:$. The theorem is trivially true if $rm n = m $ or $rm n = 0 $ or $rm: m = 0:$.
So we may assume $rm:n > m > 0:$.$ $ Note $rm (f_n,f_m): = (f_n-m,f_m) $ follows from the hypothesis.
Since $rm: (n-m)+m < n+m: , $ induction yields $rm (f_n-m,f_m) = f_(n-m,:m) = f_(n,:m) $
See this post and its links for more on such divisibility sequences.
answered Apr 4 '12 at 16:45
Bill DubuqueBill Dubuque
214k29197659
edited Apr 1 at 13:21
answered Apr 4 '12 at 16:45
Bill DubuqueBill Dubuque
214k29197659
answered Apr 4 '12 at 16:45
Bill DubuqueBill Dubuque
214k29197659
answered Apr 4 '12 at 16:45
Bill DubuqueBill Dubuque
214k29197659
214k29197659
$begingroup$
Thanks for the answer, it's always interesting a more general approach
$endgroup$
– spin
Apr 8 '12 at 20:05
add a comment |
$begingroup$
Thanks for the answer, it's always interesting a more general approach
$endgroup$
– spin
Apr 8 '12 at 20:05
$begingroup$
Thanks for the answer, it's always interesting a more general approach
$endgroup$
– spin
Apr 8 '12 at 20:05
$begingroup$
Thanks for the answer, it's always interesting a more general approach
$endgroup$
– spin
Apr 8 '12 at 20:05
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%2f128007%2fxa-1-divides-xb-1-if-and-only-if-a-divides-b%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
5
$begingroup$
By the division algorithm, you can write $b=qa+r$ with $0 leq r < a$. When you do long division of $x^b - 1$ by $x^a - 1$, you will eventuall encounter the remainder $x^r - 1$, and the process stops. If $x^a - 1$ divides $x^b - 1$, the remainder must be $0$, whence $r=0$.
$endgroup$
– Chris Leary
Apr 4 '12 at 14:57
$begingroup$
Generalization : math.stackexchange.com/questions/7473/…
$endgroup$
– lab bhattacharjee
Mar 9 '14 at 7:13