Thread: Prime Conjecture

Is the following conjecture true or false?
If m is a positive odd integer such that 2^m = 2 (mod. m(m-1)) then m is a prime.

2⁷ = 2 (mod. 7x6). 2⁴³ = 2 (mod. 43x42).

False. For example, let m = 9.

EDIT: Sorry, m = 9 doesn't negate the statement. Ignore this...

Originally Posted by richard1234

False. For example, let m = 9.

2^9 = 8 (mod.72). Hence your counterexample is false.
Also, if 2^m = 2 (mod. m(m-1)) then m = 3 (mod. 4).

The conjecture is only true for m=3 and false for m<>3...even de Fermat was incompetent to discover it!

Hence, there exists such that . So consider the following manipulations:




Therefore, this is true when:



I dunno if that helps, but it seems like it might be a way to play with the problem.

Edit:

The conjecture is true for m = 7, 43 and more. But not for all primes = 3 (mod.4).
For 2³¹ = 2 (mod.31) but 2³¹ = 8 (mod. 30).
Is the following proof valid?
Theorem.
If m is a positive odd integer such that 2^m ≡ 2 (mod. m(m-1)) then m ≡ 3 (mod. 4) and m is a prime.
Proof.
Let 2^m ≡ 2 (mod. m(m-1)) then 2^m - 2 =km(m-1) for some positive integer k.
This gives 2^m-1 – 1 = km(m-1)/2 and since 2^m-1 – 1 is odd, (m-1)/2 is odd implying m ≡ 3 (mod. 4).
Let a be a positive integer and p a prime such that (p^a+1 , (m-1)/2) = p^a. Then 2^m-1 ≡ 1 (mod. p^a).
This implies p^a divides phi(m).
But this is true for all such primes p dividing (m-1)/2 and hece for their product.
This implies (m-1)/2 divides phi(m) and therefore phi(m) = m - 1
Hence, m is a prime.

Originally Posted by Stan

[FONT=arial][SIZE=3]Is the following conjecture true or false?
If m is a positive odd integer such that 2^m = 2 (mod. m(m-1)) then m is a prime.

m<184900 values for which the conjecture is true:

m={3, 7, 19, 43, 127, 163, 379, 487, 883, 1459, 2647, 3079, 3943, 5419, 9199, 11827, 14407, 16759, 18523, 24967, 26407, 37339, 39367, 42463, 71443, 77659, 95923, 99079, 113779, 117307, 143263, 174763, 175447, 184843}

Originally Posted by MaxJasper

m<184900 values for which the conjecture is true:

Does the theorem above hold true or is it erroneous?

Originally Posted by Stan

Does the theorem above hold true or is it erroneous?

m<2000 for which the conjecture is FALSE: (resulting non-Primes)


