Modular Arithmetic — Some Advanced Tricks in Finding The Least Positive Residue

We got a least-residue question from David a few weeks ago, but never took the time to address it properly. While procrastination and busyness can take a toll on us, at some point one still needs to face the reality and get things done promptly (don’t you think, students? 😉 ). OK. Enough said. Here’s the bombshell David dropped us:

Find the least positive residue of $\displaystyle 12^{345}$ in mod 35.

Wow. That seems like a huge number. How on earth do you reduce it to a positive number below 35? Well, read on! More