3
$\begingroup$

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.

  • 0
    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.2011-06-17

1 Answers 1

4

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

Let's apply Euclid's algorithm. Write $a=qb+r$, with $0\le r 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, 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. $

  • 0
    @Jyrki: No apology needed. My comment was meant merely to inform folks of other threads that may also prove insightful.2011-06-17