Difficult Number Theory question

In summary, the conversation discusses finding solutions for the equation (2^k) - 7 = X^2 for different values of q, with q being a prime and k being q-2. The solutions for q=5,7, and 17 are found, but no other solutions have been found when checking up to q=1000000. The conversation then moves on to discussing potential methods for proving whether there are more solutions or none for this equation. Suggestions include using Ramanujan-Nagell and Quadratic reciprocity theorems.
  • #1
kurtulmehtap
3
0
Let q be a prime, k= q-2 and X be an Integer,
I have found solutions for q=5,7,17 for the equation
(2^k) - 7 = X^2 .
I have checked q for up to 1000000 but was not able to find any other
solutions.
Please prove if there can be more solutions or none for this equation.
Thanks in advance...
 
Physics news on Phys.org
  • #2
kurtulmehtap said:
Let q be a prime, k= q-2 and X be an Integer,
I have found solutions for q=5,7,17 for the equation
(2^k) - 7 = X^2 .
I have checked q for up to 1000000 but was not able to find any other
solutions.
Please prove if there can be more solutions or none for this equation.
Thanks in advance...

We have X as being odd and k>3

(X^2 -1) = 2^k - 8

n*(n+1)/2 = 2^(k-3) - 1 (since 4n^2 + 4n +1 is an odd square)

I studied numbers 2*n which are 1 more than a triangular number. There are 2 infinite infinite recursive series for n, you only need to prove that there are no more n which are a power of 2.

An = {2,1,8,23, ... A(i) = 2*A(i-1) - A(i-2) + 8}
Bn = {2,11,28,53 ... B(i) = 2*B(i-1) - B(i-2) + 8}

Note that B(i) - A(i) = 10i Hope this helps
 
  • #3
ramsey2879 said:
We have X as being odd and k>3

(X^2 -1) = 2^k - 8

n*(n+1)/2 = 2^(k-3) - 1 (since 4n^2 + 4n +1 is an odd square)

I studied numbers 2*n which are 1 more than a triangular number. There are 2 infinite infinite recursive series for n, you only need to prove that there are no more n which are a power of 2.

An = {2,1,8,23, ... A(i) = 2*A(i-1) - A(i-2) + 8}
Bn = {2,11,28,53 ... B(i) = 2*B(i-1) - B(i-2) + 8}

Note that B(i) - A(i) = 10i Hope this helps
In other words n = 4R^2 - 5R + 2 for R= an integer and for 16n - 7 to be a square and if R = 0,1,2 then X^2 = 2^k - 7. I am not sure how to check for other values of R
 
  • #4
kurtulmehtap said:
Let q be a prime, k= q-2 and X be an Integer,
I have found solutions for q=5,7,17 for the equation
(2^k) - 7 = X^2 .
I have checked q for up to 1000000 but was not able to find any other
solutions.
Please prove if there can be more solutions or none for this equation.
Thanks in advance...

Hint: Ramanujan-Nagell
 
Last edited:
  • #5
I saw this question on a different forum, it is a very though question, as [tex]x^2+7=(x-\sqrt{-7})(x+\sqrt{-7})=2^n[/tex]
so I did some research and unique factorization holds for [tex]Q[\sqrt{-7}][/tex]
by Stark–Heegner theorem

but I'm not sure how to proceed from here, because I don't know much about albegraic number theory, and n is undetermined, making things more difficult
 
  • #6
we could try something here, considering [tex]x-\sqrt{-7}=\pm 1[/tex] and [tex]x+\sqrt{-7}=(a+b\sqrt{-7})^k=2^n[/tex] for a given "algebraic" k, though I'm not sure
 
  • #7
al-mahed said:
we could try something here, considering [tex]x-\sqrt{-7}=\pm 1[/tex] and [tex]x+\sqrt{-7}=(a+b\sqrt{-7})^k=2^n[/tex] for a given "algebraic" k, though I'm not sure


or, if 2 divide both, considering n is odd, n = 2x+1, [tex]x-\sqrt{-7}=2^1[/tex] and [tex]x+\sqrt{-7}=(a+b\sqrt{-7})^k=2^{2x}[/tex]
 
  • #8
Using BBCode sup and sub tags, I rewrite the equation as
2q-2 - 7 = x2
where x is an integer and q is an odd prime.

