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

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.

-
I admire your follow-through at "getting to the bottom" of the problem, and despite a successful "pass" with your program, persisting in your efforts to seek a mathematical proof (or refutation) that explains the "why"... – amWhy Jun 17 '11 at 16:55
HINT $\$ See here, for just one of the may times this was discussed here (and more generally). – Bill Dubuque Jun 17 '11 at 16:57
@amWhy: Thanks and in fact I have other problems that I don't know the mathematical proof but I don't remember well any of them for the exception of this one. – razpeitia Jun 17 '11 at 17:02
Also We asked (a friend and I) to a math teacher at the university for a mathematical proof for other problem and if I don't bad remember where about graphs. We got the response "Search it yourself" followed with a epic poker face. – razpeitia Jun 17 '11 at 17:10

## 1 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.$$

-
@Jyrki: see the problem's constraints: $2 \leq t, a, b \leq 2^{31} - 1$. Hence, t = 0 is not a counterexample. – amWhy Jun 17 '11 at 16:38
Good explication even for a computer science student. – razpeitia Jun 17 '11 at 16:42
See here and its links for a more general viewpoint. – Bill Dubuque Jun 17 '11 at 16:56
@amWhy: Sorry, my bad. I thought I saw $0$ as the lower bound for $t$. I will edit. – Jyrki Lahtonen Jun 17 '11 at 17:04
@Jyrki: no problem! The fact is, you took the challenge to "make the problem more interesting", and in doing so, tackled the OP's question! No harm done! – amWhy Jun 17 '11 at 17:10