×

# 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$$

Note by Samuraiwarm Tsunayoshi
2 years, 4 months ago