mersenneforum.org Maximum number of consecutive integers where the product is 1 (mod n).
 Register FAQ Search Today's Posts Mark Forums Read

 2017-02-13, 05:54 #1 carpetpool     "Sam" Nov 2016 5068 Posts Maximum number of consecutive integers where the product is 1 (mod n). Let f(n) be the maximum number of consecutive integers in a row, such that the number of consecutive integers from 1 <= k <= f(n), there exists a product of k consecutive integers that is 1 (mod n). f(3) = 1 since there is at most 1 consecutive integer that is 1 (mod 3). The product of more than 1 consecutive integer cannot be 1 (mod 3). f(11) = 3 since there are at most 3 consecutive integers that the product is 1 (mod 11). There is 1 integer that is 1 (mod 11), which is x = 1 There are 2 conservative integers x, x+1 such that their product is 1 (mod 11), x = 3, and x = 7. There are 3 consecutive integers x, x+1, x+2 such that their product is 1 (mod 11), x = 5. There are no 4 consecutive integers x, x+1, x+2, x+3 such that their product is 1 (mod 11), so f(11) = 3. Edit: The same goes for n = 19. There are k = 1, 2, 3, and 5 consecutive integers such that their product is 1 (mod 19), but there are no 4 consecutive integers such that their product is 1 (mod 19), so f(19) = 3. Are there any interesting records for finding f(n) being extraordinarily large compared to most f(n)? Thanks for looking into this. Last fiddled with by carpetpool on 2017-02-13 at 05:58
2017-02-13, 09:10   #2
LaurV
Romulan Interpreter

Jun 2011
Thailand

22·17·139 Posts

Quote:
 Originally Posted by carpetpool There are 2 conservative integers x, x+1 such that their product is 1 (mod 11), x = 3, and x = 7.
Ok, so the integers 3 and 7 are conservative. Not clear if republican or democrats....
What other integers are conservative?

