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.

  • 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"...2011-06-17
  • 3
    **HINT** $\ $ [See here,](http://math.stackexchange.com/questions/11567/gcdbx-1-by-1-b-z-1-b-gcdx-y-z-1/11636#11636) for just one of the may times this was discussed here (and more generally).2011-06-17
  • 0
    @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.2011-06-17
  • 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

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

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: see the problem's constraints: $2 \leq t, a, b \leq 2^{31} - 1$. Hence, t = 0 is not a counterexample.2011-06-17
  • 0
    Good explication even for a computer science student.2011-06-17
  • 0
    [See here](http://math.stackexchange.com/questions/11567/gcdbx-1-by-1-b-z-1-b-gcdx-y-z-1/11636#11636) and its links for a more general viewpoint.2011-06-17
  • 0
    @amWhy: Sorry, my bad. I thought I saw $0$ as the lower bound for $t$. I will edit.2011-06-17
  • 0
    @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!2011-06-17
  • 0
    @Bill Dubuque: Sorry about that. Can't say that I would be surprised to learn about this. I just lack the familiarity with tools to check for the possibility of a re-run. I've been here only for two weeks, so I'm still learning how the place really works.2011-06-17
  • 0
    @Jyrki: No apology needed. My comment was meant merely to inform folks of other threads that may also prove insightful.2011-06-17