Number Theory (Thailand Math POSN 3rd round)

Not so much interesting problems there, and I'm not allowed to take exams back.

Denote $\displaystyle \left(\frac{a}{n}\right)$ as Legendre symbol.

Def: Order of $a$ modulo $n$ denoted as $ord_{n}(a)$ is the smallest positive integer $k$ such that

$a^{k} \equiv 1 \pmod{n}$

Def: $\mathbb{Z}_{n} = \{0,1,2,\dots,n-1\}$ be complete residue system modulo $n$.

Def: $\mathbb{Z}_{n}^{*} = \{x \in \mathbb{Z}_{n} | (x,n) = 1\}$ be reduced residue system modulo $n$.

1.) Find all positive integers $n$ such that

• $2 \leq n \leq 30$
• For all $x \in \mathbb{Z}_{n}^{*}$, $ord_{n}(x) < \phi(n)$.

2.) Let $a \in \mathbb{Z}_{p}^{*}$ , $p$ be prime numbers. Prove that for all $p \geq 17$,

2.1) If $\displaystyle \left(\frac{a}{p}\right) = 1$, then $ord_{p}(a) < p-1$

2.2) There exists $a$ such that $\displaystyle \left(\frac{a}{p}\right) = -1$ and $ord_{p}(a) < p-1$

3.) Let $p$ be primes from $2$ to $97$ inclusively. Find the number of primes such that

3.1) $ord_{p}(2) = p-1$

3.2) $\displaystyle \left(\frac{-1}{p}\right) = 1$