The relation between the number of $0$s which are at the end of $3^{n!}-1$ and that of $n!$

Question

Let $a_n,b_n$ be the number of $0$s which are at the end of $3^{n!}-1,n!$ in the decimal system respectively. I found that $a_n=b_n+1$ holds for $n=4,5,\cdots, 10$. Then, my questions are...

Question 1 : Does $a_n=b_n+1$ hold for every $n\ge 4\in\mathbb N$?

Question 2 : If the answer for question 1 is no, then does $\lim_{n\to\infty}(a_n/b_n)$ exist?

We know that $b_n=\sum_{k=1}^{\infty}\lfloor n/5^k\rfloor$, but I don't have any good idea to treat $3^{n!}-1$. Can anyone help?

Answer 1

Your conjecture is true. We have the following celebrated result in math olympiads:

Theorem. (Lifting The Exponent) If $p$ is an odd prime, $n\in\mathbb N$, $a,b\in\mathbb Z$ such that $p\mid a-b$ but $p\nmid a,b$, then $\nu_p(a^n-b^n)=\nu_p(n)+\nu_p(a-b)$, where $\nu_p(x)$ denotes the number of factors $p$ in the prime factorisation of the integer $x$.

Proof. See here, Theorem 1. (As you can see, it is a very elementary result.)

How does this apply here? Note that $5\mid 3^4-1$. As soon as $4\mid n!$ (that is, $n\geqslant4$) we have $\nu_5(3^{n!}-1)=\nu_5(3^4-1)+\nu_5(n!/4)=1+\nu_5(n!)$.

Now, what about the factors $2$? You may guess that $3^{n!}-1$ has a lot more factors $2$ than $5$. Indeed: Euler's theorem says: $2^k\mid3^{2^{k-1}}-1$ for $k\in\mathbb N$.
So, if $m=\nu_5(n!)$, then $m\leqslant\nu_2(n!)$ so $2^m\mid n!$, hence $3^{2^m}-1\mid3^{n!}-1$. Euler's theorem says $2^{m+1}\mid3^{n!}-1$, meaning that $\nu_2(3^{n!}-1)\geqslant m+1$: we've shown that $3^{n!}-1$ has at least as many factors $2$ as factors $5$.

Summarizing, since the number of trailing $0$'s of an integer $x$ is $\min(\nu_2(x),\nu_5(x))$, we have shown that $3^{n!}-1$ has one more zero than $n!$ has.

Answer 2

Just that you can check much higher; you know how to find $b_n.$ Then calculate $$ 3^{n!} - 1 \pmod {2^{b_n + 2}}, $$ $$ 3^{n!} - 1 \pmod {5^{b_n + 2}}. $$ I don't see much reason that (1) should hold forever, but up to 100 would be impressive.

There are topics sort of like this where there is agreement for an initial set but later disagreement. The superior highly composite numbers and the colossally abundant numbers agree on something like the first 15 terms, don't quite remember. And they stay roughly similar forever, they are approximately the least common multiple of the numbers from $1$ to some positive $N.$ But there are small disagreements, more pronounced as everything gets bigger.

Answer 3

So to answer your question in short:

Part I: Yes Part II: Not Applicable

Why? Here it is below, have fun...

Our objective is to count the number of factors that are necessarily divisible by powers 5. and check there are at least as many powers of 2 dividing this expression. We begin by factoring the expression $3^{n!} - 1$ through the use of the difference of squares factorization which yields:

$$(3^{\frac{n!}{2}} - 1)(3^{\frac{n!}{2}} + 1)$$

Notice we can repeat this as long as $n!$ has even factors into the expression:

$$(3^{\frac{n!}{2^k}} -1)^k (3^{\frac{n!}{2^k}}+1)(3^{\frac{n!}{2^{k-1}}}+1)...(3^{\frac{n!}{2}} + 1) $$

We notice that the number of even factors of $n!$ is going to be equal to the sum of the count of multiples of powers of 2. That is

$$k = \sum_{i=1}^{\infty}{\lfloor\frac{n}{2^i}\rfloor} = \lfloor \frac{n}{2} \rfloor + \lfloor \frac{n}{4} \rfloor + \lfloor \frac{n}{8}\rfloor ... $$

I'm not sure if there is a clean closed form for the floor of a geometric series but this may help shed light on the number of terms present.

Now we are going to consider terms of the form

$$3^r +1$$

In our product expansion

In general it appears that terms of the form

$$3^{5^{m-1}(2 + 4j)} \equiv 5^m - 1 \mod 5^m $$

Why is this true? First one should note that

$$3^k \ne 5w $$

