So I'm taking an intro-Math course for CS. We are currently covering modular arithmetics. My professor was explaining calculating the mod of large numbers, such as 163^42 Mod 49 in this case. First, she decided to solve for 16^42 instead because 16 is the remainder of 163 Mod 49, which made sense. Then she kept on expanding 16^n with different powers, which was easy to follow. Then this! She astrayed from the pattern and decided to use -10 as the remainder of 16^8, instead of moving forward with 39. And she didn't clearly explain why she was doing this.
Could anyone tell me more about the logic behind it? I don't see why she couldn't have continued with 39.
As has been stated, it's a simple way to keep magnitude easier to work with. This is like people saying quarter to the hour, instead of three quarters past. Because $$45\equiv -15\bmod 60$$, it's all the same.
The math we do on clocks, is an example of mixed modular arithmetic we take seconds into the day mod 60, get the magnitude of the minutes, take it mod 60, and get the magnitude of the number of hours and take it mod 12.(replacing 0 with 12 in the case of hours)
with multiplication, exponentiation and in the rare case where it's possible division, it sometimes is easier to use an alternate form of a number. All integers on the y=mx+b linear polynomial are congruent to each other mod m (or x, but we usually only care for one or the other).
an example where it can come in handy in division is modular multiplicative inverses. Let's take the modular multiplicative inverse (the number we multiply by to get 1 in the modular arithmetic we are doing) of 16 mod 49. 16 and 49 are coprime so it's findable. 1 doesn't help us much lets switch it to -48 . we then have $-48=(-3)16$. so $-3$, aka $49-3=46$, is the modular multiplicative inverse of 16 mod 49.
in exponentiation it's used (with other technicalities like Euler's totient theorem, and group theory in the way partly.) . In the case of modulo primes, we use Fermat's little theorem (a special case of Euler's totient theorem). An example is $$16^{2572435647687978}\bmod 17$$ Fermat's little theorem says $$a^{p-1}\equiv 1\bmod p$$ where p is prime, and a is not a multiple of p. Adding help from $$1^n=1$$ and $$(a^b)^c=a^{bc}$$ we can show that $$(a^{p-1})^n=a^{(p-1)n}$$, and $$1^n\equiv 1\bmod p$$ . This means if we can write $2572435647687978=16(n)+w$, using $$a^{16(n)}(a^w)=a^{16(n)+w}$$ and $1a=a$ we can calculate a number raised to it, mod 17. since all multiples of 16 as exponents give a remainder of 1 on division by 16 we just need the remainder of 2572435647687978 on division by 16. Which turns out to be 10. So it reduces to :$$16^{10}\equiv 1\bmod 17$$ we could have just used $16\equiv-1 \bmod 17$ and $$-1^{2y}=1$$ but knowing your arithmetic rules, will help you tons in modular arithmetic. As modular arithmetic is a generalization of the normal stuff, with restrictions.