Znám's problem

Encyclopedia : Z : ZN : ZNM : Znám's problem

Znám's problem is the question of what sets of integers, of a given length, can be put together such that each integer in the set is a proper divisor of the product of the other integers in the set, plus 1. That is, given k, what sets of integers

are there, such that

[\prod_^n n_j + 1]

is divisible by each n_i, though not equal to it?

For k > 4, the answer is that there is at least one set for each k. For example, one solution to k = 5 is . A few calculations will show that

[3 \cdot 7 \cdot 47 \cdot 395 + 1 = 389866], which is divisible by 2,
[2 \cdot 7 \cdot 47 \cdot 395 + 1 = 259911], which is divisible by 3,
[2 \cdot 3 \cdot 47 \cdot 395 + 1 = 111391], which is divisible by 7,
[2 \cdot 3 \cdot 7 \cdot 395 + 1 = 16591], which is divisible by 47, and
[2 \cdot 3 \cdot 7 \cdot 47 + 1 = 1975], which is divisible by 395.

The requirement that each n_i be a proper divisor rather than just a divisor rules out the solutions for k < 5. For example, for k = 4 we can put together the set . If we multiply the first three terms and add 1, we get the last term, which is a divisor in a "trivial" sense.

The Slovak mathematician Štefan Znám is credited with being the first to ponder this problem, in 1972, (though it is possible that the ancient Egyptians also pondered this problem in connection with Egyptian fractions). A decade later, Qi Sun proved that there are infinitely many solutions to Znám's problem, and his proof involves the Sylvester's sequence, 2, 3, 7, 43, 1807, 3263443, 10650056950807, ... (sequence in OEIS).

However, for each individual k, there are fewer solutions: only two for k = 5, five for k = 6, fifteen for k = 7 and ninety-three for k = 8. Presently, a few solutions are known for k = 9 and k = 10, but it's not known how many total solutions there are left to be discovered. Also unknown is whether there are any solutions using only odd numbers. With one exception, all known solutions start with 2.

From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.