Order of $2^{36} \pmod{107}$ What is the order of $2^{36}\pmod{ 107}$? 
My current thought is $$2^{106} \equiv 1 \pmod{107}$$ according to Euler's Theorem. However, I don't know how to proceed from here or maybe my approach is wrong from the beginning?
 A: The order of $a =2^{36}$ $\pmod {107}$ divides 106 thus it is $2$, $53$ or $106$.
Let's observe that:
$(2^{36})^3=2^{108}=2^{106}\cdot2^2\equiv4\pmod {107}$
thus
$((2^{36})^2)^3=((2^{36})^3)^2\equiv16\pmod {107}$
then $2\neq ord_a(p)$
Let's consider:
$(2^{36})^{53}=(2^{106})^{18}\equiv1\pmod {107}$
then $53 = ord_a(p)$
A: The order of any nonzero element of $\mathbb{Z}/(\mathbb{107Z})$ is a divisor of $106$, i.e., $1$, $2$, $53$, or $106$.  The order of $2$ mod $107$ is clearly not $1$ or $2$, and therefore $a=2^{36}\not\equiv1$ mod $107$.  It follows that $a^2\equiv2^{72}\not\equiv1$ mod $107$ either.  Thus the order of $a$ is either $53$ or $106$. But $a$ is clearly a square, hence cannot be of order $106$ (i.e., a primitive root).  That leaves $53$ as the only possible order.
A: Since 107 is a prime number and $\gcd(2,107)=1$ you can apply the Fermat Little Theorem:
$$a^{p-1}\equiv 1 \pmod p\tag{1}$$
Then is true that $$2^{106}\equiv 1 \pmod{107}$$
If you want you can also apply the Euler’s Theorem that is a generalisation of $(1)$. In fact is says that:
$$a^{\phi(n)}\equiv 1 \pmod n$$
If $n$ is a prime number then the Euler’s Theorem is the same as the Fermat Little Theorem. You only have to verify if some of the divisors of $\phi(n)$ is the littlest order. In your case the right order is $106$.
A: Since $107-1=2\cdot 53$, every quadratic non-residue, with the only exception of $-1$, is a generator of $\mathbb{Z}/(107\mathbb{Z})^*$. $107$ is a prime of the form $8k+3$, hence $\left(\frac{2}{107}\right)=-1$ and $2$ has order $106$ in $\mathbb{Z}/(107\mathbb{Z})^*$. We have $\gcd(36,106)=2$, hence the order of $2^{36}$ in $\mathbb{Z}/(107\mathbb{Z})^*$ is $\frac{106}{2}=\color{red}{53}$.
A: You are correct that $(2^{36})^{106} \equiv 1\mod 107$.
So that means the order of $2^{36}$ divides $106$. (so is $1, 2, 53,$ or $106$)
But also not that $2^{106}\equiv 1 \mod 107$ so the order of $2$ also divides $106$.
If the order of $2^{36}$ were $1$ or $2$ the $2^{36}$ or $2^{72}$ would be equivalent to $1 \mod 107$ so that would mean the order of $2$ would divide both $106$ and $72$.  That would mean the order of $2$ would be $1$ or $2$.
It's easy to verify it is not.
So the order of $2^{36}$ must be $53$ or $106$.  As $(2^{36})^{53}=(2^{106})^{18} \equiv 1 \mod 106$ the order of $2^{36}$ is at most $53$ so it is $53$.
...
Another way of putting is if $|c^a| = k$ and $|c| = m$ then $c^{ak}\equiv 1\mod p$ ($p$ is prime) so $m|ak$ and $ak|p-1$ and $m|p-1$. 
That condition $m|ak$ and both $ak$ and $m$ dividing $p-1$ is very limiting.
$|2|| 36k$ and $36k|106$ means $18k|53$ means $k|53$ so $k|53$ so $|2|| 36k$ and $|2||106$.  
So $k = 53$ or $1$ and $|2| = 1,2,k,2k$.  As $|2|$ obviously does not equal $1$ and $2$, $k =53$ is the only option.
