Composite number n such that 2^n is 2 modulo n

 
 

For all prime numbers   p   (except 2),   2^p   modulo p is 2 :
 

Here are the first few examples:
 

p = 3   ….   2^3 \; = \; 8 \; = \; (3\times 2) \; + \; 2

p = 5   ….   2^5 \; = \; 32 \; = \; (5\times 6) \; + \; 2

p = 7   ….   2^7 \; = \; 128 \; = \; (7\times 18) \; + \; 2

p = 11   …   2^{11} \; = \; 2048 \; = \; (11\times 186) \; + \; 2

p = 13   …   2^{13} \; = \; 8192 \; = \; (13\times 630) \; + \; 2

p = 17   …   2^{17} \; = \; 131072 \; = \; (17\times 7710) \; + \; 2

p = 19   …   2^{19} \; = \; 524288 \; = \; (19\times 27594) \; + \; 2

 
 

This is also true for some (but only a very few) composite numbers.

For example,    341.

2^{341}   is   2   modulo 341

 
Find another composite number n, such that   2^n   is   2   modulo n
 
 
 
 

 
 
 
 
 
 
 
 
 
 
 
 
 
 

Advertisements

About benvitalis

math grad - Interest: Number theory
This entry was posted in Number Puzzles and tagged . Bookmark the permalink.

4 Responses to Composite number n such that 2^n is 2 modulo n

  1. paul says:

    There are 78 below 100000, and If I am not mistaken p is square free.

    1 , 341 , {{11,1},{31,1}}
    2 , 561 , {{3,1},{11,1},{17,1}}
    3 , 645 , {{3,1},{5,1},{43,1}}
    4 , 1105 , {{5,1},{13,1},{17,1}}
    5 , 1387 , {{19,1},{73,1}}
    6 , 1729 , {{7,1},{13,1},{19,1}}
    7 , 1905 , {{3,1},{5,1},{127,1}}
    8 , 2047 , {{23,1},{89,1}}
    9 , 2465 , {{5,1},{17,1},{29,1}}
    10 , 2701 , {{37,1},{73,1}}
    11 , 2821 , {{7,1},{13,1},{31,1}}
    12 , 3277 , {{29,1},{113,1}}
    13 , 4033 , {{37,1},{109,1}}
    14 , 4369 , {{17,1},{257,1}}
    15 , 4371 , {{3,1},{31,1},{47,1}}
    16 , 4681 , {{31,1},{151,1}}
    17 , 5461 , {{43,1},{127,1}}
    18 , 6601 , {{7,1},{23,1},{41,1}}
    19 , 7957 , {{73,1},{109,1}}
    20 , 8321 , {{53,1},{157,1}}
    21 , 8481 , {{3,1},{11,1},{257,1}}
    22 , 8911 , {{7,1},{19,1},{67,1}}
    23 , 10261 , {{31,1},{331,1}}
    24 , 10585 , {{5,1},{29,1},{73,1}}
    25 , 11305 , {{5,1},{7,1},{17,1},{19,1}}
    26 , 12801 , {{3,1},{17,1},{251,1}}
    27 , 13741 , {{7,1},{13,1},{151,1}}
    28 , 13747 , {{59,1},{233,1}}
    29 , 13981 , {{11,1},{31,1},{41,1}}
    30 , 14491 , {{43,1},{337,1}}
    31 , 15709 , {{23,1},{683,1}}
    32 , 15841 , {{7,1},{31,1},{73,1}}
    33 , 16705 , {{5,1},{13,1},{257,1}}
    34 , 18705 , {{3,1},{5,1},{29,1},{43,1}}
    35 , 18721 , {{97,1},{193,1}}
    36 , 19951 , {{71,1},{281,1}}
    37 , 23001 , {{3,1},{11,1},{17,1},{41,1}}
    38 , 23377 , {{97,1},{241,1}}
    39 , 25761 , {{3,1},{31,1},{277,1}}
    40 , 29341 , {{13,1},{37,1},{61,1}}
    41 , 30121 , {{7,1},{13,1},{331,1}}
    42 , 30889 , {{17,1},{23,1},{79,1}}
    43 , 31417 , {{89,1},{353,1}}
    44 , 31609 , {{73,1},{433,1}}
    45 , 31621 , {{103,1},{307,1}}
    46 , 33153 , {{3,1},{43,1},{257,1}}
    47 , 34945 , {{5,1},{29,1},{241,1}}
    48 , 35333 , {{89,1},{397,1}}
    49 , 39865 , {{5,1},{7,1},{17,1},{67,1}}
    50 , 41041 , {{7,1},{11,1},{13,1},{41,1}}
    51 , 41665 , {{5,1},{13,1},{641,1}}
    52 , 42799 , {{127,1},{337,1}}
    53 , 46657 , {{13,1},{37,1},{97,1}}
    54 , 49141 , {{157,1},{313,1}}
    55 , 49981 , {{151,1},{331,1}}
    56 , 52633 , {{7,1},{73,1},{103,1}}
    57 , 55245 , {{3,1},{5,1},{29,1},{127,1}}
    58 , 57421 , {{7,1},{13,1},{631,1}}
    59 , 60701 , {{101,1},{601,1}}
    60 , 60787 , {{89,1},{683,1}}
    61 , 62745 , {{3,1},{5,1},{47,1},{89,1}}
    62 , 63973 , {{7,1},{13,1},{19,1},{37,1}}
    63 , 65077 , {{59,1},{1103,1}}
    64 , 65281 , {{97,1},{673,1}}
    65 , 68101 , {{11,1},{41,1},{151,1}}
    66 , 72885 , {{3,1},{5,1},{43,1},{113,1}}
    67 , 74665 , {{5,1},{109,1},{137,1}}
    68 , 75361 , {{11,1},{13,1},{17,1},{31,1}}
    69 , 80581 , {{61,1},{1321,1}}
    70 , 83333 , {{167,1},{499,1}}
    71 , 83665 , {{5,1},{29,1},{577,1}}
    72 , 85489 , {{53,1},{1613,1}}
    73 , 87249 , {{3,1},{127,1},{229,1}}
    74 , 88357 , {{149,1},{593,1}}
    75 , 88561 , {{11,1},{83,1},{97,1}}
    76 , 90751 , {{151,1},{601,1}}
    77 , 91001 , {{17,1},{53,1},{101,1}}
    78 , 93961 , {{7,1},{31,1},{433,1}}

    Paul.

  2. paul says:

    and 247 instances with p<=10^6.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s