Looks like we can use Fermat's little theorem and Quadratic residue results to find constraints on possible solutions.

Multiply both sides by 4:
2q - 28 = (2x)2
Now find the result modulo q, with FLT:
y2 = -26 mod q

where y = 2x. If we know y, we can always find x mod q, since q is odd.

There's a special case: q = 13, and that yields y = 0 mod 13, and thus, x = 0 mod 13. However, that value of q is not a solution of the original equation.

To have a solution, -26 must be a quadratic residue of q. From QR theorems, all of -1, 2, and 13 must be QR's of q, or else only one of them may be.

The next step is to use Quadratic reciprocity.

-1 is a QR of q <-> q = 1 mod 4 (1 or 5 mod 8)
2 is a QR of q <-> q = +-1 mod 8 (1 or 7 mod 8)
13 is q QR of Q <-> q is a QR of 13 (q = 1 mod 4) / -q is a QR of 13 (q = -1 mod 4)

That last condition is:
q = 1, 3, 4, 9, 10, 12 mod 13
in both cases.

Going over the possibilities:

ttt: q = 1 mod 8 and 1, 3, 4, 9, 10, 12 mod 13
fft: q = 3 mod 8 and 1, 3, 4, 9, 10, 12 mod 13
ftf: q = 7 mod 8 and 2, 5, 6, 7, 8, 11 mod 13
tff: q = 5 mod 8 and 2, 5, 6, 7, 8, 11 mod 13

I find q = 1, 3, 5, 7, 9, 13, 15, 17, 21, 25, 27, 31, 35, 37, 39, 43, 45, 47, 49, 51, 63, 71, 75, 81, 85, 93 mod 104

kurtulmehtap's solutions, 5, 7, 17, are in this list.
 
  • #9
lpetrich said:
I find q = 1, 3, 5, 7, 9, 13, 15, 17, 21, 25, 27, 31, 35, 37, 39, 43, 45, 47, 49, 51, 63, 71, 75, 81, 85, 93 mod 104

kurtulmehtap's solutions, 5, 7, 17, are in this list.

In a re-inventing the wheel sense, this is an interesting conversation (and I am learning from it...), but might one not simply look at Nagell's 1948 proof of Ramanujan's 1913 Conjecture?

We are talking here about how to prove a lemma, not about how to prove some open question in mathematics.

Don't get me wrong. I would love to know more about the proof of this "difficult number theory" question and I know there is more than one way to prove it, but I also know that the proof is already out there (actually, at least two proofs are out there...)RF
 
Last edited:
  • #10
Nagell's paper is likely behind a paywall, so I'm not likely to be able to get access to that proof.

I'll try again, but this time making k more general.

2k = x2 + 7

I've found

SpringerLink - Arkiv för Matematik, Volume 4, Numbers 2-3
Arkiv för Matematik
Volume 4, Numbers 2-3, 185-187, DOI: 10.1007/BF02592006
The Diophantine equation x2+7=2n
T. Nagell

SpringerLink - Abstract
Number-Theoretic Analysis
Lecture Notes in Mathematics, 1990, Volume 1452/1990, 206-207, DOI: 10.1007/BFb0096992
A note on the Ramanujan-Nagell equation
Gerhard Turnwald

and some other papers. I think that I may have enough to construct a proof. We can turn the equation into
[itex] \frac{x^2 + 7}{4} = 2^n [/itex]
(n = k - 2) and by the unique factorization property of Z((1+sqrt(-7))/2), we find (Nagell, Turnwald)

[itex] \frac{x+\sqrt{-7}}{2} = \left( \frac{1\pm\sqrt{-7}}{2} \right)^n [/itex]

for some sign in the ()'s, and likewise for the sign of sqrt(-7) reversed. In general, however,
[itex] \frac{x_n+u_n\sqrt{-7}}{2} = \left( \frac{1+\sqrt{-7}}{2} \right)^n [/itex]
for rational numbers xn and un.

This will yield the desired solutions only if un = +- 1.

Turnwald found a recurrence relation for the u's:
un = un-1 - 2un-2

where u0 = 0 and u1 = 1

