mersenneforum.org Need more items for sequence 17, 257, 641, 65537, …
 Register FAQ Search Today's Posts Mark Forums Read

 2019-10-17, 01:17 #1 miket   May 2013 910 Posts Need more items for sequence 17, 257, 641, 65537, … Let n be an odd positive integer, Let o=ordn2 be the order of 2 modulo n and m the period of 1/n, k is number of distinct odd residues contained in set {2^1,2^2,...,2^{n−1}} modulo n. If odd part of o,m and k is 1 and k divide n-1, then n is item in the sequence 17, 257, 641, 65537, …. 167772161 also is item.It seems all known items in the sequence are Fermat factors and divide 2^(2^100) - 1 and 10^(10^100) - 1. Here's my PARI/GP code to check numbers(there's large space left for improve): Code: oddres(n)=if(n<2,0,n>>valuation(n,2)) ck(n) = { my(l=List(),m=if(1
2019-10-17, 15:03   #2
Dr Sardonicus

Feb 2017
Nowhere

2·2,671 Posts

Quote:
 Originally Posted by miket Let n be an odd positive integer, Let o=ordn2 be the order of 2 modulo n and m the period of 1/n, k is number of distinct odd residues contained in set {2^1,2^2,...,2^{n−1}} modulo n. If odd part of o,m and k is 1 and k divide n-1, then n is item in the sequence 17, 257, 641, 65537, ….
First, I don't understand why n = 3 isn't on the list.

Second, the "period" of 1/n apparently is to the base ten. If this period is a power of 2, then the multiplicative order of 10 (ten) (mod n) must also be a power of 2 (so 5 can not divide n), and the multiplicative order of 5 (mod n) must therefore also be a power of 2. The multiplicative orders may, of course, be different powers of 2.

Third, if n is prime, and the multiplicative order o > 1 of 2 (mod n) is even, then exactly half the representatives of {1, 2, ... 2^(o-1) (mod n)} in the interval [1,n-1] -- that is, o/2 of them -- are odd. I leave the proof as an exercise for the reader.

 2019-10-17, 19:41 #3 Dr Sardonicus     Feb 2017 Nowhere 2·2,671 Posts Inspired by the examples p = 5*2^7 + 1 = 641 and p = 5*2^25 + 1 = 167772161 already given, I tried other known prime factors 5*2^k + 1 of Fermat numbers. Numerical checking showed that the multiplicative orders of 5 (mod p) for p = 5*2^39 + 1, 5*2^75 + 1, 5*2^127 + 1, 5*2^1947 + 1, and 5*2^3313 + 1 are powers of 2. I did not attempt a numerical check for p = 5*2^23473 + 1, a factor of F23471 It is, alas, not always true that 5 is a quintic residue of p = 5*2^k + 1, which is what is needed to make the multiplicative order of 5 (mod p) a power of 2 when p = 5*2^k + 1. The primes p = 11 = 5*2^1 + 1, 41 = 5*2^3 + 1, and 40961 = 5*2^13 + 1 provide counterexamples. I am sure there are known criteria for when 5 is a quintic residue (mod p), but I am too lazy to look them up. It is possible (AFAIK) that the multiplicative order of 5 (mod p) is a power of 2 for other prime factors k*2^n + 1 (k odd), of composite Fermat numbers, but, apart from the known prime factors of Fermat numbers up to F23, I haven't checked them.
2019-10-18, 06:09   #4
miket

May 2013

32 Posts

Quote:
 Originally Posted by Dr Sardonicus First, I don't understand why n = 3 isn't on the list.

