I am trying to prove a little modification on Euler's theorem
, for all a, and where n is the product of two distinct primes say p and q.
I am having problems with the for all a part as the above is easy to show.
I need to show that if q or p is a factor of a, then it still yields the same result, as Euler's theorem says that the gcd(a, n) must be 1. But I am not sure how to show that in the modification it doesn't matter. Any ideas?
You can work with Euler's Theorem, yes.
Well, we have that if then and from there when
Now if then and/or . If both divide at the same time then and the assertion is obvious since and so
So assume that only one of the prime divides , WLOG, becuase of the symmetry consider
That is: where
Then by Euler's Theorem. That is
So it all comes down to showing that iff
And this is true since by Euler's Theorem ( remember that )
Just to check we can say that when n|a is the same as because for all a right?
Ahh, perfect I got it now! Thanks!