2
$\begingroup$

The numbers $n=811150370266636218705704$ and $n+1$ have highest factors 173 and 167, and they happen to be the largest consecutive 173-smooth numbers.

They were found via Størmer's theorem and the continued fraction method for solving the Pell equation. That means $n$ was generated from the numerator of a convergent fraction that solves $x^2 - 2 \sqrt{k} y^2 =1$.

Out of the $2^{40} = 1099511627776$ possibilities, what was $k$? Is there a way to go backwards other than brute force?

$\endgroup$
1
$\begingroup$

Lehmer's procedure involves solving the Pell equation $$x^2-2qy^2=1$$ for $173$-smooth squarefree $q\neq2$. (This makes $\frac{x}{y}$ an approximation for $\sqrt{2q}$.) Then, for a finite number of smallest solutions $(x,y)$ of each Pell equation, the integers $n=\frac{x-1}{2}$ and $n+1$ are tested for smoothness.

Therefore, the $x$ involved is $x=2n+1$, and the $q$ involved is exactly the squarefree part of $qy^2 = \frac{x^2-1}{2} = 2n(n+1)$, that is, the factor of $2n(n+1)$ with largest square cofactor. That cofactor is $y^2$. Plugging in, we get $$\begin{align} qy^2 = 2n(n+1) &= 2^4\cdot3^3\cdot5\cdot7^2\cdot13\cdot19\cdot23^2\cdot43\cdot47^2 \cdot59\cdot61\cdot71\cdot83\cdot89 \\&\qquad\cdot103\cdot107\cdot109\cdot139\cdot151^2\cdot167^3\cdot173^2 \\\therefore\quad q &= 3\cdot5\cdot13\cdot19\cdot43\cdot59\cdot61\cdot71\cdot83\cdot89 \cdot103\cdot107\cdot109\cdot139\cdot167 \end{align}$$ I hope this answers your question.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Very nice. That really works out beautifully. $\endgroup$ – Ed Pegg Apr 26 '16 at 16:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.