for any integers w and k because this would imply that there is a positive integer $n$ such that

$$(3^k)^n \equiv 0 \mod 5^n $$

But we know 3 is coprime to $5^n$ for all positive integers $n$ so this is not a possibility.

That also means that sequence $a_(n+1) = 3*a_n \mod 5^k$ has period $4*5^{k-1}$ because this sequence can take on all $5^k$ values possible under $\mod 5^k$ except $0,5,10,15...$ because these are multiples of 5. The number of non-multiples of 5 are $\frac{4}{5}*5^k = 4*5^{k-1}$. Why all other values are possible is because both $3$ and $5$ are primes (although I wish I had a proof for why this still must be true).

Thus consider the original statement:

$$3^{5^{m-1}*2 + 5^{m-1}*4j} \equiv 5^m - 1 \mod 5^m $$

We can factor out $3^{5^{m-1}*4j}$ since $5^{m-1}*4j$ is known to leave the value unchanged and therefore what we really need to prove is:

$$3^{5^{m-1}*2} \equiv 5^m - 1 \mod 5^m $$

we can rewrite the left-hand side

$$3^{5^{m-1}*2} \equiv 9^{5^{m-1}} \equiv (2*5 -1)^{5^{m-1}}$$

From here if we expand this with the binomial theorem we will have something of the form:

$$(2*5)^{5^{m-1}} + {5^{m-1}}*(2*5)*(-1) ... + (-1)^{5^{m-1}}$$

All the middle terms will be divisible by ${5^{m-1}}*5 = 5^m$ and therefore equivalent to $0 \mod 5^m$ thus our expansion is equivalent to

$$(2*5)^{5^{m-1}} - 1 $$

Which we believe to satisfy:

$$(2*5)^{5^{m-1}} - 1 \equiv 5^m - 1 \mod 5^m$$ Obviously the 1's cancel out leaving us to prove:

$$(2*5)^{5^{m-1}}\equiv 5^m \mod 5^m$$

Obviously $5^{5^{m-1}} \equiv 0 \equiv 5^m \mod 5^m$

thereby showing indeed that:

$$3^{5^{m-1}(2 + 4j)} \equiv 5^m - 1 \mod 5^m $$

Coming back to the problem at hand:

We note none of the terms of the form: $3^{\frac{n!}{2^{k-n}}}+1$ where $n \ge 2$ can be of the form $3^{5^{m-1}(2 + 4j)} $ because $\frac{n!}{2^{k-n}} \equiv 0 \mod 4$ for all $n \ge 2$ and $5^{m-1}(2 + 4j) \equiv 2 \mod 4$. Also the term

$$3^{\frac{n!}{2^k}} + 1$$

Doesn't work since $\frac{n!}{2^k} \equiv 1,3 \mod 4$ but never $2$. So, the term

$$(3^{\frac{n!}{2^{k-1}}}+1)$$

Is the only term in the product

$$(3^{\frac{n!}{2^k}}+1)(3^{\frac{n!}{2^{k-1}}}+1)...(3^{\frac{n!}{2}} + 1) $$

That contributes factors of 5 and it contributes $w+1$ such factors if $5^w$ is the largest power of 5 that divides: $\frac{n!}{2^{k-1}}$ We can actually go ahead and calculate this number w by noting

$$w =\sum_{i=1}^{\infty}\lfloor \frac{n}{5^i} \rfloor = \lfloor \frac{n}{5} \rfloor + \lfloor \frac{n}{25} \rfloor ... $$

Now we have left to account for all the factors of 5 in the term

$$(3^{\frac{n!}{2^k}}-1)^k$$

Using super similar arguments to before (I will leave you to prove it yourself)

$$3^{5^{m-1}4j} - 1 \equiv 0 \mod 5^m$$

But..

$$\frac{n!}{2^k} \equiv 1,3 \mod 4$$

and

$${5^{m-1}4j} \equiv 0 \mod 4$$

So that means that term will NEVER contribute a factor of 5. So that means... The total number of trailing zeroes to

$$3^{n!} - 1$$

is

$$ 1 + \sum_{i=1}^{\infty} \lfloor \frac{n}{5^i} \rfloor $$

For... $n \ge 4$

The reason being is that if $n < 4$ our factorizations do not work out the way they did above.

The total number of trailing zeroes to:

$$n!$$

is simply

$$ \sum_{i=1}^{\infty} \lfloor \frac{n}{5^i} \rfloor $$

Thus:

$$a_n = b_n + 1$$

in your notation.

PLEASE ASK QUESTIONS ABOUT WHAT YOU SEE HERE. IT IS A LOT TO DIGEST FOR ONE PROBLEM