Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
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
3  
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
add comment

1 Answer

up vote 4 down vote accepted

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

share|improve this answer
    
@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
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.