Is There Always a Solution for b^x - b^y to be Divisible by a?

In summary, for any natural number a and b, with b > 1, two natural numbers x and y can always be found such that b^x - b^y is divisible by a. This has been proven through various methods, including factoring, Euler's theorem, and using Euclid's algorithm to calculate 1/a in base b. The graph of z = b^y - b^x represents a plane that intersects all values of z, showing the divisibility of a.
  • #1
Petr Mugver
279
0
For any natural number a and b, with b > 1, two natural numbers x and y can always be found such that b^x - b^y is divisible by a.

Until now, with many tries of a and b, I have always found corresponding x and y.

I would appreciate if somebody could give me a proof or a counter example.
 
Physics news on Phys.org
  • #2
Hi Petr Mugver! :smile:

It seems to be always possible. Note that (if x>y) we can factor

[tex]b^x-b^y=b^y(b^{x-y}-1)[/tex]

By this factorization, we can assume a coprime of b. Indeed, if pk is a prime power that divides both a and b, then pk will divide bk. So we just need to choose y>k.

Now, if a and b are coprime, then I claim that there is always a z such that a divides bz-1. Or, in other words, that bz=1 (mod a). This follows immediately from Euler's theorem and we can choose [itex]z=\varphi(a)[/itex].
 
  • #3
Thanks for the reply!

I need to "translate" it though (I am a physician and quite unfamiliar with all this number theory stuff), but I assume that your answer is correct, so just give me some time to understand it!

Now, please tell me: has your answer something to do with the proof I figured out, which is the following:

I calculate 1/a using Euclid Algorithm "in base b". Then 1/a will be a certain number c plus an infinite geometric series in b, in other words

1/a = c + d/(1 - b^-k) = [(cb^k - c) + db^k] / (b^k - 1)

so if d is not zero (b^k - 1) is divisible by a, and if d = 0 then b^k is divisible by a.

This is certainly less elegant, but is it the same thing?
 
  • #4
Your proof is quite nice, but I don't see how you obtained the following:

Petr Mugver said:
Then 1/a will be a certain number c plus an infinite geometric series in b

You somehow applied Euclid's algorithm to something, but I don't quite see it. (also not that Euclid's algorithm applies to integers only!)
 
  • #5
micromass said:
You somehow applied Euclid's algorithm to something, but I don't quite see it. (also not that Euclid's algorithm applies to integers only!)

For (a simple) example, let a = 6 and b = 10.

Calculating 1/6 in base 10 (that's what I mean by Euclid's Algorithm) you get

1/6 = 0,1666... = 16,666.../100 = (10 + 6 x sum_k(10^-k))/100 =
= (10 + 60/9)/100 = 150/900

so x = 3 and y = 2.
 
  • #6
Would it make sense to think of the graph of z = b^y - b^x?

if (b^y-b^x)/a = integer

b^y - b^x = integer * a

z = integer * a

It should be a plane that intersects all values of z.
 
Last edited:

What is "proof or counter example"?

"Proof or counter example" is a type of mathematical or scientific reasoning used to determine the validity of a statement or hypothesis. It involves providing either evidence to support the statement (proof) or a specific instance that disproves it (counter example).

Why is "proof or counter example" important in science?

"Proof or counter example" is crucial in science because it allows scientists to test the validity of their theories and hypotheses. By providing evidence or counterexamples, scientists can either support or refute their ideas, leading to a better understanding of the natural world.

How do you construct a proof or counter example?

To construct a proof, you must start with a given statement and use logical reasoning and mathematical principles to show that it is true. On the other hand, to create a counterexample, you must provide a specific instance that disproves the statement. This can be done by finding a case where the statement does not hold true.

Can a proof or counter example be wrong?

Yes, a proof or counter example can be incorrect if there is a flaw in the logic or if the evidence provided is not strong enough. It is essential to thoroughly check and review a proof or counter example before considering it valid.

How does "proof or counter example" differ from other types of reasoning?

"Proof or counter example" is a type of deductive reasoning, which involves using general principles to reach a specific conclusion. It differs from other types of reasoning, such as inductive reasoning, which uses specific observations to make a general conclusion, and abductive reasoning, which involves using the most likely explanation to make a conclusion.

Similar threads

  • Linear and Abstract Algebra
Replies
2
Views
696
  • Linear and Abstract Algebra
Replies
3
Views
1K
  • Linear and Abstract Algebra
Replies
9
Views
1K
  • Linear and Abstract Algebra
Replies
3
Views
773
  • General Math
2
Replies
47
Views
2K
  • Calculus and Beyond Homework Help
Replies
3
Views
465
Replies
3
Views
2K
  • Linear and Abstract Algebra
Replies
1
Views
908
  • Linear and Abstract Algebra
Replies
1
Views
862
Back
Top