Unraveling the Modular Arithmetic Puzzle

[BicycleTree]

This is another puzzle that has to do with modular arithmetic (the other one that did was Picture Puzzle).

1
1 2
1 3 2 4
1 4 5 2 3 6
1 6 4 3 9 2 8 7 5 10

What's the next row?

 

[Rahmuss]

This is another puzzle that has to do with modular arithmetic (the other one that did was Picture Puzzle).

1
1 2
1 3 2 4
1 4 5 2 3 6
1 6 4 3 9 2 8 7 5 10

What's the next row?

Answer in white at bottom and side of possible missing row. Though I'm guessing it's not quite right... though hopefully on the right track.
Are you missing a row here?

1
1 2
1 3 2 4
1 4 5 2 3 6
0 0 0 0 0 0 0 0 - Missing Row? 1 5 3 7 2 6 4 8
1 6 4 3 9 2 8 7 5 10
1 7 8 4 5 11 2 9 3 10 6 12

 

[BicycleTree]

Nope, that's not it.

No, it's not missing a row. The row lengths are 1, 2, 4, 6, 10, 12, 16, 18...

 

[Rahmuss]

1
1 2
1 3 2 4
1 4 5 2 3 6
1 6 4 3 9 2 8 7 5 10
1 7 9 10 5 11 2 8 4 3 6 12 ?

The only ones I think I have correct for sure are :

1 7 0 0 0 0 2 0 0 0 6 12

Is that correct?

 

[BicycleTree]

Yes--those five numbers are are correct. You actually have several of the others correct, too, but you don't have the row.

 

[Rahmuss]

1 7 9 10 5 11 2 8 4 3 6 12

1
1 2
1 3 2 4
1 4 5 2 3 6
1 6 4 3 9 2 8 7 5 10
1 7 3 4 5 11 2 10 9 8 6 12

How about that?

I think these ones are correct for sure :

1 7 3 4 0 11 2 0 0 0 6 12

 

[BicycleTree]

1 7 3 4 0 11 2 0 0 0 6 12

No, not all of those are correct.

 

[AKG]

1 7 5 4 3 11 2 10 9 8 6 12

WARNING: Potential answer below.

The first number is 1
The last number is the greatest, and is 1 less than the next prime, e.g. the last line of the puzzle went up to 10, which is 1 less than 11. The next prime after 11 is 13, so the new line must go up to 12.
The second number, s, is such that 2s - 2 is the greatest number.
All the numbers are arranged such that if you made the list:
A1 A2 A3 ... An
where Ai is the position of i in the original list, you'll get back the original list.
The second last number is half the last number.
Whatever remains is "reversed." The example below will clarify
So, the next prime is 13, we start with:

1 2 3 4 5 6 7 8 9 10 11 12

7 is the number such that 2*7 - 2 = 12. So 7 must go in the second spot, and by the stuff with that A1 A2, ... we know that 2 must take the place 7 did, so we get:

1 7 3 4 5 6 2 8 9 10 11 12

The second last number must be half the last, so 6 and 11 switch places

1 7 3 4 5 11 2 8 9 10 6 12

Now the examples that preceeded this didn't really have enough numbers to tell us what to do with the rest of the numbers. The very last line, the one that goes up to 10, has 4 3 instead of 3 4 and 8 7 instead of 7 8, so I figure we just reverse those remaining numbers, so we get:

1 7 5 4 3 11 2 10 9 8 6 12

 

[BicycleTree]

Nice reasoning, AKG--yes, it is important that the length of each line is 1 less than a corresponding prime. But you don't have the answer. The answer is very simple, and has to do with modular arithmetic.

Also, here is a hint: consider writing the numbers 1 ... n above each line.

 

[Rahmuss]

I think I've got it.

1
1 2
1 3 2 4
1 4 5 2 3 6
1 6 4 3 9 2 8 7 5 10
1 7 5 4 3 11 2 10 9 8 6 12

What do you think? Want an explanation?

 

[quark]

1 7 10 9 8 11 2 5 4 3 6 12 ?

 

[AKG]

Also, here is a hint: consider writing the numbers 1 ... n above each line.

Oh, I see.

1 7 9 10 8 11 2 5 3 4 6 12

 

[AKG]

Some remarks:

Since multiplication modulo n is commutative, that's why the rule:

All the numbers are arranged such that if you made the list:
A1 A2 A3 ... An
where Ai is the position of i in the original list, you'll get back the original list.

holds. Obviously, the only element x such that x*1 = 1 (mod p) is x=1, which is the rule:

The first number is 1

holds. The last number is the number x such that x*(p-1) = 1 (mod p)

x*(p - 1) = xp - x (mod p)
= -x (mod p)
= 1 (mod p)

so x+1 = 0 (mod p), and clearly p-1 is the only x that satisfies this, which is why

The last number is the greatest

holds. I said that the second number was the number such that:

The second number, s, is such that 2s - 2 is the greatest number.

The greatest number is just p-1, so

2s - 2 = p - 1
2s = p + 1

so

2s = 1 (mod p)

Of course, the second number must be the s that satisfies 2s = 1 (mod p), since the pattern is that the kth number is the one that satisfies xk = 1 (mod p), so this is why that rule holds.

The last rule that might be right is:

The second last number is half the last number.

That would be 0.5(p-1). So, is 0.5(p-1) the unique element that will satisfy

0.5(p-1)(p-2) = 1 (mod p) ?

0.5(p-1)(p-2) = 0.5(p² - 3p + 2) (mod p)
= p(p - 3)/2 + 1 (mod p)

and (p-3)/2 is a natural number because p-3 is even, which is because p is odd, which is because it's prime. The exception is p=2, but in that case, we wouldn't be talking about the "p-2" position anyways. So (p-3)/2 = n, some natural number

= pn + 1 (mod p)
= 1 (mod p)

as desired.

The final rule I gave, that the remaining elements are just written backwards, was just wrong anyways.

 

[BicycleTree]

Right, AKG! In other words, the mth row is the ordered list of multiplicative inverses of the integers mod the mth prime, with the 0th element omitted from each list since it has no multiplicative inverse. The reason it's only mod _primes_ is that the integers mod nonprimes are not fields (do not have multiplicative inverses for every nonzero element).

 

[Rahmuss]

I thought for sure I had it; but I reversed some of the numbers I guess. I don't know as much about math as I'd like.