Is there any polynomial function $f$ such that If $gcd(p,q)=1$ then $gcd(f(p),f(q))=1$ for all such $p,q$?












9












$begingroup$


Is there a polynomial, $f(x)$, such that for all natural numbers $p$ and $q$, if $gcd(p, q) = 1$ then $gcd(f(p), f(q)) = 1$?



Note : Function $f(x)$ must be a polynomial in $x$, not depend on $p$ or $q$, and not be the trivial case of a polynomial with only $1$ term ($f(x) = c$ or $f(x) = x^p$).






elementary-number-theory prime-numbers







share|cite|improve this question











$endgroup$












  • $begingroup$
    At least $f(x) = x^2+x-1$ for $p=2$ and $q=3$, because $gcd(5,11)=1$
    $endgroup$
    – Eemil Wallin
    Jun 15 '15 at 9:57










  • $begingroup$
    It's not a polynomial, but if $F_n$ is the $n^{text{th}}$ Fibonacci number, then $gcd(p, q) = gcd(F_p, F_q)$ : math.stackexchange.com/a/506108/97045
    $endgroup$
    – DanielV
    Jun 15 '15 at 10:18






  • 2




    $begingroup$
    @RoryDaulton: OP said that $f(p)$ and $f(q)$ should be coprime for all such $p,q$. Though poorly stated, this means that it should do this for all coprime numbers.
    $endgroup$
    – user230734
    Jun 15 '15 at 10:45






  • 2




    $begingroup$
    @BolzWeir: I agree that seems to be what the OP means, but if so the question should have the introductory "If $p,q$ are co-prime integers, then" removed. I would do that edit myself if the OP himself made his meaning clear. I hate to edit other people's questions unless the meaning is made perfectly clear.
    $endgroup$
    – Rory Daulton
    Jun 15 '15 at 10:47








  • 1




    $begingroup$
    @EstebanCrespi The question explicitly excludes $f(x) = x^n$ for any $n geq 0$...
    $endgroup$
    – A.P.
    Jun 15 '15 at 14:00
















9












$begingroup$


Is there a polynomial, $f(x)$, such that for all natural numbers $p$ and $q$, if $gcd(p, q) = 1$ then $gcd(f(p), f(q)) = 1$?



Note : Function $f(x)$ must be a polynomial in $x$, not depend on $p$ or $q$, and not be the trivial case of a polynomial with only $1$ term ($f(x) = c$ or $f(x) = x^p$).






elementary-number-theory prime-numbers







share|cite|improve this question











$endgroup$












  • $begingroup$
    At least $f(x) = x^2+x-1$ for $p=2$ and $q=3$, because $gcd(5,11)=1$
    $endgroup$
    – Eemil Wallin
    Jun 15 '15 at 9:57










  • $begingroup$
    It's not a polynomial, but if $F_n$ is the $n^{text{th}}$ Fibonacci number, then $gcd(p, q) = gcd(F_p, F_q)$ : math.stackexchange.com/a/506108/97045
    $endgroup$
    – DanielV
    Jun 15 '15 at 10:18






  • 2




    $begingroup$
    @RoryDaulton: OP said that $f(p)$ and $f(q)$ should be coprime for all such $p,q$. Though poorly stated, this means that it should do this for all coprime numbers.
    $endgroup$
    – user230734
    Jun 15 '15 at 10:45






  • 2




    $begingroup$
    @BolzWeir: I agree that seems to be what the OP means, but if so the question should have the introductory "If $p,q$ are co-prime integers, then" removed. I would do that edit myself if the OP himself made his meaning clear. I hate to edit other people's questions unless the meaning is made perfectly clear.
    $endgroup$
    – Rory Daulton
    Jun 15 '15 at 10:47








  • 1




    $begingroup$
    @EstebanCrespi The question explicitly excludes $f(x) = x^n$ for any $n geq 0$...
    $endgroup$
    – A.P.
    Jun 15 '15 at 14:00














9












9








9


4



$begingroup$


