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$
2
  • $\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, 2015 at 15:42
  • $\begingroup$ That is correct $\endgroup$
    – Kurtul
    May 27, 2015 at 15:45

1 Answer 1

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$
2
  • $\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, 2015 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, 2015 at 13:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .