SOLUTION: Suppose that a and d are integers. m and n are natural numbers such that d divides {{{a^m-1}}} and d divides {{{a^n-1}}}. Prove that d divides {{{a^gcd(m,n) -1}}}

Algebra.Com
Question 1019200: Suppose that a and d are integers. m and n are natural numbers such that
d divides and d divides . Prove that d divides
Answer by richard1234(7193)   (Show Source): You can put this solution on YOUR website!
From Bezout's lemma (or Euclidean algorithm), there exist integers and such that .

Since is divisible by d, then . Note that the exponent could be negative, but this is okay, since this still obeys the rules of modular arithmetic (if e > 0, then , where is defined as the integer such that (if an inverse exists). In particular, a and d are relatively prime, so an inverse of a exists mod d.

Similarly, .

It follows that , or is divisible by d. Since we expressed gcd(m,n) = xm + yn, it follows that d divides .
RELATED QUESTIONS

This is a Number Theory proof: If N = abc + 1, prove that (N, a) = (N, b) = (N, c) =... (answered by KMST)
How do i show for integers m and n and a natural number k that is greator and equal to 1. (answered by venugopalramana)
I am having a lot of trouble with these proofs; I get so far and alskdjfl.... prove or (answered by khwang)
1. Whenever we encounter a new proposition, it is a good idea to explore the proposition (answered by richard1234)
If m and n are consecutive even integers and m > n > 0, how many integers are greater... (answered by Fombitz)
Let f(x) =x^n + a(sub1)x^n-1 + a(sub2)x^n-2..........a(sub n-1)x+a(sub n) be a polynomial (answered by khwang)
Two nonzero integers, x and y, are such that x+y and y/x are both odd integers. Let n be (answered by richard1234)
Prove or Disprove: For all integers a and n, if (a divides nē) and a < n, then (a divides (answered by richard1234)
Determine all natural numbers n such that for all positive divisors d of n, d+1 is also... (answered by Edwin McCravy)