Problems & Puzzles: Puzzles

Puzzle 1076 Set of integers N, 1<N<S such that...   Giorgos Kalogeropoulos, sent the following interesting puzzle: For every positive integer N with  1 < N < S, we are interested in those N such that when N^2 is divided by S, leaves a remainder 1. These N form a list {N1,N2,...Nk}. We are searching for S such that all terms of the list are primes. e.g. S=8 -> {3,5,7} list of length 3 and all terms are primes.        S=24 -> {5,7,11,13,17,19,23} length 7 and all terms are primes.        S=123450 -> {19751,41149,60901,62549,82301,103699,123449} length 7 and all terms are primes.   Q1. What is the largest S of length 7 that you can find? Q2. Can you find an S of length greater than 7 or prove that it does not exist?

---

During the week 20-26 Feb, 2022, contributions came from Paul Cleary, Emmanuel Vantieghem, Michael Hürter, Gennady Gusev, Adam Stinchcombe

***

Paul wrote:

This is my Largest S of length 7.

5987250,  with the following primes:- {443501, 1903501, 2347001, 3640249, 4083749, 5543749, 5987249}.

There is a smaller one with an S of

449250, with the following primes:- {28751, 149749, 178501, 270749, 299501, 420499, 449249}.

The next length greater than 7 would be at 15, I couldn’t find an example with all 15 prime, the number S = 120 does have 12 of the 15 primes so I have no reason to think that 15 is impossible, though I do believe it to be quite a large number.

The lengths follow this formula:- 2^n - 1.

***

Emmanuel wrote:

My biggest  S  with seven prime "roots of unity" is : 201950042342 with primes {120687276301, 3188176399, 78074589643, 81262766041, 198761865943, 123875452699, 201950042341}.

To find more than seven prime "roots of unity" we need to find  15 (or 31, 63, ..., 2^u -1) prime solutions.

Perhaps that is too strong a condition.

The best result with the smallest S which I could obtain was for  S = 420 with  12  prime solutions of x^2 == 1 (mod S) : {29, 41, 71, 139, 181, 211, 239, 251, 281, 349, 379, 419}.

***

Michael wrote:

I found the following solution:

 

S = 300000000000001076556609810 -> {40000000000000143540881309, 60000000000000215311321961, 100000000000000358852203271,
200000000000000717704406539, 240000000000000861245287849, 260000000000000933015728501, 300000000000001076556609809} list of length 7 and all terms are primes.

***

Gennady wrote:

Another solution for Q1:

S=7392960 -> {2719,118081,161569,531521,575009,693089,695809}

For Q2: no solution.

***

Adam wrote:

I find 7 square roots of 1 mod m, except 1, which are all prime for    123450   (which has a curious, counting digital expansion)   and   285750
 

***