Given $a,b\in2\mathbb N_{\geq0}+1$ and $a<b$, is there a bound of the form $k=O(\log\log(ab))$ or $k=O(\log(ab))$ on the minimum $k\in\mathbb N$ satisfying $$\mathsf{GCD}\big({2q^ka+1},{2q^kb+1}\big)=1$$ where $q\in\mathbb N_{>1}$ is fixed?
$\begingroup$
$\endgroup$
13
-
2$\begingroup$ Have you been able to make any progress on this question? If so, it would be helpful to include this information in the question. $\endgroup$Dean Miller– Dean Miller2025-08-12 10:16:39 +00:00Commented Aug 12 at 10:16
-
1$\begingroup$ @DeanMiller Heuristics suggest probability of coprime is $\frac1{\zeta(2)}$ and so $k=O(1)$ should suffice for every $a,b\in2\mathbb N_{\geq0}+1$. $\endgroup$Turbo– Turbo2025-08-12 10:22:12 +00:00Commented Aug 12 at 10:22
-
1$\begingroup$ As it stands now, no. Say, $a=7,\,b=13,\,q=4$. Then the said GCD is always 3. $\endgroup$Ivan Neretin– Ivan Neretin2025-08-12 11:55:51 +00:00Commented Aug 12 at 11:55
-
$\begingroup$ @IvanNeretin Thanks didn't notice.. is $q=2^k$ only source of concern? $\endgroup$Turbo– Turbo2025-08-12 12:01:54 +00:00Commented Aug 12 at 12:01
-
$\begingroup$ $q=7$ will do just as well. $\endgroup$Ivan Neretin– Ivan Neretin2025-08-12 12:12:12 +00:00Commented Aug 12 at 12:12
|
Show 8 more comments