Divisibility relations

Prove: If $$a^{n}-1|b^{n}-1$$, then there exists $$k$$ such that $$b=a^{k}$$.

Note by Jessica Wang
2 years, 11 months ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

Sort by:

Suppose that $$a,b,n$$ are integers

$\frac{b^{n}-1}{a^{n}-1}=m$

let $$b=a^{k}$$

$\frac{a^{nk}-1}{a^{n}-1}=m$

if $$n|k$$,

$$a^{nk}-1 = (a^n-1)(a^k+a^{k-n}+a^{k-2n}+...a^n+1)$$

Hence, $\frac{b^{n}-1}{a^{n}-1}=\frac{(a^n-1)(a^k+a^{k-n}+a^{k-2n}+...a^n+1)}{a^{n}-1}=a^k+a^{k-n}+a^{k-2n}+...a^n+1=m$

Thus, when $$k$$ is any number which can be divided by $$n$$, $$b=a^k$$

*not sure if this is correct, waiting for others to complete

- 2 years, 11 months ago

This should do.

- 2 years, 11 months ago

Let A: $$a^n -1 | b^n -1$$.

and B : $$b = a^k$$

You have to prove that A implies B. What you've proven is that B implies A. Both are not the same thing. You can see this with the help of an example.

Suppose we want to prove " every integer x is even". (Obviously false).

Take A: x is an integer

and B: x is an even number.

We see that B implies A, but A does not imply B.

- 2 years, 11 months ago

He has done nothing wrong. He was very careful with the wording, knew the limits of his approach and even hinted, his proof wouldn't be complete. The assumption $$b = a^k$$ is perfectly fine. It was not postulated, $$k$$ would be a integer. Proving $$k$$ being an integer is the actual "difficult" part. There just missed the part for showing $$n \ !| \ k$$ contradicts A. However I added that part, you may bother reading my post with the included link.

- 2 years, 11 months ago

I'm sorry - my solution above is wrong as we cannot assume that $$b=a^k$$, but we instead have to prove that the statement $$a^n-1|b^n-1$$ implies $$b=a^k$$. I've asked help from my friend and his suggestion is 'every prime that can divide $$b$$ must also divide $$a$$'. However, I still have no idea how to prove.

- 2 years, 11 months ago

Hey I did not understand how did you find $$b=a^{k}$$

- 2 years, 11 months ago