Results 1 to 2 of 2

Thread: Finding remainder in non-prime congruence

  1. #1
    Newbie
    Joined
    May 2009
    Posts
    9

    Finding remainder in non-prime congruence

    Find $\displaystyle r \in Z$ such that $\displaystyle 0 \leq r \leq 4096$ and $\displaystyle 2^{4096} \equiv r \,(mod \,4097)$ Why does this prove that $\displaystyle 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, $\displaystyle r=1$ if 2 and 4097 are relatively prime. They are, so $\displaystyle 2^{4096}\equiv1\,\bmod{4097}.$

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

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


    Hence, if $\displaystyle 2^{4096}\equiv1\,\bmod n,$ nothing can be deduced about the primeness or otherwise of $\displaystyle n.$ You need more information on $\displaystyle n.$ The question you posted may be part of another question containing some other results about 4097.
    Last edited by TheAbstractionist; Jun 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: Nov 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: Apr 24th 2009, 08:44 PM
  4. Prime Congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Jul 15th 2008, 02:06 PM
  5. Find remainder with congruence theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Feb 6th 2008, 02:51 PM

Search Tags


/mathhelpforum @mathhelpforum