Results 1 to 6 of 6

Thread: Divisibility

  1. #1
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6

    Divisibility

    Hi

    Prove that if $\displaystyle m=\alpha n$, where $\displaystyle m$ and $\displaystyle n$ are positive integers, and $\displaystyle \alpha$ is a positive odd integer, then $\displaystyle 2^n+1 \mid 2^m+1$

    Result due to Gauss or Euler... I can't remember... more likely to Gauss
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Jan 2009
    Posts
    715
    Isn't it $\displaystyle x+1 \mid x^{2n+1} + 1 $ ?

    If it is correct , then $\displaystyle (x^n)+1 \mid (x^n)^{\alpha} +1 ~$ ... since $\displaystyle \alpha ~ is ~ odd $


    $\displaystyle m=\alpha n $
    $\displaystyle x^m = x^{\alpha n} $
    $\displaystyle x^m + 1 = x^{\alpha n} + 1 $

    Therefore , $\displaystyle x^n + 1 \mid x^m + 1 $

    Finally , sub. x into 2

    $\displaystyle 2^n+1 \mid 2^m+1 $
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member TheAbstractionist's Avatar
    Joined
    Apr 2009
    Posts
    328
    Thanks
    1
    The fact that $\displaystyle \alpha$ is odd means that the expression $\displaystyle 2^{n(\alpha-1)}-2^{n(\alpha-2)}+2^{n(\alpha-3)}-\cdots$ will end in $\displaystyle +1.$ Hence

    $\displaystyle 2^m+1$

    $\displaystyle =\quad2^{\alpha n}+1$

    $\displaystyle =\quad(2^n+1)\left(2^{n(\alpha-1)}-2^{n(\alpha-2)}+2^{n(\alpha-3)}-\cdots+1\right)$

    $\displaystyle \implies\ 2^n+1\,\mid\,2^m+1$
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Jan 2009
    Posts
    715
    Is it true for all positive integers $\displaystyle \alpha $

    $\displaystyle 2^n - 1 \mid 2^m - 1$ ??

    Therefore ,

    If $\displaystyle n \mid m ~$ , then $\displaystyle 2^n -1 \mid 2^m - 1 $ .
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member TheAbstractionist's Avatar
    Joined
    Apr 2009
    Posts
    328
    Thanks
    1
    Quote Originally Posted by simplependulum View Post
    Is it true for all positive integers $\displaystyle \alpha $

    $\displaystyle 2^n - 1 \mid 2^m - 1$ ??

    Therefore ,

    If $\displaystyle n \mid m ~$ , then $\displaystyle 2^n -1 \mid 2^m - 1 $ .
    Yup, Iíd say thatís true.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Quote Originally Posted by simplependulum View Post
    Isn't it $\displaystyle x+1 \mid x^{2n+1} + 1 $ ?

    If it is correct , then $\displaystyle (x^n)+1 \mid (x^n)^{\alpha} +1 ~$ ... since $\displaystyle \alpha ~ is ~ odd $


    $\displaystyle m=\alpha n $
    $\displaystyle x^m = x^{\alpha n} $
    $\displaystyle x^m + 1 = x^{\alpha n} + 1 $

    Therefore , $\displaystyle x^n + 1 \mid x^m + 1 $

    Finally , sub. x into 2

    $\displaystyle 2^n+1 \mid 2^m+1 $
    I don't understand your reasoning

    $\displaystyle =\quad(2^n+1)\left(2^{n(\alpha-1)}-2^{n(\alpha-2)}+2^{n(\alpha-3)}-\cdots+1\right)$
    Yup, that's the key step


    Here is how I did :

    $\displaystyle \begin{aligned}2^m+1 &=2^{\alpha n}+1 \\
    &=(2^n)^\alpha+1 \\
    &=(2^n+1-1)^\alpha+1 \\
    &=1+\sum_{k=0}^\alpha {\alpha \choose k} \left\{(2^n+1)^k (-1)^{\alpha-k}\right\} \\
    &=1+(-1)^\alpha +(2^n+1) \sum_{k=1}^\alpha \left\{{\alpha \choose k} (2^n+1)^{k-1} (-1)^{\alpha-k}\right\} \end{aligned}$

    Because $\displaystyle \alpha$ is odd, we have $\displaystyle 2^m+1=(2^n+1) \sum_{k=1}^\alpha \left\{{\alpha \choose k} (2^n+1)^{k-1} (-1)^{\alpha-k}\right\}$

    And since the sum is an integer, we're done
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Divisibility 11
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Dec 20th 2008, 02:41 AM
  2. Divisibility (gcd) 10
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Dec 19th 2008, 04:44 PM
  3. Divisibility (gcd) 9
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Dec 19th 2008, 01:12 PM
  4. Divisibility (gcd) 8
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Dec 19th 2008, 03:53 AM
  5. Divisibility
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Dec 14th 2008, 09:24 AM

Search Tags


/mathhelpforum @mathhelpforum