Skip to main content
Added some more code
Source Link
Peter Mueller
  • 22.5k
  • 1
  • 75
  • 107

Take $n=382315009082231724951830011$. Then $3^n-2$ is divisible by the primes $5, 19, 23, 47, 71, 97, 149, 167, 173, 263, 359, 383, 389, 461, 479, 503, 557$. Furthermore, $\varphi(3^n-2)<2/3\cdot(3^n-2)<2\cdot 3^{n-1}$.

The following Sage code verifies this examples. I believe that this is close to a minimal counterexample.

sage: n=382315009082231724951830011
sage: l=[5, 19, 23, 47, 71, 97, 149, 167, 173, 263, 359, 383, 389, 461, 479, 503, 557]
sage: set(3.powermod(n,p) for p in l)
set([2])
sage: prod(1-1/p for p in l).n()
0.666250824539016

As there are some speculations about how to find such an example, here is the (not really clever) Sage code which greedily collects the congruences for $n$ which do not contradict each other:


p,n,Q = 5,3,4
lp = [p]
s = 1-1/p
while True:
    p=p.next_prime()
    e=IntegerModRing(p)(3).multiplicative_order()
    l=[z for z in [1..e-1] if 3.powermod(z,p) == 2]
    if len(l) == 0:
        continue
    b=l[0]
    if (b-n) % e.gcd(Q) != 0:
        continue
    QQ=Q.lcm(e)
    n=CRT_list([n,b],[Q,e]) % QQ
    Q=QQ
    s*=(1-1/p)
    lp.append(p)
    print p,s.n()
    if 2/3>s:
        print n,lp
        break

Take $n=382315009082231724951830011$. Then $3^n-2$ is divisible by the primes $5, 19, 23, 47, 71, 97, 149, 167, 173, 263, 359, 383, 389, 461, 479, 503, 557$. Furthermore, $\varphi(3^n-2)<2/3\cdot(3^n-2)<2\cdot 3^{n-1}$.

The following Sage code verifies this examples. I believe that this is close to a minimal counterexample.

sage: n=382315009082231724951830011
sage: l=[5, 19, 23, 47, 71, 97, 149, 167, 173, 263, 359, 383, 389, 461, 479, 503, 557]
sage: set(3.powermod(n,p) for p in l)
set([2])
sage: prod(1-1/p for p in l).n()
0.666250824539016

Take $n=382315009082231724951830011$. Then $3^n-2$ is divisible by the primes $5, 19, 23, 47, 71, 97, 149, 167, 173, 263, 359, 383, 389, 461, 479, 503, 557$. Furthermore, $\varphi(3^n-2)<2/3\cdot(3^n-2)<2\cdot 3^{n-1}$.

The following Sage code verifies this examples. I believe that this is close to a minimal counterexample.

sage: n=382315009082231724951830011
sage: l=[5, 19, 23, 47, 71, 97, 149, 167, 173, 263, 359, 383, 389, 461, 479, 503, 557]
sage: set(3.powermod(n,p) for p in l)
set([2])
sage: prod(1-1/p for p in l).n()
0.666250824539016

As there are some speculations about how to find such an example, here is the (not really clever) Sage code which greedily collects the congruences for $n$ which do not contradict each other:


p,n,Q = 5,3,4
lp = [p]
s = 1-1/p
while True:
    p=p.next_prime()
    e=IntegerModRing(p)(3).multiplicative_order()
    l=[z for z in [1..e-1] if 3.powermod(z,p) == 2]
    if len(l) == 0:
        continue
    b=l[0]
    if (b-n) % e.gcd(Q) != 0:
        continue
    QQ=Q.lcm(e)
    n=CRT_list([n,b],[Q,e]) % QQ
    Q=QQ
    s*=(1-1/p)
    lp.append(p)
    print p,s.n()
    if 2/3>s:
        print n,lp
        break

Source Link
Peter Mueller
  • 22.5k
  • 1
  • 75
  • 107

Take $n=382315009082231724951830011$. Then $3^n-2$ is divisible by the primes $5, 19, 23, 47, 71, 97, 149, 167, 173, 263, 359, 383, 389, 461, 479, 503, 557$. Furthermore, $\varphi(3^n-2)<2/3\cdot(3^n-2)<2\cdot 3^{n-1}$.

The following Sage code verifies this examples. I believe that this is close to a minimal counterexample.

sage: n=382315009082231724951830011
sage: l=[5, 19, 23, 47, 71, 97, 149, 167, 173, 263, 359, 383, 389, 461, 479, 503, 557]
sage: set(3.powermod(n,p) for p in l)
set([2])
sage: prod(1-1/p for p in l).n()
0.666250824539016