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

nkpstn

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?

jreelawg

An even integer is defined by 2n for some integer n, and an odd integer is defined as 2m+1 for some integer m.

2^k+1
=2*(2*2*...*2)+1
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
=16AB-2A
=2(8AB-A)
(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
=2r*(4s-1)
=2*(4rs-r)

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.

nkpstn

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.

DonAntonio

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]


DonAntonio

nkpstn

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
g=8t-x
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)
...

haruspex

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.

nkpstn

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.