Results 1 to 2 of 2

Math Help - Finding remainder in non-prime congruence

  1. #1
    Newbie
    Joined
    May 2009
    Posts
    9

    Finding remainder in non-prime congruence

    Find r \in Z such that 0 \leq r \leq 4096 and 2^{4096} \equiv r \,(mod \,4097) Why does this prove that 4097 is not a prime? According to FLT r would be 1 if 4097 where a prime, but now it isn't, so, help appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member TheAbstractionist's Avatar
    Joined
    Apr 2009
    Posts
    328
    Thanks
    1
    Quote Originally Posted by knarQ View Post
    According to FLT r would be 1 if 4097 where a prime
    That’s the wrong statement of Fermat’s little theorem, According to FLT, r=1 if 2 and 4097 are relatively prime. They are, so 2^{4096}\equiv1\,\bmod{4097}.

    However, this alone neither proves nor disproves that 4097 is not prime. For example:

    1. Since 2^2\equiv1\,\bmod3,\ 2^{4096}=(2^2)^{2048}\equiv1\,\bmod3 and 3 is a prime.
    2. Since 2^4\equiv1\,\bmod{15},\ 2^{4096}=(2^4)^{1024}\equiv1\,\bmod15 but 15 is not a prime.


    Hence, if 2^{4096}\equiv1\,\bmod n, nothing can be deduced about the primeness or otherwise of n. You need more information on n. The question you posted may be part of another question containing some other results about 4097.
    Last edited by TheAbstractionist; June 4th 2009 at 06:21 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. prime congruence help
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: November 14th 2011, 08:14 AM
  2. Congruence, finding remainder
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: May 7th 2009, 02:42 PM
  3. Prime Power Congruence
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: April 24th 2009, 08:44 PM
  4. Prime Congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: July 15th 2008, 02:06 PM
  5. Find remainder with congruence theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 6th 2008, 02:51 PM

Search Tags


/mathhelpforum @mathhelpforum