2^n mod n

2ⁿ mod n and related sequences

2 n mod n, n ≥ 1

.

{0, 0, 2, 0, 2, 4, 2, 0, 8, 4, 2, 4, 2, 4, 8, 0, 2, 10, 2, 16, 8, 4, 2, 16, 7, 4, 26, 16, 2, 4, 2, 0, 8, 4, 18, 28, 2, 4, 8, 16, 2, 22, 2, 16, 17, 4, 2, 16, 30, 24, 8, 16, 2, 28, 43, 32, 8, 4, ...}

A015911 Numbers 

n, n ≥ 1,

such that 

2 n mod n

is odd.

{25, 45, 55, 91, 95, 99, 125, 135, 143, 153, 155, 161, 175, 187, 225, 235, 245, 247, 261, 273, 275, 279, 285, 289, 297, 319, 329, 333, 335, 355, 363, 369, 387, 391, 403, 407, ...}

Smallest k > 0 such that 2^k mod k = n

A036236 Least inverse of A015910: smallest integer 

k > 0

such that 

2 k mod k = n, n ≥ 0,

or 

0

if no such 

k

exists.

{1, 0, 3, 4700063497, 6, 19147, 10669, 25, 9, 2228071, 18, 262279, 3763, 95, 1010, 481, 20, 45, 35, 2873, 2951, 3175999, 42, 555, 50, 95921, 27, 174934013, 36, 777, 49, ...}

We can easily prove that 

2 3 n ≡ 3 n − 1 (mod 3 n)

. So 

3 n

is the least 

k

with 

2 k ≡ 3 n − 1 (mod k)

. Hence for each 

n, a (3 n − 1) = 3 n

. — Farideh Firoozbakht (mymontain(AT)yahoo.com), Nov 14 2006

2ⁿ ≡ c (mod n) for a fixed c

Notice that the set 

{ n ∈ ℤ + | 2 n mod n = c }

is a subset of 

{ n ∈ ℤ + | 2 n ≡ c (mod n) }

. The latter is also equivalent to n | (2 n - c). It is therefore more convenient and comprehensive to consider solutions to the congruence (or divisibility) than to the equation with the remainder.

List of sequences and initial terms

c

Sequences containing 

n

such that 

2 n ≡ c (mod n), n ≥ 1

.

A-number

–11

{1, 13, 16043199041, 91118493923, 28047837698634913, ...}

A334634

–10

{1, 2, 3, 9, 14, 161, 261, 5727, 12127, 16394, 20029238, 577738261, 2637324098, 45019843643, 54756012358, 142046769201, 2144325306742, 2247950127743, ...}

A245594

–9

{1, 11, 121, 323, 117283, 432091, 4132384531, 15516834659, 15941429747, 98953554491, 3272831195051, 7362974489179, 26306805687881, 33869035218491, ...}

A240942

–8

{1, 2, 4, 5, 6, 8, 12, 18, 24, 36, 72, 88, 198, 228, 1032, 2412, 2838, 4553, 5958, 10008, 24588, 25938, 46777, 65538, 75468, 82505, 130056, 143916, ...}

A245319

–7

{1, 3, 15, 75, 6308237, 871506915, 2465425275, 2937864075, 2948967789, 83313712623, 195392257275, 11126651718075, 45237726869109, 2920008144904215, ...}

A240941

–6

{1, 2, 10, 1030, 10009593662, 13957196317, 55299492770, 3764656723270, ...}

A245728

–5

{1, 7, 133, 1517, 11761, 676333, 1484413, 3627557, 10289371, 1449045241, 2433687407, 12309023183, 29013950411, 11701492535299, 223598572318157, ...}

A245318

–4

{1, 2, 3, 4, 20, 260, 740, 2132, 2180, 5252, 43364, 49268, 49737, 80660, 130052, 293620, 542852, 661412, 717027, 865460, 1564180, 2185220, 2192132, ...}

A244673

–3

{1, 5, 917, 3223, 62911, 326329, 395819, 33504053, 4446226763, 17556128765, 141613728437, 5259417592253, 113837290408523, ...}

A015940

–2

{1, 2, 6, 66, 946, 8646, 180246, 199606, 265826, 383846, 1234806, 3757426, 9880278, 14304466, 23612226, 27052806, 43091686, 63265474, 66154726, 69410706, ...}

A006517

–1

{1, 3, 9, 27, 81, 171, 243, 513, 729, 1539, 2187, 3249, 4617, 6561, 9747, 13203, 13851, 19683, 29241, 39609, 41553, 59049, 61731, 87723, 97641, 118827, 124659, ...}

