Modular arithmetic for a beginner I am a student who is struggling terribly with Discrete Mathematics 2. I've already changed my major from computer science to IT because it's just not a great fit for me but I'd still like to leave this course with some knowledge seeing as I've spent a great deal of money on college to begin with.
I am having trouble understanding modular arithmetic and I have to solve these two problems by hand:
$$89 ^ {307} \bmod 713$$
$$49 ^ {307} \bmod 713$$
If anyone could show me how to even approach this I'd be thankful. My class is learning through theorems which isn't helpful at all. I need this to be broken down like it's being taught to a 3 year old. Thank you for your help in advanced.
 A: Start by factoring into primes, $713=23\times 31$. We'll first find $89^{307}$ modulo $23$ and $31$, and combine those answers to get the final one. Modulo $23$, $89$ is equivalent to $-3$, since it's $4*23-3$. So we're calculating $(-3)^{307}$ modulo $23$. 
Now you need to use one of these theorems, namely "Fermat's little theorem," which says that $n^{p-1}\equiv 1\pmod p$ for any prime $p$. That tells us that $(-3)^{22}\equiv 1 \pmod{23}$, in this case.  Then $(-3)^{44}=((-3)^{22})^2\equiv 1^2\pmod{23}$, and similarly for bigger multiples of $22$: this leads to the common strategy in problems like this of cancelling out multiples of $p-1$ from the power we're taking. That is, since $307=308-1$ and $308$ is a multiple of $22$, $(-3)^{301}\equiv (-3)^{-1}\pmod{23}$. So we have to find the multiplicative inverse of $-3\pmod{23}$, i.e. we need $x,y$ so $-3x+23y=1$. We have $2=23+7(-3)$ and $1=-3+2*2$, so $-3x+23y=-3+2*2=-3+2(23+7(-3))=15(-3)+2(23)$, which shows $15$ is the inverse of $-3$ modulo $23$. What I've done here is run the Euclidean algorithm backwards-if you don't know the algorithm you'd better look it up. 
Now, modulo $31$, we're doing $89\equiv -4$ to the $307\equiv 7$, and here we basically just calculate directly: $(-4)^7=(-4)(-4)^2(-4)^4\equiv (-4)(-15)(8)\equiv 15(\pmod{31})$. So, $89^{307}$ is $15$ modulo both $23$ and $31$, and so it's also $15$ modulo $713$! This follows from another theorem, usually called the Chinese Remainder theorem.
A: Two tools are required for this kind of problems: the Chinese remainder theorem, which is used to solve systems of simultaneous congruences via  Bézout's identity, and the little Fermat's theorem. I'll try to show from the first problem.
First, as $713=23\cdot 31$ and the factors are (co)prime, $\;\mathbf Z/713\mathbf Z\simeq \mathbf Z/23\mathbf Z\times \mathbf Z/31\mathbf Z$. The interesting isomorphism is from right to left: if you have a pair of congruence classes: $\alpha\pmod{23}$ and $\beta \pmod{31}$, it corresponds to the congruence class of 
$$ 23u\beta+31v\alpha\mod 23\cdot31, $$
where $u$ and $v$ are the coefficients of a Bézout's identity between $23$ and $31$, say
$$ -4\cdot 23+3\cdot 31=1. \tag{1}$$
Now as $89\equiv 20\mod23$, we have $89^{307}\equiv 20^{307}\mod 23$. Furthermore, by Little Fermat, $20^{22}\equiv 1\mod23$, so $20^{307}\equiv 20^{307\bmod22}=20^{-1}\mod23$.
We find the inverse of $20\bmod23$ with Bézout' identity:
$$7\cdot 23-8\cdot 20=1$$
which shows $\;20^{-1}\equiv-8\equiv\color{red}{15}\mod23$.
Similarly, $89\equiv -4\mod31$, and
$$89^{307}\equiv -4^{307\bmod30}=-4^7=-2^{14}\mod31.$$
Furthermore, $2^5\equiv 1\mod 31$, hence $$89^{307}\equiv -2^{-1}\equiv \color{blue}{15}\mod31. $$
Thus we have to solve the system of congruences $\;\begin{cases}x\equiv 15\mod23\\ x\equiv15\mod31\end{cases}$. We just have to apply formula $(1)$:
$$x\equiv-\color{blue}{15}\cdot4\cdot23+\color{red}{15}\cdot3\cdot31\equiv15\mod713.$$
