0
$\begingroup$

I need help proving the following:

Let $a\neq \pm1$ be an integer which is not divisible by an odd prime p. Let $d$ be the order of $a$ modulo $p$ and let $k_0$ be the largest integer such that $a^d=1 $ mod $ p^{k_0}$. Prove that if $k\geq{k_0}$ is a solution of the exponential congruence $a^k=1$ mod $p^k$ then $$\frac{p^k}{k}\leq \frac{a^d}{d}$$ I don't know how to relate the result with the solution of the equation.

$\endgroup$
0
$\begingroup$

I note in the following $v_p(x)$ for the $p$-adic valuation of $x$, i e $x=x_1 p^{v_p(x)}$ with $p$ not dividing $x_1$

I leave some details of the proof to you.

1) Suppose you have $m, q$ such that $v_p(a^m-1)=q\geq 1$. Then for any $n\geq 1$, you have $v_p(a^{mn}-1)=q+v_p(n)$. To see that, first take $n=p$, and putting $a^m=1+up^q$ with $p$ not dividing $u$, write $$a^{mp}=(1+up^q)^p=1+{p \choose 1}up^q+\cdots$$. You have hence the result for $n$ a power of $p$. Now take $n$ prime to $p$, and use the same way.

2) Now you have $d|k$, as $k\geq k_0$, and hence $a^k$ is congruent to $1$ modulo $p^{k_0}$. Put $k=dk_1$, by the above we get $v_p(a^k-1)=k_0+v_p(k_1)$. So $k_0+v_p(k_1)\geq k$, and we get $$p^k \leq p^{k_0}p^{vp(k_1)}$$

As $p^{k_0}\leq a^d-1\leq a^d$ and $p^{vp(k_1)}\leq k_1=\frac{k}{d}$, we are done.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.