How can I show that ord_n(a^u) is equal to t/(t,u) I'm having a hard time on this question:
Let n > 0, a $\neq$ 0, and (a,n) = 1. If ord$_n$ a = t, and if $u$ is a positive integer, then show that:
$$ord_{n}(a^{u}) =\frac{t}{(t,u)}.$$
So far I've converted them from ord notation into congruence notation:
$$(a^{u})^{k}\equiv1\ (mod\ n)=\frac{t}{(t,u)}$$
$$ord_{n}a= t =>a^{k}\equiv1\ (mod\ n)=t$$
But I'm not sure how to proceed. 
 A: We will try to give a proof that uses not much machinery.
Let $k=\frac{t}{(t,u)}$. We want to show that $a^u$ has order $k$. To do this, we must show two things:
(i) $(a^u)^k\equiv 1\pmod{n}$, and
(ii) there is no positive integer $l\lt k$ such that $(a^u)^l\equiv 1\pmod{n}$.
Proof of (i): We have $(a^u)^k=a^{ut/(t,u)}$. But $(t,u)$ divides $u$. Let $u=(u_1)(t,u)$. Then $a^{ut/(t,u)}=a^{tu_1}=(a^t)^{u_1}$.
Since $a^t\equiv 1\pmod{n}$, it follows that $(a^t)^{u_1}\equiv 1\pmod{n}$, and we are finished with the proof of (i).
Proof of (ii): Suppose that $(a^u)^l\equiv 1\pmod{n}$. We will show that $k$ divides $l$, and therefore $k\le l$.
Since $a^{ul}\equiv 1\pmod{n}$, and $t$ is the order of $a$, it follows that $t$ divides $ul$. Let $u=(u_1)(t,u)$. Recall that $t=(k)(t,u)$. Then from $t$ divides $ul$, we conclude that $k$ divides $u_1l$. But $k$ and $u_1$ are relatively prime, so $k$ divides $l$.  This concludes the proof of (ii).
A: Going off of your notation, you know that $a^t \equiv 1 \pmod n$, and that this $t$ is minimal. 
Lemma: If $a^l \equiv \pmod n$, then $t \mid l$.
Sketch: if not, then $l = qt + r$ for some positive $r < t$, which implies that $a^r \equiv 1 \pmod n$. This is a contradiction, as $t$ is minimal $\diamondsuit$
So now we raise $a$ to the $k$th power. We're looking for the smallest multiple $km$ of $k$ so that $a^{mk} \equiv 1 \pmod n$. Then $mk$ will be a multiple of $k$ and by the lemma it will be a multiple of $t$. 
In particular, $mk$ will be a multiple of $\DeclareMathOperator{\lcm}{lcm}\lcm(t,k)$. We're talking about orders, so we'll take the smallest multiple of $\lcm(t,k)$, which is $\lcm(t,k)$ itself. So $m = \dfrac{\lcm(t,k)}{k}$.
Lemma: For any two positive integers $a,b$, we have that $\gcd(a,b)\lcm(a,b) = ab$.
Sketch: Immediate from unique factorization. $\diamondsuit$
This means that the order is $\dfrac{\lcm(t,k)}{k} = \dfrac{t}{\gcd(t,k)}$, which is what you want to show. 
