Results 1 to 4 of 4

Math Help - Need Help Related to FLittleTheorem

  1. #1
    Newbie
    Joined
    Jun 2009
    Posts
    5

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Gamma's Avatar
    Joined
    Dec 2008
    From
    Iowa City, IA
    Posts
    517
    Quote Originally Posted by robersi View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jun 2009
    Posts
    5
    Thank you for your reply. I didn't realize there are so many numbers ( so frequent) that satisfy this condition.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Jun 2009
    Posts
    5
    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Related Rates
    Posted in the Calculus Forum
    Replies: 8
    Last Post: May 3rd 2010, 04:18 AM
  2. Questions related to dv/dt = f(t).
    Posted in the Differential Equations Forum
    Replies: 9
    Last Post: April 26th 2010, 03:10 PM
  3. related rates
    Posted in the Algebra Forum
    Replies: 3
    Last Post: October 18th 2009, 04:05 PM
  4. Related Rate
    Posted in the Calculus Forum
    Replies: 5
    Last Post: March 3rd 2009, 06:00 PM
  5. How are the DFT and DCT related?
    Posted in the Calculus Forum
    Replies: 1
    Last Post: April 15th 2006, 12:32 AM

Search Tags


/mathhelpforum @mathhelpforum