solution mod 999999999 = 0

Everything about Sudoku that doesn't fit in one of the other sections

solution mod 999999999 = 0

Postby dobrichev » Wed Sep 02, 2026 10:36 am

Conjecture: Every Sudoku solution, represented as a number, is divisible by 999999999 without remainder.
dobrichev
2016 Supporter
 
Posts: 1897
Joined: 24 May 2010

Re: solution mod 999999999 = 0

Postby blue » Thu Sep 03, 2026 2:03 am

Amazing :!:

These might be valid too:

1) For NxN latin squares with odd N and "digits" either (1,...,N) or (0,...,N-1), the N*N-digit base N+1 number with digits taken from the grid,
is divisible by the N-digit base (N+1) number where each digit is N. Example: 9x9 grid, base 10 -> divisible by 999999999 (base 10).

2) For NxN latin squares with even N and "digits" (0,...,N-1), the N*N-digit base N number with digits taken from the grid,
is divisible by the N-digit base N number where each digit is (N-1). Example: 10x10 grid, base 10 -> divisible by 9999999999 (base 10).

They were valid for 100000 random latin squares each, for sizes N=1,2,...,26.
blue
 
Posts: 1121
Joined: 11 March 2013

Re: solution mod 999999999 = 0

Postby coloin » Thu Sep 03, 2026 10:39 am

Wow ... nice conjecture

prime factorizing 999999999 ... you get 3^4 × 37 × 333667

We can easily prove its divisible by 9 because each row always adds up to 45 ..so it will always be divisible by 9

not sure how to prove the second 9

There are block rules for 37 and 111 which looks like it will be extendable to 999 [9x111]
Code: Select all
The 3-Digit Grouping Rule
For larger numbers, it is often faster to use the base-1000 grouping method because 999 is a multiple of 37  (37x27 = 999)
Split the number into groups of three digits starting from the right.
Add all these 3-digit groups together.
If the sum is still large, repeat the addition.If the final sum is divisible by 37, the original number is divisible by 37.

Not sure about 333667 though !
coloin
 
Posts: 2717
Joined: 05 May 2005
Location: Devon

Re: solution mod 999999999 = 0

Postby dobrichev » Thu Sep 03, 2026 1:32 pm

Congratulations to Blue for his wonderful generalization!

The applicability to Latin Squares of any size makes it unlikely that the conjecture is new. However, I can't find anything similar on the web.
If it is indeed new, I think it deserves popularization.

Of the factors for N=9, 3 * 333667 = 001001001 and may act as a mask.
dobrichev
2016 Supporter
 
Posts: 1897
Joined: 24 May 2010

Re: solution mod 999999999 = 0

Postby dobrichev » Thu Sep 03, 2026 3:23 pm

Likely the conjecure can be further relaxed.

For 9 digit, a number is divisible by 999999999 if it is
sum(n=1..9 (sum(c=0..8 n*10^(9*r+c))) where r is an arbitrary natural number, which may be different for each of the addends.

Row doesn't matter, each digit must occur exactly once at each column.
So, Latin square and Sudoku are just special compact square cases.

Below are some examples, all divisible by 999999999.
Code: Select all
111111111
222222222
333333333
444444444
555555555
666666666
777777777
888888888
999999999 // canonical

222222222
111111111
333333333
444444444
555555555
666666666
777777777
888888888
999999999 // rows 1 and 2 exchanged

111111111
222222229
333333333
444444444
555555555
666666666
777777777
888888888
999999992 // rightmost 2 and 9 exchanged

111111111
222222222
333333333
444444444
000000000
555555555
666666666
777777777
888888888
999999999 // extra row with 0

111111111
222222222
333333333
000044444
444400000
555555555
666666666
777777777
888888888
999999999 // extra 0 spread in two rows
dobrichev
2016 Supporter
 
Posts: 1897
Joined: 24 May 2010

Re: solution mod 999999999 = 0

Postby Serg » Thu Sep 03, 2026 5:27 pm

Hi, people!
It looks like I've found proof for the Latin Square case.
Let's consider an example of 9x9 LS with 1..9 digits. 81-digit "LS number" can be presented as sum: "72-digit number" x 10^9 + "9-digit LS last row".

Because (A + B) mod C = ((A mod C) + (B mod C)) mod C,
"LS number" mod 999999999 = ((("72-digit number" x 10^9) mod 999999999) + ("9-digit LS last row" mod 999999999)) mod 999999999.

("72-digit number" x 10^9) mod 999999999 = ("72-digit number" x (999999999+1)) mod 999999999 = "72-digit number" mod 999999999.

We'll continue 9 times such transformation, coming to "63-digit number", "54-digit number", etc. At finish we'll have:
"LS number" mod 999999999 = (("9-digit LS row1" mod 999999999) + ("9-digit LS row2" mod 999999999) + ... + ("9-digit LS last row" mod 999999999)) mod 999999999

"9-digit LS last row" is less than 999999999, so ("9-digit LS last row" mod 999999999) = "9-digit LS last row". Similarly
"9-digit LS row1" mod 999999999 = "9-digit LS row1", etc.

"LS number" mod 999999999 = ("9-digit LS row1" + "9-digit LS row2" + ... + "9-digit LS last row") mod 999999999

"9-digit LS row1" + "9-digit LS row2" + ... + "9-digit LS last row" = 45 x 111111111 = 5 x 999999999

(5 x 999999999) mod 999999999 = 0.

Serg
Serg
2018 Supporter
 
Posts: 930
Joined: 01 June 2010
Location: Russia

Re: solution mod 999999999 = 0

Postby blue » Thu Sep 03, 2026 5:33 pm

dobrichev wrote:Row doesn't matter, each digit must occur exactly once at each column.

Nice observation.

It makes the conjectures easy to prove.
I can add one more "latin squares" case:

3) For NxN latin squares with even N and "digits" (1,...,N), the N*N-digit base N+2 number with digits taken from the grid,
is divisible by the N-digit base N+2 number where each digit is (N+1). Example: 8x8 grid, base 10 -> divisible by 99999999 (base 10).

