0

How come for any primes $x$ and positive integers $a,b \in \mathbb Z$ that $$( \text{value 1} \cdot a + b) \ \text{mod} \ x = ( \text{value 2} \cdot a + b) \ \text{mod} \ x$$ even when $\text{value 1} \neq \text{value 2}$? I can't find a correlation between them that can describe their relationship.

What relationship is there? How is this possible? Oh, and x is a prime number.

If you can, please give me a layman's answer. Half the stuff on this forum I'm not sure I fully understand, not for lack of intelligence, but for lack of familiarity with the nomenclature.

Andrew Tawfeek
  • 2,555
Mine
  • 127

2 Answers2

1

$p\mod x = q\mod x$ simply means $p-q$ is a multiple of x, so $p-q=k*x$ for some integer $k$.

So in your case we start with $(value1 * a + b)\mod x=(value2 * a + b)\mod x$ and get $(value1 * a + b) - (value2 * a + b) = k * x$, for some (unknown) integer $k$. This simplifies to $value1 - value2 = k * x / a$.

Since $x$ is prime, it simplifies the argument; $x$ either divides $a$ evenly or not. If $x$ divides $a$, then $a/x$ is an integer, and we get $value1 - value2 = k*x/a=k/(a/x)$. If $a$ doesn't divide $x$, then it must divide $k$ (because we know $value1 - value2$ is an integer), so $value1-value2=(k / a) * x$.

So if $x$ divides $a$, we can choose $k$ to get any value of $k/(a/x)$, so any choice of $value1$ and $value2$ are valid.

If $x$ doesn't divide $a$, then $k/a*x$ is an integer only when $k/a$ is an integer. So when $k/a * x$ is an integer, it is also a multiple of $x$. That means $value1$ and $value2$ must have a difference of some multiple of $x$.

8163264128
  • 111
0

This isn't true.

Counterexample: $$\left( \underset{\text{Value 1}}{3} \cdot \underset{a}2+\underset{b}3 \right) \ \text{mod} \ \underset{x}5 \neq \left(\underset{\text{Value 2}}4 \cdot \underset{a}2+\underset{b}3 \right) \ \text{mod} \ \underset{x}5$$

Andrew Tawfeek
  • 2,555