20170213, 05:54  #1 
"Sam"
Nov 2016
506_{8} 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 20170213 at 05:58 
20170213, 09:10  #2  
Romulan Interpreter
Jun 2011
Thailand
2^{2}·17·139 Posts 
Quote:
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 p1, 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)=p2. 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 20170213 at 09:25 

20170213, 12:42  #3  
"Forget I exist"
Jul 2009
Dumbassville
20C0_{16} Posts 
Quote:
Last fiddled with by science_man_88 on 20170213 at 12:46 

20170213, 14:24  #4 
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×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^31 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 20170213 at 14:48 
20170213, 16:00  #5  
"Sam"
Nov 2016
326_{10} Posts 
Quote:
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 20170213 at 16:02 

20170213, 16:09  #6  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 
Quote:
Last fiddled with by science_man_88 on 20170213 at 16:16 

20170213, 16:34  #7 
Jun 2003
4970_{10} 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 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 Code:
7921:1:1 7921:2:1255 7921:3:550 7921:4:2003 7921:5:3545 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 20170213 at 16:55 
20170213, 16:34  #8 
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 nonresidue (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 degree4 polynomial has Galois group D4. An interesting problem! Thus endeth my first post. 
20170213, 22:17  #9 
Feb 2017
Nowhere
10711_{8} Posts 
Due to my atrocious typing skills, I mistyped condition (3) above, putting the coefficient 6 in the xyterm. 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 20170213 at 22:31 Reason: Forgot BTW comment; testing editing function 
20170214, 16:41  #10 
Feb 2017
Nowhere
29·157 Posts 
On 20170213 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. 
20170214, 20:47  #11 
"Rashid Naimi"
Oct 2015
Remote to Here/There
2^{3}×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.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Sums of consecutive integers  TheMawn  Other Mathematical Topics  4  20141219 12:42 
Consecutive psmooth integers  XYYXF  Computer Science & Computational Number Theory  0  20141205 17:32 
F5=4294967297 is a product of two integers.  literka  Factoring  1  20120103 09:50 
Consecutive integers.  mfgoode  Puzzles  12  20070724 09:43 
On consecutive integers  Kees  Puzzles  22  20060730 15:33 