Prove or refute that $\frac{t^a-1}{t^b-1}$ has more than 100 digits if $a \mod b \neq 0$

Question

I'm a computer science student from Mexico and I have been training for the ICPC-ACM. So one of this problems called division sounds simple at first.

The problem is straight for you have and 3 integers $t$, $a$ and $b$, greater or equal than $0$ and less or equal than $2^{31} - 1$. Your job is simple, print the integer part of $\frac{t^a-1}{t^b-1}$ if the original number doesn't exceed 100 digits.

At first I think "It would be easy", I'll just check some tricky cases (like a = b or t = 0 or b=0 or a=0) and apply logarithms (to count the digits) if $(a-b)*\log(t) > 99$ then don't print else print the integer part.

But the problem (at least for me) here is know if $\frac{t^a-1}{t^b-1}$ doesn't exceed 100 digits including the fractional part.

Test case: $t = 2; a = 3; b = 2;$ then $\frac{t^a-1}{t^b-1}=\frac{2^3-1}{2^2-1}=\frac{7}{3}=2.333333...$ witch obviously have more than 100 digits.

After searching a little bit I found this page and if you take a look it's just matter of check some cases, that I have already checked except for this one if a % b != 0 then not a integer with less than 100 digits.

I put that condition in my code and It worked! But I'm a want a simple (if possible) explanation of why $\frac{t^a-1}{t^b-1}$ has more than 100 digits if $a \mod b \neq 0$.

Update: Full and accepted code here:

import java.io.*;
import java.math.BigInteger;

public class Main {

private static BigInteger f(BigInteger x, BigInteger k){
    if(k.equals(BigInteger.ONE))
        return BigInteger.ONE;
    if(k.testBit(0)){
        return (x.add(BigInteger.ONE).multiply(f(x.pow(2), k.divide(new BigInteger("2"))))).multiply(x).add(BigInteger.ONE);
    }
    else{
        return x.add(BigInteger.ONE).multiply(f(x.pow(2), k.divide(new BigInteger("2")))); 
    }
}

private static String D(long t, long a, long b){
    BigInteger T = new BigInteger(t+"");
    BigInteger A = new BigInteger(a+""); 
    BigInteger B = new BigInteger(b+"");
    return f(T.pow((int)b), A.divide(B)).toString();
}

public static void main(String[] args) {
    BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    String line;
    String lines[];
    long a, b, t;
    try{
        while(true){
            line = input.readLine();
            if(line == null)
                break;
            lines = line.split("[ ]+");

            t = Long.parseLong(lines[0]);
            a = Long.parseLong(lines[1]);
            b = Long.parseLong(lines[2]);
            System.out.print("("+t+"^"+a+"-1)/("+t+"^"+b+"-1) ");
            if(t == 1)
                System.out.print("is not an integer with less than 100 digits.\n");
            else if(a == b)
                System.out.print("1\n");
            else if(b == 0)
                System.out.print("is not an integer with less than 100 digits.\n");
            else if(a == 0)
                System.out.print("0\n");
            else if(a % b != 0)
                System.out.print("is not an integer with less than 100 digits.\n");
            else if((a - b)*Math.log10((double)t) > 99f)
                System.out.print("is not an integer with less than 100 digits.\n");
            else
                System.out.print(D(t, a, b)+"\n");

        }
    }
    catch(IOException e){}

}

}

Answer 1

Just for closure, what you are asking us to prove is wrong.

A couple of counterexamples:

$\dfrac{3^3 - 1}{3^2 - 1}$

$\dfrac{4^3 - 1}{4^2 - 1}$ (see Gerry's comment)

In general if $\dfrac{t^a - 1}{t^b - 1} = \dfrac{p}{q}$ in reduced form, and $q = 2^n 5^m$ then the number has a finite representation (in base 10). See this: http://en.wikipedia.org/wiki/Decimal_representation#Finite_decimal_representations

Answer 2

Aryabhata's counterexamples are based on finding integers $a, n \ge 2$ such that $a^n-1$ is of the shape $2^s5^t$. We show that there are not many such counterexamples. (there is nothing here about counterexamples of Myerson's type.) In order to save some words, call the numbers of shape $2^s5^t$ bad.

The case $n$ even: Imagine first that $n$ is even, say $n=2m$. We want $a^{2m}-1$ to be bad.

Suppose first that $a$ is even. Then $a^{2m}-1$ is odd. If it is bad it must have shape $5^t$. It is clear that $t \ne 1$. So if $a^{2m}-1$ is bad, there is a solution of the exponential diophantine equation $$2^n-5^t=1$$ with $n, t >1$. This contradicts Mihailescu's Theorem, aka the Catalan Conjecture. We could give elementary proofs of the Catalan Conjecture for the small number of cases we quote it, but this solution is already much too long.

Suppose next that $a$ is odd. Note that $a^{2m}-1=(a^m-1)(a^m+1)$, and these two numbers have greatest common divisor $2$. Let $c=a^m$. So $(c-1)(c+1)$ is bad. There are two possibilities. Either $c-1$ is a power of $2$ and $c+1$ is twice a power of $5$ (which could be $5^0$) or the other way around.

In the first case, $c-1=2^k$, $c+1=(2)5^t$, which gives $2^{k-1}+1=5^t$. This has solution $k=3$, $t=1$, and, by Mihailescu's Theorem, no other solutions. In the second case, we get $5^t+1=2^{k-1}$, which has solution $t=0$, $k=1$, and no other solutions.

The case $n$ odd: We next look for solutions with $n>2$ and odd. We want $a^n-1$ to be bad. If $a$ is even, then $a^n-1$ is odd, so if it is bad it is of shape $5^k$. This contradicts Mihailescu's Theorem.

So look for solutions with $a$ odd. Since $a-1$ divides $a^n-1$, $a-1$ must be bad. There are two cases to consider: (i) $a-1$ is divisible by $5$ and (ii) $a-1$ is not divisible by $5$, and hence is a power of $2$.

Case (i): Note that since $n$ is odd, $a^{n-1}+a^{n-2}+ \cdots +1$ is odd. If $a^n-1$ is to be bad, the preceding sum must be a power of $5$. Since $a \equiv 1 \pmod{5}$, it follows that $n \equiv 0 \pmod{5}$. Since $n$ is a multiple of $5$, it follows that $a^5-1$ divides $a^n-1$. And since $a^n-1$ is bad, so is $a^5-1$. We show this is impossible.

Since $a\equiv 1 \pmod{5}$, $a$ is congruent to one of $1$, $6$, $11$, $16$, or $21$ modulo $25$. For each of these possibilities, compute $1+a+a^2+a^3+a^4$ modulo $25$. In none of the cases do we get $0$. Since it is clear that $1+a+a^2+a^3+a^4>5$, this contradicts the fact that this sum is a power of $5$.

Case (ii): Suppose that $a-1$ is a power of $2$. Then $a$ is congruent to one of $0$, $2$, $3$, or $4$ modulo $5$.
If $a$ is a multiple of $5$, then $5$ cannot divide $a^n-1$, so $a^n-1$ is a power of $2$, which is impossible. This is also the case if $n$ is congruent to $2$, $3$, or $4$ modulo $5$, since no odd power of any of these can be congruent to $1$ modulo $5$.