Prove or refute that $\frac{t^a-1}{t^b-1}$ is not a integer if $a \mod b \neq 0$

158 Views Asked by At

Hi guys in my last question I got the wrong idea maybe because a poor problem's description or maybe because of my poor English skills.

So, anyway I found out the problem requires to be a integer.

Then here the correct interpretation: Given 3 integers $2 \leq t, a, b \leq 2^{31}-1$ proof or refute that $\frac{t^a-1}{t^b-1}$ is not a integer if $a \mod b \neq 0$

Bonus: If it is possible explain it in a easy way that a cs student could comprehend.

1

There are 1 best solutions below

7
On BEST ANSWER

Assume $a>b$ to make it more interesting.

Let's apply Euclid's algorithm. Write $a=qb+r$, with $0\le r<b$ and $q$ integer. Write $N=t^b-1$, so $t^b\equiv 1 \pmod{N}$. Raise this congruence to $q^{th}$ power to get the congruence $t^{qb}\equiv 1 \pmod{N}$. Multiply this by $t^r$ to get $t^a=t^{qb+r}\equiv t^r\pmod{N}.$ So in the end we get $$ t^a-1\equiv t^r-1\pmod{N}. $$ Here always $t^r-1<t^b-1$, so we see that $N$ divides $t^a-1$ if and only if $r=0$. This is exactly what we wanted.

=============================

If we want more precise information, we see that Euclid's algorithm runs the distance, and we get that $$ gcd(t^a-1,t^b-1)=t^{gcd(a,b)}-1. $$