The largest power of $2$ that divides $10^9$ is $2^9=512$. From there on we have
$$ 2^{9+n} \bmod 10^9 = 2^9\left(2^n \bmod \frac{10^9}{2^9}\right) $$
The sequence $2^n \bmod 5^9$ does satisfy the conditions for Euler's Theorem to apply; we find that it has period $\varphi(5^9)=4\cdot 5^8=1562500$. (Though actually it is not trivial that the period is not some divisor of this -- see Carmichael's theorem).
So we get
$$ 2^n \bmod 10^9 = \begin{cases} 2^n \bmod 10^9 & n < 1562509 \\
2^{((n-9)\bmod 1562500)+9} \bmod 10^9 & n \ge 1562509 \end{cases}$$
For the forward direction, note that $a^{(p-1)}$ is $1$ modulo $p$ and $a^{(p-1)/2}$ is a square root of $1$ modulo $p$. As you said, the different powers $a$, $a^2$, $a^3$, $\ldots$ $a^{p-1}$ are distinct. Thus, it must be that $a^{(p-1)/2}$ is congruent to $-1$ modulo $p$ and $a^{(p-1)/2}$ and $a^{p-1}$ are the only powers $a^k$ with $1 \leq k \leq p-1$ that are congruent to $\pm 1 \pmod{p}$. It follows that
$(-a)^{(p-1)/2} \equiv (-1)^{(p-1)/2} \cdot (-1) \equiv (-1)^{(p+1)/2} \pmod{p}$
We now use the fact that $p \equiv 3 \pmod{4}$ to conclude that $(-a)^{(p-1)/2} \equiv 1 \pmod{p}$.
Now note that $(-a)^k$ can only be 1 modulo $p$ if $a^k \equiv \pm 1 \pmod{p}$. Thus, the only possible $k$s with $1 \leq k \leq p-1$ such that $(-a)^k \equiv 1 \pmod{p}$ are $(p-1)/2$ and $p-1$. From the above, it follows that the order of $(-a)$ modulo $p$ is $(p-1)/2$.
For the reverse direction, note that $(-a)^{(p-1)/2} \equiv 1 \pmod{p}$ implies, since $p \equiv 3 \pmod{4}$, that $a^{(p-1)/2} \equiv -1 \pmod{p}$. Thus, $a$ to a power that is an odd multiple of $(p-1)/2$ is $-1$ modulo $p$. In particular, if $a^{n(p-1)/4} \equiv 1 \pmod{p}$, then $n$ must be a multiple of $4$.
Assume the order of $a$ modulo $p$ is $k$. Then $(-a)^{2k} \equiv 1 \pmod{p}$, so $2k$ is a multiple of $(p-1)/2$, the order of $-a$ modulo $p$. Thus, $k$ is a multiple of $(p-1)/4$. The observation in the above paragraph shows then that $k$ is a multiple of $(p-1)$, so $k=p-1$ and $a$ is a primitive root modulo $p$.
Best Answer
If $g$ is a primitive root modulo $p,ord_pg=p-1$
If $g^x\equiv g^y\pmod p\iff g^{x-y}\equiv1\pmod p\iff ord_pg\mid (x-y)$ (Proof below)
$\implies (p-1)\mid (x-y)$
This can be generalized to any composite $m>4$ having primitive root.So, $m$ must be of the form $p^e,2p^e$ where $p$ is an odd prime.
Now, $\phi(p^e)=p^{e-1}(p-1), \phi(2p^e)=phi(2)\phi(p^e)=p^{e-1}(p-1)$
In either cases if $g$ is a primitive root modulo $m,ord_pg=\phi(m)=p^{e-1}(p-1)$
If $g^x\equiv g^y\pmod m\iff g^{x-y}\equiv1\pmod m\iff ord_mg\mid (x-y)$ $\implies p^{e-1}(p-1)\mid (x-y)$
[
Proof :
Let $ord_ma=d$ and $a^n\equiv1\pmod m$ and $n=q\cdot d+r$ where $0\le r<d$
So, $a^{q\cdot d+r}\equiv1\pmod m\implies a^r\cdot (a^d)^q\equiv1\implies a^r\equiv1\pmod m$
But $d$ is the smallest positive integer such that $a^d\equiv1\pmod m$
$\implies r=0\implies n=q\cdot d$ i.e., $d\mid n$
]