Is there a polynomial, $f(x)$, such that for all natural numbers $p$ and $q$, if $gcd(p, q) = 1$ then $gcd(f(p), f(q)) = 1$?



Note : Function $f(x)$ must be a polynomial in $x$, not depend on $p$ or $q$, and not be the trivial case of a polynomial with only $1$ term ($f(x) = c$ or $f(x) = x^p$).






elementary-number-theory prime-numbers







share|cite|improve this question











$endgroup$




Is there a polynomial, $f(x)$, such that for all natural numbers $p$ and $q$, if $gcd(p, q) = 1$ then $gcd(f(p), f(q)) = 1$?



Note : Function $f(x)$ must be a polynomial in $x$, not depend on $p$ or $q$, and not be the trivial case of a polynomial with only $1$ term ($f(x) = c$ or $f(x) = x^p$).






elementary-number-theory prime-numbers




elementary-number-theory prime-numbers






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Jun 15 '15 at 11:04









DanielV

18.1k42755




18.1k42755










asked Jun 15 '15 at 9:46









hanugmhanugm

878621




878621












  • $begingroup$
    At least $f(x) = x^2+x-1$ for $p=2$ and $q=3$, because $gcd(5,11)=1$
    $endgroup$
    – Eemil Wallin
    Jun 15 '15 at 9:57










  • $begingroup$
    It's not a polynomial, but if $F_n$ is the $n^{text{th}}$ Fibonacci number, then $gcd(p, q) = gcd(F_p, F_q)$ : math.stackexchange.com/a/506108/97045
    $endgroup$
    – DanielV
    Jun 15 '15 at 10:18






  • 2




    $begingroup$
    @RoryDaulton: OP said that $f(p)$ and $f(q)$ should be coprime for all such $p,q$. Though poorly stated, this means that it should do this for all coprime numbers.
    $endgroup$
    – user230734
    Jun 15 '15 at 10:45






  • 2




    $begingroup$
    @BolzWeir: I agree that seems to be what the OP means, but if so the question should have the introductory "If $p,q$ are co-prime integers, then" removed. I would do that edit myself if the OP himself made his meaning clear. I hate to edit other people's questions unless the meaning is made perfectly clear.
    $endgroup$
    – Rory Daulton
    Jun 15 '15 at 10:47








  • 1




    $begingroup$
    @EstebanCrespi The question explicitly excludes $f(x) = x^n$ for any $n geq 0$...
    $endgroup$
    – A.P.
    Jun 15 '15 at 14:00


















  • $begingroup$
    At least $f(x) = x^2+x-1$ for $p=2$ and $q=3$, because $gcd(5,11)=1$
    $endgroup$
    – Eemil Wallin
    Jun 15 '15 at 9:57










  • $begingroup$
    It's not a polynomial, but if $F_n$ is the $n^{text{th}}$ Fibonacci number, then $gcd(p, q) = gcd(F_p, F_q)$ : math.stackexchange.com/a/506108/97045
    $endgroup$
    – DanielV
    Jun 15 '15 at 10:18






  • 2




    $begingroup$
    @RoryDaulton: OP said that $f(p)$ and $f(q)$ should be coprime for all such $p,q$. Though poorly stated, this means that it should do this for all coprime numbers.
    $endgroup$
    – user230734
    Jun 15 '15 at 10:45






  • 2




    $begingroup$
    @BolzWeir: I agree that seems to be what the OP means, but if so the question should have the introductory "If $p,q$ are co-prime integers, then" removed. I would do that edit myself if the OP himself made his meaning clear. I hate to edit other people's questions unless the meaning is made perfectly clear.
    $endgroup$
    – Rory Daulton
    Jun 15 '15 at 10:47








  • 1




    $begingroup$
    @EstebanCrespi The question explicitly excludes $f(x) = x^n$ for any $n geq 0$...
    $endgroup$
    – A.P.
    Jun 15 '15 at 14:00
















$begingroup$
At least $f(x) = x^2+x-1$ for $p=2$ and $q=3$, because $gcd(5,11)=1$
$endgroup$
– Eemil Wallin
Jun 15 '15 at 9:57




