# Solve system of inequalities modulo

Let $$p \in \mathbb{N}$$ be a composite number and let $$x, y$$ be vectors with elements from $$\mathbb{Z}_p$$ of some fixed length (in my case it's 39). How to find such $$k \in \mathbb{Z}_p$$ that the value below is minimized? $$\max(f(x + ky)))$$ Here, $$\max$$ is just maximum value of vector entries, while $$f$$ is the inclusion map from $$\mathbb{Z}_p$$ to $$\mathbb{Z}$$.

I'm looking for practical solutions. In my case $$k = 39$$ and $$p = 311^2 \cdot 313^2 \cdot 317^2 \cdot 331^2 \cdot 337^2 \cdot 347^2 \cdot 349^2 \cdot 353^2$$. The brute force search over all values of $$k$$ is impossible.

Another version of the problem is as follows:

Given $$0 \leq \nu < p$$, find $$k \in \mathbb{Z}_p$$ such that $$\max(f(x + ky))) < \nu$$

Is there any clever approach to any of the problems?

As an addendum, here's example on what exact function I want to minimize. Let $$p = 10$$, $$k = 3$$. Here's example in Python:

p = 10
x = [4, 3, 8]
y = [1, 5, 0]
for v in range(p):
print(max([(e+v*f) % 10 for e, f in zip(x, y)]))


Output:

9 6 9 5 7 9 4 4 7 7


So here, we know that the minimum is at $$v = 6$$ or $$v = 7$$.

• @Macavity no, that's just my sloppiness in the code (sorry) – enedil Dec 30 '18 at 2:04