Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

2^k+1 never divisible by u(8x-1) in integers

  1. May 12, 2012 #1
    It seems that there exists no integer k such that 2^k+1 is divisible by a positive integer n, if and only if n is of the form u(8x-1) (where u and x are also both positive integers).

    How could this be proved/disproved?
  2. jcsd
  3. May 13, 2012 #2
    An even integer is defined by 2n for some integer n, and an odd integer is defined as 2m+1 for some integer m.

    where (2*2*...*2) is an integer by closure properties
    therefore 2^k+1 is odd by definition of odd

    u(8x-1) u,x arbitrary positive integers
    =2A(8*(2B)-1) A,B arbitrary integers
    (8AB-A) is an integer by closure properties

    Suppose that 2(8AB-A) divides 2^k+1.

    Then 2^k+1=2(8AB-A)*P for some integer P
    =2*(ABP-AP) => even
    Which is a contradiction, an odd cannot equal an even.

    But, the claim is that an there does not exist an integer n if and only if n=u(8x-1) ...

    Counter example, let n=c(2d-1) c, and d positive integers
    =2r*(2*(2s)-1) r,s arbitrary integers

    If 2*(4rs-r) divides 2^k+1,
    then 2^k+1=2*(4rs-r)*t for some integer t
    =2*(4rst-rt) => even

    even cannot equal an odd

    So there is at least one integer other than u(8x-1) such that it does not divide 2^k+1 for any k
    So the original assumption is false

    I don't know for sure if this what your looking for or completely sure it's correct. I'm new to number theory.
  4. May 13, 2012 #3
    your argument simply put is that 2^k+1 wouldn't be divisible by any even number, indeed this is correct. I forgot to specify that n here must also be odd.
  5. May 13, 2012 #4

    Why have you decided that both u, x are even numbers? This is not given in the OP and, of course, then these are not "arbitrary integeres".

    This is incorrect: [itex]\,\,2A\left(8(2B)-1\right)=32AB-2A[/itex]

  6. May 13, 2012 #5
    I'm pretty sure the if part of this conjecture involves proving that 8gx - g - x cannot be a power of two.
    2^k+1/u(8x-1) = m; in integers
    Then 2^k = um(8x-1) - 1
    for this to possibly be true (um) must be of form 8g-1 because subtracting a number that isn't divisible by 8 from a number that is divisible by 8 won't yield a result divisible by 8 and you need one divisible by 8 because it has to be a power of two and it isn't 2 or 4 because um(8x-1) cannot be 3 or 5 as x is an integer (the smallest possible value of um(8x-1) is 7).
    (8g-1)(8x-1) - 1 = 2^k and k is greater than or equal to 3
    (64gx -8g - 8x +1) - 1 = 2^k
    8gx - g - x = 2^(k-3)
    ...this is where i'm at.

    Additional logic:
    the smallest possible value of 8gx - g - x is 6
    therefore analogously the whole thing must be divisible by eight and for that to be true
    g+x must also be divisible by eight
    so g+x can be expressed as 8t
    8x(8t-x) - 8t = 2^(k-3)
    64tx - 8x^2 - 8t = 2^(k-3)
    8tx - x^2 - t = 2^(k-6)
    8(g+x)x - x^2 - x - g = 2^(k-6)
    8g + 8x^2 - x^2 - x - g = 2^(k-6)
    7g + 7x^2 - x = 2^(k-6)
  7. May 14, 2012 #6


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Your wording strikes me as a little odd (the "and only if" bit), so to make sure we're on the same page I'll paraphrase it:
    If n is a factor of 2^k+1 then n is not congruent to 7 mod 8.

    I believe this is a special case of a much more general circumstance that appears to be true:
    If (x,y)=1 [i.e. x and y are coprime] then
    a) No factor of x[itex]^{2}[/itex]+y[itex]^{2}[/itex] is congruent to 3 or 7 mod 8
    b) No factor of 2x[itex]^{2}[/itex]+y[itex]^{2}[/itex] is congruent to 5 or 7 mod 8
    (Your conjecture follows from (a) for k even and (b) for k odd.)

    I'll sketch a proof of (a):
    x[itex]^{2}[/itex]+y[itex]^{2}[/itex] can be factorised as x+iy, x-iy.
    Since x and y coprime, neither of these complex factors has any real factors greater than 1.
    If n is a real factor of x[itex]^{2}[/itex]+y[itex]^{2}[/itex], it must be factorisable into complex factors of x+iy, x-iy.
    If these are a+ib, c+id respectively, ad + bc = 0.
    Since (x,y)=1, (a,b)=1 and (c,d)=1.
    So every real factor of a is also a real factor of c and vice versa.
    Hence a = +/-c, and b = +/-d.
    Thus, w.l.o.g., a = c, d = -b.
    So n = a[itex]^{2}[/itex]+b[itex]^{2}[/itex]. Since each square is individually 0, 1 or 4 modulo 8, the sum must be 0, 1, 2, 4 or 5 modulo 8.
  8. May 14, 2012 #7
    ah I see. Although I do believe referring to complex numbers is over complicating it.
    I've also found that the only if part of my conjecture is untrue with a counterexample of 73. (I checked all the way to 71 before the first post) I guess there is no more purpose for this thread. Though I still am wondering how to prove that 8gx - g - x can't be a power of 2... eh I'll probably figure it out on my own later.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook