1
$\begingroup$

This problem is inspired by the linked question about a recurrence (at the end of this post).

Is there a way to solve for all solutions to the following system?

$$(*)\begin{cases} x_{1}x_{2}&\bmod (x_{1}+x_{2})&=x_{3}\\ x_{2}x_{3}&\bmod (x_{2}+x_{3})&=x_{4}\\ x_{3}x_{4}&\bmod (x_{3}+x_{4})&=x_{5}\\ &\dots&\\ x_{n-2}x_{n-1}&\bmod (x_{n-2}+x_{n-1})&=x_{n}\\ x_{n-1}x_{n}&\bmod (x_{n-1}+x_{n})&=x_{1}\\ x_{n}x_{1}&\bmod (x_{n}+x_{1})&=x_{2} \end{cases}$$

Where we want to find all such $x_1,\dots,x_n\in\mathbb N$ for some $n\ge 2$.

Or perhaps, this is too hard to be solved in general?

In that case, what can we say about this system and its solutions? Below are my observations.


Generally, if $(x_1=x_2=\dots=x_n=a,a\in\mathbb N)$, then we have:

$$ a^2\bmod 2a=\begin{cases}0,& 2\mid a\\a,& 2\not\mid a\end{cases} $$

Giving the "trivial solution" $(x_1,\dots,x_n)=(a,\dots,a),a=2k-1,k\in\mathbb N$ in this case.

So from now on assume otherwise (at least one $x_i,i=1,\dots,n$ is distinct), to obtain "non-trivial solutions" to the system.

Notice that "repeating" a solution of smaller $n$ gives a solution for larger $n$. For example, if $(a,b,c)$ is one solution to $n=3$, then $(a,b,c,a,b,c)$ is one solution to $n=6$. Let these solutions be called "repeated solutions".

From now on, we are interested in nontrivial solutions (are not "trivial" and are not "repeated").

If there aren't any additional trivial solutions to classify, then my question is,

Are there ways to obtain families of nontrivial solutions for arbitrary fixed $n$ cases?


If $n=2$, then we have:

$$\begin{cases} x_{1}x_{2}\bmod (x_{1}+x_{2})&=x_{1}\\ x_{2}x_{1}\bmod (x_{2}+x_{1})&=x_{2} \end{cases} \\\iff\\ x_{1}x_{2}\bmod (x_{1}+x_{2})=x_{1}=x_{2} $$

Which clearly does not have any additional solutions, other than the "trivial solution"


For $n=3$, we have the system:

$$\begin{cases} x_{1}x_{2}\bmod (x_{1}+x_{2})&=x_{3}\\ x_{2}x_{3}\bmod (x_{2}+x_{3})&=x_{1}\\ x_{3}x_{1}\bmod (x_{3}+x_{1})&=x_{2} \end{cases} $$

Notice that if $(x_1,x_2,x_3)=(a,b,c)$ is a solution, then all of the (up to six) permutations of $(a,b,c)$ are also solutions. Hence, here we search for "non-trivial solutions" in form of sets either as $S=\{a,b,c\}$ or $S=\{a,b\}$, where then actual solutions are given as $x_1,x_2,x_3\in S$.

By brute force I've found all solutions for $a,b,c\le 1000$ to be:

$$\{5,7,11\},\{69,99,111\},\{87,111,153\},\{125,475,575\},\{184,704,776\},\{315,525,735\},\{324,756,864\},\{335,365,475\},\{391,575,713\}$$

There are presumably infinitely many more?

How can we solve for all solutions for this $n=3$ case of the system?


For $n\ge 4$, similarly as in $n=3$, I'm not sure how to solve for all solutions.

For $n\ge 4$, if $(x_1,x_2,\dots,x_n)$ is a solution, then $(x_2,\dots,x_n,x_1),(x_3,\dots,x_n,x_1,x_2),$ $\dots$ $,(x_n,x_1,\dots,x_{n-1})$ are also solutions. Hence, we can search for nontrivial solutions in forms of sets $S=\{x_1,\dots,x_n\}$ where each $S$ represents up to $n$ solutions. (Note that we allow duplicate elements in this set, and that it is ordered since solutions are obtained from it by shifting all of its elements one by one step.)

For example, for $n=4$, one such $S$ is: $\{128,192,256,320\}$, representing four solutions: $(128,192,256,320),(192,256,320,128),(256,320,128,192),(320,128,192,256)$.

Is it possible to solve for all such solution sets $S$ for given $n\ge 4$?


It appears that solution sets $S$ do exist for arbitrarily large $n$.

One way to obtain random solutions for random $n$, is to iterate the following recursion...

$$ \begin{equation} f_k(c_1,c_2)=f_k=\begin{cases} c_1, & k=1.\\ c_2, & k=2.\\ f_{k-1}f_{k-2} \mod[f_{n-1}+f_{n-2}], & n>2. \end{cases} \end{equation} $$

(This recursion has been discussed here.)

...for random cases of $(c_1,c_2)$, until it enters a cycle (becomes periodic). The obtained cycle is a solution to the system $(*)$ (and hence is generated by corresponding solution set $S$).

For example, choosing $(c_1,c_2)=(137,147)$, the $f_k$ will enter the cycle (at $k=10$): $$f_{k\ge10}(137,147)=\{147,259,315,77,343,371,161\}=S$$ That cycle represents one $S$ that is one solution set for $n=|S|=7$.

Another example, iterating $f_k(189,962)$ gives a length-$18$ cycle (we enter the cycle at $k=48$), which then represents one solution set $S$ for $n=18$.

Now, notice that if $x_1,x_2$ are a part of a solution $(x_1,x_2,\dots,x_n)$ to the system $(*)$, then $f_k(x_1,x_2)$ would generate the remaining corresponding $x_3,x_4,\dots,x_n$ values at $k=3,4,\dots,n$, and start repeating all of them for all following $k\gt n$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.