Wednesday, January 27, 2016

elementary number theory - $x^a - 1$ divides $x^b - 1$ if and only if $a$ divides $b$



Let $x > 1$ and $a$, $b$ be positive integers. I know that $a$ divides $b$ implies that $x^a - 1$ divides $x^b - 1$. If $b = qa$, then




$$x^b - 1 = (x^a)^q - 1^q = (x^a - 1)((x^a)^{q-1} + \ldots + x^a + 1).$$



I'm interested in the converse of the statement. If $x^a - 1$ divides $x^b - 1$, does this imply that $a$ divides $b$?


Answer



Let $b=a \cdot q+r$, where $0 < r < a$.



Then



$$x^b-1=x^b-x^r+x^r-1=x^r(x^{aq}-1)+x^r-1 \,.$$




Use that $x^a-1$ divides $x^{aq}-1$.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...