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, $\phi\left(p^{n} \pm q^{n}\right)$ 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 $\phi\left(p^{n} \pm q^{n}\right)$ 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, $\phi\left(2^{210} + 1\right)$ is divisible by $210^{9}$ and $\phi\left(2^{210} - 1\right)$ is divisible by $210^{15}$

 2020-07-20, 13:02 #4 Dr Sardonicus     Feb 2017 Nowhere 345910 Posts The algebraic (cyclotomic) factorization of $a^{n}\;\pm\;b^{n}$ 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 $b^{d_{1}}\Phi_{d_{1}}(a/b)$ and $b^{d_{2}}\Phi_{d_{2}}(a/b)$. The "typical" prime factors q1 and q2 respectively, will satisfy $d_{1}\;\mid\; q_{1}\; -\; 1\text{ and }d_{2}\;\mid\;q_{2}\;-\;1$ 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 $a^{n}\;\pm\;b^{n}$ 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 $b^{d_{1}}\Phi_{d_{1}}(a/b)$ and $b^{d_{2}}\Phi_{d_{2}}(a/b)$. The "typical" prime factors q1 and q2 respectively, will satisfy $d_{1}\;\mid\; q_{1}\; -\; 1\text{ and }d_{2}\;\mid\;q_{2}\;-\;1$ 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!

 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