Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Numerical analysis of the first several hundred n suggests the following inequality:

$\varphi(3^n-2) \ge 2\cdot3^{n-1}$

share|improve this question
    
Up to a small additive factor, your inequality says that if $p_1,\dots,p_k$ are distinct primes dividing a number of the form $3^n-2$, then $(1-p_1^{-1})\cdots(1-p_k^{-1})\ge2/3$. I suspect this is an instance of mathoverflow.net/questions/120514 . –  Emil Jeřábek Feb 7 '13 at 14:09
    
I can't see the connection to mathoverflow.net/questions/120514? –  Werner Aumayr Feb 7 '13 at 14:18
2  
The connection is only vague, just that some things are just naturally expected to be somewhat rare, a couple of hundreds is not much to test. In particular, you need an n such that 3^n - 2 is divisible by primes such that Emil J.'s product is less than 2/3. The only reason this is an issue at all is that you cannot have 2 and 3 for obvious reasons, neiter 11 nor 13, and also not 5 and 7 at the same time. So things get a bit large. Calculations got slightly too complex for me for just doing them so, but with Emil J. idea and some calculation with congruences one should find a counter ex. –  quid Feb 7 '13 at 15:07
    
It seems not to hold for n=1. Also, if you find a counterexample, both Emil's k and your n will be substantially larger than a thousand. Gerhard "Ask Me About System Design" Paseman, 2013.02.07 –  Gerhard Paseman Feb 7 '13 at 15:59
2  
@Gerhard Paseman: now while I might have been a bit too optimistic regarding how easy or not it is to find a counterexample but that one would need substantially more than a thousand different primes (the k) seems unlikely to me. Did you really mean this? –  quid Feb 7 '13 at 16:09

1 Answer 1

up vote 11 down vote accepted

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

share|improve this answer
    
Perfect! Thank you so much! –  Werner Aumayr Feb 7 '13 at 18:08
4  
@Werner: If you like the answer, you might consider accepting it. –  Peter Mueller Feb 7 '13 at 19:07
    
I would like the answer more if I had a good lower bound on k, the number of distinct prime factors of the counterexample. Can you at least trial divide by candidates up to 3^20 or even perhaps 3^50 to get an idea? Gerhard "Would Be Ever So Grateful" Paseman, 2013.02.07 –  Gerhard Paseman Feb 7 '13 at 20:51
    
Thanks for this answer! After I initially saw the question I got quite curious what would be the outcome. Did you also try what happens if you start with 7 insted of 5? I would be quite curious how it compares. ps for Gerhard Paseman: regarding the k again, it occurs to me we were also talking about somewhat different things (which is my fault) but to me the k here is seventeen, if I counted right in any case the number of primes one had to take into account. But sure the 'rest' seems huge so there might be quite a few additional factors 'hiding'. –  quid Feb 7 '13 at 21:38
2  
@Gerhard: I believe there is no way to factor $3^n-2$, this number has more that $10^{26}$ decimal digits! @quid: Indeed, if one starts with $7$, things look quite differently. Up to $p<70000$, this greedy approach yields $425$ compatible primes, starting with $7, 17, 23, 47, 71, 167,\ldots$, yet the product of the $1-1/p$ for these primes is still bigger than $0.692$. –  Peter Mueller Feb 7 '13 at 22:40

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.