mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math > Number Theory Discussion Group

Reply
 
Thread Tools
Old 2020-07-18, 19:17   #1
mickfrancis
 
Apr 2014
Marlow, UK

23×7 Posts
Default 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?
mickfrancis is offline   Reply With Quote
Old 2020-07-18, 20:28   #2
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

57616 Posts
Default

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).
R. Gerbicz is offline   Reply With Quote
Old 2020-07-20, 08:04   #3
mickfrancis
 
Apr 2014
Marlow, UK

5610 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
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}
mickfrancis is offline   Reply With Quote
Old 2020-07-20, 13:02   #4
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2·1,741 Posts
Default

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
Dr Sardonicus is offline   Reply With Quote
Old 2020-07-20, 15:55   #5
mickfrancis
 
Apr 2014
Marlow, UK

23×7 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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!
mickfrancis is offline   Reply With Quote
Reply

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 2019-08-24 15:00
Consecutive numbers not coprime to Euler's totient... carpetpool Miscellaneous Math 5 2017-03-09 05:45
Basic Number Theory 7: idempotents and Euler's function Nick Number Theory Discussion Group 17 2016-12-01 14:27
euler's totient function toilet Math 1 2007-04-29 13:49
application of euler's phi function TalX Math 3 2007-04-27 11:50

All times are UTC. The time now is 21:21.

Mon Sep 28 21:21:10 UTC 2020 up 18 days, 18:32, 0 users, load averages: 1.08, 1.35, 1.48

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.