This site is supported by donations to The OEIS Foundation.

2^n mod n

From OeisWiki
Jump to: navigation, search

2n mod n and related sequences

A015910
2n 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 
2n 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 2k mod k = n

A036236 Least inverse of A015910: smallest integer 
k > 0
such that 
2k 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 3n   ≡   3n  −  1 (mod 3n)
. So 
3n
is the least 
k
with 
2k   ≡   3n  −  1 (mod k)
. Hence for each 
n, a (3n  −  1) = 3n
. — Farideh Firoozbakht (mymontain(AT)yahoo.com), Nov 14 2006

2nc (mod n) for a fixed c

Notice that the set 
{ n ∈ ℤ + | 2n mod n = c }
is a subset of 
{ n ∈ ℤ + | 2n   ≡   c (mod n) }
. The latter is also equivalent to n | (2n - 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 
2n   ≡   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, ...} = 
{ 2n }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

2n ≡ 1 (mod n)

2n   ≡   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 
2n   ≡   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 
2n   ≡   c (mod n)
, then 
m = 2k(2n – 1)
satisfies 
2m   ≡   2 2k(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 
2n – 1
.
The above statement also holds for non-integer 
c
, provided that 
2k(c –1)
is an integer and 
2k(c –1)   ≥   k
.
For 
c = 3/2
and 
k = 1
, this implies that for every term 
n
of A296104, 
2n – 2
belongs to A015919.

- Max Alekseyev, 23 September 2016, 5 December 2017

See also


External links