4.9.17

Products of Primes Without Selfie Powers

In my previous post I suggested that there are products of primes p and q that are easier (relatively) to factor because there is an integer k such that k = (p*q - 1)/2 and k^k = (phi(p*q))/2 and I called k a selfie power.



Before I talk about such products, I'll talk about products of primes, which have no selfie power and no semi selfie powers* because proper categorization is important.



Theorem: Given a product of primes p and q, if p or q divides phi(p*q) then p*q has no selfie power (ie an integer k such that k = (p*q - 1)/2 and k^k = (phi(p*q))/2 )

Proof: If p or q divides phi(p*q) then GCD(phi(p*q), k) = 1 since by definition of a selfie power k = (p*q - 1)/2 but also by definition of a selfie power k^k = (phi(p*q))/2 so 2*(k^k) = phi(p*q), which is a contradiction.



Example: Let p = 5 and q = 11, then p*q = 55 and phi(p*q) = (p-1)*(q-1) = 4*10 = 40 and clearly p divides phi(p*q). Furthermore, (p*q-1)/2 = 27 and 27^27 (mod 55) = 42 so 27 is not a selfie square as expected.


*to be defined in future blog posts