Timeline for Inequality with Euler's totient function
Current License: CC BY-SA 3.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 7, 2013 at 11:34 | vote | accept | Werner Aumayr | ||
| Feb 7, 2013 at 19:20 | comment | added | user9072 | @Emil Jeřábek: yes, I did not want to claim that one needs 3 is a primitive root. The "always" might not be the best choice of word to convey that I meant this as sufficient property not as characterization, but this was the intent of adding "always". Thanks for clarifiying this. | |
| Feb 7, 2013 at 19:10 | comment | added | Emil Jeřábek | Actually, you don’t need 3 to be a primitive root, only that the order of 2 mod $p$ divides the order of 3. (E.g., 3 is not a primitive root modulo 23, 47, 71, 97 in Peter Mueller’s solution.) Each such prime corresponds to a constraint on $n$ which is a congruence modulo the order of 3. By a version of the Chinese remainder theorem, a set of such constraints is solvable iff they are pairwise compatible in the sense that they induce the same congruence modulo their gcd. | |
| Feb 7, 2013 at 19:00 | comment | added | user9072 | Argh! The last mod p in the first comment should be p−1. If only it where p, the thing would be quite a bit simpler. ;) Further clarfification: my "has certain properties" is quite unspecific, what I mean is one should not test for the n and see if 3^n - 2 somehow factors, but construct the n such that the divisibilty is guaranteed. | |
| Feb 7, 2013 at 18:53 | comment | added | user9072 | cont. The number of primes for which 3 is a primitive root is/should be a nonsmall (about a third) constant fraction of all primes (Artin conj). So this is not too restrictive regarding the primes one can take. However, in addition (and realizing this made me stop my handcomputations) there is an issue now finding a common solution of the different congruence mod (p-1) for the various primes (excluding taking 5 and 7 together for example). So that in addition one can only take primes where the indices of $2$ base $3$ are somehow compatible. | |
| Feb 7, 2013 at 18:45 | comment | added | user9072 | In some sense the question is settled by Peter Mueller's answer but some general remarks follwoing up on Gerhard Paseman's comment and to explain how (I assume) the example was found: I consider it as misleading to think about this problem as finding some n such that 3^n - 2 has certain properties. It is relatively easy (if one does not go really large) to decide when for some given prime $p$ there is some $n$ such that $3^n-2$ is divisible by $p$ and also to find it (it works always if $3$ is primitive root mod $p$). Also one gets an entire coset mod $p$. cont. | |
| Feb 7, 2013 at 17:46 | answer | added | Peter Mueller | timeline score: 12 | |
| Feb 7, 2013 at 17:12 | comment | added | Gerhard Paseman | Excepting the cases n=1, 0, of course, I wager five cents that no counterexample will be found where k has only one decimal digit, seperately I wager 50 cents that if there is a counterexample such an n will have at least 10 decimal digits, and I will pay someone five dollars for a (clear demonstration of a) counterexample in which n has five or fewer decimal digits (but n has more than 1 decimal digit). It may be likely that k has three decimal digits, but my gut tells me k will be larger. Gerhard "Will Book Prime Number Races" Paseman, 2013.02.07 | |
| Feb 7, 2013 at 17:02 | comment | added | Gerhard Paseman | I will back off on the size of k, as I have not done the calculations, and it may be possible to find a few small simultaneous prime divisors of 3^n - 2 that will do the job. However, my experience with the product involving primes of (1 - 1/p) in perfect numbers and in bounding Jacobsthal's function have conditioned me to expect smallish examples to factor like primes whose numbers of digits grow at an exponential rate (so i^th prime has near 2^i decimal digits). (Continued) Gerhard "Ask Me About System Design" Paseman, 2013.02.07 | |
| Feb 7, 2013 at 16:09 | comment | added | user9072 | @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? | |
| Feb 7, 2013 at 15:59 | comment | added | Gerhard Paseman | 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 | |
| Feb 7, 2013 at 15:07 | comment | added | user9072 | 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. | |
| Feb 7, 2013 at 14:18 | comment | added | Werner Aumayr | I can't see the connection to mathoverflow.net/questions/120514? | |
| Feb 7, 2013 at 14:09 | comment | added | Emil Jeřábek | 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 . | |
| Feb 7, 2013 at 14:07 | history | edited | Werner Aumayr | CC BY-SA 3.0 |
added 2 characters in body
|
| Feb 7, 2013 at 13:13 | history | asked | Werner Aumayr | CC BY-SA 3.0 |