'If odd part of o,m and k is 1 and k divide n-1' should be: 'If o,m and k in the set {2,4,8,...} and k divide n-1'.

 2019-10-19, 12:16 #5 Dr Sardonicus     Feb 2017 Nowhere 123368 Posts I checked p = 5*2^23473 + 1; it didn't take nearly as long as I had feared it would. It's on the list.
 2019-10-21, 20:20 #6 Dr Sardonicus     Feb 2017 Nowhere 123368 Posts This topic inspired me to formulate a hypothesis. I checked some of the primes p = q*2^n + 1 which divide Fm = 2^(2^m) + 1, where q is an odd prime. In every case I checked, it was true that Mod(q,p)^2^n = Mod(1,p) [that is, that q is a q-th power residue (mod p)]. I suspect this might always be true when q is an odd prime (my hypothesis), but don't see an obvious proof. Before trying to prove it myself (assuming it's not already known), I tried checking to make sure there weren't any obvious counterexamples. If somebody knows (of) a proof, please point me in the right direction. Meanwhile... I have counterexamples for composite odd q, where the prime p = q*2^n + 1 divides 2^(2^m) + 1, but Mod(q,p)^(2^n) is not Mod(1,p). I also have counterexamples for p = 5*2^n + 1 which do not divide Fermat numbers; the smallest is p = 11: Mod(5, 11)^2 = Mod(3,11), not Mod(1,11). The following list, culled from a web page, is of triples [m, q, n] where p = q*2^n + 1 divides 2^(2^m) + 1, and q is prime. Code: v=[[5, 5, 7], [12, 7, 14], [12, 397, 16], [12, 17353230210429594579133099699123162989482444520899, 15], [18, 13, 20], [19, 33629, 21], [19, 8962167624028624126082526703, 22], [23, 5, 25], [25, 48413, 29], [36, 5, 39], [38, 3, 41], [55, 29, 57], [71, 683, 73], [73, 5, 75], [81, 271, 84], [117, 7, 120], [125, 5, 127], [144, 17, 147], [172, 20569603303, 174], [207, 3, 209], [228, 29, 231], [251, 85801657, 254], [284, 7, 290], [316, 7, 320], [416, 38039, 419], [547, 77377, 550], [556, 127, 558], [579, 63856313, 581], [637, 11969, 643], [642, 52943971, 644], [744, 17, 747], [1945, 5, 1947], [2023, 29, 2027], [2089, 431, 2099], [3056, 3370842847, 3058], [3310, 5, 3313], [3723, 13308899, 3725], [4724, 29, 4727], [5320, 21341, 5323], [6537, 17, 6539], [6835, 19, 6838], [9448, 19, 9450], [14276, 157, 14280], [18749, 11, 18759], [23288, 19, 23290], [23471, 5, 23473], [30256, 121531, 30260], [48624, 28949, 48627], [79221, 6089, 79223], [95328, 7, 95330], [114293, 13, 114296], [125410, 5, 125413], [138557, 7333, 138560], [157167, 3, 157169], [213319, 3, 213321], [287384, 211, 287388], [303088, 3, 303093], [382447, 3, 382449], [472097, 89, 472099], [585042, 151, 585044], [617813, 659, 617815], [960897, 11, 960901], [1494096, 131, 1494099], [2145351, 3, 2145353], [2167797, 7, 2167800], [2478782, 3, 2478785], [3329780, 193, 3329782]] I only checked up to [95328, 7, 95330]. The checking... ... was... ... ... ... ... ... ... ... ... getting... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... slow. I would appreciate it if someone could check whether (Mod(q,p)^(2^n) = Mod(1,p) for the ones with larger m. Last fiddled with by Dr Sardonicus on 2019-10-21 at 21:07 Reason: infxig sytpo

 Similar Threads Thread Thread Starter Forum Replies Last Post devarajkandadai Miscellaneous Math 3 2020-12-01 22:08 sweety439 And now for something completely different 17 2017-06-13 03:49 roger Puzzles 16 2006-10-18 19:52 adpowers Lounge 40 2004-08-12 22:05 Xyzzy Lounge 18 2002-10-30 21:54

All times are UTC. The time now is 08:15.

Wed Jan 19 08:15:48 UTC 2022 up 180 days, 2:44, 0 users, load averages: 1.38, 1.28, 1.24