MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

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

share|cite|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 . – Emil Jeřábek Feb 7 '13 at 14:09
I can't see the connection to – Werner Aumayr Feb 7 '13 at 14:18
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
@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
up vote 12 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)
sage: prod(1-1/p for p in l).n()

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:
    l=[z for z in [1..e-1] if 3.powermod(z,p) == 2]
    if len(l) == 0:
    if (b-n) % e.gcd(Q) != 0:
    n=CRT_list([n,b],[Q,e]) % QQ
    print p,s.n()
    if 2/3>s:
        print n,lp

share|cite|improve this answer
Perfect! Thank you so much! – Werner Aumayr Feb 7 '13 at 18:08
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
@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
Ah. We are, and I mistook Emil's k for omega(n). My mistake. Indeed Emil's k can be two digits. My k is omega(n), and for every such counterexample, my gut says my k has more than two digits. Peter, I was hoping you would compute it mod p for a few million choice primes p, but it is not as important now. Gerhard "Not Quite The Omega Man" Paseman, 2013.02.07 – Gerhard Paseman Feb 7 '13 at 23:01

Your Answer


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.