[edit, sorry if it looked funny for me, but this seems trivial, for any prime p, see Wilson's theorem, product of all numbers smaller than p is -1 (mod p), therefore, letting apart p-1, which is -1 (mod p), you have the product of all the other is 1 (mod p), therefore f(11)=9, f(19)=17, etc. f(p)=p-2. Indeed 1*2*3*4*5*6*7*8*9=9!=362880=1 mod (11). Then, for f(n) even, the negatives (mod n) are always a solution (in your example, 7=-4 mod 11, and 8=-3 mod 11) because signs compensate, so 3*4=(-3)*(-4)=7*8 (mod 11)]

Last fiddled with by LaurV on 2017-02-13 at 09:25

2017-02-13, 12:42   #3
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

20C016 Posts

Quote:
 Originally Posted by LaurV Ok, so the integers 3 and 7 are conservative. Not clear if republican or democrats.... What other integers are conservative? [edit, sorry if it looked funny for me, but this seems trivial, for any prime p, see Wilson's theorem, product of all numbers smaller than p is -1 (mod p), therefore, letting apart p-1, which is -1 (mod p), you have the product of all the other is 1 (mod p), therefore f(11)=9, f(19)=17, etc. f(p)=p-2. Indeed 1*2*3*4*5*6*7*8*9=9!=362880=1 mod (11). Then, for f(n) even, the negatives (mod n) are always a solution (in your example, 7=-4 mod 11, and 8=-3 mod 11) because signs compensate, so 3*4=(-3)*(-4)=7*8 (mod 11)]
and any n-powersmooth number has a maximum of n-1 for the length.

Last fiddled with by science_man_88 on 2017-02-13 at 12:46

 2017-02-13, 14:24 #4 science_man_88     "Forget I exist" Jul 2009 Dumbassville 26×131 Posts sorry double posting: it can be brought down to a prime power situation, with n= p1^k * p2^j for example we get that we can limit it to numbers less than the greatest power needed to sum to the exponents ex. 18=2*3^2 and the value must stay under 9 27=3^3 but the value must still stay under 9 because 3=2+1 so 3^2*3^1 =3^3 and hence anything at or above 9 falls to the 0 product rule. 81=3^4 and 6=3+2+1 so 3^1*3^2*3^3 >3^4 and is divisible by it so no length greater than 3^3-1 is possible to use as then the product contains all prime powers dividing into n 225=3^2 *5^2 but no length greater than 24 should work in theory because then you have all the prime powers that divide 225 in there. Last fiddled with by science_man_88 on 2017-02-13 at 14:48
2017-02-13, 16:00   #5
carpetpool

"Sam"
Nov 2016

32610 Posts

Quote:
 Originally Posted by LaurV Ok, so the integers 3 and 7 are conservative. Not clear if republican or democrats.... What other integers are conservative? [edit, sorry if it looked funny for me, but this seems trivial, for any prime p, see Wilson's theorem, product of all numbers smaller than p is -1 (mod p), therefore, letting apart p-1, which is -1 (mod p), you have the product of all the other is 1 (mod p), therefore f(11)=9, f(19)=17, etc. f(p)=p-2. Indeed 1*2*3*4*5*6*7*8*9=9!=362880=1 mod (11). Then, for f(n) even, the negatives (mod n) are always a solution (in your example, 7=-4 mod 11, and 8=-3 mod 11) because signs compensate, so 3*4=(-3)*(-4)=7*8 (mod 11)]
For prime p, f(p) = p-2 if and only if there are 1, 2, 3,... p-1, AND p consecutive integers such that the product is 1 (mod p).
For instance,

f(11) would be 9 if there were 1, 2, 3, 4, 5, 6, 7, 8, AND 9 consecutive integers such that

k = 1 (mod 11)
k*(k+1) = 1 (mod 11)
k*(k+1)*(k+2) = 1 (mod 11)
k*(k+1)*(k+2)*(k+3) = 1 (mod 11)
...
k*(k+1)*(k+2)*(k+3)*(k+4)*(k+5)*(k+6)*(k+7)*(k+8) = 1 (mod 11)

But no solution to k*(k+1)*(k+2)*(k+3) = 1 (mod 11) exists which is where the pattern stops, and why f(11) = 3. It's hard to get the idea first of this, but interesting.

Last fiddled with by carpetpool on 2017-02-13 at 16:02

2017-02-13, 16:09   #6
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by carpetpool For prime p, f(p) = p-2 if and only if there are 1, 2, 3,... p-1, AND p consecutive integers such that the product is 1 (mod p). For instance, f(11) would be 9 if there were 1, 2, 3, 4, 5, 6, 7, 8, AND 9 consecutive integers such that k = 1 (mod 11) k*(k+1) = 1 (mod 11) k*(k+1)*(k+2) = 1 (mod 11) k*(k+1)*(k+2)*(k+3) = 1 (mod 11) ... k*(k+1)*(k+2)*(k+3)*(k+4)*(k+5)*(k+6)*(k+7)*(k+8) = 1 (mod 11) But no solution to k*(k+1)*(k+2)*(k+3) = 1 (mod 11) exists which is where the pattern stops, and why f(11) = 3. It's hard to get the idea first of this, but interesting.
my working out works as an upper bound of your request and can even be improved.edit: I got to my answer by generalizing what your request could mean ( though I did interpret it the same as LaurV to some extent) and then asking an opposing question. your request can be what is the maximal length where we are guaranteed to get a non-zero residue , asking the opposing question when do we get forced to have a 0 residue helped me through the math but there's a better answer for the maximal number of consecutive numbers needed for this to occur can you find it ?

Last fiddled with by science_man_88 on 2017-02-13 at 16:16

 2017-02-13, 16:34 #7 axn     Jun 2003 497010 Posts Checking all n <= 10000, here are the ones with f(n) >= 9 Code: 241:9 1721:9 2591:9 4159:9 4391:10 6271:10 8609:9 9049:9 9721:10 For 4391, here are the k values where it occurs Code: 4391:1:1 4391:2:891 4391:3:656 4391:4:211 4391:5:621 4391:6:275 4391:7:3510 4391:8:1147 4391:9:234 4391:10:2102 EDIT:- 7921 is the only composite < 10000 with f(n) > 3. f(7921)=5 Code: 7921:1:1 7921:2:1255 7921:3:550 7921:4:2003 7921:5:3545 EDIT2:- All prime n between 1e4 and 1e5 with f(n)>=9 Code: 10159:11 14431:10 15241:10 19249:9 23399:9 25849:9 27239:10 27329:9 28921:9 29599:9 30839:10 31159:9 33049:9 33311:13 <-- 33769:9 35279:9 38281:13 <-- 39199:9 40751:9 42169:11 44249:9 46199:9 47599:10 52321:9 52369:9 52609:10 57559:9 58511:12 65111:9 66809:9 67391:9 67801:9 70009:11 70271:9 70639:12 75401:9 79631:9 85639:10 86929:11 89681:11 97001:9 Last fiddled with by axn on 2017-02-13 at 16:55
 2017-02-13, 16:34 #8 Dr Sardonicus     Feb 2017 Nowhere 29×157 Posts Greetings, forumites! If I understand the problem correctly, what is required is saying something intelligent about k = f(n), for which each of the k polynomials x - 1, x*(x - 1) - 1, ..., x*(...)*(x - (k -1)) - 1 has at least one linear factor (mod n). As has been pointed out, k < p, where p is the smallest prime factor of n. So, let us assume that n = p, a prime. In order than f(p) $\ge$ 2, we require that x^2 - x - 1 have a linear factor (mod p). This is true if p = 5, or p == 1 or -1 (mod 5). In order that f(p) $\ge$ 3, we require that, in addition, f3 = x^3 - 3*x^2 + 2*x - 1 have at least one linear factor (mod p). Now f3 is irreducible in Q[x], has Galois group S3, and discriminant -23. There are three cases in which f3 has at least one linear factor (mod p): (1) p = 23; (2) -23 is a quadratic non-residue (mod p); and (3) p = x^2 + 6*x*y + y^2, alternatively x^2 + 23*y^2 for integers x and y. The condition (3) is not describable with rational integer congruences, but is satisfied by (asymptotically) 1/6 of primes p. The situation becomes more complicated as the degree of the polynomial increases. The degree-4 polynomial has Galois group D4. An interesting problem! Thus endeth my first post.
 2017-02-13, 22:17 #9 Dr Sardonicus     Feb 2017 Nowhere 107118 Posts Due to my atrocious typing skills, I mistyped condition (3) above, putting the coefficient 6 in the xy-term. The condition should be (3) p = x^2 + x*y + 6*y^2 or x^2 + 23*y^2. Also, for p = 321721, f(p) = 15. BTW, it is obvious that f(n) $\ge$ k if and only if f(P) $\ge k$ for each prime (power) factor P of n. Use CRT to cobble together solutions for the various P. (Apparently I was too late to edit the earlier post.) Last fiddled with by Dr Sardonicus on 2017-02-13 at 22:31 Reason: Forgot BTW comment; testing editing function
 2017-02-14, 16:41 #10 Dr Sardonicus     Feb 2017 Nowhere 29·157 Posts On 2017-02-13 at 05:54, carpetpool asked Are there any interesting records for finding f(n) being extraordinarily large compared to most f(n)? Checking the requisite polynomials up to degree 25, and primes p < 2^26, I found all possible values of f(p) up to 23. There is an asterisk next to each prime p for which f(p) > f(q) for all primes q < p. That is as close to "extraordinarily large" as I can manage. The value f(p) = 1 first occurs for p = 2* The value f(p) = 2 first occurs for p = 29 The value f(p) = 3 first occurs for p = 5* The value f(p) = 4 first occurs for p = 199 The value f(p) = 5 first occurs for p = 89* The value f(p) = 6 first occurs for p = 1951 The value f(p) = 7 first occurs for p = 359 The value f(p) = 8 first occurs for p = 4721 The value f(p) = 9 first occurs for p = 241* The value f(p) = 10 first occurs for p = 4391* The value f(p) = 11 first occurs for p = 10159* The value f(p) = 12 first occurs for p = 58511 The value f(p) = 13 first occurs for p = 33311* The value f(p) = 14 first occurs for p = 365369 The value f(p) = 15 first occurs for p = 321721* The value f(p) = 16 first occurs for p = 833479 The value f(p) = 17 first occurs for p = 551519* The value f(p) = 18 first occurs for p = 2738279 The value f(p) = 19 first occurs for p = 12778391 The value f(p) = 20 first occurs for p = 12051041 The value f(p) = 21 first occurs for p = 51398521 The value f(p) = 22 first occurs for p = 1847239* The value f(p) = 23 first occurs for p = 36748039* If anyone wants to push the computations further, they can have at it. The approach of determining explicitly the primes p for which each requisite polynomial has at least one linear factor (mod p), is of limited utility for computations. However, it is theoretically helpful: Assuming the polynomials are all irreducible in Q[x] (a question I'm too lazy to consider beyond checking up to degree 300), then for each n, there will exist primes p for which the first n polynomials will not only have a linear factor (mod p), but will all split into distinct linear factors (mod p). Thus, it is theoretically clear that for each positive integer n, there are infinitely many primes p for which f(p) is at least n. Some additional conditions on the splitting fields of the polynomials (which I'm too lazy to formulate precisely), would insure that for each positive integer n, there are infinitely many primes p for which f(p) is exactly equal to n.
 2017-02-14, 20:47 #11 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 23×11×23 Posts I think this is one of the most interesting posts on this board.i do not have a complete grasp on the mechanics of it, but I think the problem is essentially analogous and as unpredictable (as well as, as predictable) as prime distribution. Basically it is a matter of different integer periods interfering (sieving) each other. Except that rather than 0 reminder we are noting reminders of 1.

 Similar Threads Thread Thread Starter Forum Replies Last Post TheMawn Other Mathematical Topics 4 2014-12-19 12:42 XYYXF Computer Science & Computational Number Theory 0 2014-12-05 17:32 literka Factoring 1 2012-01-03 09:50 mfgoode Puzzles 12 2007-07-24 09:43 Kees Puzzles 22 2006-07-30 15:33

All times are UTC. The time now is 00:27.

Wed May 19 00:27:32 UTC 2021 up 40 days, 19:08, 0 users, load averages: 1.99, 2.15, 1.99