 mersenneforum.org > Math Factors of Euler Totient Function of sum/difference of prime powers
 Register FAQ Search Today's Posts Mark Forums Read 2020-07-18, 19:17 #1 mickfrancis   Apr 2014 Marlow, UK 23·7 Posts Factors of Euler Totient Function of sum/difference of prime powers It appears that for prime p and q, p>= q, is divisible by (often a high power of) n. The power of n seems to increase with the number of distinct prime factors of n. Is this true in general?   2020-07-18, 20:28 #2 R. Gerbicz   "Robert Gerbicz" Oct 2005 Hungary 7·199 Posts See https://en.wikipedia.org/wiki/Zsigmondy%27s_theorem and you don't need that p,q are primes, check me, but with few exception this should be working, since there is a prime r for that r | a^n-b^n but doesn't divide for smaller exponent, hence ord(a/b)=n|r-1=eulerphi(r)|eulerphi(a^n-b^n), what was needed. (as I said in general there is a few exception).   2020-07-20, 08:04   #3
mickfrancis

Apr 2014
Marlow, UK

1110002 Posts Quote:
 Originally Posted by R. Gerbicz See https://en.wikipedia.org/wiki/Zsigmondy%27s_theorem and you don't need that p,q are primes, check me, but with few exception this should be working, since there is a prime r for that r | a^n-b^n but doesn't divide for smaller exponent, hence ord(a/b)=n|r-1=eulerphi(r)|eulerphi(a^n-b^n), what was needed. (as I said in general there is a few exception).
Thanks for the reply, Robert. I don't think this is quite what I'm saying, though I may just be misunderstanding - forgive me if so.

What I have noticed is that is divisible specifically by a power of n greater than 0, and that this power is higher for more composite n. Does this make sense?

For example, is divisible by and is divisible by   2020-07-20, 13:02 #4 Dr Sardonicus   Feb 2017 Nowhere 345910 Posts The algebraic (cyclotomic) factorization of can yield factors of n in addition to those which divide p-1 where p divides the "primitive part." Looking at the "minus" case, suppose that n = d1d2. Consider the cyclotomic factors and . The "typical" prime factors q1 and q2 respectively, will satisfy thus contributing a factor of n to the totient. So the more prime factors corresponding to complementary divisors of n you can "pair up," the more factors of n will automatically be in the totient. Last fiddled with by Dr Sardonicus on 2020-07-20 at 13:04 Reason: xingif ostpy   2020-07-20, 15:55   #5
mickfrancis

Apr 2014
Marlow, UK

3816 Posts Quote:
 Originally Posted by Dr Sardonicus The algebraic (cyclotomic) factorization of can yield factors of n in addition to those which divide p-1 where p divides the "primitive part." Looking at the "minus" case, suppose that n = d1d2. Consider the cyclotomic factors and . The "typical" prime factors q1 and q2 respectively, will satisfy thus contributing a factor of n to the totient. So the more prime factors corresponding to complementary divisors of n you can "pair up," the more factors of n will automatically be in the totient.
Thanks for this. I shall cogitate upon it!  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post bhelmes Computer Science & Computational Number Theory 2 2019-08-24 15:00 carpetpool Miscellaneous Math 5 2017-03-09 05:45 Nick Number Theory Discussion Group 17 2016-12-01 14:27 toilet Math 1 2007-04-29 13:49 TalX Math 3 2007-04-27 11:50

All times are UTC. The time now is 12:03.

Sun Sep 20 12:03:52 UTC 2020 up 10 days, 9:14, 0 users, load averages: 1.51, 1.74, 1.64