A006521

–½

{1, 5, 65, 377, 1189, 1469, 25805, 58589, 134945, 137345, 170585, 272609, 285389, 420209, 538733, 592409, 618449, 680705, 778805, 1163065, 1520441, 1700945, ...}

A296369

0

{1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, ...} = 

{ 2 n }n ≥ 0

A000079

½

{1, 3, 15, 35, 119, 255, 455, 1295, 2555, 2703, 3815, 3855, 4355, 5543, 6479, 8007, 9215, 10439, 10619, 11951, 16211, 22895, 23435, 26319, 26795, 27839, ...}

A187787

1

{1}

3/2

{1, 111481, 465793, 79036177, 1781269903307, 250369632905747, 708229497085909, 15673900819204067, ...}

A296370

2

{1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, ...}

A015919

3

{1, 4700063497, 3468371109448915, 8365386194032363, 10991007971508067, ...}

A050259

4

{1, 2, 4, 6, 10, 12, 14, 22, 26, 30, 34, 38, 46, 58, 62, 74, 82, 86, 94, 106, 118, 122, 132, 134, 142, 146, 158, 166, 170, 178, 182, 194, 202, 206, 214, 218, 226, 254, 262, ...}

A015921

5

{1, 3, 19147, 129505699483, 674344345281, 1643434407157, 5675297754009, 12174063716147, 162466075477787, 313255455573801, 324082741109271, ...}

A128121

6

{1, 2, 10669, 6611474, 43070220513807782, ...}

A128122

7

{1, 5, 25, 1727, 3830879, 33554425, 19584403931, 25086500333, 23476467919565, ...}

A033981

8

{1, 2, 3, 4, 8, 9, 15, 21, 33, 39, 51, 57, 63, 69, 87, 93, 111, 123, 129, 141, 159, 177, 183, 195, 201, 213, 219, 237, 248, 249, 267, 291, 303, 309, 315, 321, 327, 339, 381, ...}

A015922

9

{1, 7, 2228071, 16888457, 352978207, 1737848873, 77362855777, 567442642711, ...}

A051447

10

{1, 2, 6, 18, 16666, 262134, 4048124214, 24430928839, 243293052886, 41293676570106, 3935632929857549, ...}

A128123

11

{1, 3, 262279, 143823239, 382114303, 1223853491, 381541784791, 556985326431, 6236258437049, 98828020264153, ...}

A033982

12

{1, 2, 4, 5, 3763, 125714, 167716, 1803962, 2895548, 4031785, 36226466, 16207566916, 103742264732, 29000474325364, 51053256144532, 219291270961199, 1611547934753332, ...}

A128124

13

{1, 11, 95, 4834519, 156203641, 135466795859, 182901372149135, ...}

A051446

14

{1, 2, 3, 10, 1010, 61610, 469730, 2037190, 3820821, 9227438, 21728810, 24372562, 207034456857, 1957657325241, 2002159320610, 35169368880130, 36496347203230, ...}

A128125

15

{1, 13, 481, 44669, 1237231339, 1546675117, 62823773963, 284876771881, 1119485807557, ...}

A033983

16

{1, 2, 4, 6, 7, 8, 12, 16, 20, 24, 28, 40, 44, 48, 52, 60, 68, 76, 80, 92, 112, 116, 120, 124, 148, 154, 164, 172, 188, 204, 208, 212, 236, 240, 244, 264, 268, 280, 284, 292, ...}

A015924

17

{1, 3, 5, 9, 45, 99, 53559, 1143357, 2027985, 36806085, 1773607905, 3314574181, 1045463125509, 1226640523999, 3567404505159, 28726885591099, 39880799734039, ...}

A124974

18

{1, 2, 14, 35, 77, 98, 686, 1715, 5957, 18995, 26075, 43921, 49901, 52334, 86555, 102475, 221995, 250355, 1228283, 1493597, 4260059, 6469715, 10538675, 15374219, ...}

A128126

19

{1, 17, 2873, 10081, 3345113, 420048673, 449349533, 2961432773, 19723772249, 821451792317, 1207046362769, ...}

A125000

2 5

{1, 2, 3, 4, 5, 8, 14, 16, 25, 32, 56, 65, 85, 145, 165, 185, 205, 221, 224, 265, 305, 365, 368, 445, 465, 485, 505, 545, 565, 685, 745, 785, 825, 865, 905, 965, 985, 1022, ...}

A015925

2 6