He took the resulting series with respect to modulus 8:
0, 1, 1, 7, 5, 7, 5, 7, 5, ...
It's easy to verify that the 7, 5 repeats itself modulo 8. This means that the only even solutions are some subset n = 0, 2, or k = 2, 4. Since k = 2 gives an imaginary x, the only even k is
k = 4, with x = 3.

Turnwald also finds that un = n*4n-1 modulo 7, which I have also verified.

I've been unable to follow the rest of his proof, at least for now, so I'll leave off here.
 
  • #11
Hi Ipetrich,

Interesting post and fair enough regarding access to Nagell's proof. So, here's a thought for you: If you're going to put in the effort reinventing the wheel, then think about at least adding one spoke to it.

The proof you are seeking amounts to a special case of the following for b = n (mod 2):

z^2 = 2^(x + 2 - 2*b) - 7

&

y = (2^x - 8)/(2*(2 + b)) = 2^(1-b)*((n^2 - n)*(n-2)^b)/(2 + b)!

which can be restated:

y = (2^x - 8)/4 = (n^2 - n) (Pronic Number)
OR
y = (2^x - 8)/6 = ((n^2 - n)*(n-2))/3! (Tetrahedral Number)

The only x solutions to this up to at least 1.41*10^1505 (as per CRGReathouse's computer check...) are: 1,2,3,5,7,13
Related Thread: A Tetrahedral Counterpart to Ramanujan-Nagell Triangular Numbers? https://www.physicsforums.com/showthread.php?t=443958

Note: 1 + 4 = 5, 3 + 4 = 7, 13 + 4 = 17; and 7 + 4 = 11 = p_(2+1), p_(3+1), p_(6+1); and p_(4+1)

For the special case of b = 0, you get, for the n solutions, the indices associated with Ramanujan-Nagell squares and triangles [--> 2*T_(n-1) = (n^2 - n)]. But for b = 1, you get indices associated with Tetrahedrals [--> Tetra_(n - 2) = ((n^2 - n)*(n-2))/3!].

1,2,3,5,7,13 are the unique factors of the Leech Lattice, and via the prime counting function, you get 0, 1, 2, 3, 4, 6 which, by the Crystal Restriction Theorem, are the only N (N > 0) such that 2*cos ((2*pi)/(|n|!/|n-1|!)) are in N (this framing of the formula works also for 0, but the standard formula is 2*cos ((2*pi)/n)).

0,1,2 3,4, & 6 are also the only N for which if we define p'_n as an Integer such that for 0 < d(n) < 3, starting from p'_0 = 1, then d(p'_n - 1) = n, as well as being the only Integers such that Euler-Totient (n) = 0, 1 or 2.

Also, for x > 1 = 2, 3, 5, 7 & 13, you have the complete set of prime numbers (all Mersenne Primes Exponents) that Frampton and Kephart associated with anomaly cancellations in 26 dimensional string theory. (I call these "Frampton-Kephart" Primes)

So, maybe think about extending the construction of your proof to prove the more general case presented above? It would be an original contribution to number theory that might have some legs.RF

P.S. As per Richard Guy, the n for the special case of b = 0 --> { 1,2,3,6,91 } are also the unique solutions to the following: 2x^2(x^2-1) = 3(y^2-1) (I call these "Why the Coincidence?" Numbers since Guy asked this question.). See the entry for 91 on the website of Robert Munafo's "Notable Properties of Specific Numbers" (http://mrob.com/pub/math/numbers-9.html). My guess is that there is a Tetrahedral Counterpart to this also.
 
Last edited:
  • #12
lpetrich said:
Nagell's paper is likely behind a paywall,at least for now, so I'll leave off here.

Could You please generalize... :D
 
  • #13
Another road to Ramanujan Nagell.

Another road to Ramanujan-Nagell

Pell’s equation (PE), xx-dyy=1, has the highest solutions for x and y among d<100 for d=61. Looking at various ways to incorporate d=61 in a group of other values of d includes the approaches d=nn-3, and d=n(n+1)(n+2)+1. An observation is that x for primes d=n(n+1)(n+2) is usually much lower than for d=n(n+1)(n+2)+1. (Prof John Robertson has told me – without demonstration - in an email that counter-examples exist. I assume they are very high, certainly higher than d= 1560781 = 115*116*117+1. In this region the x solutions for d=n(n+1)(n+2)+1are often in excess of 1E+300, and very much lower for d=n(n+1)(n+2).

A third approach, presented here (and perhaps already known to you), is made by looking at the equation for d=2^n-3, hence the - not quite perfect – connection to the Mersenne numbers, including d= 5, 13, 29, 61, 125, 253..

The sometime large solutions can be generated by solving the companion equation with lower solutions
ss-dtt=-1 (eq. 1)

xx-dyy=1 for [x,y] =[2ss+1, 2st]
(Another equation with even lower solutions is uu-dvv=-4 eq. 2)

xx-dyy=1 for [x,y] =[ (u2 + 3)u/2, (u2 + 1)v/2] (u,v,odd)
Looking at solutions for equation 1, I noted that for some n, t in equation 1 was simply equal to the previous d in the sequence d=2^n-3 i.e. the Mersenne numbers minus 2, i.e. we have for

n_______d=2^n-3___d=2^(n-1)-3_________Pell's equation

___________________/_______________________/ (the re-ocurring numbers (1,1)-(5,5)-(13,13)...
3_________5_______1_________________2^2-5*1^2=-1
4_________13_____ 5_______________18^2-13*5^2 =-1
5_________29_____13______________70^2-29*13^2=-1
6_________61_____29_______________no solution
7________125_____61___________682^2-125^*61^2=-1
15_____32765_ _16381___2965142^2-32765*16381^2=-1

The reader can appreciate my disappointment that 61 came up only in the solution for n=7 with n=6 without solution.

The general formulation of the equations is ss-dtt = ss - (2^n-3)*(2^(n-1)-3)^2=-1 requiring that ss= (2^n-3)*(2^(n-1)-3)^2-1 = 0, and therefore that
(2^n-3)*(2^(n-1)-3)^2-1 must be a square of a natural number.

After some rearrangement (and credit to Wolfram Alpha) we have
(2^n-3)*(2^(n-1)-3)^2-1 = 1/4 (-7+2^n) (-4+2^n)^2, i.e. it is required that
2^n-7 is a perfect square, 2^n-7=x^2. This is the Ramanujan-Nagell equation, conjectured by Ramanujan (that solutions exist for 3, 4, 5, 7 and 15 only), proposed independently in 1943 by Wilhelm Ljunggren, and proved in 1948 by Trygve Nagell, (Wikipedia, the Ramanujan-Nagell equation).

There is no hope for including 61 in the sequence but I found an interesting relation.
PS.
It is interesting how the online help (also including OEIS) can improve results from hobby activities in number theory by amateurs (such as myself).
 
Last edited:

1. What is number theory?

Number theory is a branch of mathematics that studies the properties and relationships of whole numbers, including prime numbers, divisibility, and the distribution of prime numbers.

2. What makes a number theory question difficult?

A difficult number theory question typically involves complex mathematical concepts and requires advanced problem-solving skills. It may also require knowledge from other branches of mathematics, such as algebra or calculus.

3. How can I approach a difficult number theory question?

The best approach to solving a difficult number theory question is to break it down into smaller, more manageable steps. It also helps to have a strong understanding of basic number theory principles and techniques.

4. Are there any strategies for solving difficult number theory questions?

Yes, there are several strategies that can be helpful when tackling difficult number theory questions. These include using patterns and relationships between numbers, trying out different approaches and techniques, and seeking assistance from other mathematicians or resources.

5. Can number theory be applied to real-world problems?

Yes, number theory has various applications in real-world problems, such as cryptography, coding theory, and data encryption. It also has practical applications in fields like computer science, physics, and engineering.

Similar threads

  • Linear and Abstract Algebra
Replies
2
Views
676
  • Linear and Abstract Algebra
Replies
8
Views
842
  • Linear and Abstract Algebra
Replies
1
Views
719
  • Linear and Abstract Algebra
Replies
10
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
13
Views
2K
  • Linear and Abstract Algebra
Replies
1
Views
706
  • Engineering and Comp Sci Homework Help
Replies
32
Views
3K
  • Calculus and Beyond Homework Help
Replies
3
Views
482
  • Linear and Abstract Algebra
Replies
4
Views
1K
  • Linear and Abstract Algebra
Replies
11
Views
1K
Back
Top