Results 1 to 2 of 2

Math Help - Divisiblility

  1. #1
    Newbie
    Joined
    Apr 2009
    Posts
    11

    Divisiblility

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

    such that

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

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    First consider <br />
a > 2<br />

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

    The case b=1 is trivial, so consider b>1

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

    Now: <br />
\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{ (*)}}<br />
\Rightarrow \left( {a - 1} \right)^{2b}  \equiv 1\left( {\bmod .p} \right){\text{  (**)}}

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

    Thus <br />
\left. t \right|{\text{gcd}}\left( {2b,p - 1} \right)<br />
and note that: <br />
{\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)<br />
that is <br />
p\left| {\left[ {\left( {a - 1} \right)^2  - 1} \right]} \right.<br />
and using Euclid's Lemma we get: <br />
\left. p \right|a{\text{ OR}}\left. {{\text{ }}p} \right|\left( {a - 2} \right)<br />

    If we had: <br />
\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)<br />
, contradicting \text{(*)} <br />
 \Rightarrow \left. p \right|a \Rightarrow p = a \Rightarrow \boxed{\left. a \right|b}<br />

    Now since 2a\geq{b} it follows that we have <br />
b = 2a{\text{ or }}b = a<br />

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


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

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

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

Search Tags


/mathhelpforum @mathhelpforum