Mixing
![What is the meaning of $|f-g|_infty$? [closed]](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhZCTB4-bb-s-32SAm6ytjzFOU06cH9o8q-a_wq_UnH6lcd8hvws23CmBWHM6g256LzTX9yK1EiCCzTC1NSgtxlNk_J9hdr9bA3tD0Nqntbl521j4bLAm_uXPANuWLBhcCKTKzns2gaUodx/s72-c/1.jpg)
gcd of power plus one
Clash Royale CLAN TAG#URR8PPP
up vote
10
down vote
favorite
I know that $$gcd(a^b-1,a^c-1)=a^gcd(b,c)-1$$
which can be seen by expanding both terms into geometric series. Is there any such simplification for
$$gcd(a^b+1,a^c+1)=?$$
EDIT: When working with polynomials instead of whole numbers, it is
$$gcd(x^n+1,x^m+1)=begincasesa^gcd(n,m)+1 & nu_2(n) =nu_2(m)\1 &textelseendcases$$
But this gives only a lower bound for the whole-number case.
elementary-number-theory greatest-common-divisor
asked Feb 13 '17 at 19:43
Simon
2,185115
add a comment |Â
up vote
10
down vote
favorite
I know that $$gcd(a^b-1,a^c-1)=a^gcd(b,c)-1$$
which can be seen by expanding both terms into geometric series. Is there any such simplification for
$$gcd(a^b+1,a^c+1)=?$$
EDIT: When working with polynomials instead of whole numbers, it is
$$gcd(x^n+1,x^m+1)=begincasesa^gcd(n,m)+1 & nu_2(n) =nu_2(m)\1 &textelseendcases$$
But this gives only a lower bound for the whole-number case.
elementary-number-theory greatest-common-divisor
asked Feb 13 '17 at 19:43
Simon
2,185115
I ran into this same issue.
– amcalde
Apr 6 '17 at 13:14
add a comment |Â
up vote
10
down vote
favorite
up vote
10
down vote
favorite
I know that $$gcd(a^b-1,a^c-1)=a^gcd(b,c)-1$$
which can be seen by expanding both terms into geometric series. Is there any such simplification for
$$gcd(a^b+1,a^c+1)=?$$
EDIT: When working with polynomials instead of whole numbers, it is
$$gcd(x^n+1,x^m+1)=begincasesa^gcd(n,m)+1 & nu_2(n) =nu_2(m)\1 &textelseendcases$$
But this gives only a lower bound for the whole-number case.
elementary-number-theory greatest-common-divisor
asked Feb 13 '17 at 19:43
Simon
2,185115
I know that $$gcd(a^b-1,a^c-1)=a^gcd(b,c)-1$$
which can be seen by expanding both terms into geometric series. Is there any such simplification for
$$gcd(a^b+1,a^c+1)=?$$
EDIT: When working with polynomials instead of whole numbers, it is
$$gcd(x^n+1,x^m+1)=begincasesa^gcd(n,m)+1 & nu_2(n) =nu_2(m)\1 &textelseendcases$$
But this gives only a lower bound for the whole-number case.
elementary-number-theory greatest-common-divisor
asked Feb 13 '17 at 19:43
Simon
2,185115
edited Feb 13 '17 at 23:39
asked Feb 13 '17 at 19:43
Simon
2,185115
asked Feb 13 '17 at 19:43
Simon
2,185115
asked Feb 13 '17 at 19:43
Simon
2,185115
2,185115
I ran into this same issue.
– amcalde
Apr 6 '17 at 13:14
add a comment |Â
I ran into this same issue.
– amcalde
Apr 6 '17 at 13:14
I ran into this same issue.
– amcalde
Apr 6 '17 at 13:14
I ran into this same issue.
– amcalde
Apr 6 '17 at 13:14
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
5
down vote
accepted
Let's first deal with the cases $a = 0$ and $a = 1$ separately.
For $a = 0$ we have $a^m + 1 = 1$ if $m > 0$ and $a^0 + 1 = 2$, so $gcd(0^b+1, 0^c+1) = 1$ if $b > 0$ or $c > 0$, and $gcd(0^0+1, 0^0+1) = 0^0+1$. So $gcd(0^b+1, 0^c+1) = 0^gcd(b,c) + 1$. For $a = 1$ we have $a^m + 1 = 2$ for all $m in mathbbN$ and hence $gcd(1^b+1, 1^c+1) = gcd(2,2) = 2 = 1^gcd(b,c) + 1$.
Next we consider $a geqslant 2$. We know
$$gcd(a^2b-1, a^2c-1) = a^gcd(2b,2c)-1 = a^2gcd(b,c)-1 = (a^gcd(b,c)-1)(a^gcd(b,c)+1)$$
and $gcd(a^b-1,a^c-1) = a^gcd(b,c)-1$, hence
$$gcd(a^b+1,a^c+1) mid gcdbiggl((a^b+1)fraca^b-1a^gcd(b,c)-1, (a^c+1)fraca^c-1a^gcd(b,c)-1biggr) = a^gcd(b,c)+1.$$
If $nu_2(b) = nu_2(c)$, then
$$a^gcd(b,c)+1 mid gcd(a^b+1,a^c+1),$$
so in this case we have $gcd(a^b+1,a^c+1) = a^gcd(b,c)+1$.
If $p$ is an odd prime dividing $a^m+1$, then $operatornameord_p(a) mid 2m$ but $operatornameord_p(a) nmid m$, hence it follows that $nu_2bigl(operatornameord_p(a)bigr) = nu_2(m) + 1$. Thus, if $nu_2(b) neq nu_2(c)$, no odd prime divides $gcd(a^b+1,a^c+1)$, i.e.
$$gcd(a^b+1,a^c+1) = 2^k$$
for some $k$. If $a$ is even, then $k = 0$ since $a^max b,c+1$ is odd. The square of an odd number is $equiv 1 pmod4$, so $nu_2(a^m+1) = 1$ if $a$ is odd and $nu_2(m) geqslant 1$.
We thus have
$$gcd(a^b+1,a^c+1) = begincases a^gcd(b,c)+1 &textif nu_2(b) = nu_2(c) \ qquad 2 &textif nu_2(b) neq nu_2(c)text and a equiv 1 pmod2 \ qquad 1 &textif nu_2(b) neq nu_2(c) text and a equiv 0 pmod2endcases tag$ast$$$
for $a geqslant 2$. Though $gcd(a^b+1,a^c+1) = a^gcd(b,c)+1$ for $ain 0,1$ and arbitary $b,c in mathbbN$, this also matches $(ast)$.
For $a < 0$, we have $gcd(a^b+1,a^c+1) = gcd(lvert arvert^b - 1, lvert arvert^c-1) = lvert arvert^gcd(b,c)-1$ if $b$ and $c$ are both odd and $gcd(a^b+1,a^c+1) = gcd(lvert arvert^b+1, lvert arvert^c+1)$ if both are even. These give nothing new. If one exponent is even and the other odd, say $b$ is even, then, using $d = -a$, we have $gcd(a^b+1,a^c+1) = gcd(d^b + 1, d^c - 1)$ and
$$gcd(d^b+1,d^c-1) mid gcd(d^2b-1,d^c-1) = d^gcd(2b,c)-1 = d^gcd(b,c)-1 = gcd(d^b-1,d^c-1).$$
Since $gcd(d^b+1,d^b-1) = gcd(d^b+1,2) mid 2$, it follows that $gcd(d^b+1,d^c-1) = 1$ if $d$ is even, and $gcd(d^b+1,d^c-1) = 2$ if $d$ is odd. Noting that $lvert arvert^m - 1 = -(a^m+1)$ for $a < 0$ and odd $m$, we see that $(ast)$ holds for all $a in mathbbZ$ if we don't insist on a non-negative $gcd$. If we do,
$$gcd(a^b+1,a^c+1) = begincaseslvert a^gcd(b,c)+1rvert &textif nu_2(b) = nu_2(c) \ qquad 2 &textif nu_2(b) neq nu_2(c)text and a equiv 1 pmod2 \ qquad 1 &textif nu_2(b) neq nu_2(c) text and a equiv 0 pmod2endcases tag$astast$$$
holds for all $ain mathbbZ$ and $b,c in mathbbN$.
answered Nov 20 '17 at 23:05
Daniel Fischer♦
171k16154274
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
5
down vote
accepted
Let's first deal with the cases $a = 0$ and $a = 1$ separately.
For $a = 0$ we have $a^m + 1 = 1$ if $m > 0$ and $a^0 + 1 = 2$, so $gcd(0^b+1, 0^c+1) = 1$ if $b > 0$ or $c > 0$, and $gcd(0^0+1, 0^0+1) = 0^0+1$. So $gcd(0^b+1, 0^c+1) = 0^gcd(b,c) + 1$. For $a = 1$ we have $a^m + 1 = 2$ for all $m in mathbbN$ and hence $gcd(1^b+1, 1^c+1) = gcd(2,2) = 2 = 1^gcd(b,c) + 1$.
Next we consider $a geqslant 2$. We know
$$gcd(a^2b-1, a^2c-1) = a^gcd(2b,2c)-1 = a^2gcd(b,c)-1 = (a^gcd(b,c)-1)(a^gcd(b,c)+1)$$
and $gcd(a^b-1,a^c-1) = a^gcd(b,c)-1$, hence
$$gcd(a^b+1,a^c+1) mid gcdbiggl((a^b+1)fraca^b-1a^gcd(b,c)-1, (a^c+1)fraca^c-1a^gcd(b,c)-1biggr) = a^gcd(b,c)+1.$$
If $nu_2(b) = nu_2(c)$, then
$$a^gcd(b,c)+1 mid gcd(a^b+1,a^c+1),$$
so in this case we have $gcd(a^b+1,a^c+1) = a^gcd(b,c)+1$.
If $p$ is an odd prime dividing $a^m+1$, then $operatornameord_p(a) mid 2m$ but $operatornameord_p(a) nmid m$, hence it follows that $nu_2bigl(operatornameord_p(a)bigr) = nu_2(m) + 1$. Thus, if $nu_2(b) neq nu_2(c)$, no odd prime divides $gcd(a^b+1,a^c+1)$, i.e.
$$gcd(a^b+1,a^c+1) = 2^k$$
for some $k$. If $a$ is even, then $k = 0$ since $a^max b,c+1$ is odd. The square of an odd number is $equiv 1 pmod4$, so $nu_2(a^m+1) = 1$ if $a$ is odd and $nu_2(m) geqslant 1$.
We thus have
$$gcd(a^b+1,a^c+1) = begincases a^gcd(b,c)+1 &textif nu_2(b) = nu_2(c) \ qquad 2 &textif nu_2(b) neq nu_2(c)text and a equiv 1 pmod2 \ qquad 1 &textif nu_2(b) neq nu_2(c) text and a equiv 0 pmod2endcases tag$ast$$$
for $a geqslant 2$. Though $gcd(a^b+1,a^c+1) = a^gcd(b,c)+1$ for $ain 0,1$ and arbitary $b,c in mathbbN$, this also matches $(ast)$.
For $a < 0$, we have $gcd(a^b+1,a^c+1) = gcd(lvert arvert^b - 1, lvert arvert^c-1) = lvert arvert^gcd(b,c)-1$ if $b$ and $c$ are both odd and $gcd(a^b+1,a^c+1) = gcd(lvert arvert^b+1, lvert arvert^c+1)$ if both are even. These give nothing new. If one exponent is even and the other odd, say $b$ is even, then, using $d = -a$, we have $gcd(a^b+1,a^c+1) = gcd(d^b + 1, d^c - 1)$ and
$$gcd(d^b+1,d^c-1) mid gcd(d^2b-1,d^c-1) = d^gcd(2b,c)-1 = d^gcd(b,c)-1 = gcd(d^b-1,d^c-1).$$
Since $gcd(d^b+1,d^b-1) = gcd(d^b+1,2) mid 2$, it follows that $gcd(d^b+1,d^c-1) = 1$ if $d$ is even, and $gcd(d^b+1,d^c-1) = 2$ if $d$ is odd. Noting that $lvert arvert^m - 1 = -(a^m+1)$ for $a < 0$ and odd $m$, we see that $(ast)$ holds for all $a in mathbbZ$ if we don't insist on a non-negative $gcd$. If we do,
$$gcd(a^b+1,a^c+1) = begincaseslvert a^gcd(b,c)+1rvert &textif nu_2(b) = nu_2(c) \ qquad 2 &textif nu_2(b) neq nu_2(c)text and a equiv 1 pmod2 \ qquad 1 &textif nu_2(b) neq nu_2(c) text and a equiv 0 pmod2endcases tag$astast$$$
holds for all $ain mathbbZ$ and $b,c in mathbbN$.
answered Nov 20 '17 at 23:05
Daniel Fischer♦
171k16154274
add a comment |Â
up vote
5
down vote
accepted
Let's first deal with the cases $a = 0$ and $a = 1$ separately.
For $a = 0$ we have $a^m + 1 = 1$ if $m > 0$ and $a^0 + 1 = 2$, so $gcd(0^b+1, 0^c+1) = 1$ if $b > 0$ or $c > 0$, and $gcd(0^0+1, 0^0+1) = 0^0+1$. So $gcd(0^b+1, 0^c+1) = 0^gcd(b,c) + 1$. For $a = 1$ we have $a^m + 1 = 2$ for all $m in mathbbN$ and hence $gcd(1^b+1, 1^c+1) = gcd(2,2) = 2 = 1^gcd(b,c) + 1$.
Next we consider $a geqslant 2$. We know
$$gcd(a^2b-1, a^2c-1) = a^gcd(2b,2c)-1 = a^2gcd(b,c)-1 = (a^gcd(b,c)-1)(a^gcd(b,c)+1)$$
and $gcd(a^b-1,a^c-1) = a^gcd(b,c)-1$, hence
$$gcd(a^b+1,a^c+1) mid gcdbiggl((a^b+1)fraca^b-1a^gcd(b,c)-1, (a^c+1)fraca^c-1a^gcd(b,c)-1biggr) = a^gcd(b,c)+1.$$
If $nu_2(b) = nu_2(c)$, then
$$a^gcd(b,c)+1 mid gcd(a^b+1,a^c+1),$$
so in this case we have $gcd(a^b+1,a^c+1) = a^gcd(b,c)+1$.
If $p$ is an odd prime dividing $a^m+1$, then $operatornameord_p(a) mid 2m$ but $operatornameord_p(a) nmid m$, hence it follows that $nu_2bigl(operatornameord_p(a)bigr) = nu_2(m) + 1$. Thus, if $nu_2(b) neq nu_2(c)$, no odd prime divides $gcd(a^b+1,a^c+1)$, i.e.
$$gcd(a^b+1,a^c+1) = 2^k$$
for some $k$. If $a$ is even, then $k = 0$ since $a^max b,c+1$ is odd. The square of an odd number is $equiv 1 pmod4$, so $nu_2(a^m+1) = 1$ if $a$ is odd and $nu_2(m) geqslant 1$.
We thus have
$$gcd(a^b+1,a^c+1) = begincases a^gcd(b,c)+1 &textif nu_2(b) = nu_2(c) \ qquad 2 &textif nu_2(b) neq nu_2(c)text and a equiv 1 pmod2 \ qquad 1 &textif nu_2(b) neq nu_2(c) text and a equiv 0 pmod2endcases tag$ast$$$
for $a geqslant 2$. Though $gcd(a^b+1,a^c+1) = a^gcd(b,c)+1$ for $ain 0,1$ and arbitary $b,c in mathbbN$, this also matches $(ast)$.
For $a < 0$, we have $gcd(a^b+1,a^c+1) = gcd(lvert arvert^b - 1, lvert arvert^c-1) = lvert arvert^gcd(b,c)-1$ if $b$ and $c$ are both odd and $gcd(a^b+1,a^c+1) = gcd(lvert arvert^b+1, lvert arvert^c+1)$ if both are even. These give nothing new. If one exponent is even and the other odd, say $b$ is even, then, using $d = -a$, we have $gcd(a^b+1,a^c+1) = gcd(d^b + 1, d^c - 1)$ and
$$gcd(d^b+1,d^c-1) mid gcd(d^2b-1,d^c-1) = d^gcd(2b,c)-1 = d^gcd(b,c)-1 = gcd(d^b-1,d^c-1).$$
Since $gcd(d^b+1,d^b-1) = gcd(d^b+1,2) mid 2$, it follows that $gcd(d^b+1,d^c-1) = 1$ if $d$ is even, and $gcd(d^b+1,d^c-1) = 2$ if $d$ is odd. Noting that $lvert arvert^m - 1 = -(a^m+1)$ for $a < 0$ and odd $m$, we see that $(ast)$ holds for all $a in mathbbZ$ if we don't insist on a non-negative $gcd$. If we do,
$$gcd(a^b+1,a^c+1) = begincaseslvert a^gcd(b,c)+1rvert &textif nu_2(b) = nu_2(c) \ qquad 2 &textif nu_2(b) neq nu_2(c)text and a equiv 1 pmod2 \ qquad 1 &textif nu_2(b) neq nu_2(c) text and a equiv 0 pmod2endcases tag$astast$$$
holds for all $ain mathbbZ$ and $b,c in mathbbN$.
answered Nov 20 '17 at 23:05
Daniel Fischer♦
171k16154274
add a comment |Â
up vote
5
down vote
accepted
up vote
5
down vote
accepted
Let's first deal with the cases $a = 0$ and $a = 1$ separately.
For $a = 0$ we have $a^m + 1 = 1$ if $m > 0$ and $a^0 + 1 = 2$, so $gcd(0^b+1, 0^c+1) = 1$ if $b > 0$ or $c > 0$, and $gcd(0^0+1, 0^0+1) = 0^0+1$. So $gcd(0^b+1, 0^c+1) = 0^gcd(b,c) + 1$. For $a = 1$ we have $a^m + 1 = 2$ for all $m in mathbbN$ and hence $gcd(1^b+1, 1^c+1) = gcd(2,2) = 2 = 1^gcd(b,c) + 1$.
Next we consider $a geqslant 2$. We know
$$gcd(a^2b-1, a^2c-1) = a^gcd(2b,2c)-1 = a^2gcd(b,c)-1 = (a^gcd(b,c)-1)(a^gcd(b,c)+1)$$
and $gcd(a^b-1,a^c-1) = a^gcd(b,c)-1$, hence
$$gcd(a^b+1,a^c+1) mid gcdbiggl((a^b+1)fraca^b-1a^gcd(b,c)-1, (a^c+1)fraca^c-1a^gcd(b,c)-1biggr) = a^gcd(b,c)+1.$$
If $nu_2(b) = nu_2(c)$, then
$$a^gcd(b,c)+1 mid gcd(a^b+1,a^c+1),$$
so in this case we have $gcd(a^b+1,a^c+1) = a^gcd(b,c)+1$.
If $p$ is an odd prime dividing $a^m+1$, then $operatornameord_p(a) mid 2m$ but $operatornameord_p(a) nmid m$, hence it follows that $nu_2bigl(operatornameord_p(a)bigr) = nu_2(m) + 1$. Thus, if $nu_2(b) neq nu_2(c)$, no odd prime divides $gcd(a^b+1,a^c+1)$, i.e.
$$gcd(a^b+1,a^c+1) = 2^k$$
for some $k$. If $a$ is even, then $k = 0$ since $a^max b,c+1$ is odd. The square of an odd number is $equiv 1 pmod4$, so $nu_2(a^m+1) = 1$ if $a$ is odd and $nu_2(m) geqslant 1$.
We thus have
$$gcd(a^b+1,a^c+1) = begincases a^gcd(b,c)+1 &textif nu_2(b) = nu_2(c) \ qquad 2 &textif nu_2(b) neq nu_2(c)text and a equiv 1 pmod2 \ qquad 1 &textif nu_2(b) neq nu_2(c) text and a equiv 0 pmod2endcases tag$ast$$$
for $a geqslant 2$. Though $gcd(a^b+1,a^c+1) = a^gcd(b,c)+1$ for $ain 0,1$ and arbitary $b,c in mathbbN$, this also matches $(ast)$.
For $a < 0$, we have $gcd(a^b+1,a^c+1) = gcd(lvert arvert^b - 1, lvert arvert^c-1) = lvert arvert^gcd(b,c)-1$ if $b$ and $c$ are both odd and $gcd(a^b+1,a^c+1) = gcd(lvert arvert^b+1, lvert arvert^c+1)$ if both are even. These give nothing new. If one exponent is even and the other odd, say $b$ is even, then, using $d = -a$, we have $gcd(a^b+1,a^c+1) = gcd(d^b + 1, d^c - 1)$ and
$$gcd(d^b+1,d^c-1) mid gcd(d^2b-1,d^c-1) = d^gcd(2b,c)-1 = d^gcd(b,c)-1 = gcd(d^b-1,d^c-1).$$
Since $gcd(d^b+1,d^b-1) = gcd(d^b+1,2) mid 2$, it follows that $gcd(d^b+1,d^c-1) = 1$ if $d$ is even, and $gcd(d^b+1,d^c-1) = 2$ if $d$ is odd. Noting that $lvert arvert^m - 1 = -(a^m+1)$ for $a < 0$ and odd $m$, we see that $(ast)$ holds for all $a in mathbbZ$ if we don't insist on a non-negative $gcd$. If we do,
$$gcd(a^b+1,a^c+1) = begincaseslvert a^gcd(b,c)+1rvert &textif nu_2(b) = nu_2(c) \ qquad 2 &textif nu_2(b) neq nu_2(c)text and a equiv 1 pmod2 \ qquad 1 &textif nu_2(b) neq nu_2(c) text and a equiv 0 pmod2endcases tag$astast$$$
holds for all $ain mathbbZ$ and $b,c in mathbbN$.
answered Nov 20 '17 at 23:05
Daniel Fischer♦
171k16154274
Let's first deal with the cases $a = 0$ and $a = 1$ separately.
For $a = 0$ we have $a^m + 1 = 1$ if $m > 0$ and $a^0 + 1 = 2$, so $gcd(0^b+1, 0^c+1) = 1$ if $b > 0$ or $c > 0$, and $gcd(0^0+1, 0^0+1) = 0^0+1$. So $gcd(0^b+1, 0^c+1) = 0^gcd(b,c) + 1$. For $a = 1$ we have $a^m + 1 = 2$ for all $m in mathbbN$ and hence $gcd(1^b+1, 1^c+1) = gcd(2,2) = 2 = 1^gcd(b,c) + 1$.
Next we consider $a geqslant 2$. We know
$$gcd(a^2b-1, a^2c-1) = a^gcd(2b,2c)-1 = a^2gcd(b,c)-1 = (a^gcd(b,c)-1)(a^gcd(b,c)+1)$$
and $gcd(a^b-1,a^c-1) = a^gcd(b,c)-1$, hence
$$gcd(a^b+1,a^c+1) mid gcdbiggl((a^b+1)fraca^b-1a^gcd(b,c)-1, (a^c+1)fraca^c-1a^gcd(b,c)-1biggr) = a^gcd(b,c)+1.$$
If $nu_2(b) = nu_2(c)$, then
$$a^gcd(b,c)+1 mid gcd(a^b+1,a^c+1),$$
so in this case we have $gcd(a^b+1,a^c+1) = a^gcd(b,c)+1$.
If $p$ is an odd prime dividing $a^m+1$, then $operatornameord_p(a) mid 2m$ but $operatornameord_p(a) nmid m$, hence it follows that $nu_2bigl(operatornameord_p(a)bigr) = nu_2(m) + 1$. Thus, if $nu_2(b) neq nu_2(c)$, no odd prime divides $gcd(a^b+1,a^c+1)$, i.e.
$$gcd(a^b+1,a^c+1) = 2^k$$
for some $k$. If $a$ is even, then $k = 0$ since $a^max b,c+1$ is odd. The square of an odd number is $equiv 1 pmod4$, so $nu_2(a^m+1) = 1$ if $a$ is odd and $nu_2(m) geqslant 1$.
We thus have
$$gcd(a^b+1,a^c+1) = begincases a^gcd(b,c)+1 &textif nu_2(b) = nu_2(c) \ qquad 2 &textif nu_2(b) neq nu_2(c)text and a equiv 1 pmod2 \ qquad 1 &textif nu_2(b) neq nu_2(c) text and a equiv 0 pmod2endcases tag$ast$$$
for $a geqslant 2$. Though $gcd(a^b+1,a^c+1) = a^gcd(b,c)+1$ for $ain 0,1$ and arbitary $b,c in mathbbN$, this also matches $(ast)$.
For $a < 0$, we have $gcd(a^b+1,a^c+1) = gcd(lvert arvert^b - 1, lvert arvert^c-1) = lvert arvert^gcd(b,c)-1$ if $b$ and $c$ are both odd and $gcd(a^b+1,a^c+1) = gcd(lvert arvert^b+1, lvert arvert^c+1)$ if both are even. These give nothing new. If one exponent is even and the other odd, say $b$ is even, then, using $d = -a$, we have $gcd(a^b+1,a^c+1) = gcd(d^b + 1, d^c - 1)$ and
$$gcd(d^b+1,d^c-1) mid gcd(d^2b-1,d^c-1) = d^gcd(2b,c)-1 = d^gcd(b,c)-1 = gcd(d^b-1,d^c-1).$$
Since $gcd(d^b+1,d^b-1) = gcd(d^b+1,2) mid 2$, it follows that $gcd(d^b+1,d^c-1) = 1$ if $d$ is even, and $gcd(d^b+1,d^c-1) = 2$ if $d$ is odd. Noting that $lvert arvert^m - 1 = -(a^m+1)$ for $a < 0$ and odd $m$, we see that $(ast)$ holds for all $a in mathbbZ$ if we don't insist on a non-negative $gcd$. If we do,
$$gcd(a^b+1,a^c+1) = begincaseslvert a^gcd(b,c)+1rvert &textif nu_2(b) = nu_2(c) \ qquad 2 &textif nu_2(b) neq nu_2(c)text and a equiv 1 pmod2 \ qquad 1 &textif nu_2(b) neq nu_2(c) text and a equiv 0 pmod2endcases tag$astast$$$
holds for all $ain mathbbZ$ and $b,c in mathbbN$.
answered Nov 20 '17 at 23:05
Daniel Fischer♦
171k16154274
answered Nov 20 '17 at 23:05
Daniel Fischer♦
171k16154274
answered Nov 20 '17 at 23:05
Daniel Fischer♦
171k16154274
answered Nov 20 '17 at 23:05
Daniel Fischer♦
171k16154274
171k16154274
add a comment |Â
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2142932%2fgcd-of-power-plus-one%23new-answer', 'question_page');
);
Post as a guest
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
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
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
I ran into this same issue.
– amcalde
Apr 6 '17 at 13:14