6
$\begingroup$

(This is my very first question here! :-) ) So I encountered this fun problem yesterday and am feeling like sharing it with you. I almost solved it with the help of my computer but I guess there is a way to solve it without.

So the question is: find all the integer $a$ so that $a*99$ is equal to $1a1$. (The same number "$a$" between two 1)

This is what I've done so far (spoiler alert if you want to solve it all by yourself):


I quickly converted this equation into this one: $89*a -1 =10^n$ with $n$ equals to the number of numbers in $a$ plus one.

Then comes $a=(10^n +1)/89$

So now the problem is equivalent to finding the n so that $10^n +1$ can be divided by $89$. One can notice maybe that $89$ is a prime number. Fermat theorem gives us : $10^{88} -1 =0 [mod 89]$ but this doesn't seem to help :/

Conceptually speaking, I find difficult to convert those two ideas mathematically: -How searching integers solutions differs from searching any solutions. -How to use the fact that n is actually the number of numbers in $a$ plus one.

Hope you find the problem interesting and that some very bright solutions will come to your mind :-)

NB: using a computer, I have found some n that verify the equation but this is cheating somehow...

$\endgroup$
7
  • 1
    $\begingroup$ Welcome to the site ! $\endgroup$ Commented Sep 8, 2019 at 8:39
  • $\begingroup$ What does $1a1$ mean here? $\endgroup$ Commented Sep 8, 2019 at 8:39
  • $\begingroup$ I explained between parenthesis what it means but maybe I was not clear enough. If "a" is 333 for instance, 1a1 would be 13331. $\endgroup$
    – Jeanba
    Commented Sep 8, 2019 at 8:44
  • $\begingroup$ Really nice first question :) You can make your math formulas more readable with MathJax. Here is a tutorial: math.meta.stackexchange.com/questions/5020/… $\endgroup$
    – Botond
    Commented Sep 8, 2019 at 8:51
  • 1
    $\begingroup$ You need to find the smallest $n$ such that $10^n=1\mod 89$ such $n\mid 88$(n divides $88$). If such $n$ is divisible by $2$ then $10^{n/2}=-1\mod 89$ and $n/2$ is the smallest such $n$. otherwise the congruence $10^k=-1\mod 89$ has no solutions. $\endgroup$
    – kingW3
    Commented Sep 8, 2019 at 8:55

1 Answer 1

6
$\begingroup$

The observation that $10^{88}\equiv1\pmod{89}$ is very useful.

If $a$ is an $n$-digit number, the equation can be rewritten as $$ 99a=10^n+10a+1 $$ and so $$ a=\frac{10^n+1}{89} $$ so we need $10^n\equiv-1\pmod{89}$.

By Euler-Fermat, $10^{88}\equiv 1\pmod{89}$. Let's try and find the order of $10$ modulo $89$. We have $10^2\equiv11\pmod{89}$, $10^4\equiv32\pmod{89}$ and $10^{11}\equiv55\pmod{89}$, so $10^{44}\equiv1\pmod{89}$, but $10^{22}\equiv88\equiv-1\pmod{89}$. There's no need to look at $10^8$.

So the order is $44$ and we have also found a solution to $10^n\equiv-1\pmod{89}$, namely $n=22$.

Suppose $10^m\equiv-1\pmod{89}$; then $10^m\equiv10^{22}$, so $10^{m-22}\equiv1\pmod{89}$ and therefore $m\equiv22\pmod{44}$.

The solutions are the positive integers of the form $22+44k$.

The smallest solution is $$ \frac{10^{22}+1}{89}=112359550561797752809 $$ The next solution is $$ \frac{10^{66}+1}{89}= 11235955056179775280898876404494382022471910112359550561797752809 $$

$\endgroup$
7
  • $\begingroup$ Interestingly, the solutions are very close to sums $\sigma_n:=\sum_{k=1}^{n}10^{n-k}F_n$, where $F_n$ is the $n$-th Fibonacci number: $$\tfrac1{89}\left(10^{22}+1\right)-\sigma_{21}=2113\qquad\tfrac1{89}\left(10^{66}+1\right)-\sigma_{65}=3314006522814$$ both tiny relative errors. Even better, it appears that $$\tfrac1{89}\left(10^{22}+1\right)=\left\lceil\frac{\sigma_{21+p}}{10^p}\right\rceil\qquad \tfrac1{89}\left(10^{66}+1\right)=\left\lceil\frac{\sigma_{65+q}}{10^q}\right\rceil$$ for $p\geq 5$ and $q\geq 17$. I feel like I'm missing an obvious connection. $\endgroup$
    – Blue
    Commented Sep 8, 2019 at 10:53
  • 1
    $\begingroup$ @Blue Quite interesting indeed. $\endgroup$
    – egreg
    Commented Sep 8, 2019 at 11:02
  • $\begingroup$ Whoops ... My definition of $\sigma_n$ should use "$F_k$", not "$F_n$". $\endgroup$
    – Blue
    Commented Sep 8, 2019 at 11:08
  • $\begingroup$ With the related sum $\sigma_\star:=\sum_{k=1}^\infty 10^{-k}F_k = .11235955\ldots$ (omitting the leading $0$ on purpose), the recurrence $F_n+F_{n+1}=F_{n+2}$ makes clear why $99\sigma_\star=100\sigma_\star - 1\sigma_\star=11.1235955\ldots$ would have a digit string (without a decimal point) that is the concatenation of $1$ with $\sigma_\star$'s digit string (without a decimal point). So, maybe it's not surprising that the Fibonacci sums $\sigma_n$ enter into the "finitized" problem. $\endgroup$
    – Blue
    Commented Sep 8, 2019 at 11:36
  • $\begingroup$ Thanks for your answer :) I don't understand why there is no need to look at 10^8 and why 10^¹¹ =55 imply 10^44=1 (I don't understand the "so"). Could you explain ? :-) $\endgroup$
    – Jeanba
    Commented Sep 9, 2019 at 12:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .