So I've actually been working with congruences recently in class and most of the time I end up using Fermat or the Euler Totient function to simplify a large exponent. In general, I run into a situation where I find :
$a^y = z $ (mod n)
I know that,
$ a^x = 1$ (mod n)
My problem then simplifies to finding $ y = b $ (mod x)
I've seen several "tricks" such as finding what something is congruent to modulo 2,3,4..all the way up till 11.
My question is if there is a general approach that will work for anything?
Here's an example :
$a = 7^{13198459348751983475867345892342398209234983465234531}$
Suppose I want to find this Congruent to Modulo 5, 11 and 55.
Since 5 is Prime, I know $7^4 = 1$ (mod 5)
So my problem is now finding that large exponent = x (mod 4)
From the Divisibility tricks I've learnt it tells me to check what the last two digits are congruent to mod 4 which is = 3.
So my answer then is $7^3$ (mod 5) = 3
If I try the same approach for Mod 55 now, using the Euler Function I know that $7^{40} = 1$ (mod 55)
However I'm not sure how to find that large exponent mod 40. I'm sure there is an easy way here somewhere but I figured learning the divisibilty in general would be much easier.