4
$\begingroup$

This isn't homework, but I'm trying to work some other math problems for fun in my spare time, and noticed that I had trouble solving this slightly adjacent question. I've noticed that the ways we can get a 0 in a decimal expansion is either a) with no carry-in through 25, 45, or 5*6, or b) with a carry-in through basically any other product of numbers, but I'm not sure how to proceed from here.

Any thoughts appreciated.

Thanks.

$\endgroup$
5
  • 3
    $\begingroup$ Seems to be unknown: oeis.org/A071531 (but for $a \leq 10000$ the answer is yes and smallest such $p\leq 10$ in all these cases) $\endgroup$
    – Sil
    Nov 17, 2021 at 18:09
  • 1
    $\begingroup$ We can safely assume that this is true, proving it is however another story. $\endgroup$
    – Peter
    Nov 17, 2021 at 18:22
  • 2
    $\begingroup$ In fact, it is likely the case that for each such $a$ there is $N$ such that all $a^p$ for $p \ge N$ contain $0$: see OEIS sequence A020665. Again, however, no proof is in sight. $\endgroup$ Nov 17, 2021 at 18:48
  • $\begingroup$ I am slightly confused although this probably does not really change the answer. Must $p$ be a perfect power or is it an arbitary integer ? $\endgroup$
    – Peter
    Nov 17, 2021 at 19:12
  • $\begingroup$ @Peter I think $p$ is just a positive integer. Of course $a^p$ is a perfect power, for $p>1.$ $\endgroup$
    – coffeemath
    Nov 18, 2021 at 2:59

1 Answer 1

7
$\begingroup$

There are four cases.

Case 1: $a$ is divisible by $10$. Then $p=1$ works.

Case 2: $a$ is not divisible by $2$ or by $5$. Then $p=40$ works: by Euler's theorem, $a^{40} \equiv 1 \pmod{100}$, so the second digit from the end of $a^{40}$ is $0$.

Case 3: $a = 2^b \cdot c$, where $c$ is not divisible by $2$ or by $5$. Then $p=40\,000$ works. First, we check that $2^{40\,000} \equiv 9\,376\pmod{100\,000}$. Next, we check that $9\,376^2 \equiv 9\,376 \pmod{100\,000}$; it follows that $(2^b)^{40\,000} \equiv 9\,376^b \equiv 9\,376 \pmod{100\,000}$ by induction. Meanwhile, $c^{40\,000} \equiv 1 \pmod{100\,000}$ (again, by Euler's theorem). Therefore $a^{40\,000} \equiv 9\,376 \pmod{100\,000}$: the last five digits of $a^{40\,000}$ are $09\,376$, which includes $0$.

Case 4: $a = 5^b \cdot c$, where $c$ is not divisible by $2$ or $5$. Then $p=4\,000$ works. First, we check that $5^{4\,000} \equiv 625 \pmod{10\,000}$. Next, we check that $625^2 \equiv 625 \pmod{10\,000}$; it follows that $(5^b)^{4\,000} \equiv 625^b \equiv 625 \pmod{10\,000}$ by induction. Meanwhile, $c^{4\,000} \equiv 1 \pmod{10\,000}$ (again, by Euler's theorem). Therefore $a^{4\,000} \equiv 625 \pmod{10\,000}$: the last four digits of $a^{4\,000}$ are $0\,625$, which includes $0$.


This proves that $p$ exists for every $a$, and in fact the smallest $p$ that works is always at most $40\,000$ (so this is an upper bound on every term of https://oeis.org/A071531).

As pointed out by Sil in the comments, we can actually do better and prove $p=2500$ works for all $a$.

  • When $\gcd(a,10)=1$, we work modulo $50000$: the Carmichael lambda of $50000$ is $2500$, so we always get $a^{2500} \equiv 1$. In particular, returning to modulo $100000$, we get either $1$ or $50001$.
  • When $\gcd(a,10)=2$, we multiply this by some power of $2^{2500}$ .We have $2^{2500} \equiv 9376 \pmod{100000}$. Multiplying $1$ or $50001$ by $9376$ gives $9376$ modulo $100000$, and multiplying by $9376$ more times keeps the same value.
  • When $\gcd(a,10)=5$, we multiply this by some power of $5^{2500}$ .We have $5^{2500} \equiv 40625 \pmod{100000}$. Multiplying $1$ or $50001$ by $40625$ gives either $40625$ or $90625$, and multiplying these by $40625$ more times just swaps these two values.
  • When $\gcd(a,10)=10$, we get lots of zeroes at the end as usual.

So the last five digits of $a^{2500}$ are always either $00\,000$, $00\,001$, $50\,001$, $09\,376$, $40\,625$, or $90\,625$, and all of these contain a zero.

For all known cases, much smaller values of $p$ work, but proving this seems very hard.

$\endgroup$
3
  • $\begingroup$ Brilliant! Btw you can push the common limit down to $p=2500$, provided that $a^{2500} \equiv 1, 50001 \pmod{10^5}$ is shown somehow for $(a,10)=1$ (the rest seems to be straightforward I think). $\endgroup$
    – Sil
    Nov 18, 2021 at 16:53
  • $\begingroup$ That should be doable: $\lambda(100\,000) = 2500$, where $\lambda(n)$ is the Carmichael lambda, so $a^{2500} \equiv 1 \pmod{100\,000}$ for all $a$ coprime to $10$. $\endgroup$ Nov 18, 2021 at 16:56
  • 1
    $\begingroup$ Sorry, I meant $\lambda(50\,000) = 2500$, I got a bit carried away. That is exactly what guarantees us either $1$ or $50\,001$. $\endgroup$ Nov 18, 2021 at 17:03

You must log in to answer this question.

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