Let:
$G=\{1,\ldots,p-1\}$ be the multiplicative group of integers modulo prime $p=2^k+1$;
$v_2(a)$ be the exponent of $2$ in the prime factorization of $a$;
$\mu(a)=\max\{j\in[0,k]\ |\ x^{2^j} \equiv a\}$ for some $x\in\mathbb{G}$;
$A_i = \{a\in\mathbb{G}\ |\ v_2(a)=i\}$;
$B_i = \{a\in\mathbb{G}\ |\ \mu(a)=i\}$.
Now, couple questions:
- Prove that $a$-powers of the elements of $G$ are exactly $2^{v_2(a)}$-powers of the elements of $G$.
I prove this by introducing two sub-groups $G_1=\{x^a,x\in G\}$ and $G_2=\{x^{2^{v_2(a)}},x\in G\}$ and showing that $G_1\subseteq G_2$ and $G_2\subseteq G_1$. But could there be less laborious and more intuitive proof, which is often the case with simpler problems in number theory?
- Let $g$ be a primitive root modulo $p$ and $f$ be a map from $G$ to itself that sends $x$ to $g^x$ modulo $p$. Prove that $f$ is a bijection that sends $A_i$ to $B_i$ for each $i\in\{0,\ldots,k\}$.
This one I can't formally prove at all...