Prove that $gcd(f(x),g(x)) = 1$.
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
Let $F$ be a field, let $p , q$ be two coprime natural numbers and we consider the two polynomials
$$
f(X) = sum_i = 0^p - 1 X^k i qquad mbox and qquad g(X) = sum_j = 0^q - 1 X^k j
$$
in $F[X]$, where $k in mathbbN$. If $x$ is an arbitrary element in $F$, how can I show that $gcd(f(x) , g(x)) = 1$?
polynomials greatest-common-divisor
edited Aug 21 at 18:25
3.14159
17710
asked Aug 20 at 12:26
joseabp91
1,100411
add a comment |Â
up vote
0
down vote
favorite
Let $F$ be a field, let $p , q$ be two coprime natural numbers and we consider the two polynomials
$$
f(X) = sum_i = 0^p - 1 X^k i qquad mbox and qquad g(X) = sum_j = 0^q - 1 X^k j
$$
in $F[X]$, where $k in mathbbN$. If $x$ is an arbitrary element in $F$, how can I show that $gcd(f(x) , g(x)) = 1$?
polynomials greatest-common-divisor
edited Aug 21 at 18:25
3.14159
17710
asked Aug 20 at 12:26
joseabp91
1,100411
If $F$ is a field, and $xin F$, then aren't $f(x), g(x)$ just elements of $F$? Do you mean $gcd(f, g)$ (alternatively $gcd(f(X), g(X))$) instead?
– Arthur
Aug 20 at 12:31
Yes, if $x in F$, then $f(x) , g(x)$ are in $F$. And I can alternatively show that $gcd(f(X) , g(X)) = 1$ to end my proof.
– joseabp91
Aug 20 at 12:34
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
Let $F$ be a field, let $p , q$ be two coprime natural numbers and we consider the two polynomials
$$
f(X) = sum_i = 0^p - 1 X^k i qquad mbox and qquad g(X) = sum_j = 0^q - 1 X^k j
$$
in $F[X]$, where $k in mathbbN$. If $x$ is an arbitrary element in $F$, how can I show that $gcd(f(x) , g(x)) = 1$?
polynomials greatest-common-divisor
edited Aug 21 at 18:25
3.14159
17710
asked Aug 20 at 12:26
joseabp91
1,100411
Let $F$ be a field, let $p , q$ be two coprime natural numbers and we consider the two polynomials
$$
f(X) = sum_i = 0^p - 1 X^k i qquad mbox and qquad g(X) = sum_j = 0^q - 1 X^k j
$$
in $F[X]$, where $k in mathbbN$. If $x$ is an arbitrary element in $F$, how can I show that $gcd(f(x) , g(x)) = 1$?
polynomials greatest-common-divisor
edited Aug 21 at 18:25
3.14159
17710
asked Aug 20 at 12:26
joseabp91
1,100411
edited Aug 21 at 18:25
3.14159
17710
edited Aug 21 at 18:25
3.14159
17710
edited Aug 21 at 18:25
3.14159
17710
17710
asked Aug 20 at 12:26
joseabp91
1,100411
asked Aug 20 at 12:26
joseabp91
1,100411
asked Aug 20 at 12:26
joseabp91
1,100411
1,100411
If $F$ is a field, and $xin F$, then aren't $f(x), g(x)$ just elements of $F$? Do you mean $gcd(f, g)$ (alternatively $gcd(f(X), g(X))$) instead?
– Arthur
Aug 20 at 12:31
Yes, if $x in F$, then $f(x) , g(x)$ are in $F$. And I can alternatively show that $gcd(f(X) , g(X)) = 1$ to end my proof.
– joseabp91
Aug 20 at 12:34
add a comment |Â
If $F$ is a field, and $xin F$, then aren't $f(x), g(x)$ just elements of $F$? Do you mean $gcd(f, g)$ (alternatively $gcd(f(X), g(X))$) instead?
– Arthur
Aug 20 at 12:31
Yes, if $x in F$, then $f(x) , g(x)$ are in $F$. And I can alternatively show that $gcd(f(X) , g(X)) = 1$ to end my proof.
– joseabp91
Aug 20 at 12:34
If $F$ is a field, and $xin F$, then aren't $f(x), g(x)$ just elements of $F$? Do you mean $gcd(f, g)$ (alternatively $gcd(f(X), g(X))$) instead?
– Arthur
Aug 20 at 12:31
If $F$ is a field, and $xin F$, then aren't $f(x), g(x)$ just elements of $F$? Do you mean $gcd(f, g)$ (alternatively $gcd(f(X), g(X))$) instead?
– Arthur
Aug 20 at 12:31
Yes, if $x in F$, then $f(x) , g(x)$ are in $F$. And I can alternatively show that $gcd(f(X) , g(X)) = 1$ to end my proof.
– joseabp91
Aug 20 at 12:34
Yes, if $x in F$, then $f(x) , g(x)$ are in $F$. And I can alternatively show that $gcd(f(X) , g(X)) = 1$ to end my proof.
– joseabp91
Aug 20 at 12:34
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
1
down vote
accepted
Hint (for the polynomial $gcd$): $;X^kp = left(X^k-1right)f(X)+1,$ and $,X^kq = left(X^k-1right)g(X)+1,$.
Since $,p,q,$ are coprime, there exist integers $,a,b,$ such that $,ap-bq=1,$, and it can be assumed WLOG that they are positive i.e. $,a,b in Bbb N,$. Then $,X^kap=X^k(bq+1) = X^k cdot X^kbq,$, and therefore:
$$
left(left(X^k-1right)f(X)+1right)^a - X^k cdot left( left(X^k-1right)g(X)+1right)^b = 0
$$
Expanding the binomials, $,h(X) = gcdleft(f(X),g(X)right),$ would have to divide $,1-X^k,$, but both $,f(X),$ and $,g(X),$ are coprime with $,1-X^k,$.
answered Aug 20 at 19:45
dxiv
55.3k64798
Expanding $$ left(left(X^k-1right)f(X)+1right)^a - X^k cdot left( left(X^k-1right)g(X)+1right)^b $$ I got that there exists $h(X) in F[X]$ such that $$ (X^k - 1) h(X) = left(left(X^k-1right)f(X)+1right)^a - X^k cdot left( left(X^k-1right)g(X)+1right)^b = 0mbox. $$ Why do you say that $gcd(f(X) , g(X))$ would have to divide $1 - X^k$? And why are both $f(X)$ and $g(X)$ coprime with $1 - X^k$?
– joseabp91
Aug 21 at 21:08
@joseabp91 See the detailed proof for $k=1$ here. The case $k gt 1$ works out in an entirely similar way.
– dxiv
Aug 21 at 21:58
1
Thank you very much by your anwers.
– joseabp91
Aug 21 at 22:25
add a comment |Â
up vote
0
down vote
Perhaps this will help:
$$ 1+x+x^2+...+x^n-1 = x^n-1over x-1$$
and a fact that $$gcd(x^n-1,x^m-1) = x^gcd(m,n)-1$$
answered Aug 20 at 12:29
greedoid
27.5k93776
It is not valid for me, as my statement and the fact $gcd(x^n - 1 , x^m - 1) = x^gcd(n , m) - 1$ are clearly equivalent. Unless you help me to prove your statement.
– joseabp91
Aug 20 at 12:36
I'm almost sure you can find a proove on this site. Perhaps even in my posts you can find it.
– greedoid
Aug 20 at 12:37
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
Hint (for the polynomial $gcd$): $;X^kp = left(X^k-1right)f(X)+1,$ and $,X^kq = left(X^k-1right)g(X)+1,$.
Since $,p,q,$ are coprime, there exist integers $,a,b,$ such that $,ap-bq=1,$, and it can be assumed WLOG that they are positive i.e. $,a,b in Bbb N,$. Then $,X^kap=X^k(bq+1) = X^k cdot X^kbq,$, and therefore:
$$
left(left(X^k-1right)f(X)+1right)^a - X^k cdot left( left(X^k-1right)g(X)+1right)^b = 0
$$
Expanding the binomials, $,h(X) = gcdleft(f(X),g(X)right),$ would have to divide $,1-X^k,$, but both $,f(X),$ and $,g(X),$ are coprime with $,1-X^k,$.
answered Aug 20 at 19:45
dxiv
55.3k64798
Expanding $$ left(left(X^k-1right)f(X)+1right)^a - X^k cdot left( left(X^k-1right)g(X)+1right)^b $$ I got that there exists $h(X) in F[X]$ such that $$ (X^k - 1) h(X) = left(left(X^k-1right)f(X)+1right)^a - X^k cdot left( left(X^k-1right)g(X)+1right)^b = 0mbox. $$ Why do you say that $gcd(f(X) , g(X))$ would have to divide $1 - X^k$? And why are both $f(X)$ and $g(X)$ coprime with $1 - X^k$?
– joseabp91
Aug 21 at 21:08
@joseabp91 See the detailed proof for $k=1$ here. The case $k gt 1$ works out in an entirely similar way.
– dxiv
Aug 21 at 21:58
1
Thank you very much by your anwers.
– joseabp91
Aug 21 at 22:25
add a comment |Â
up vote
1
down vote
accepted
Hint (for the polynomial $gcd$): $;X^kp = left(X^k-1right)f(X)+1,$ and $,X^kq = left(X^k-1right)g(X)+1,$.
Since $,p,q,$ are coprime, there exist integers $,a,b,$ such that $,ap-bq=1,$, and it can be assumed WLOG that they are positive i.e. $,a,b in Bbb N,$. Then $,X^kap=X^k(bq+1) = X^k cdot X^kbq,$, and therefore:
$$
left(left(X^k-1right)f(X)+1right)^a - X^k cdot left( left(X^k-1right)g(X)+1right)^b = 0
$$
Expanding the binomials, $,h(X) = gcdleft(f(X),g(X)right),$ would have to divide $,1-X^k,$, but both $,f(X),$ and $,g(X),$ are coprime with $,1-X^k,$.
answered Aug 20 at 19:45
dxiv
55.3k64798
Expanding $$ left(left(X^k-1right)f(X)+1right)^a - X^k cdot left( left(X^k-1right)g(X)+1right)^b $$ I got that there exists $h(X) in F[X]$ such that $$ (X^k - 1) h(X) = left(left(X^k-1right)f(X)+1right)^a - X^k cdot left( left(X^k-1right)g(X)+1right)^b = 0mbox. $$ Why do you say that $gcd(f(X) , g(X))$ would have to divide $1 - X^k$? And why are both $f(X)$ and $g(X)$ coprime with $1 - X^k$?
– joseabp91
Aug 21 at 21:08
@joseabp91 See the detailed proof for $k=1$ here. The case $k gt 1$ works out in an entirely similar way.
– dxiv
Aug 21 at 21:58
1
Thank you very much by your anwers.
– joseabp91
Aug 21 at 22:25
add a comment |Â
up vote
1
down vote
accepted
up vote
1
down vote
accepted
Hint (for the polynomial $gcd$): $;X^kp = left(X^k-1right)f(X)+1,$ and $,X^kq = left(X^k-1right)g(X)+1,$.
Since $,p,q,$ are coprime, there exist integers $,a,b,$ such that $,ap-bq=1,$, and it can be assumed WLOG that they are positive i.e. $,a,b in Bbb N,$. Then $,X^kap=X^k(bq+1) = X^k cdot X^kbq,$, and therefore:
$$
left(left(X^k-1right)f(X)+1right)^a - X^k cdot left( left(X^k-1right)g(X)+1right)^b = 0
$$
Expanding the binomials, $,h(X) = gcdleft(f(X),g(X)right),$ would have to divide $,1-X^k,$, but both $,f(X),$ and $,g(X),$ are coprime with $,1-X^k,$.
answered Aug 20 at 19:45
dxiv
55.3k64798
Hint (for the polynomial $gcd$): $;X^kp = left(X^k-1right)f(X)+1,$ and $,X^kq = left(X^k-1right)g(X)+1,$.
Since $,p,q,$ are coprime, there exist integers $,a,b,$ such that $,ap-bq=1,$, and it can be assumed WLOG that they are positive i.e. $,a,b in Bbb N,$. Then $,X^kap=X^k(bq+1) = X^k cdot X^kbq,$, and therefore:
$$
left(left(X^k-1right)f(X)+1right)^a - X^k cdot left( left(X^k-1right)g(X)+1right)^b = 0
$$
Expanding the binomials, $,h(X) = gcdleft(f(X),g(X)right),$ would have to divide $,1-X^k,$, but both $,f(X),$ and $,g(X),$ are coprime with $,1-X^k,$.
answered Aug 20 at 19:45
dxiv
55.3k64798
answered Aug 20 at 19:45
dxiv
55.3k64798
answered Aug 20 at 19:45
dxiv
55.3k64798
answered Aug 20 at 19:45
dxiv
55.3k64798
55.3k64798
Expanding $$ left(left(X^k-1right)f(X)+1right)^a - X^k cdot left( left(X^k-1right)g(X)+1right)^b $$ I got that there exists $h(X) in F[X]$ such that $$ (X^k - 1) h(X) = left(left(X^k-1right)f(X)+1right)^a - X^k cdot left( left(X^k-1right)g(X)+1right)^b = 0mbox. $$ Why do you say that $gcd(f(X) , g(X))$ would have to divide $1 - X^k$? And why are both $f(X)$ and $g(X)$ coprime with $1 - X^k$?
– joseabp91
Aug 21 at 21:08
@joseabp91 See the detailed proof for $k=1$ here. The case $k gt 1$ works out in an entirely similar way.
– dxiv
Aug 21 at 21:58
1
Thank you very much by your anwers.
– joseabp91
Aug 21 at 22:25
add a comment |Â
Expanding $$ left(left(X^k-1right)f(X)+1right)^a - X^k cdot left( left(X^k-1right)g(X)+1right)^b $$ I got that there exists $h(X) in F[X]$ such that $$ (X^k - 1) h(X) = left(left(X^k-1right)f(X)+1right)^a - X^k cdot left( left(X^k-1right)g(X)+1right)^b = 0mbox. $$ Why do you say that $gcd(f(X) , g(X))$ would have to divide $1 - X^k$? And why are both $f(X)$ and $g(X)$ coprime with $1 - X^k$?
– joseabp91
Aug 21 at 21:08
@joseabp91 See the detailed proof for $k=1$ here. The case $k gt 1$ works out in an entirely similar way.
– dxiv
Aug 21 at 21:58
1
Thank you very much by your anwers.
– joseabp91
Aug 21 at 22:25
Expanding $$ left(left(X^k-1right)f(X)+1right)^a - X^k cdot left( left(X^k-1right)g(X)+1right)^b $$ I got that there exists $h(X) in F[X]$ such that $$ (X^k - 1) h(X) = left(left(X^k-1right)f(X)+1right)^a - X^k cdot left( left(X^k-1right)g(X)+1right)^b = 0mbox. $$ Why do you say that $gcd(f(X) , g(X))$ would have to divide $1 - X^k$? And why are both $f(X)$ and $g(X)$ coprime with $1 - X^k$?
– joseabp91
Aug 21 at 21:08
Expanding $$ left(left(X^k-1right)f(X)+1right)^a - X^k cdot left( left(X^k-1right)g(X)+1right)^b $$ I got that there exists $h(X) in F[X]$ such that $$ (X^k - 1) h(X) = left(left(X^k-1right)f(X)+1right)^a - X^k cdot left( left(X^k-1right)g(X)+1right)^b = 0mbox. $$ Why do you say that $gcd(f(X) , g(X))$ would have to divide $1 - X^k$? And why are both $f(X)$ and $g(X)$ coprime with $1 - X^k$?
– joseabp91
Aug 21 at 21:08
@joseabp91 See the detailed proof for $k=1$ here. The case $k gt 1$ works out in an entirely similar way.
– dxiv
Aug 21 at 21:58
@joseabp91 See the detailed proof for $k=1$ here. The case $k gt 1$ works out in an entirely similar way.
– dxiv
Aug 21 at 21:58
1
1
Thank you very much by your anwers.
– joseabp91
Aug 21 at 22:25
Thank you very much by your anwers.
– joseabp91
Aug 21 at 22:25
add a comment |Â
up vote
0
down vote
Perhaps this will help:
$$ 1+x+x^2+...+x^n-1 = x^n-1over x-1$$
and a fact that $$gcd(x^n-1,x^m-1) = x^gcd(m,n)-1$$
answered Aug 20 at 12:29
greedoid
27.5k93776
It is not valid for me, as my statement and the fact $gcd(x^n - 1 , x^m - 1) = x^gcd(n , m) - 1$ are clearly equivalent. Unless you help me to prove your statement.
– joseabp91
Aug 20 at 12:36
I'm almost sure you can find a proove on this site. Perhaps even in my posts you can find it.
– greedoid
Aug 20 at 12:37
add a comment |Â
up vote
0
down vote
Perhaps this will help:
$$ 1+x+x^2+...+x^n-1 = x^n-1over x-1$$
and a fact that $$gcd(x^n-1,x^m-1) = x^gcd(m,n)-1$$
answered Aug 20 at 12:29
greedoid
27.5k93776
It is not valid for me, as my statement and the fact $gcd(x^n - 1 , x^m - 1) = x^gcd(n , m) - 1$ are clearly equivalent. Unless you help me to prove your statement.
– joseabp91
Aug 20 at 12:36
I'm almost sure you can find a proove on this site. Perhaps even in my posts you can find it.
– greedoid
Aug 20 at 12:37
add a comment |Â
up vote
0
down vote
up vote
0
down vote
Perhaps this will help:
$$ 1+x+x^2+...+x^n-1 = x^n-1over x-1$$
and a fact that $$gcd(x^n-1,x^m-1) = x^gcd(m,n)-1$$
answered Aug 20 at 12:29
greedoid
27.5k93776
Perhaps this will help:
$$ 1+x+x^2+...+x^n-1 = x^n-1over x-1$$
and a fact that $$gcd(x^n-1,x^m-1) = x^gcd(m,n)-1$$
answered Aug 20 at 12:29
greedoid
27.5k93776
answered Aug 20 at 12:29
greedoid
27.5k93776
answered Aug 20 at 12:29
greedoid
27.5k93776
answered Aug 20 at 12:29
greedoid
27.5k93776
27.5k93776
It is not valid for me, as my statement and the fact $gcd(x^n - 1 , x^m - 1) = x^gcd(n , m) - 1$ are clearly equivalent. Unless you help me to prove your statement.
– joseabp91
Aug 20 at 12:36
I'm almost sure you can find a proove on this site. Perhaps even in my posts you can find it.
– greedoid
Aug 20 at 12:37
add a comment |Â
It is not valid for me, as my statement and the fact $gcd(x^n - 1 , x^m - 1) = x^gcd(n , m) - 1$ are clearly equivalent. Unless you help me to prove your statement.
– joseabp91
Aug 20 at 12:36
I'm almost sure you can find a proove on this site. Perhaps even in my posts you can find it.
– greedoid
Aug 20 at 12:37
It is not valid for me, as my statement and the fact $gcd(x^n - 1 , x^m - 1) = x^gcd(n , m) - 1$ are clearly equivalent. Unless you help me to prove your statement.
– joseabp91
Aug 20 at 12:36
It is not valid for me, as my statement and the fact $gcd(x^n - 1 , x^m - 1) = x^gcd(n , m) - 1$ are clearly equivalent. Unless you help me to prove your statement.
– joseabp91
Aug 20 at 12:36
I'm almost sure you can find a proove on this site. Perhaps even in my posts you can find it.
– greedoid
Aug 20 at 12:37
I'm almost sure you can find a proove on this site. Perhaps even in my posts you can find it.
– greedoid
Aug 20 at 12:37
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%2f2888718%2fprove-that-gcdfx-gx-1%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
If $F$ is a field, and $xin F$, then aren't $f(x), g(x)$ just elements of $F$? Do you mean $gcd(f, g)$ (alternatively $gcd(f(X), g(X))$) instead?
– Arthur
Aug 20 at 12:31
Yes, if $x in F$, then $f(x) , g(x)$ are in $F$. And I can alternatively show that $gcd(f(X) , g(X)) = 1$ to end my proof.
– joseabp91
Aug 20 at 12:34