If $ageq 2$, $anmid b$, and $a^n-1mid b^n-1$ for all $ninmathbb{N}$, then $b=1$











up vote
7
down vote

favorite
1












Let $a,binmathbb{N}$ be such that $ageq 2$, $anmid b$, and $a^n-1mid b^n-1$ for all $ninmathbb{N}$, then $b=1$.



PS: In fact, if we do not assume that $anmid b$, then the statement should be $b=a^k$ for some $kinmathbb{N}cup{0}$. The above statement can deduce the fact.










share|cite|improve this question
























  • Please, try to make the titles of your questions more informative. E.g., Why does $a<b$ imply $a+c<b+c$? is much more useful for other users than A question about inequality. From How can I ask a good question?: Make your title as descriptive as possible. In many cases one can actually phrase the title as the question, at least in such a way so as to be comprehensible to an expert reader. You can find more tips for choosing a good title here.
    – Martin Sleziak
    Oct 12 '16 at 5:23















up vote
7
down vote

favorite
1












Let $a,binmathbb{N}$ be such that $ageq 2$, $anmid b$, and $a^n-1mid b^n-1$ for all $ninmathbb{N}$, then $b=1$.



PS: In fact, if we do not assume that $anmid b$, then the statement should be $b=a^k$ for some $kinmathbb{N}cup{0}$. The above statement can deduce the fact.










share|cite|improve this question
























  • Please, try to make the titles of your questions more informative. E.g., Why does $a<b$ imply $a+c<b+c$? is much more useful for other users than A question about inequality. From How can I ask a good question?: Make your title as descriptive as possible. In many cases one can actually phrase the title as the question, at least in such a way so as to be comprehensible to an expert reader. You can find more tips for choosing a good title here.
    – Martin Sleziak
    Oct 12 '16 at 5:23













up vote
7
down vote

favorite
1









up vote
7
down vote

favorite
1






1





Let $a,binmathbb{N}$ be such that $ageq 2$, $anmid b$, and $a^n-1mid b^n-1$ for all $ninmathbb{N}$, then $b=1$.



PS: In fact, if we do not assume that $anmid b$, then the statement should be $b=a^k$ for some $kinmathbb{N}cup{0}$. The above statement can deduce the fact.










share|cite|improve this question















Let $a,binmathbb{N}$ be such that $ageq 2$, $anmid b$, and $a^n-1mid b^n-1$ for all $ninmathbb{N}$, then $b=1$.



PS: In fact, if we do not assume that $anmid b$, then the statement should be $b=a^k$ for some $kinmathbb{N}cup{0}$. The above statement can deduce the fact.







elementary-number-theory divisibility






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Oct 12 '16 at 5:23









Martin Sleziak

44.6k7115270




44.6k7115270










asked Oct 12 '16 at 4:14









m-agag2016

63448




63448












  • Please, try to make the titles of your questions more informative. E.g., Why does $a<b$ imply $a+c<b+c$? is much more useful for other users than A question about inequality. From How can I ask a good question?: Make your title as descriptive as possible. In many cases one can actually phrase the title as the question, at least in such a way so as to be comprehensible to an expert reader. You can find more tips for choosing a good title here.
    – Martin Sleziak
    Oct 12 '16 at 5:23


















  • Please, try to make the titles of your questions more informative. E.g., Why does $a<b$ imply $a+c<b+c$? is much more useful for other users than A question about inequality. From How can I ask a good question?: Make your title as descriptive as possible. In many cases one can actually phrase the title as the question, at least in such a way so as to be comprehensible to an expert reader. You can find more tips for choosing a good title here.
    – Martin Sleziak
    Oct 12 '16 at 5:23
















Please, try to make the titles of your questions more informative. E.g., Why does $a<b$ imply $a+c<b+c$? is much more useful for other users than A question about inequality. From How can I ask a good question?: Make your title as descriptive as possible. In many cases one can actually phrase the title as the question, at least in such a way so as to be comprehensible to an expert reader. You can find more tips for choosing a good title here.
– Martin Sleziak
Oct 12 '16 at 5:23




Please, try to make the titles of your questions more informative. E.g., Why does $a<b$ imply $a+c<b+c$? is much more useful for other users than A question about inequality. From How can I ask a good question?: Make your title as descriptive as possible. In many cases one can actually phrase the title as the question, at least in such a way so as to be comprehensible to an expert reader. You can find more tips for choosing a good title here.
– Martin Sleziak
Oct 12 '16 at 5:23










2 Answers
2






active

oldest

votes

















up vote
2
down vote













This is a solution here which was found in some paper in AMM. it's a very nice proof. but it's very constructive. For example, the construction of $Q_k(x)$, $p_k$ and $r_{k,n}$, it's not so easy to construct them. Maybe there is some direct method.



