## Inequality with Euler’s totient function

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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

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

-
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 at 14:09
I can't see the connection to mathoverflow.net/questions/120514? – Werner Aumayr Feb 7 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 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 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 at 16:09
show 7 more comments

## 1 Answer

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

```
-
Perfect! Thank you so much! – Werner Aumayr Feb 7 at 18:08

4
@Werner: If you like the answer, you might consider accepting it. – Peter Mueller Feb 7 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 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 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 at 22:40
show 2 more comments
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 17, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9477497935295105, "perplexity_flag": "middle"}