{ 9, 15, 21, 25, 27, 33, 35, 39, 45, 49, 51, 55, 57, 63, 65, \
69, 75, 77, 81, 85, 87, 91, 93, 95, 99, 105, 111, 115, 117, 119, 121, \
123, 125, 129, 133, 135, 141, 143, 145, 147, 153, 155, 159, 161, 165, \
169, 171, 175, 177, 183, 185, 187, 189, 195, 201, 203, 205, 207, 209, \
213, 215, 217, 219, 221, 225, 231, 235, 237, 243, 245, 247, 249, 253, \
255, 259, 261, 265, 267, 273, 275, 279, 285, 287, 289, 291, 295, 297, \
299, 301, 303, 305, 309, 315, 319, 321, 323, 325, 327, 329, 333, 335, \
339, 341, 343, 345, 351, 355, 357, 361, 363, 365, 369, 371, 375, 377, \
381, 385, 387, 391, 393, 395, 399, 403, 405, 407, 411, 413, 415, 417, \
423, 425, 427, 429, 435, 437, 441, 445, 447, 451, 453, 455, 459, 465, \
469, 471, 473, 475, 477, 481, 483, 485, 489, 493, 495, 497, 501, 505, \
507, 511, 513, 515, 517, 519, 525, 527, 529, 531, 533, 535, 537, 539, \
543, 545, 549, 551, 553, 555, 559, 561, 565, 567, 573, 575, 579, 581, \
583, 585, 589, 591, 595, 597, 603, 605, 609, 611, 615, 621, 623, 625, \
627, 629, 633, 635, 637, 639, 645, 649, 651, 655, 657, 663, 665, 667, \
669, 671, 675, 679, 681, 685, 687, 689, 693, 695, 697, 699, 703, 705, \
707, 711, 713, 715, 717, 721, 723, 725, 729, 731, 735, 737, 741, 745, \
747, 749, 753, 755, 759, 763, 765, 767, 771, 775, 777, 779, 781, 783, \
785, 789, 791, 793, 795, 799, 801, 803, 805, 807, 813, 815, 817, 819, \
825, 831, 833, 835, 837, 841, 843, 845, 847, 849, 851, 855, 861, 865, \
867, 869, 871, 873, 875, 879, 885, 889, 891, 893, 895, 897, 899, 901, \
903, 905, 909, 913, 915, 917, 921, 923, 925, 927, 931, 933, 935, 939, \
943, 945, 949, 951, 955, 957, 959, 961, 963, 965, 969, 973, 975, 979, \
981, 985, 987, 989, 993, 995, 999, 1001, 1003, 1005, 1007, 1011, \
1015, 1017, 1023, 1025, 1027, 1029, 1035, 1037, 1041, 1043, 1045, \
1047, 1053, 1055, 1057, 1059, 1065, 1067, 1071, 1073, 1075, 1077, \
1079, 1081, 1083, 1085, 1089, 1095, 1099, 1101, 1105, 1107, 1111, \
1113, 1115, 1119, 1121, 1125, 1127, 1131, 1133, 1135, 1137, 1139, \
1141, 1143, 1145, 1147, 1149, 1155, 1157, 1159, 1161, 1165, 1167, \
1169, 1173, 1175, 1177, 1179, 1183, 1185, 1189, 1191, 1195, 1197, \
1199, 1203, 1205, 1207, 1209, 1211, 1215, 1219, 1221, 1225, 1227, \
1233, 1235, 1239, 1241, 1243, 1245, 1247, 1251, 1253, 1255, 1257, \
1261, 1263, 1265, 1267, 1269, 1271, 1273, 1275, 1281, 1285, 1287, \
1293, 1295, 1299, 1305, 1309, 1311, 1313, 1315, 1317, 1323, 1325, \
1329, 1331, 1333, 1335, 1337, 1339, 1341, 1343, 1345, 1347, 1349, \
1351, 1353, 1355, 1357, 1359, 1363, 1365, 1369, 1371, 1375, 1377, \
1379, 1383, 1385, 1387, 1389, 1391, 1393, 1395, 1397, 1401, 1403, \
1405, 1407, 1411, 1413, 1415, 1417, 1419, 1421, 1425, 1431, 1435, \
1437, 1441, 1443, 1445, 1449, 1455, 1457, 1461, 1463, 1465, 1467, \
1469, 1473, 1475, 1477, 1479, 1485, 1491, 1495, 1497, 1501, 1503, \
1505, 1507, 1509, 1513, 1515, 1517, 1519, 1521, 1525, 1527, 1529, \
1533, 1535, 1537, 1539, 1541, 1545, 1547, 1551, 1555, 1557, 1561, \
1563, 1565, 1569, 1573, 1575, 1577, 1581, 1585, 1587, 1589, 1591, \
1593, 1595, 1599, 1603, 1605, 1611, 1615, 1617, 1623, 1625, 1629, \
1631, 1633, 1635, 1639, 1641, 1643, 1645, 1647, 1649, 1651, 1653, \
1655, 1659, 1661, 1665, 1671, 1673, 1675, 1677, 1679, 1681, 1683, \
1685, 1687, 1689, 1691, 1695, 1701, 1703, 1705, 1707, 1711, 1713, \
1715, 1717, 1719, 1725, 1727, 1729, 1731, 1735, 1737, 1739, 1743, \
1745, 1749, 1751, 1755, 1757, 1761, 1763, 1765, 1767, 1769, 1771, \
1773, 1775, 1779, 1781, 1785, 1791, 1793, 1795, 1797, 1799, 1803, \
1805, 1807, 1809, 1813, 1815, 1817, 1819, 1821, 1825, 1827, 1829, \
1833, 1835, 1837, 1839, 1841, 1843, 1845, 1849, 1851, 1853, 1855, \
1857, 1859, 1863, 1865, 1869, 1875, 1881, 1883, 1885, 1887, 1891, \
1893, 1895, 1897, 1899, 1903, 1905, 1909, 1911, 1915, 1917, 1919, \
1921, 1923, 1925, 1927, 1929, 1935, 1937, 1939, 1941, 1943, 1945, \
1947, 1953, 1955, 1957, 1959, 1961, 1963, 1965, 1967, 1969, 1971, \
1975, 1977, 1981, 1983, 1985, 1989, 1991, 1995, 2001}

