|March 3rd, 2017, 12:50 AM||#1|
Joined: Mar 2017
From: Walnut Creek, CA
Math Focus: Number Theory
Is this known?
While working on one of my favorite math problems, large semi-prime factorization, I stumbled across something that surprised me. I'm no math expert but I've read quite a few undergraduate level number theory books and I haven't seen anything like this. I am hoping someone could help me find out if this is already known.
First, I found that for an integer a, and a positive integer m, the following is true:
a^(2^(φ(φ(m))) ≡ a^(2^(2*φ(φ(m))) (mod m)
where φ is Euler's totient function. I struggled to try and find a reason why this was true for quite a while and then I finally came up with an explanation and proof. Finding the proof made it clear that this is just a special case of a more general result which is this:
a^(x1^(x2^(...(xn(b*φ(φ(...(φ(m))))))))) ≡ a^(x1^(x2^(...(xn(c*φ(φ(...(φ(m))))))))) (mod m)
where a is an integer, b, c, and m are positive integers, x1, x2, ..., xn is a finite non-empty sequence of n non-negative integers, and φ(φ(...(φ(m)))) is Euler's totient function recursively applied to m, n times. I also have a proof for this.
My question is whether anyone else has ever identified and/or proved this before? Thanks very much for any feedback.