# Thread: Need Help Related to FLittleTheorem

1. ## Need Help Related to FLittleTheorem

Is there or has there been any work done on the existence of integers A s.t. A^n = A (modulo n^2) where n is prime and A is coprime to n?

haven't used LaTex for a while now... forgot... sorry

2. Originally Posted by robersi
Is there or has there been any work done on the existence of integers A s.t. A^n = A (modulo n^2) where n is prime and A is coprime to n?

haven't used LaTex for a while now... forgot... sorry
You just need one number to do it? I mean clearly 1 will always satisfy this requirement.

Less trivially, if $\displaystyle gcd(a,p)=1$, then certainly $\displaystyle gcd(a,p^2)=1$. This means a is invertible, so this is equivelent to seeing which elements have order dividing p-1 (mod $\displaystyle p^2$). because

$\displaystyle a^{p-1}=a^p\cdot a^{-1}=aa^{-1}=1$ (mod $\displaystyle p^2$).

Now one thing to consider is the order of this multiplicative group is $\displaystyle \phi(p^2)=p(p-1)$. This means for every a that is relatively prime to $\displaystyle p^2$, $\displaystyle a^p$ will satisfy this property.

For instance lets go mod $\displaystyle 7^2=49$
$\displaystyle 1^7\equiv 1$ (mod 49) works and $\displaystyle 1^6\equiv1$ (mod 49)
$\displaystyle 2^7\equiv 30$ (mod 49) works because $\displaystyle 30^6 \equiv 1$ (mod 49)
$\displaystyle 3^7\equiv 31$ (mod 49) works because $\displaystyle 31^6 \equiv 1$ (mod 49)
$\displaystyle \vdots$

You will need to skip things that are not relatively prime to $\displaystyle p^2$ like p, 2p, 3p, etc... I am not sure that this will generate everything, nor are these necessarily all going to be unique, but there are certainly quite a few numbers that should satisfy this property.

3. Thank you for your reply. I didn't realize there are so many numbers ( so frequent) that satisfy this condition.

4. Hey, I think in order to generate all I just need to count up to n-1 .... not (n^2) - 1. (x + ny )^n = x^n (modulo n^2) where y and x some integer.

Thanks again