## 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

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.

• benvitalis says:

Do you know why it works for some squarefree numbers?

• paul says:

I couldn’t find any solution that had a square factor.

2. paul says:

and 247 instances with p<=10^6.