$begingroup$
At least $f(x) = x^2+x-1$ for $p=2$ and $q=3$, because $gcd(5,11)=1$
$endgroup$
– Eemil Wallin
Jun 15 '15 at 9:57












$begingroup$
It's not a polynomial, but if $F_n$ is the $n^{text{th}}$ Fibonacci number, then $gcd(p, q) = gcd(F_p, F_q)$ : math.stackexchange.com/a/506108/97045
$endgroup$
– DanielV
Jun 15 '15 at 10:18




$begingroup$
It's not a polynomial, but if $F_n$ is the $n^{text{th}}$ Fibonacci number, then $gcd(p, q) = gcd(F_p, F_q)$ : math.stackexchange.com/a/506108/97045
$endgroup$
– DanielV
Jun 15 '15 at 10:18




2




2




$begingroup$
@RoryDaulton: OP said that $f(p)$ and $f(q)$ should be coprime for all such $p,q$. Though poorly stated, this means that it should do this for all coprime numbers.
$endgroup$
– user230734
Jun 15 '15 at 10:45




$begingroup$
@RoryDaulton: OP said that $f(p)$ and $f(q)$ should be coprime for all such $p,q$. Though poorly stated, this means that it should do this for all coprime numbers.
$endgroup$
– user230734
Jun 15 '15 at 10:45




2




2




$begingroup$
@BolzWeir: I agree that seems to be what the OP means, but if so the question should have the introductory "If $p,q$ are co-prime integers, then" removed. I would do that edit myself if the OP himself made his meaning clear. I hate to edit other people's questions unless the meaning is made perfectly clear.
$endgroup$
– Rory Daulton
Jun 15 '15 at 10:47






$begingroup$
@BolzWeir: I agree that seems to be what the OP means, but if so the question should have the introductory "If $p,q$ are co-prime integers, then" removed. I would do that edit myself if the OP himself made his meaning clear. I hate to edit other people's questions unless the meaning is made perfectly clear.
$endgroup$
– Rory Daulton
Jun 15 '15 at 10:47






1




1




$begingroup$
@EstebanCrespi The question explicitly excludes $f(x) = x^n$ for any $n geq 0$...
$endgroup$
– A.P.
Jun 15 '15 at 14:00




$begingroup$
@EstebanCrespi The question explicitly excludes $f(x) = x^n$ for any $n geq 0$...
$endgroup$
– A.P.
Jun 15 '15 at 14:00










2 Answers
2






active

oldest

votes


















1












$begingroup$

How about $f(x)=(x-p)(x-q)+1$?






share|cite|improve this answer









$endgroup$









  • 2




    $begingroup$
    I believe he means $forall p, q$
    $endgroup$
    – DanielV
    Jun 15 '15 at 10:18










  • $begingroup$
    In this case, $mathrm{gcd}(f(p),f(q)) = mathrm{gcd}((p-p)(p-q)+1,,(q-p)(q-q)+1) = mathrm{gcd}(1,1) = 1$, so I believe it is true for all $p,q$.
    $endgroup$
    – molarmass
    Jun 15 '15 at 10:28












  • $begingroup$
    @molarmass Going from "$f(p)$ and $f(q)$ are coprime" to "$f(a)$ and $f(b)$ are coprime for every coprime pair $a,b$" is quite a big leap...
    $endgroup$
    – A.P.
    Jun 15 '15 at 10:50










  • $begingroup$
    $f(p)$ and $f(q)$ are coprime for all $p,q$, which implies $f(a)$ and $f(b)$ are coprime for every coprime pair $a,b$.
    $endgroup$
    – molarmass
    Jun 15 '15 at 10:53






  • 2




    $begingroup$
    @molarmass The definition of $f$ depends on $p$ and $q$. Thus you can't say "for all $p,q$" because those numbers are fixed as soon as you define $f$.
    $endgroup$
    – A.P.
    Jun 15 '15 at 11:05



















1












$begingroup$

