Results 1 to 2 of 2

Thread: Divisiblility

  1. #1
    Newbie
    Joined
    Apr 2009
    Posts
    11

    Divisiblility

    Find all$\displaystyle (a,b)$,
    where a is a prime number, $\displaystyle 2a \geq b$

    such that

    $\displaystyle (a-1)^b+1 \equiv 0 \bmod b^{a-1}$
    Last edited by LegendWayne; Apr 16th 2009 at 05:53 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    First consider $\displaystyle
    a > 2
    $

    In this case we have: $\displaystyle
    \left( {a - 1} \right)^b + 1
    $ odd, thus $\displaystyle b$ is odd.

    The case $\displaystyle b=1$ is trivial, so consider $\displaystyle b>1$

    Let $\displaystyle
    p = \min \left\{ {x \in \mathbb{Z}^ + /x \ne 1 \wedge \left. x \right|b} \right\}
    $ this turns out to be the smallest prime dividing $\displaystyle b$

    Now: $\displaystyle
    \left( {a - 1} \right)^b + 1 \equiv 0\left( {\bmod .b^{a - 1} } \right) \Rightarrow \left( {a - 1} \right)^b \equiv - 1\left( {\bmod .p} \right){\text{ (*)}}
    $$\displaystyle \Rightarrow \left( {a - 1} \right)^{2b} \equiv 1\left( {\bmod .p} \right){\text{ (**)}}$

    Let $\displaystyle
    t = {\text{ord}}_{\text{p}} \left( {a - 1} \right) \Rightarrow \left. t \right|\left( {2b} \right)
    $ because of $\displaystyle
    {\text{(**)}}
    $ and we also have $\displaystyle
    \left. t \right|\left( {p - 1} \right)
    $ (by Fermat's Little Theorem)

    Thus $\displaystyle
    \left. t \right|{\text{gcd}}\left( {2b,p - 1} \right)
    $ and note that: $\displaystyle
    {\text{gcd}}\left( {2b,p - 1} \right) = 2 \Rightarrow \left. t \right|2 \Rightarrow \left( {a - 1} \right)^2 \equiv 1\left( {\bmod .p} \right)
    $ that is $\displaystyle
    p\left| {\left[ {\left( {a - 1} \right)^2 - 1} \right]} \right.
    $ and using Euclid's Lemma we get: $\displaystyle
    \left. p \right|a{\text{ OR}}\left. {{\text{ }}p} \right|\left( {a - 2} \right)
    $

    If we had: $\displaystyle
    \left. {{\text{ }}p} \right|\left( {a - 2} \right) \Rightarrow \left( {a - 1} \right)^b \equiv \left( 1 \right)^b \equiv 1\left( {\bmod .p} \right)
    $, contradicting $\displaystyle \text{(*)}$ $\displaystyle
    \Rightarrow \left. p \right|a \Rightarrow p = a \Rightarrow \boxed{\left. a \right|b}
    $

    Now since $\displaystyle 2a\geq{b}$ it follows that we have $\displaystyle
    b = 2a{\text{ or }}b = a
    $

    If $\displaystyle b=a$ then $\displaystyle
    a^{a - 1} \left| {\left[ {\left( {a - 1} \right)^a + 1} \right]} \right.
    $ and expand $\displaystyle
    \left( {a - 1} \right)^a + 1
    $ by using the Binomial Theorem: $\displaystyle
    \left( {a - 1} \right)^a + 1 = \binom{a}{1}\cdot a - \binom{a}{2}\cdot a^2 \pm ...
    $ and note that $\displaystyle a|\binom{a}{k}$ for all $\displaystyle 0<k<a$ thus $\displaystyle a^2\left| {\left[ {\left( {a - 1} \right)^a + 1} \right]} \right.$ but note that $\displaystyle
    \tfrac{{\left( {a - 1} \right)^a + 1}}
    {{a^2 }} \equiv 1\left( {\bmod .a} \right)
    $ thus $\displaystyle a-1\leq 2$ thus $\displaystyle a=3$ and we get the solution $\displaystyle (a,b)=
    {\left( {3,3} \right)}
    $


    If $\displaystyle b=2a$ we find that $\displaystyle a\not|
    \left[ {\left( {a - 1} \right)^{2a} + 1} \right]
    $ hence this generates no solutions.

    Now it only remains to check what happens when $\displaystyle a=2$, here we have $\displaystyle
    \left( {a - 1} \right)^b + 1 = 2
    $ and so $\displaystyle b=1$ or $\displaystyle b=2$.

    Thus the solutions are $\displaystyle
    \left( {a,1} \right)\forall a\in\mathbb{Z^{+}};\left( {2,2} \right);\left( {3,3} \right)
    $
    Last edited by PaulRS; Apr 19th 2009 at 05:14 AM. Reason: Forgot to consider b=1
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum