|
||
|
Title: Devilish Quickie Post by ecoist on Jun 26th, 2006, 8:58pm Show that there exist positive integers m and n such that 18m+37n is congruent to 1 modulo 666. |
||
|
Title: Re: Devilish Quickie Post by pex on Jun 27th, 2006, 4:13am [hideb]We may even take m = n. Note that 18n + 37n = (18 + 37)n - (some multiple of 18 * 37). Calculating 18 + 37 = 55 and 18 * 37 = 666, it follows that 18n + 37n = 55n (mod 666). Since 18 and 37 are coprime, x = 1 (mod 18) and x = 1 (mod 37) together imply that x = 1 (mod 666). Since 55 = 3*18 + 1 = 1 (mod 18), any power of 55 will be congruent to 1 (mod 18). Since 37 is a prime number that does not divide 55, Fermat's Little Theorem gives 5536 = 1 (mod 37). Therefore 5536 = 1 (mod 666), and hence 1836 + 3736 = 1 (mod 666). Hence, such positive integers do indeed exist, an example being m = n = 36.[/hideb] |
||
|
Title: Re: Devilish Quickie Post by ecoist on Jun 27th, 2006, 5:08pm Here's another solution. [hide]For some positive integer m, 18m=1 (mod 37), and for some positive integer n, 37n=1 (mod 18). Hence 0=(18m-1)(37n-1) (mod 666) =18m37n-18m-37n+1 (mod 666) =-18m-37n+1 (mod 666), equivalent to 18m+37n=1 (mod 666).[/hide] |
||
|
Title: Re: Devilish Quickie Post by ecoist on Jun 27th, 2006, 8:38pm I thought my solution was shorter than pex's. Wrong! Here is my rewrite of his solution. [hide]1=(18+37)n=55n (mod 666=18*37), for some positive integer n ( because, if a and b are relatively prime, then so are a+b and a*b). 55n=18n+37n (mod 666) (because the middle terms of the expansion of the binomial (18+37)n are all divisible by 666). Q.E.D.[/hide] |
||
|
Powered by YaBB 1 Gold - SP 1.4! Forum software copyright © 2000-2004 Yet another Bulletin Board |