Given 2 functions $f(x)$ and $g(x)$ find a value where $g(x)$ divides $f(x)$ meaning $f(x) = 0 \mod g(x)$

Question

Problem:

Given 2 functions $f(x) = 2^{p-1} + x*p$ and $g(x) = 2 * x * p + 1$ find the values where $f(x) = 0 \mod{g(x)}$, where $p$ is a prime number and $x$ is a non negative integer in the range $1,2,3,4,5,6... \frac{2^{p-1} - 1}{p}$. In these examples the $p$ is fixed a priori, so it constitute a constant value.

Context:

I'm currently trying to come up with an efficient algorithm to determine when the function $g(x)$ divides $f(x)$ at the point x. In other words have a $f(x) = 0 \mod g(x)$.

For example:

If we set $p = 11$ then we have:

• $f(x) = 2^{10} + x * 11$
• $g(x) = 2 * x * 11 + 1$

So for $x = 1$ we have:

• $f(1) = 1024 + 11 = 1035$
• $g(1) = 2 * 1 * 11 + 1 = 23$

Then:

• $ f(1) = 0 \mod g(1) $
• $1035 = 0 \mod 23$

If $x = 2$ we have:

• $f(2) = 2^{10} + 2 * 11 = 1046$
• $g(2) = 2 * 2 * 11 + 1 = 45$

Finally:

• $ f(2) = 11 \mod g(2) $
• $1046 = 11 \mod 45$

And so on ... However, It doesn't matter how many divisor f(x) has I just need to know if it has any

So the set of values where $f(x) = 0 \mod g(x) = {23, ...}$

I don't really know how modular arithmetics work for functions, or if this is even possible. I have been looking for examples online but unfortunately, as soon as I put mod and function in a sentence the search engine comes up with something different.

Answer 1

Note that

$$f(x) \equiv 0 \pmod{g(x)} \; \Rightarrow \; 2f(x) \equiv 0 \pmod{g(x)} \tag{1}\label{eq1}$$

Thus,

$$2^p + 2xp \equiv 2^p + (2xp + 1) - 1 \equiv 2^p - 1 \equiv 0 \pmod{g(x)} \tag{2}\label{eq2}$$

With $p$ being a prime number, $2^p - 1$ is called a Mersenne number. When it's also a prime number, it's called a Mersenne prime. The Lucas-Lehmer primality test can relatively efficiently check if very large Mersenne numbers are prime, which is why the currently largest known primes are all Mersenne primes. Regarding checking for factors, I would suggest first checking against the List of known Mersenne primes since, if it's in the list, then $x$ is the last value, i.e., $x = \frac{2^{p-1} - 1}{p}$. Also, an answer at How to check if number is a Mersenne prime? has links to $2$ appropriate OEIS pages and a C# code sample with the values that fit into an unsigned integer in it. Otherwise, there are a few simple things you can do to simplify your checks, such as described at Factors of a Mersenne number.