4
$\begingroup$

Let $n$ be a positive integer. Let $a$ be a nonzero integer such that $\gcd(a,n)=1$.

How to show that $\frac{a^{\phi (n)}-1}{n} \equiv \sum_i \frac{1}{ai} \left \lfloor \frac{ai}{n} \right \rfloor \pmod{n}$ where $i$ runs over all positive integers which are less than $n$ and relatively prime to $n$?

Remark: I find that if we take $a=2$ and $n=p$ where $p$ is an odd prime, then we can answer this question : congruent to mod p $1^{p-2}+2^{p-2}+\cdots+\left(\frac{p-1}{2}\right)^{p-2}\equiv\frac{2-2^p}{p}\pmod p.$.

EDIT:I just find out that this problem is stated in :

M. Lerch, “Zur Theorie des Fermatschen Quotienten. . . ,” Math. Ann. 60 (1905) 471–490. (when $n$ is a prime)

Using similar method, I can showed that:

$\phi (n) \frac{a^{\phi (n)}-1}{n} \equiv \phi (n) \sum_i \frac{1}{ai} \left \lfloor \frac{ai}{n} \right \rfloor \pmod{n}$ so the result is true when $\gcd (\phi (n) ,n)=1$. It seems that my problem is stated on page 487,equation $(30)$ of the paper. Since I don't understand German , I may miss something of the paper. Can someone explain to me that the techniques the author used?

  • 0
    @Zander:Oh, thanks for your translation:) Now it seems that the trick given in the paper is not sufficient to this problem.I have to work on the case when (n, \phi (n) )>1 now...2012-07-02

0 Answers 0