# 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 $gcd(a,p)=1$, then certainly $gcd(a,p^2)=1$. This means a is invertible, so this is equivelent to seeing which elements have order dividing p-1 (mod $p^2$). because

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

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

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

You will need to skip things that are not relatively prime to $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