Results 1 to 6 of 6

Math Help - 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 m=\alpha n, where m and n are positive integers, and \alpha is a positive odd integer, then 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  x+1 \mid x^{2n+1} + 1 ?

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


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

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

    Finally , sub. x into 2

     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 \alpha is odd means that the expression 2^{n(\alpha-1)}-2^{n(\alpha-2)}+2^{n(\alpha-3)}-\cdots will end in +1. Hence

    2^m+1

    =\quad2^{\alpha n}+1

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

    \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  \alpha

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

    Therefore ,

    If  n \mid m ~ , then  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  \alpha

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

    Therefore ,

    If  n \mid m ~ , then  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  x+1 \mid x^{2n+1} + 1 ?

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


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

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

    Finally , sub. x into 2

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

    =\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 :

    \begin{aligned}2^m+1 &=2^{\alpha n}+1 \\<br />
&=(2^n)^\alpha+1 \\<br />
&=(2^n+1-1)^\alpha+1 \\<br />
&=1+\sum_{k=0}^\alpha {\alpha \choose k} \left\{(2^n+1)^k (-1)^{\alpha-k}\right\} \\<br />
&=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 \alpha is odd, we have 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: December 20th 2008, 03:41 AM
  2. Divisibility (gcd) 10
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 19th 2008, 05:44 PM
  3. Divisibility (gcd) 9
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 19th 2008, 02:12 PM
  4. Divisibility (gcd) 8
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: December 19th 2008, 04:53 AM
  5. Divisibility
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 14th 2008, 10:24 AM

Search Tags


/mathhelpforum @mathhelpforum