{1, 2, 4, 6, 8, 10, 12, 16, 18, 24, 30, 31, 32, 36, 42, 48, 64, 66, 72, 78, 84, 90, 96, 102, 114, 126, 138, 144, 168, 174, 176, 186, 192, 210, 222, 234, 246, 252, 258, 282, ...}

A015926

2 7

{1, 2, 3, 4, 7, 8, 15, 16, 28, 32, 49, 62, 64, 91, 112, 128, 133, 196, 217, 255, 259, 301, 427, 448, 469, 511, 527, 553, 679, 721, 763, 784, 889, 973, 992, 1015, 1057, 1099, ...}

A015927

2 8

{1, 2, 4, 6, 8, 12, 14, 16, 20, 24, 32, 40, 48, 56, 60, 64, 80, 88, 96, 104, 120, 127, 128, 136, 140, 152, 160, 184, 192, 224, 232, 240, 248, 256, 260, 272, 296, 308, 320, ...}

A015929

2 9

{1, 2, 3, 4, 5, 8, 9, 16, 17, 21, 27, 32, 45, 63, 64, 99, 105, 117, 124, 128, 153, 171, 189, 207, 254, 256, 261, 273, 279, 333, 369, 387, 423, 429, 477, 512, 513, 531, 549, ...}

A015931

2 10

{1, 2, 4, 6, 7, 8, 10, 12, 16, 24, 28, 30, 32, 34, 48, 50, 64, 70, 73, 96, 110, 112, 128, 130, 150, 170, 190, 192, 230, 256, 290, 310, 330, 370, 384, 410, 430, 442, 448, 470, ...}

A015932

2 11

{1, 2, 3, 4, 8, 11, 14, 15, 16, 31, 32, 35, 51, 56, 64, 121, 128, 146, 224, 256, 341, 451, 455, 496, 508, 512, 671, 781, 896, 1024, 1111, 1235, 1271, 1441, 1547, 1661, 1736, ...}

A015935

2 12

{1, 2, 4, 6, 8, 12, 16, 18, 20, 22, 23, 24, 32, 36, 40, 42, 48, 60, 62, 64, 68, 72, 80, 84, 89, 96, 120, 126, 128, 132, 144, 156, 160, 168, 180, 192, 204, 228, 240, 252, 256, ...}

A015937

2ⁿ ≡ 1 (mod n)

2 n ≡ 1 (mod n)

has the only solution 

n = 1

.

Proof

Assume that there exists a solution 

n > 1

. Consider its smallest prime divisor 

p

. Then 

2 n ≡ 1 (mod p)

, implying that the multiplicative order 

ordp(2)

divides 

n

. However, since 

ordp(2) < p

and 

p

is the smallest prime divisor of 

n

, we have 

ordp(2) = 1

, that is, 

p

divides 

2 1 − 1 = 1

which is impossible. Max Alekseyev 06:05, 29 July 2011 (UTC)

New terms from existing ones

Property

For any integer 

c

, if 

n

satisfies 

2 n ≡ c (mod n)

, then 

m = 2 k(2 n – 1)

satisfies 

2 m ≡ 2 2 k(c –1) (mod m)

for any integer 

k ≥ 0

.

For 

c = 2

and 

k = 0

, this implies that A015919 is infinite: if 

n

is a term, then so is 

2 n – 1

.

The above statement also holds for non-integer 

c

, provided that 

2 k(c –1)

is an integer and 

2 k(c –1) ≥ k

.

For 

c = 3/2

and 

k = 1

, this implies that for every term 

n

of A296104, 

2 n – 2

belongs to A015919.

- Max Alekseyev, 23 September 2016, 5 December 2017

External links

Joe K. Crump, 2^n mod n = c.

2^n mod n

Contents

2ⁿ mod n and related sequences

Smallest k > 0 such that 2^k mod k = n

2ⁿ ≡ c (mod n) for a fixed c

List of sequences and initial terms

2ⁿ ≡ 1 (mod n)

New terms from existing ones

See also

External links

Navigation menu

Views

Personal tools

Navigation

Search

Tools

2^n mod n

Contents

2n mod n and related sequences

Smallest k > 0 such that 2k mod k = n

2n ≡ c (mod n) for a fixed c

List of sequences and initial terms

2n ≡ 1 (mod n)

New terms from existing ones

See also

External links

Navigation menu

Search

2ⁿ mod n and related sequences

Smallest k > 0 such that 2^k mod k = n

2ⁿ ≡ c (mod n) for a fixed c

2ⁿ ≡ 1 (mod n)