This is a solution here which was found in some paper in AMM. it's a very nice proof. but it's very constructive. For example, the construction of $Q_k(x)$, $p_k$ and $r_{k,n}$, it's not so easy to construct them. Maybe there is some direct method.






share|cite|improve this answer




























    up vote
    0
    down vote













    Here is my proof from AoPS.



    $textbf{Problem 1.}$ Prove that if $b^n-1mid a^n-1$ for all $n$, then $a=b^k$ for some integer $k$.



    $textbf{Lemma 1.}$ If $b^n-1mid a^n-1$ for all $n$, then $(b-1)(b^2-1)ldots (b^n-1)mid n!(a-1)(a-b)ldots (a-b^{n-1})$ for every $n$.



    $textbf{Proof of Lemma 1.}$ First consider any prime $pmid (b-1)(b^2-1)ldots (b^n-1)$, so there exists minimal $d$ such that $pmid b^d-1$ and it's well-known fact that then $x^d-1equiv (x-1)(x-b)ldots (x-b^{d-1})pmod{p^{nu_p(b^d-1)}}$, so $P(x)=x^d-1$ has exactly $d$ consecutive roots $1, b, b^2,ldots , b^{d-1}$. From the condition $b^d-1mid a^d-1$ we get that $a$ is also the root of polynomial $x^d-1$. So easy to see that there exists only one $0leq d'leq d$, such that $a-b^{d'}equiv 0pmod{p^{nu_p(b^d-1)}}$. From this we get that for all $iequiv d'pmod{d}$, $a-b^iequiv 0pmod{p^{nu_p(b^d-1)}}$. Now from LTE lemma we get that $nu_p(b^{jd}-1)leqnu_p(b^d-1)+nu_p(j)$, for each $j$, so $nu_p(prod_{i=1}^n(b^i-1))leq[n/d]nu_p(b^d-1)+nu_p(n!)leqnu_p(n!(a-1)(a-b)ldots (a-b^{n-1}))$. Combining similar inequalities for every $p$ we get Lemma 1. $Box$



    $textbf{Proof of Problem 1.}$ Firstly it's simple exercise to prove that if a prime $p$ is such that $pmid a$, then $pmid b$. So there exists a positive integer $t$, such that $anmid b^{t-1}$, but $amid b^t$. From Lemma 1 we get that $(2t)!frac{(a-1)(a-b)ldots (a-b^{t-1})(a-b^t)ldots (a-b^{2t-1})}{(b-1)(b^2-1)ldots (b^t-1)(b^{t+1}-1)ldots (b^{2t}-1)}inmathbb{Z}$. But for every $i$ we have that $gcd(a, b^i-1)$, so if we just look on the numerator of the fraction above then we get that $$gcd(a,1)gcd(a, b)ldots gcd(a, b^{t-1})a^tmid (2t)!frac{(a-1)(a-b)ldots (a-b^{t-1})(a-b^t)ldots (a-b^{2t-1})}{(b-1)(b^2-1)ldots (b^t-1)(b^{t+1}-1)ldots (b^{2t}-1)}$$ and if $anot= b^x$ for every natural $x$, then $$|(2t)!frac{(a-1)(a-b)ldots (a-b^{t-1})(a-b^t)ldots (a-b^{2t-1})}{(b-1)(b^2-1)ldots (b^t-1)(b^{t+1}-1)ldots (b^{2t}-1)}|geq gcd(a,1)gcd(a, b)ldots gcd(a, b^{t-1})a^t$$ But it's easy to check that $|(2t)!frac{(a-1)(a-b)ldots (a-b^{t-1})(a-b^t)ldots (a-b^{2t-1})}{(b-1)(b^2-1)ldots (b^t-1)(b^{t+1}-1)ldots (b^{2t}-1)}|leq (2t)!a^t$ and $gcd(a,1)gcd(a, b)ldots gcd(a, b^{t-1})geq 2^{frac{t(t-1)}{2}}$ (here we used the fact that $gcd(a, b^i)midgcd(a, b^{i+1})$ and $gcd(a, b^{i-1})not=gcd(a, b^i)$ for $ileq t-1$). So $2^{frac{t(t-1)}{2}}a^tleq (2t)!a^t$. Contradiction. $Box$






    share|cite|improve this answer























    • Can someone find any mistakes in another proof : Let $p$ be a prime number greater than $a$. Consider a polynomial $F(x)=x^p-1$ over $mod{frac{b^p-1}{b-1}}$. One can get that it has $d$ consecutive roots $1, b,ldots , b^{p-1}$. So from the fact $b^p-1mid a^p-1$ we get that $a$ is also root of $F(x)equiv 0pmod{frac{b^p-1}{b-1}}$. Thus, $aequiv b^ipmod{frac{b^p-1}{b-1}}$ for some $ileq p-1$.
      – solver6
      Nov 27 at 21:19










    • Can someone find any mistakes in another proof : Let $p$ be a prime number greater than $a$. Consider a polynomial $F(x)=x^p-1$ over $mod{frac{b^p-1}{b-1}}$. One can get that $P(x)$ has $d$ consecutive roots $1, b,ldots , b^{p-1}$. So from the fact $b^p-1mid a^p-1$ we get that $a$ is also root of $F(x)equiv 0pmod{frac{b^p-1}{b-1}}$. Thus, $aequiv b^ipmod{frac{b^p-1}{b-1}}$ for some $ileq p-1$. Finally, if $anot= b^i$, then $b^{p-1}-1geq |a-b^i|geqfrac{b^p-1}{b-1}$. Contradiction. $Box$
      – solver6
      Nov 27 at 21:26













    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%2f1964788%2fif-a-geq-2-a-nmid-b-and-an-1-mid-bn-1-for-all-n-in-mathbbn-then%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








    up vote
    2
    down vote













    This is a solution here which was found in some paper in AMM. it's a very nice proof. but it's very constructive. For example, the construction of $Q_k(x)$, $p_k$ and $r_{k,n}$, it's not so easy to construct them. Maybe there is some direct method.



    This is a solution here which was found in some paper in AMM. it's a very nice proof. but it's very constructive. For example, the construction of $Q_k(x)$, $p_k$ and $r_{k,n}$, it's not so easy to construct them. Maybe there is some direct method.






    share|cite|improve this answer

























      up vote
      2
      down vote













      This is a solution here which was found in some paper in AMM. it's a very nice proof. but it's very constructive. For example, the construction of $Q_k(x)$, $p_k$ and $r_{k,n}$, it's not so easy to construct them. Maybe there is some direct method.



      This is a solution here which was found in some paper in AMM. it's a very nice proof. but it's very constructive. For example, the construction of $Q_k(x)$, $p_k$ and $r_{k,n}$, it's not so easy to construct them. Maybe there is some direct method.






      share|cite|improve this answer























        up vote
        2
        down vote










        up vote
        2
        down vote









        This is a solution here which was found in some paper in AMM. it's a very nice proof. but it's very constructive. For example, the construction of $Q_k(x)$, $p_k$ and $r_{k,n}$, it's not so easy to construct them. Maybe there is some direct method.



        This is a solution here which was found in some paper in AMM. it's a very nice proof. but it's very constructive. For example, the construction of $Q_k(x)$, $p_k$ and $r_{k,n}$, it's not so easy to construct them. Maybe there is some direct method.






        share|cite|improve this answer












        This is a solution here which was found in some paper in AMM. it's a very nice proof. but it's very constructive. For example, the construction of $Q_k(x)$, $p_k$ and $r_{k,n}$, it's not so easy to construct them. Maybe there is some direct method.



        This is a solution here which was found in some paper in AMM. it's a very nice proof. but it's very constructive. For example, the construction of $Q_k(x)$, $p_k$ and $r_{k,n}$, it's not so easy to construct them. Maybe there is some direct method.







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered Nov 20 '16 at 4:27









        m-agag2016

        63448




        63448






















            up vote
            0
            down vote













            Here is my proof from AoPS.



            $textbf{Problem 1.}$ Prove that if $b^n-1mid a^n-1$ for all $n$, then $a=b^k$ for some integer $k$.



            $textbf{Lemma 1.}$ If $b^n-1mid a^n-1$ for all $n$, then $(b-1)(b^2-1)ldots (b^n-1)mid n!(a-1)(a-b)ldots (a-b^{n-1})$ for every $n$.



            $textbf{Proof of Lemma 1.}$ First consider any prime $pmid (b-1)(b^2-1)ldots (b^n-1)$, so there exists minimal $d$ such that $pmid b^d-1$ and it's well-known fact that then $x^d-1equiv (x-1)(x-b)ldots (x-b^{d-1})pmod{p^{nu_p(b^d-1)}}$, so $P(x)=x^d-1$ has exactly $d$ consecutive roots $1, b, b^2,ldots , b^{d-1}$. From the condition $b^d-1mid a^d-1$ we get that $a$ is also the root of polynomial $x^d-1$. So easy to see that there exists only one $0leq d'leq d$, such that $a-b^{d'}equiv 0pmod{p^{nu_p(b^d-1)}}$. From this we get that for all $iequiv d'pmod{d}$, $a-b^iequiv 0pmod{p^{nu_p(b^d-1)}}$. Now from LTE lemma we get that $nu_p(b^{jd}-1)leqnu_p(b^d-1)+nu_p(j)$, for each $j$, so $nu_p(prod_{i=1}^n(b^i-1))leq[n/d]nu_p(b^d-1)+nu_p(n!)leqnu_p(n!(a-1)(a-b)ldots (a-b^{n-1}))$. Combining similar inequalities for every $p$ we get Lemma 1. $Box$



            $textbf{Proof of Problem 1.}$ Firstly it's simple exercise to prove that if a prime $p$ is such that $pmid a$, then $pmid b$. So there exists a positive integer $t$, such that $anmid b^{t-1}$, but $amid b^t$. From Lemma 1 we get that $(2t)!frac{(a-1)(a-b)ldots (a-b^{t-1})(a-b^t)ldots (a-b^{2t-1})}{(b-1)(b^2-1)ldots (b^t-1)(b^{t+1}-1)ldots (b^{2t}-1)}inmathbb{Z}$. But for every $i$ we have that $gcd(a, b^i-1)$, so if we just look on the numerator of the fraction above then we get that $$gcd(a,1)gcd(a, b)ldots gcd(a, b^{t-1})a^tmid (2t)!frac{(a-1)(a-b)ldots (a-b^{t-1})(a-b^t)ldots (a-b^{2t-1})}{(b-1)(b^2-1)ldots (b^t-1)(b^{t+1}-1)ldots (b^{2t}-1)}$$ and if $anot= b^x$ for every natural $x$, then $$|(2t)!frac{(a-1)(a-b)ldots (a-b^{t-1})(a-b^t)ldots (a-b^{2t-1})}{(b-1)(b^2-1)ldots (b^t-1)(b^{t+1}-1)ldots (b^{2t}-1)}|geq gcd(a,1)gcd(a, b)ldots gcd(a, b^{t-1})a^t$$ But it's easy to check that $|(2t)!frac{(a-1)(a-b)ldots (a-b^{t-1})(a-b^t)ldots (a-b^{2t-1})}{(b-1)(b^2-1)ldots (b^t-1)(b^{t+1}-1)ldots (b^{2t}-1)}|leq (2t)!a^t$ and $gcd(a,1)gcd(a, b)ldots gcd(a, b^{t-1})geq 2^{frac{t(t-1)}{2}}$ (here we used the fact that $gcd(a, b^i)midgcd(a, b^{i+1})$ and $gcd(a, b^{i-1})not=gcd(a, b^i)$ for $ileq t-1$). So $2^{frac{t(t-1)}{2}}a^tleq (2t)!a^t$. Contradiction. $Box$






            share|cite|improve this answer























            • Can someone find any mistakes in another proof : Let $p$ be a prime number greater than $a$. Consider a polynomial $F(x)=x^p-1$ over $mod{frac{b^p-1}{b-1}}$. One can get that it has $d$ consecutive roots $1, b,ldots , b^{p-1}$. So from the fact $b^p-1mid a^p-1$ we get that $a$ is also root of $F(x)equiv 0pmod{frac{b^p-1}{b-1}}$. Thus, $aequiv b^ipmod{frac{b^p-1}{b-1}}$ for some $ileq p-1$.
              – solver6
              Nov 27 at 21:19










            • Can someone find any mistakes in another proof : Let $p$ be a prime number greater than $a$. Consider a polynomial $F(x)=x^p-1$ over $mod{frac{b^p-1}{b-1}}$. One can get that $P(x)$ has $d$ consecutive roots $1, b,ldots , b^{p-1}$. So from the fact $b^p-1mid a^p-1$ we get that $a$ is also root of $F(x)equiv 0pmod{frac{b^p-1}{b-1}}$. Thus, $aequiv b^ipmod{frac{b^p-1}{b-1}}$ for some $ileq p-1$. Finally, if $anot= b^i$, then $b^{p-1}-1geq |a-b^i|geqfrac{b^p-1}{b-1}$. Contradiction. $Box$
              – solver6
              Nov 27 at 21:26

















            up vote
            0
            down vote













            Here is my proof from AoPS.



            $textbf{Problem 1.}$ Prove that if $b^n-1mid a^n-1$ for all $n$, then $a=b^k$ for some integer $k$.



            $textbf{Lemma 1.}$ If $b^n-1mid a^n-1$ for all $n$, then $(b-1)(b^2-1)ldots (b^n-1)mid n!(a-1)(a-b)ldots (a-b^{n-1})$ for every $n$.



            $textbf{Proof of Lemma 1.}$ First consider any prime $pmid (b-1)(b^2-1)ldots (b^n-1)$, so there exists minimal $d$ such that $pmid b^d-1$ and it's well-known fact that then $x^d-1equiv (x-1)(x-b)ldots (x-b^{d-1})pmod{p^{nu_p(b^d-1)}}$, so $P(x)=x^d-1$ has exactly $d$ consecutive roots $1, b, b^2,ldots , b^{d-1}$. From the condition $b^d-1mid a^d-1$ we get that $a$ is also the root of polynomial $x^d-1$. So easy to see that there exists only one $0leq d'leq d$, such that $a-b^{d'}equiv 0pmod{p^{nu_p(b^d-1)}}$. From this we get that for all $iequiv d'pmod{d}$, $a-b^iequiv 0pmod{p^{nu_p(b^d-1)}}$. Now from LTE lemma we get that $nu_p(b^{jd}-1)leqnu_p(b^d-1)+nu_p(j)$, for each $j$, so $nu_p(prod_{i=1}^n(b^i-1))leq[n/d]nu_p(b^d-1)+nu_p(n!)leqnu_p(n!(a-1)(a-b)ldots (a-b^{n-1}))$. Combining similar inequalities for every $p$ we get Lemma 1. $Box$



            $textbf{Proof of Problem 1.}$ Firstly it's simple exercise to prove that if a prime $p$ is such that $pmid a$, then $pmid b$. So there exists a positive integer $t$, such that $anmid b^{t-1}$, but $amid b^t$. From Lemma 1 we get that $(2t)!frac{(a-1)(a-b)ldots (a-b^{t-1})(a-b^t)ldots (a-b^{2t-1})}{(b-1)(b^2-1)ldots (b^t-1)(b^{t+1}-1)ldots (b^{2t}-1)}inmathbb{Z}$. But for every $i$ we have that $gcd(a, b^i-1)$, so if we just look on the numerator of the fraction above then we get that $$gcd(a,1)gcd(a, b)ldots gcd(a, b^{t-1})a^tmid (2t)!frac{(a-1)(a-b)ldots (a-b^{t-1})(a-b^t)ldots (a-b^{2t-1})}{(b-1)(b^2-1)ldots (b^t-1)(b^{t+1}-1)ldots (b^{2t}-1)}$$ and if $anot= b^x$ for every natural $x$, then $$|(2t)!frac{(a-1)(a-b)ldots (a-b^{t-1})(a-b^t)ldots (a-b^{2t-1})}{(b-1)(b^2-1)ldots (b^t-1)(b^{t+1}-1)ldots (b^{2t}-1)}|geq gcd(a,1)gcd(a, b)ldots gcd(a, b^{t-1})a^t$$ But it's easy to check that $|(2t)!frac{(a-1)(a-b)ldots (a-b^{t-1})(a-b^t)ldots (a-b^{2t-1})}{(b-1)(b^2-1)ldots (b^t-1)(b^{t+1}-1)ldots (b^{2t}-1)}|leq (2t)!a^t$ and $gcd(a,1)gcd(a, b)ldots gcd(a, b^{t-1})geq 2^{frac{t(t-1)}{2}}$ (here we used the fact that $gcd(a, b^i)midgcd(a, b^{i+1})$ and $gcd(a, b^{i-1})not=gcd(a, b^i)$ for $ileq t-1$). So $2^{frac{t(t-1)}{2}}a^tleq (2t)!a^t$. Contradiction. $Box$






            share|cite|improve this answer























            • Can someone find any mistakes in another proof : Let $p$ be a prime number greater than $a$. Consider a polynomial $F(x)=x^p-1$ over $mod{frac{b^p-1}{b-1}}$. One can get that it has $d$ consecutive roots $1, b,ldots , b^{p-1}$. So from the fact $b^p-1mid a^p-1$ we get that $a$ is also root of $F(x)equiv 0pmod{frac{b^p-1}{b-1}}$. Thus, $aequiv b^ipmod{frac{b^p-1}{b-1}}$ for some $ileq p-1$.
              – solver6
              Nov 27 at 21:19










            • Can someone find any mistakes in another proof : Let $p$ be a prime number greater than $a$. Consider a polynomial $F(x)=x^p-1$ over $mod{frac{b^p-1}{b-1}}$. One can get that $P(x)$ has $d$ consecutive roots $1, b,ldots , b^{p-1}$. So from the fact $b^p-1mid a^p-1$ we get that $a$ is also root of $F(x)equiv 0pmod{frac{b^p-1}{b-1}}$. Thus, $aequiv b^ipmod{frac{b^p-1}{b-1}}$ for some $ileq p-1$. Finally, if $anot= b^i$, then $b^{p-1}-1geq |a-b^i|geqfrac{b^p-1}{b-1}$. Contradiction. $Box$
              – solver6
              Nov 27 at 21:26















            up vote
            0
            down vote










            up vote
            0
            down vote









            Here is my proof from AoPS.



            $textbf{Problem 1.}$ Prove that if $b^n-1mid a^n-1$ for all $n$, then $a=b^k$ for some integer $k$.



            $textbf{Lemma 1.}$ If $b^n-1mid a^n-1$ for all $n$, then $(b-1)(b^2-1)ldots (b^n-1)mid n!(a-1)(a-b)ldots (a-b^{n-1})$ for every $n$.



            $textbf{Proof of Lemma 1.}$ First consider any prime $pmid (b-1)(b^2-1)ldots (b^n-1)$, so there exists minimal $d$ such that $pmid b^d-1$ and it's well-known fact that then $x^d-1equiv (x-1)(x-b)ldots (x-b^{d-1})pmod{p^{nu_p(b^d-1)}}$, so $P(x)=x^d-1$ has exactly $d$ consecutive roots $1, b, b^2,ldots , b^{d-1}$. From the condition $b^d-1mid a^d-1$ we get that $a$ is also the root of polynomial $x^d-1$. So easy to see that there exists only one $0leq d'leq d$, such that $a-b^{d'}equiv 0pmod{p^{nu_p(b^d-1)}}$. From this we get that for all $iequiv d'pmod{d}$, $a-b^iequiv 0pmod{p^{nu_p(b^d-1)}}$. Now from LTE lemma we get that $nu_p(b^{jd}-1)leqnu_p(b^d-1)+nu_p(j)$, for each $j$, so $nu_p(prod_{i=1}^n(b^i-1))leq[n/d]nu_p(b^d-1)+nu_p(n!)leqnu_p(n!(a-1)(a-b)ldots (a-b^{n-1}))$. Combining similar inequalities for every $p$ we get Lemma 1. $Box$



            $textbf{Proof of Problem 1.}$ Firstly it's simple exercise to prove that if a prime $p$ is such that $pmid a$, then $pmid b$. So there exists a positive integer $t$, such that $anmid b^{t-1}$, but $amid b^t$. From Lemma 1 we get that $(2t)!frac{(a-1)(a-b)ldots (a-b^{t-1})(a-b^t)ldots (a-b^{2t-1})}{(b-1)(b^2-1)ldots (b^t-1)(b^{t+1}-1)ldots (b^{2t}-1)}inmathbb{Z}$. But for every $i$ we have that $gcd(a, b^i-1)$, so if we just look on the numerator of the fraction above then we get that $$gcd(a,1)gcd(a, b)ldots gcd(a, b^{t-1})a^tmid (2t)!frac{(a-1)(a-b)ldots (a-b^{t-1})(a-b^t)ldots (a-b^{2t-1})}{(b-1)(b^2-1)ldots (b^t-1)(b^{t+1}-1)ldots (b^{2t}-1)}$$ and if $anot= b^x$ for every natural $x$, then $$|(2t)!frac{(a-1)(a-b)ldots (a-b^{t-1})(a-b^t)ldots (a-b^{2t-1})}{(b-1)(b^2-1)ldots (b^t-1)(b^{t+1}-1)ldots (b^{2t}-1)}|geq gcd(a,1)gcd(a, b)ldots gcd(a, b^{t-1})a^t$$ But it's easy to check that $|(2t)!frac{(a-1)(a-b)ldots (a-b^{t-1})(a-b^t)ldots (a-b^{2t-1})}{(b-1)(b^2-1)ldots (b^t-1)(b^{t+1}-1)ldots (b^{2t}-1)}|leq (2t)!a^t$ and $gcd(a,1)gcd(a, b)ldots gcd(a, b^{t-1})geq 2^{frac{t(t-1)}{2}}$ (here we used the fact that $gcd(a, b^i)midgcd(a, b^{i+1})$ and $gcd(a, b^{i-1})not=gcd(a, b^i)$ for $ileq t-1$). So $2^{frac{t(t-1)}{2}}a^tleq (2t)!a^t$. Contradiction. $Box$






            share|cite|improve this answer














            Here is my proof from AoPS.



            $textbf{Problem 1.}$ Prove that if $b^n-1mid a^n-1$ for all $n$, then $a=b^k$ for some integer $k$.



            $textbf{Lemma 1.}$ If $b^n-1mid a^n-1$ for all $n$, then $(b-1)(b^2-1)ldots (b^n-1)mid n!(a-1)(a-b)ldots (a-b^{n-1})$ for every $n$.



            $textbf{Proof of Lemma 1.}$ First consider any prime $pmid (b-1)(b^2-1)ldots (b^n-1)$, so there exists minimal $d$ such that $pmid b^d-1$ and it's well-known fact that then $x^d-1equiv (x-1)(x-b)ldots (x-b^{d-1})pmod{p^{nu_p(b^d-1)}}$, so $P(x)=x^d-1$ has exactly $d$ consecutive roots $1, b, b^2,ldots , b^{d-1}$. From the condition $b^d-1mid a^d-1$ we get that $a$ is also the root of polynomial $x^d-1$. So easy to see that there exists only one $0leq d'leq d$, such that $a-b^{d'}equiv 0pmod{p^{nu_p(b^d-1)}}$. From this we get that for all $iequiv d'pmod{d}$, $a-b^iequiv 0pmod{p^{nu_p(b^d-1)}}$. Now from LTE lemma we get that $nu_p(b^{jd}-1)leqnu_p(b^d-1)+nu_p(j)$, for each $j$, so $nu_p(prod_{i=1}^n(b^i-1))leq[n/d]nu_p(b^d-1)+nu_p(n!)leqnu_p(n!(a-1)(a-b)ldots (a-b^{n-1}))$. Combining similar inequalities for every $p$ we get Lemma 1. $Box$



            $textbf{Proof of Problem 1.}$ Firstly it's simple exercise to prove that if a prime $p$ is such that $pmid a$, then $pmid b$. So there exists a positive integer $t$, such that $anmid b^{t-1}$, but $amid b^t$. From Lemma 1 we get that $(2t)!frac{(a-1)(a-b)ldots (a-b^{t-1})(a-b^t)ldots (a-b^{2t-1})}{(b-1)(b^2-1)ldots (b^t-1)(b^{t+1}-1)ldots (b^{2t}-1)}inmathbb{Z}$. But for every $i$ we have that $gcd(a, b^i-1)$, so if we just look on the numerator of the fraction above then we get that $$gcd(a,1)gcd(a, b)ldots gcd(a, b^{t-1})a^tmid (2t)!frac{(a-1)(a-b)ldots (a-b^{t-1})(a-b^t)ldots (a-b^{2t-1})}{(b-1)(b^2-1)ldots (b^t-1)(b^{t+1}-1)ldots (b^{2t}-1)}$$ and if $anot= b^x$ for every natural $x$, then $$|(2t)!frac{(a-1)(a-b)ldots (a-b^{t-1})(a-b^t)ldots (a-b^{2t-1})}{(b-1)(b^2-1)ldots (b^t-1)(b^{t+1}-1)ldots (b^{2t}-1)}|geq gcd(a,1)gcd(a, b)ldots gcd(a, b^{t-1})a^t$$ But it's easy to check that $|(2t)!frac{(a-1)(a-b)ldots (a-b^{t-1})(a-b^t)ldots (a-b^{2t-1})}{(b-1)(b^2-1)ldots (b^t-1)(b^{t+1}-1)ldots (b^{2t}-1)}|leq (2t)!a^t$ and $gcd(a,1)gcd(a, b)ldots gcd(a, b^{t-1})geq 2^{frac{t(t-1)}{2}}$ (here we used the fact that $gcd(a, b^i)midgcd(a, b^{i+1})$ and $gcd(a, b^{i-1})not=gcd(a, b^i)$ for $ileq t-1$). So $2^{frac{t(t-1)}{2}}a^tleq (2t)!a^t$. Contradiction. $Box$







            share|cite|improve this answer














            share|cite|improve this answer



            share|cite|improve this answer








            edited Nov 27 at 20:38

























            answered Nov 27 at 19:58









            solver6

            5917




            5917












            • Can someone find any mistakes in another proof : Let $p$ be a prime number greater than $a$. Consider a polynomial $F(x)=x^p-1$ over $mod{frac{b^p-1}{b-1}}$. One can get that it has $d$ consecutive roots $1, b,ldots , b^{p-1}$. So from the fact $b^p-1mid a^p-1$ we get that $a$ is also root of $F(x)equiv 0pmod{frac{b^p-1}{b-1}}$. Thus, $aequiv b^ipmod{frac{b^p-1}{b-1}}$ for some $ileq p-1$.
              – solver6
              Nov 27 at 21:19










            • Can someone find any mistakes in another proof : Let $p$ be a prime number greater than $a$. Consider a polynomial $F(x)=x^p-1$ over $mod{frac{b^p-1}{b-1}}$. One can get that $P(x)$ has $d$ consecutive roots $1, b,ldots , b^{p-1}$. So from the fact $b^p-1mid a^p-1$ we get that $a$ is also root of $F(x)equiv 0pmod{frac{b^p-1}{b-1}}$. Thus, $aequiv b^ipmod{frac{b^p-1}{b-1}}$ for some $ileq p-1$. Finally, if $anot= b^i$, then $b^{p-1}-1geq |a-b^i|geqfrac{b^p-1}{b-1}$. Contradiction. $Box$
              – solver6
              Nov 27 at 21:26




















            • Can someone find any mistakes in another proof : Let $p$ be a prime number greater than $a$. Consider a polynomial $F(x)=x^p-1$ over $mod{frac{b^p-1}{b-1}}$. One can get that it has $d$ consecutive roots $1, b,ldots , b^{p-1}$. So from the fact $b^p-1mid a^p-1$ we get that $a$ is also root of $F(x)equiv 0pmod{frac{b^p-1}{b-1}}$. Thus, $aequiv b^ipmod{frac{b^p-1}{b-1}}$ for some $ileq p-1$.
              – solver6
              Nov 27 at 21:19










            • Can someone find any mistakes in another proof : Let $p$ be a prime number greater than $a$. Consider a polynomial $F(x)=x^p-1$ over $mod{frac{b^p-1}{b-1}}$. One can get that $P(x)$ has $d$ consecutive roots $1, b,ldots , b^{p-1}$. So from the fact $b^p-1mid a^p-1$ we get that $a$ is also root of $F(x)equiv 0pmod{frac{b^p-1}{b-1}}$. Thus, $aequiv b^ipmod{frac{b^p-1}{b-1}}$ for some $ileq p-1$. Finally, if $anot= b^i$, then $b^{p-1}-1geq |a-b^i|geqfrac{b^p-1}{b-1}$. Contradiction. $Box$
              – solver6
              Nov 27 at 21:26


















            Can someone find any mistakes in another proof : Let $p$ be a prime number greater than $a$. Consider a polynomial $F(x)=x^p-1$ over $mod{frac{b^p-1}{b-1}}$. One can get that it has $d$ consecutive roots $1, b,ldots , b^{p-1}$. So from the fact $b^p-1mid a^p-1$ we get that $a$ is also root of $F(x)equiv 0pmod{frac{b^p-1}{b-1}}$. Thus, $aequiv b^ipmod{frac{b^p-1}{b-1}}$ for some $ileq p-1$.
            – solver6
            Nov 27 at 21:19




            Can someone find any mistakes in another proof : Let $p$ be a prime number greater than $a$. Consider a polynomial $F(x)=x^p-1$ over $mod{frac{b^p-1}{b-1}}$. One can get that it has $d$ consecutive roots $1, b,ldots , b^{p-1}$. So from the fact $b^p-1mid a^p-1$ we get that $a$ is also root of $F(x)equiv 0pmod{frac{b^p-1}{b-1}}$. Thus, $aequiv b^ipmod{frac{b^p-1}{b-1}}$ for some $ileq p-1$.
            – solver6
            Nov 27 at 21:19












            Can someone find any mistakes in another proof : Let $p$ be a prime number greater than $a$. Consider a polynomial $F(x)=x^p-1$ over $mod{frac{b^p-1}{b-1}}$. One can get that $P(x)$ has $d$ consecutive roots $1, b,ldots , b^{p-1}$. So from the fact $b^p-1mid a^p-1$ we get that $a$ is also root of $F(x)equiv 0pmod{frac{b^p-1}{b-1}}$. Thus, $aequiv b^ipmod{frac{b^p-1}{b-1}}$ for some $ileq p-1$. Finally, if $anot= b^i$, then $b^{p-1}-1geq |a-b^i|geqfrac{b^p-1}{b-1}$. Contradiction. $Box$
            – solver6
            Nov 27 at 21:26






            Can someone find any mistakes in another proof : Let $p$ be a prime number greater than $a$. Consider a polynomial $F(x)=x^p-1$ over $mod{frac{b^p-1}{b-1}}$. One can get that $P(x)$ has $d$ consecutive roots $1, b,ldots , b^{p-1}$. So from the fact $b^p-1mid a^p-1$ we get that $a$ is also root of $F(x)equiv 0pmod{frac{b^p-1}{b-1}}$. Thus, $aequiv b^ipmod{frac{b^p-1}{b-1}}$ for some $ileq p-1$. Finally, if $anot= b^i$, then $b^{p-1}-1geq |a-b^i|geqfrac{b^p-1}{b-1}$. Contradiction. $Box$
            – solver6
            Nov 27 at 21:26




















            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.





            Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


            Please pay close attention to the following guidance:


            • 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.


            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%2f1964788%2fif-a-geq-2-a-nmid-b-and-an-1-mid-bn-1-for-all-n-in-mathbbn-then%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

            Wiesbaden

            Marschland

            Dieringhausen