5
$\begingroup$

For

$(x2^9)^2=2^q-1+y^2q^2$,where $q$ is prime,

is it possible to show that there exists only an unique solution for the pair $\{x,y\}$?

$\endgroup$
  • $\begingroup$ I think the question is: given a prime $q$, show that there is at most one pair $(x,y)$ of positive integers such that $$2^{18}x^2=2^q-1+q^2y^2.$$ $\endgroup$ – Charles May 27 '15 at 15:42
  • $\begingroup$ That is correct $\endgroup$ – Kurtul May 27 '15 at 15:45
2
$\begingroup$

$\newcommand\Z{\mathbf{Z}}$

If $2^{q} - 1 \equiv 0 \mod p$, then $2$ has order $q$ in the group $\mathbf{F}^{\times}_p$. Since the latter group has order $p -1$, it follows that any prime divisor of $2^{q} - 1$ is $1 \mod q$. Moreover, $2$ will be a quadratic residue modulo $p$, so any factor will also be congruent to $\pm 1$ modulo $8$.

With this in mind, consider the following lemma.

Lemma: Consider $128$ ordered elements (not necessarily distinct) of the abelian group $\Z/128 \Z$. Then some non-trivial subset of these elements sums to zero.

Proof: Order the list as $s_1, \ldots, s_{128}$. Consider the elements: $$s_1, \ s_1 + s_2, \ s_1 + s_2 + s_3, \ \ldots $$ There are $128$ such sums. If they are all distinct, one must be the identity. If two are the same, their difference is also a non-trivial sum which is equal to zero.

You can't do better (a priori) than 128, because one might have $s_i = 1$ modulo $128$ for all $i$.

We deduce:

Corollary: For any $129$ primes $\equiv \pm 1 \mod 8$, a non-trivial proper subset of them has a product which is $\pm 1 \mod 2^{10}$.

Proof:: Apply the lemma above to any subset of size $128$ and to the group of elements $\pm p_i \equiv 1 \mod 8$. Note that the group $(1 + 8\Z)/(1 + 2^{10} \Z)$ is cyclic of order $128$.

Corollary: If $2^{q} - 1$ has at least $129$ prime divisors, then there are at least two solutions to

$$2^{q} - 1 = (2^9 x)^2 - y^2 q^2 = (2^9 x + y q)(2^9 x - y q).$$

Proof: We want to write $2^q - 1 = AB$, where $A$ and $B$ have the required form, that is, we can solve for integral $x$ and $y$ in the equations:

$$A = 2^9 x + y q,$$ $$B = 2^9 x - y q.$$

This amounts to asking that $A \equiv B \equiv 1 \mod q$, and that $A$ is $\equiv \pm 1 \mod 2^{10}$. The trivial solution is $A = 1$ and $B = 2^{q} - 1$; we want to construct another such solution. Since all the prime factors of $2^q - 1$ are $1 \mod q$, the first condition is automatic. For the second, if we are assuming that $2^q - 1$ has at least $129$ prime factors, then, by the Lemma, there is a proper divisor which is $\pm 1 \mod 2^{10}$. This gives the desired solution.

One certainly expects that the numbers $2^{q} - 1$ can have an arbitrarily large number of prime factors, so one expects --- by the obvious generalization of the lemma above --- that there can exist arbitrarily many solutions as $q$ varies. In addition, one can hope to find a small $q$ with many factors such that some product is $\pm 1 \mod 2^{10}$ --- the bound in the Lemma is sharp in the worst case scenario, but in practice one expects many fewer than $129$ primes should suffice. The problem is that $2^q - 1$ is hard to factor as $q$ gets large. Instead, one can search for $q$ for which $2^q - 1$ has a small factor, say less than 500,000. For such small factors, they have (roughly) a one in $256$ chance of being $\pm 1 \mod 1024$, given they are $\pm 1$ modulo $8$. Since computing the GCD of $2^q - 1$ and (say) 500,000! is relatively cheap, it is realistic to search over a range of various $q$. One finds that:

