Given positive integers $a,b\in\mathbb{N}$ with ${\text gcd}(a,b) = 1$, and given a positive integer $d$, are there necessarily positive integers $m,n$ such that $d \;| \; (2^ma + 2^nb)$?
$\begingroup$
$\endgroup$
3
asked Jan 16, 2019 at 15:49
-
$\begingroup$ You will need d coprime to a and b. Otherwise an odd prime p could divide d and a, and you are out of luck. If d is coprime to both a and b, a version of the Chinese remainder theorem might work. Gerhard "The Question Needs More Work" Paseman, 2019.01.16. $\endgroup$– Gerhard PasemanCommented Jan 16, 2019 at 16:36
-
$\begingroup$ Upon further reflection, an example like Seva's should work. If d is a prime like a Mersenne prime where 2 is far from being a primitive root, there should be coprime a and b such that the divisibility relation fails. I am guessing d=17, a=3 and b=11, but that doesn't work, and I don't see how to save it., d=127 should yield an example. Gerhard "It's About Powers Of Two" Paseman, 2019.01.16. $\endgroup$– Gerhard PasemanCommented Jan 16, 2019 at 16:45
-
$\begingroup$ Ah. d=31, a is 3 mod d and b is 5 mod d. We have 2^m times 3 run through 3,6,12,24,17 and for b we have 5,10,20,9,18. Gerhard "Likes The Power Of Small" Paseman, 2019.01.16. $\endgroup$– Gerhard PasemanCommented Jan 16, 2019 at 16:54
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
Not necessarily: consider the situation where $a=b=1$ and $d$ is a Mersenne prime.
-
4
$\begingroup$
$\endgroup$
I have written a (very unoptimized) SageMath code (which, up to some tweaks, should work in just Python) which brute-forces this (I have taken Gerhard's suggestion from the comments to only include $a,b$ relatively prime to $d$):
k = 0
l = 0
for d in range(1,20):
for a in range(1,d):
for b in range(1,a+1):
if gcd(a,b)==1 and gcd(a,d)==1 and gcd(b,d)==1:
l = l+1
flag = false
for m in range(d):
for n in range(d):
if (2^m*a+2^n*b)%d==0:
flag = true
break
if flag:
break
if not flag:
a,b,d
k = k+1
k,l
within a second the code returns few dozen counterexamples, the smallest of which is $(1,1,7)$ (already indicated in the other answer).
Overall, in the computed range, 61 our of 396 triples are counterexamples. Extending the search up to 100, we get 19889/46522, which means that there are almost as many counterexamples as examples.