Originally Posted by MaxJasper

m<2000 for which the conjecture is FALSE: (resulting non-Primes)


{ 9, 15, 21, 25, 27, 33, 35, 39, 45, 49, 51, 55, 57, 63, 65, \
69, 75, 77, 81, 85, 87, 91, 93, 95, 99, 105, 111, 115, 117, 119, 121, \
123, 125, 129, 133, 135, 141, 143, 145, 147, 153, 155, 159, 161, 165, \
169, 171, 175, 177, 183, 185, 187, 189, 195, 201, 203, 205, 207, 209, \
213, 215, 217, 219, 221, 225, 231, 235, 237, 243, 245, 247, 249, 253, \
255, 259, 261, 265, 267, 273, 275, 279, 285, 287, 289, 291, 295, 297, \
299, 301, 303, 305, 309, 315, 319, 321, 323, 325, 327, 329, 333, 335, \
339, 341, 343, 345, 351, 355, 357, 361, 363, 365, 369, 371, 375, 377, \
381, 385, 387, 391, 393, 395, 399, 403, 405, 407, 411, 413, 415, 417, \
423, 425, 427, 429, 435, 437, 441, 445, 447, 451, 453, 455, 459, 465, \
469, 471, 473, 475, 477, 481, 483, 485, 489, 493, 495, 497, 501, 505, \
507, 511, 513, 515, 517, 519, 525, 527, 529, 531, 533, 535, 537, 539, \
543, 545, 549, 551, 553, 555, 559, 561, 565, 567, 573, 575, 579, 581, \
583, 585, 589, 591, 595, 597, 603, 605, 609, 611, 615, 621, 623, 625, \
627, 629, 633, 635, 637, 639, 645, 649, 651, 655, 657, 663, 665, 667, \
669, 671, 675, 679, 681, 685, 687, 689, 693, 695, 697, 699, 703, 705, \
707, 711, 713, 715, 717, 721, 723, 725, 729, 731, 735, 737, 741, 745, \
747, 749, 753, 755, 759, 763, 765, 767, 771, 775, 777, 779, 781, 783, \
785, 789, 791, 793, 795, 799, 801, 803, 805, 807, 813, 815, 817, 819, \
825, 831, 833, 835, 837, 841, 843, 845, 847, 849, 851, 855, 861, 865, \
867, 869, 871, 873, 875, 879, 885, 889, 891, 893, 895, 897, 899, 901, \
903, 905, 909, 913, 915, 917, 921, 923, 925, 927, 931, 933, 935, 939, \
943, 945, 949, 951, 955, 957, 959, 961, 963, 965, 969, 973, 975, 979, \
981, 985, 987, 989, 993, 995, 999, 1001, 1003, 1005, 1007, 1011, \
1015, 1017, 1023, 1025, 1027, 1029, 1035, 1037, 1041, 1043, 1045, \
1047, 1053, 1055, 1057, 1059, 1065, 1067, 1071, 1073, 1075, 1077, \
1079, 1081, 1083, 1085, 1089, 1095, 1099, 1101, 1105, 1107, 1111, \
1113, 1115, 1119, 1121, 1125, 1127, 1131, 1133, 1135, 1137, 1139, \
1141, 1143, 1145, 1147, 1149, 1155, 1157, 1159, 1161, 1165, 1167, \
1169, 1173, 1175, 1177, 1179, 1183, 1185, 1189, 1191, 1195, 1197, \
1199, 1203, 1205, 1207, 1209, 1211, 1215, 1219, 1221, 1225, 1227, \
1233, 1235, 1239, 1241, 1243, 1245, 1247, 1251, 1253, 1255, 1257, \
1261, 1263, 1265, 1267, 1269, 1271, 1273, 1275, 1281, 1285, 1287, \
1293, 1295, 1299, 1305, 1309, 1311, 1313, 1315, 1317, 1323, 1325, \
1329, 1331, 1333, 1335, 1337, 1339, 1341, 1343, 1345, 1347, 1349, \
1351, 1353, 1355, 1357, 1359, 1363, 1365, 1369, 1371, 1375, 1377, \
1379, 1383, 1385, 1387, 1389, 1391, 1393, 1395, 1397, 1401, 1403, \
1405, 1407, 1411, 1413, 1415, 1417, 1419, 1421, 1425, 1431, 1435, \
1437, 1441, 1443, 1445, 1449, 1455, 1457, 1461, 1463, 1465, 1467, \
1469, 1473, 1475, 1477, 1479, 1485, 1491, 1495, 1497, 1501, 1503, \
1505, 1507, 1509, 1513, 1515, 1517, 1519, 1521, 1525, 1527, 1529, \
1533, 1535, 1537, 1539, 1541, 1545, 1547, 1551, 1555, 1557, 1561, \
1563, 1565, 1569, 1573, 1575, 1577, 1581, 1585, 1587, 1589, 1591, \
1593, 1595, 1599, 1603, 1605, 1611, 1615, 1617, 1623, 1625, 1629, \
1631, 1633, 1635, 1639, 1641, 1643, 1645, 1647, 1649, 1651, 1653, \
1655, 1659, 1661, 1665, 1671, 1673, 1675, 1677, 1679, 1681, 1683, \
1685, 1687, 1689, 1691, 1695, 1701, 1703, 1705, 1707, 1711, 1713, \
1715, 1717, 1719, 1725, 1727, 1729, 1731, 1735, 1737, 1739, 1743, \
1745, 1749, 1751, 1755, 1757, 1761, 1763, 1765, 1767, 1769, 1771, \
1773, 1775, 1779, 1781, 1785, 1791, 1793, 1795, 1797, 1799, 1803, \
1805, 1807, 1809, 1813, 1815, 1817, 1819, 1821, 1825, 1827, 1829, \
1833, 1835, 1837, 1839, 1841, 1843, 1845, 1849, 1851, 1853, 1855, \
1857, 1859, 1863, 1865, 1869, 1875, 1881, 1883, 1885, 1887, 1891, \
1893, 1895, 1897, 1899, 1903, 1905, 1909, 1911, 1915, 1917, 1919, \
1921, 1923, 1925, 1927, 1929, 1935, 1937, 1939, 1941, 1943, 1945, \
1947, 1953, 1955, 1957, 1959, 1961, 1963, 1965, 1967, 1969, 1971, \
1975, 1977, 1981, 1983, 1985, 1989, 1991, 1995, 2001}

But for each of the above non-prime values of m, 2^m - 1 is not zero (mod. m(m-1) and therefore the conjecture still holds.

Originally Posted by Stan

But for each of the above non-prime values of m, 2^m - 1 is not zero (mod. m(m-1) and therefore the conjecture still holds.

Your original condition was: 2m = 2 (mod. m(m-1))

Originally Posted by MaxJasper

Your original condition was: 2m = 2 (mod. m(m-1))

If you look at the original post, you will see the condition is 2^m = 2 (mod. m(m-1)).

Sure 2^m was correct and I use it...I don't know what happened to ^ in my last post!