If the digits are (0,1,...,N-1), and the "base", B, satisfies "N*(N-1)/2 is a multiple of (B-1)", then it's true.
-- odd N => B = N+1 works, even N => B = N works.
If the digits are (1,...,N), and the "base", B, satisfies "N*(N+1)/2 is a multiple of (B-1)", then it's true.
-- odd N => B = N+1 works, even N => B = N+2 works.

dobrichev wrote:The applicability to Latin Squares of any size makes it unlikely that the conjecture is new. However, I can't find anything similar on the web.
If it is indeed new, I think it deserves popularization.

Indeed.

@Serg - Sorry I stepped on your post. It came up while I was preparing this one. Looking forward to reviewing your proof ...
blue
 
Posts: 1121
Joined: 11 March 2013

Re: solution mod 999999999 = 0

Postby Serg » Thu Sep 03, 2026 11:01 pm

Hi!
Some addition: if we treat "LS number" as decimal number, then "LS 8x8 number" (number range: 1..8), "LS 9x9 number" (0..8), "LS 9x9 (1..9) and "LS 10x10 number" (0..9) are always divisible by 99...9 (N "9" digits).

Serg

[Edited. I corrected a typo.]
Last edited by Serg on Fri Sep 04, 2026 12:25 pm, edited 2 times in total.
Serg
2018 Supporter
 
Posts: 930
Joined: 01 June 2010
Location: Russia

Re: solution mod 999999999 = 0

Postby dobrichev » Fri Sep 04, 2026 10:15 am

Hi Serg,
After rereading your proof several times, I consider the proof to be correct.
dobrichev
2016 Supporter
 
Posts: 1897
Joined: 24 May 2010

Re: solution mod 999999999 = 0

Postby JPF » Fri Nov 06, 2026 9:22 pm

Hi everyone,

After several years away from the forum, I came across this thread by chance and found it very interesting. Working on it with Claude (Anthropic's AI), I found a few complements. The proofs are short; I can send the details to anyone interested.

Setting (blue's): an NxN Latin square, rows written one after another as the digits of a number X in base B, and M = B^N - 1 (so M = 999999999 for Sudoku).

1) Modulo (B-1)*M, all Latin squares on the same symbols leave the SAME remainder, for every N and every B, and this remainder can be written down explicitly.
Why: each symbol d marks a permutation matrix P_d (one cell per row and per column), and X = sum of d*P_d. Every permutation matrix, read as a number, leaves the same remainder modulo (B-1)*M.
Two by-products:
- Modulo M only the columns matter (Mladen's remark); modulo (B-1)*M the rows matter too.
- M divides X exactly when B-1 divides the sum of the symbols: blue's condition is necessary as well as sufficient.

2) (B-1)*M cannot be improved: no larger number gives all Latin squares the same remainder, for every N except N = 3.
The proof builds two Latin squares whose last two rows differ only by swapping two neighbouring symbols. For N = 3 this is impossible, and indeed for 3x3 squares a number three times larger works when 3 divides B-1 (for instance in base 10, all twelve 3x3 squares on 1,2,3 leave remainder 18648 modulo 26973).

3) The Sudoku case (N = 9, base 10, digits 1..9): X/999999999 always leaves remainder 5 when divided by 9.
In other words, X mod 8999999991 = 4999999995 for every grid. Consequences:
- X is divisible by 81 (coloin's "second 9", already contained in the conjecture), but never by 243.
- X is never divisible by 3*999999999, nor by 999999999^2.
Mladen's own relaxed examples show that the rows matter here: they are all divisible by M, but X/M mod 9 is 5, 0 or 7 depending on the example.

4) 9*999999999 is the best possible even for Sudoku grids alone. Sudokus are a smaller family than Latin squares, so they might have had a larger common modulus - they don't. These three grids (solutions of 17-clue puzzles) have differences whose gcd is exactly 8999999991:
Code: Select all
A = 123456789456789123789123456214368597867945231935217864348672915591834672672591348
B = 123456789456789123789123456214378695867295341935641872348962517591837264672514938
C = 123456789456789123789123465214368597637594812895217346368971254571642938942835671


5) A last curiosity: a Sudoku number is never divisible by 1000000001 (hence never by eighteen 9's).

JPF
JPF
2017 Supporter
 
Posts: 6152
Joined: 06 December 2005
Location: Paris, France


Return to General