Yeah, I realize I'm a bit late for this, but here goes:



We show that for any prime $p$, $P(p)$ is a (positive or negative) power of $p$. Assume for the sake of contradiction that some prime $qneq p$ divides $P(p)$. Then



$$q|P(p)implies q|P(p+q),$$



so $gcd(P(p),P(p+q))neq 1$, a contradiction. Now, as $-x^{d+1}<P(x)<x^{d+1}$ for all sufficiently large $x$ (if $d$ is the degree of $P$), we must have by the Pigeonhole principle that there exist some fixed $sin{-1,1},kinmathbb{Z}_{geq 0}$ so that $P(p)=sp^k$ for infinitely many primes $p$ (as the only possibilities for large enough $p$ are $pm 1,pm p,cdots,pm p^d$). But then



$$P(x)-sx^k$$



has infinitely many roots, and thus $P(x)$ is identically the polynomial $pm x^k$.






share|cite|improve this answer









$endgroup$














    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
    });


    }
    });














    draft saved

    draft discarded


















    StackExchange.ready(
    function () {
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1325953%2fis-there-any-polynomial-function-f-such-that-if-gcdp-q-1-then-gcdfp%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









    1












    $begingroup$

    How about $f(x)=(x-p)(x-q)+1$?






    share|cite|improve this answer









    $endgroup$









    • 2




      $begingroup$
      I believe he means $forall p, q$
      $endgroup$
      – DanielV
      Jun 15 '15 at 10:18










    • $begingroup$
      In this case, $mathrm{gcd}(f(p),f(q)) = mathrm{gcd}((p-p)(p-q)+1,,(q-p)(q-q)+1) = mathrm{gcd}(1,1) = 1$, so I believe it is true for all $p,q$.
      $endgroup$
      – molarmass
      Jun 15 '15 at 10:28












    • $begingroup$
      @molarmass Going from "$f(p)$ and $f(q)$ are coprime" to "$f(a)$ and $f(b)$ are coprime for every coprime pair $a,b$" is quite a big leap...
      $endgroup$
      – A.P.
      Jun 15 '15 at 10:50










    • $begingroup$
      $f(p)$ and $f(q)$ are coprime for all $p,q$, which implies $f(a)$ and $f(b)$ are coprime for every coprime pair $a,b$.
      $endgroup$
      – molarmass
      Jun 15 '15 at 10:53






    • 2




      $begingroup$
      @molarmass The definition of $f$ depends on $p$ and $q$. Thus you can't say "for all $p,q$" because those numbers are fixed as soon as you define $f$.
      $endgroup$
      – A.P.
      Jun 15 '15 at 11:05
















    1












    $begingroup$

    How about $f(x)=(x-p)(x-q)+1$?






    share|cite|improve this answer









    $endgroup$









    • 2




      $begingroup$
      I believe he means $forall p, q$
      $endgroup$
      – DanielV
      Jun 15 '15 at 10:18










    • $begingroup$
      In this case, $mathrm{gcd}(f(p),f(q)) = mathrm{gcd}((p-p)(p-q)+1,,(q-p)(q-q)+1) = mathrm{gcd}(1,1) = 1$, so I believe it is true for all $p,q$.
      $endgroup$
      – molarmass
      Jun 15 '15 at 10:28












    • $begingroup$
      @molarmass Going from "$f(p)$ and $f(q)$ are coprime" to "$f(a)$ and $f(b)$ are coprime for every coprime pair $a,b$" is quite a big leap...
      $endgroup$
      – A.P.
      Jun 15 '15 at 10:50










    • $begingroup$
      $f(p)$ and $f(q)$ are coprime for all $p,q$, which implies $f(a)$ and $f(b)$ are coprime for every coprime pair $a,b$.
      $endgroup$
      – molarmass
      Jun 15 '15 at 10:53






    • 2




      $begingroup$
      @molarmass The definition of $f$ depends on $p$ and $q$. Thus you can't say "for all $p,q$" because those numbers are fixed as soon as you define $f$.
      $endgroup$
      – A.P.
      Jun 15 '15 at 11:05














    1












    1








    1





    $begingroup$

    How about $f(x)=(x-p)(x-q)+1$?






    share|cite|improve this answer









    $endgroup$



    How about $f(x)=(x-p)(x-q)+1$?







    share|cite|improve this answer












    share|cite|improve this answer



    share|cite|improve this answer










    answered Jun 15 '15 at 10:16









    Anurag AAnurag A

    26.4k12351




    26.4k12351








    • 2




      $begingroup$
      I believe he means $forall p, q$
      $endgroup$
      – DanielV
      Jun 15 '15 at 10:18










    • $begingroup$
      In this case, $mathrm{gcd}(f(p),f(q)) = mathrm{gcd}((p-p)(p-q)+1,,(q-p)(q-q)+1) = mathrm{gcd}(1,1) = 1$, so I believe it is true for all $p,q$.
      $endgroup$
      – molarmass
      Jun 15 '15 at 10:28












    • $begingroup$
      @molarmass Going from "$f(p)$ and $f(q)$ are coprime" to "$f(a)$ and $f(b)$ are coprime for every coprime pair $a,b$" is quite a big leap...
      $endgroup$
      – A.P.
      Jun 15 '15 at 10:50










    • $begingroup$
      $f(p)$ and $f(q)$ are coprime for all $p,q$, which implies $f(a)$ and $f(b)$ are coprime for every coprime pair $a,b$.
      $endgroup$
      – molarmass
      Jun 15 '15 at 10:53






    • 2




      $begingroup$
      @molarmass The definition of $f$ depends on $p$ and $q$. Thus you can't say "for all $p,q$" because those numbers are fixed as soon as you define $f$.
      $endgroup$
      – A.P.
      Jun 15 '15 at 11:05














    • 2




      $begingroup$
      I believe he means $forall p, q$
      $endgroup$
      – DanielV
      Jun 15 '15 at 10:18










    • $begingroup$
      In this case, $mathrm{gcd}(f(p),f(q)) = mathrm{gcd}((p-p)(p-q)+1,,(q-p)(q-q)+1) = mathrm{gcd}(1,1) = 1$, so I believe it is true for all $p,q$.
      $endgroup$
      – molarmass
      Jun 15 '15 at 10:28












    • $begingroup$
      @molarmass Going from "$f(p)$ and $f(q)$ are coprime" to "$f(a)$ and $f(b)$ are coprime for every coprime pair $a,b$" is quite a big leap...
      $endgroup$
      – A.P.
      Jun 15 '15 at 10:50










    • $begingroup$
      $f(p)$ and $f(q)$ are coprime for all $p,q$, which implies $f(a)$ and $f(b)$ are coprime for every coprime pair $a,b$.
      $endgroup$
      – molarmass
      Jun 15 '15 at 10:53






    • 2




      $begingroup$
      @molarmass The definition of $f$ depends on $p$ and $q$. Thus you can't say "for all $p,q$" because those numbers are fixed as soon as you define $f$.
      $endgroup$
      – A.P.
      Jun 15 '15 at 11:05








    2




    2




    $begingroup$
    I believe he means $forall p, q$
    $endgroup$
    – DanielV
    Jun 15 '15 at 10:18




    $begingroup$
    I believe he means $forall p, q$
    $endgroup$
    – DanielV
    Jun 15 '15 at 10:18












    $begingroup$
    In this case, $mathrm{gcd}(f(p),f(q)) = mathrm{gcd}((p-p)(p-q)+1,,(q-p)(q-q)+1) = mathrm{gcd}(1,1) = 1$, so I believe it is true for all $p,q$.
    $endgroup$
    – molarmass
    Jun 15 '15 at 10:28






    $begingroup$
    In this case, $mathrm{gcd}(f(p),f(q)) = mathrm{gcd}((p-p)(p-q)+1,,(q-p)(q-q)+1) = mathrm{gcd}(1,1) = 1$, so I believe it is true for all $p,q$.
    $endgroup$
    – molarmass
    Jun 15 '15 at 10:28














    $begingroup$
    @molarmass Going from "$f(p)$ and $f(q)$ are coprime" to "$f(a)$ and $f(b)$ are coprime for every coprime pair $a,b$" is quite a big leap...
    $endgroup$
    – A.P.
    Jun 15 '15 at 10:50




    $begingroup$
    @molarmass Going from "$f(p)$ and $f(q)$ are coprime" to "$f(a)$ and $f(b)$ are coprime for every coprime pair $a,b$" is quite a big leap...
    $endgroup$
    – A.P.
    Jun 15 '15 at 10:50












    $begingroup$
    $f(p)$ and $f(q)$ are coprime for all $p,q$, which implies $f(a)$ and $f(b)$ are coprime for every coprime pair $a,b$.
    $endgroup$
    – molarmass
    Jun 15 '15 at 10:53




    $begingroup$
    $f(p)$ and $f(q)$ are coprime for all $p,q$, which implies $f(a)$ and $f(b)$ are coprime for every coprime pair $a,b$.
    $endgroup$
    – molarmass
    Jun 15 '15 at 10:53




    2




    2




    $begingroup$
    @molarmass The definition of $f$ depends on $p$ and $q$. Thus you can't say "for all $p,q$" because those numbers are fixed as soon as you define $f$.
    $endgroup$
    – A.P.
    Jun 15 '15 at 11:05




    $begingroup$
    @molarmass The definition of $f$ depends on $p$ and $q$. Thus you can't say "for all $p,q$" because those numbers are fixed as soon as you define $f$.
    $endgroup$
    – A.P.
    Jun 15 '15 at 11:05











    1












    $begingroup$

    Yeah, I realize I'm a bit late for this, but here goes:



    We show that for any prime $p$, $P(p)$ is a (positive or negative) power of $p$. Assume for the sake of contradiction that some prime $qneq p$ divides $P(p)$. Then



    $$q|P(p)implies q|P(p+q),$$



    so $gcd(P(p),P(p+q))neq 1$, a contradiction. Now, as $-x^{d+1}<P(x)<x^{d+1}$ for all sufficiently large $x$ (if $d$ is the degree of $P$), we must have by the Pigeonhole principle that there exist some fixed $sin{-1,1},kinmathbb{Z}_{geq 0}$ so that $P(p)=sp^k$ for infinitely many primes $p$ (as the only possibilities for large enough $p$ are $pm 1,pm p,cdots,pm p^d$). But then



    $$P(x)-sx^k$$



    has infinitely many roots, and thus $P(x)$ is identically the polynomial $pm x^k$.






    share|cite|improve this answer









    $endgroup$


















      1












      $begingroup$

      Yeah, I realize I'm a bit late for this, but here goes:



      We show that for any prime $p$, $P(p)$ is a (positive or negative) power of $p$. Assume for the sake of contradiction that some prime $qneq p$ divides $P(p)$. Then



      $$q|P(p)implies q|P(p+q),$$



      so $gcd(P(p),P(p+q))neq 1$, a contradiction. Now, as $-x^{d+1}<P(x)<x^{d+1}$ for all sufficiently large $x$ (if $d$ is the degree of $P$), we must have by the Pigeonhole principle that there exist some fixed $sin{-1,1},kinmathbb{Z}_{geq 0}$ so that $P(p)=sp^k$ for infinitely many primes $p$ (as the only possibilities for large enough $p$ are $pm 1,pm p,cdots,pm p^d$). But then



      $$P(x)-sx^k$$



      has infinitely many roots, and thus $P(x)$ is identically the polynomial $pm x^k$.






      share|cite|improve this answer









      $endgroup$
















        1












        1








        1





        $begingroup$

        Yeah, I realize I'm a bit late for this, but here goes:



        We show that for any prime $p$, $P(p)$ is a (positive or negative) power of $p$. Assume for the sake of contradiction that some prime $qneq p$ divides $P(p)$. Then



        $$q|P(p)implies q|P(p+q),$$



        so $gcd(P(p),P(p+q))neq 1$, a contradiction. Now, as $-x^{d+1}<P(x)<x^{d+1}$ for all sufficiently large $x$ (if $d$ is the degree of $P$), we must have by the Pigeonhole principle that there exist some fixed $sin{-1,1},kinmathbb{Z}_{geq 0}$ so that $P(p)=sp^k$ for infinitely many primes $p$ (as the only possibilities for large enough $p$ are $pm 1,pm p,cdots,pm p^d$). But then



        $$P(x)-sx^k$$



        has infinitely many roots, and thus $P(x)$ is identically the polynomial $pm x^k$.






        share|cite|improve this answer









        $endgroup$



        Yeah, I realize I'm a bit late for this, but here goes:



        We show that for any prime $p$, $P(p)$ is a (positive or negative) power of $p$. Assume for the sake of contradiction that some prime $qneq p$ divides $P(p)$. Then



        $$q|P(p)implies q|P(p+q),$$



        so $gcd(P(p),P(p+q))neq 1$, a contradiction. Now, as $-x^{d+1}<P(x)<x^{d+1}$ for all sufficiently large $x$ (if $d$ is the degree of $P$), we must have by the Pigeonhole principle that there exist some fixed $sin{-1,1},kinmathbb{Z}_{geq 0}$ so that $P(p)=sp^k$ for infinitely many primes $p$ (as the only possibilities for large enough $p$ are $pm 1,pm p,cdots,pm p^d$). But then



        $$P(x)-sx^k$$



        has infinitely many roots, and thus $P(x)$ is identically the polynomial $pm x^k$.







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered Dec 11 '18 at 4:32









        Carl SchildkrautCarl Schildkraut

        11.8k11444




        11.8k11444






























            draft saved

            draft discarded




















































            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.




            draft saved


            draft discarded














            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1325953%2fis-there-any-polynomial-function-f-such-that-if-gcdp-q-1-then-gcdfp%23new-answer', 'question_page');
            }
            );

            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







            -

            Popular posts from this blog

            How to send String Array data to Server using php in android

            Image
            0 I have a String array which contains value string array = {6,37,38,837,7,...} and I have also used some string values. I want to send that all string values and string array to my database which is located at server side. When I am click on submit button the data will stored in table. On the PHP side I want to read this array as it is,other thing i will do at background means PHP side. See my below code then you will get it what I am says. Here is my code: public class Hotels extends Activity { // Declare Variables JSONArray jsonarray = null; private static final String TAG_ID = "id"; public static final String TAG_NAME = "name"; public static final String TAG_LOCATION = "location"; public static final String TAG_DESC = "description"; String f_date, l_date;...
            Read more

            Title Spacing in Bjornstrup Chapter, Removing Chapter Number From Contents

            Image
            up vote 5 down vote favorite 2 I would like to make it so that the vertical space below the title of each chapter is the same when using the Bjornstrup package (i.e. so that the descenders do not affect the spacing - as shown by the red arrow in the picture below). I think I'm fairly happy with the spacing around "A chapter", so I'd really like titles without descenders (e.g. "Contents") to have the same vertical spacing as "A chapter" below the title. I would also like to remove the large "0" in the contents title. Any help appreciated, as always. documentclass[11pt,a4paper]{book} % Packages[![enter image description here][1]][1] usepackage[left=3.5cm, right=3.5cm, top=4.3cm, bottom=4.25cm]{geometry} usepackage[utf8]{inputenc} usepackage{libertine} usepackage[libertine]{newtx...
            Read more

            Is anime1.com a legal site for watching anime?

            Image
            up vote 4 down vote favorite 1 Other anime streaming sites are blocking my IP because I'm Iranian while anime1.com isn't. I wanted to know if it's legal to watch/stream anime from this site. Thanks. anime-production share | improve this question edited Nov 27 at 22:38 W. Are 1,599 2 23 asked Nov 27 at 20:36 mhnajafi 23 3 add a comment ...
            Read more