document.write( "Question 1019200: Suppose that a and d are integers. m and n are natural numbers such that
\n" ); document.write( "d divides $\"a%5Em-1\"$ and d divides $\"a%5En-1\"$ . Prove that d divides $\"a%5Egcd%28m%2Cn%29+-1\"$ \n" ); document.write( "

Algebra.Com's Answer #635309 by richard1234(7193) $\"\"$ $\"About$

You can put this solution on YOUR website!
From Bezout's lemma (or Euclidean algorithm), there exist integers

and

such that

.\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "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.\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "Similarly,

. \r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "It follows that

, or

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

. \n" ); document.write( "

\n" );