20200718, 19:17  #1 
Apr 2014
Marlow, UK
2^{3}·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?

20200718, 20:28  #2 
"Robert Gerbicz"
Oct 2005
Hungary
2561_{8} 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^nb^n but doesn't divide for smaller exponent, hence ord(a/b)=nr1=eulerphi(r)eulerphi(a^nb^n), what was needed. (as I said in general there is a few exception). 
20200720, 08:04  #3  
Apr 2014
Marlow, UK
38_{16} Posts 
Quote:
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 

20200720, 13:02  #4 
Feb 2017
Nowhere
3456_{10} Posts 
The algebraic (cyclotomic) factorization of can yield factors of n in addition to those which divide p1 where p divides the "primitive part."
Looking at the "minus" case, suppose that n = d_{1}d_{2}. Consider the cyclotomic factors and . The "typical" prime factors q_{1} and q_{2} 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 20200720 at 13:04 Reason: xingif ostpy 
20200720, 15:55  #5  
Apr 2014
Marlow, UK
56_{10} Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
euler phi function and quadratic irred. polynomials  bhelmes  Computer Science & Computational Number Theory  2  20190824 15:00 
Consecutive numbers not coprime to Euler's totient...  carpetpool  Miscellaneous Math  5  20170309 05:45 
Basic Number Theory 7: idempotents and Euler's function  Nick  Number Theory Discussion Group  17  20161201 14:27 
euler's totient function  toilet  Math  1  20070429 13:49 
application of euler's phi function  TalX  Math  3  20070427 11:50 