$$2^{3527} - 1 \equiv 0 \mod p = 63487,$$

and, with $q = 3527$, we have

$$p \equiv 1 \mod q, \quad p \equiv -1 \mod 1024.$$

Hence, if

$$A = p, \quad B = \frac{2^{q} - 1}{p}, \qquad x = \frac{B+A}{2^{10}}, \quad y = \frac{B-A}{2q},$$

then

$$(2^9 x)^2 = 2^{q} - 1 + q^2 y^2$$

is a second solution (beyond the trivial case when $A = 1$ and $B = 2^{q} - 1$). Explicitly, $x$ equals

$$\begin{aligned} & \ 83139985554814564201142265398423940983734084680519373351274507224446764599607 \\ & \ 49451696564934671744653119863727621498244035702529608058476405955664605629948\\ & \ 62838307137784283737806179254649900079974691279735262514980072403875850975080\\ & \ 61957046474191593038928867902487454538277902526798081847840485073702295261112\\ & \ 33113621488853227725892116562645102916296506631441882237602645539576240063083\\ & \ 16542844209980653631941354248232439226396413730532924481168362238086941828118\\ & \ 38308509653785749056465841156627127934624282576692681779074414679440900436490\\ & \ 51748113171730486696573215817843552171786257357981110777970815770070081216602\\ & \ 65313780022194173593463676305763851504432476029971231801801391928524170852121\\ & \ 01902453812880831869001524277687896922188634322634430157407549044529132580919\\ & \ 11569976254856032521966500715204341110750005850922868567006271584961070720322\\ & \ 41598144814720814044682551670392948705627868423019659857466668911286790507132\\ & \ 78061681936258561522605907127622832906278247368600982784494146323005476392476\\ & \ 84876567107301371945802093257368889076102458785927292, \end{aligned}$$

and $y$ equals $$\begin{aligned} & \ 12069087781135542067191618906717623414707074385150529956295023447382121767791\\ & \ 05108950564572314129079216719656518913269335491833047724961701119733563391702\\ & \ 21086819748949689048414166084031967349290343616451503943200963161549315480363\\ & \ 27678482504901076165560414053323951438502491095469412505271995564994492535778\\ & \ 14390182648792983440787287689275387778039073262063579162362504824571316958406\\ & \ 17541802164873857289354684824240149952910395188554822039795350571562379987523\\ & \ 84806905852775249083331587942215222427708430019638971667390445227069390706969\\ & \ 98722720142876668326806205415008760621478470021912766860879233817486782416473\\ & \ 08148754003788890524483527720031497581590424646256101696207063415765346038073\\ & \ 70619239113182587444550263802148058753660499226875199387749550640997707933493\\ & \ 22008457000988457230293974586386340416417352706456622825717950397363217524469\\ & \ 82619294058728964216296418047984459806430810499740874921185975186441405369904\\ & \ 16321968004356218741019059951614088587472203757506011677250071708925093255726\\ & \ 72145393353824298961227862701381590929108153926394871.\end{aligned}$$

There's also a second solution when $q = 6947$. In this case, $p= 180623$ and $p' = 333457$ are divisors of $2^q - 1$, and

$$A = p p' = 60230003711 \equiv -1 \mod 1024.$$

$\endgroup$
  • $\begingroup$ I have learned a lot from your answer, Forgive my ignorance for asking since you have proved that If $2^q−1$ has at least 129 prime divisors then there are at least two solutions. What if 2q−1 has at less than 129 prime divisors? $\endgroup$ – Kurtul May 29 '15 at 8:38
  • $\begingroup$ The number of solutions is the number of divisors of $2^q - 1$ which are $1$ modulo $2^{10}$. There's probably not much more that one can say in general. For example, $2^{3527} - 1$ presumably has fewer than $129$ prime factors, but it just so happens to have a small prime factor $p = 63487$ such that $(2^q - 1)/p$ is $1$ modulo $2^{10}$. $\endgroup$ – Epargyreus May 29 '15 at 13:03

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.