A natural integer N can be written as x mod p, for instance:(adsbygoogle = window.adsbygoogle || []).push({});

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

p=2 1 2 1 2 1 2 1 2 1 2 1 2

p=3 1 2 3 1 2 3 1 2 3 1 2 3

p=5 1 2 3 4 5 1 2 3 4 5 1 2

p=7 1 2 3 4 5 6 7 1 2 3 4 5

Etc.

The puzzle is quite difficult to state in this format but I'll have a go:

You choose any value x from each row of mod p (up to the maximum value of p, in the above case 7) and eliminate them. You have to find the minumum number N where it is impossible to eliminate all values of N.

Examples:

For p=2, the minimum N is 2. This is because eliminating any value of x (1 or 2), you will always have one remaining.

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

p=2 1 2

For p=3.

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

p=2 1 2 1

p=3 1 2 3

Having a minimum of N=3 would not work: if you chose x=1 in the p=2 row, you'd eliminate N=1 and N=3. Then you eliminate x=2 in the p=3 row and you eliminate them all.

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

p=2 1 2 1 2

p=3 1 2 3 1

Having a minimum of N=4 would work however. There is no combination of x you could use to eliminate all values of N. For instance, with x=1 in the p=2 row, you'd eliminate N=1 and N=3. Then whether you choose x=2 or x=1 on the p=3 row, you'd have one left. I.e N=4

For p=5.

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

p=2 1 2 1 2 1 2

p=3 1 2 3 1 2 3

p=5 1 2 3 4 5 1

I'll leave this to you, but you could try N=6. Try some combinations of x on each row. Is it possible to eliminate every value of N with N=6? (Answer is no :p)

The question is: how do you generalise this up to any p? E.g. how would you find out the minimum N needed when p = 41? What about when p = 211? Etc.

I've had a go, but it gets very tricky after a while trying to eliminate every value of N and finding all the combinations of x to use! I've started to make a program to do this for higher values of p!

Tell me if you need any clarifications / I haven't explained the problem properly

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Interesting modular arithmetic problem I found

Can you offer guidance or do you also need help?

Draft saved
Draft deleted

**Physics Forums | Science Articles, Homework Help, Discussion**