Well, I have a positive integer $n$ that only contain the digits $1$ and $0$. Besides that I have a positive integer $k$, which must have a last digit equal to $1,3,7$ or $9$. Solve the equation below:
$$k=\gcd\left(n,\text{digitreverse}\left(n\right)\right)\tag1$$
Where $\text{digitreverse}\left(\cdot\right)$ reverses the digits of $n$.
So for example when $n=10100101$ we get $\text{digitreverse}\left(10100101\right)=10100101$.
Edit: I do not really have a way of solving this. I only found two solutions by hand (which I do not know are the only solutions possible):
- When $k=9$, we find $n=1011111111$;
- When $k=17$, we find $n=11111110010111111111$.
We call $"n"$ a good number if $n$ contains only the digits $0$ and $1$.
We will show that the following proposition is true.
[Proposition]
For any positive integer $k>1$ with $\gcd(k,10)=1$, there exist infinitely many good numbers $n$ such that $k=\gcd\left(n,\text{digitreverse}\left(n\right)\right)$.
[Proof]
Since $\gcd(k,10)=1$, there exist infinitely many positive integers $e$ such that $10^e \equiv 1\pmod{k}$.
Since $k>1$ is an odd number, we can take $s \in \mathbb{N}$ such that $k=2s+1$.
Set $n = -10^{se} + \sum_{i=0}^{k}10^{ie}$.
Then $m:=\text{digitreverse}\left(n\right) = -10^{(s+1)e} + \sum_{i=0}^{k}10^{ie}$.
Set $d = \gcd(m,n) = \gcd(m,n-m)$.
Since $n-m = 10^{se}(10^e-1)$ and $\gcd(d,10)=1$, we have $10^e \equiv 1\pmod{d}$.
So we have $0 \equiv n \equiv -1 + \sum_{i=0}^{k}1 = k \pmod{d}$, which implies $k \geq d$.
Since $10^e \equiv 1\pmod{k}$, we also have $n \equiv m \equiv 0 \pmod{k}$, which implies $d \geq k$.
Since $k \geq d$ and $d \geq k$, we must have $k=d$.
So we can say that $k=\gcd\left(n,\text{digitreverse}\left(n\right)\right)$.
$\blacksquare$