mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2017-02-13, 05:54   #1
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

5068 Posts
Exclamation 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
carpetpool is offline   Reply With Quote
Old 2017-02-13, 09:10   #2
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22·17·139 Posts
Default

Quote:
Originally Posted by carpetpool View Post
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
LaurV is offline   Reply With Quote
Old 2017-02-13, 12:42   #3
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

20C016 Posts
Default

Quote:
Originally Posted by LaurV View Post
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
science_man_88 is offline   Reply With Quote
Old 2017-02-13, 14:24   #4
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

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
science_man_88 is offline   Reply With Quote
Old 2017-02-13, 16:00   #5
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

32610 Posts
Post

Quote:
Originally Posted by LaurV View Post
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
carpetpool is offline   Reply With Quote
Old 2017-02-13, 16:09   #6
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by carpetpool View Post
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
science_man_88 is offline   Reply With Quote
Old 2017-02-13, 16:34   #7
axn
 
axn's Avatar
 
Jun 2003

497010 Posts
Default

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
axn is offline   Reply With Quote
Old 2017-02-13, 16:34   #8
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

29×157 Posts
Default

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.
Dr Sardonicus is offline   Reply With Quote
Old 2017-02-13, 22:17   #9
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

107118 Posts
Default

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
Dr Sardonicus is offline   Reply With Quote
Old 2017-02-14, 16:41   #10
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

29·157 Posts
Default

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.
Dr Sardonicus is offline   Reply With Quote
Old 2017-02-14, 20:47   #11
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

23×11×23 Posts
Default

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.
a1call is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Sums of consecutive integers TheMawn Other Mathematical Topics 4 2014-12-19 12:42
Consecutive p-smooth integers XYYXF Computer Science & Computational Number Theory 0 2014-12-05 17:32
F5=4294967297 is a product of two integers. literka Factoring 1 2012-01-03 09:50
Consecutive integers. mfgoode Puzzles 12 2007-07-24 09:43
On consecutive integers 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.