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

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

  • $\begingroup$ 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 . $\endgroup$ – Emil Jeřábek Feb 7 '13 at 14:09
  • $\begingroup$ I can't see the connection to mathoverflow.net/questions/120514? $\endgroup$ – Werner Aumayr Feb 7 '13 at 14:18
  • 2
    $\begingroup$ 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. $\endgroup$ – user9072 Feb 7 '13 at 15:07
  • $\begingroup$ 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 $\endgroup$ – Gerhard Paseman Feb 7 '13 at 15:59
  • 2
    $\begingroup$ @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? $\endgroup$ – user9072 Feb 7 '13 at 16:09

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

| cite | improve this answer | |
  • $\begingroup$ 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 $\endgroup$ – Gerhard Paseman Feb 7 '13 at 20:51
  • $\begingroup$ 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'. $\endgroup$ – user9072 Feb 7 '13 at 21:38
  • 2
    $\begingroup$ @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$. $\endgroup$ – Peter Mueller Feb 7 '13 at 22:40
  • $\begingroup$ 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 $\endgroup$ – Gerhard Paseman Feb 7 '13 at 23:01
  • $\begingroup$ @Peter Mueller: thank you for this additional information. I'd guessed the situations are more similar. $\endgroup$ – user9072 Feb 7 '13 at 23:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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