wu :: forums « wu :: forums - Devilish Quickie » Welcome, Guest. Please Login or Register. Mar 30th, 2025, 11:47am

RIDDLES SITE WRITE MATH! Home Help Search Members Login Register

wu :: forums    riddles    easy (Moderators: ThudnBlunder, william wu, Grimbal, Icarus, towr, Eigenray, SMQ)    Devilish Quickie « Previous topic | Next topic » Pages: 1  Reply Notify of replies Send Topic Print    Author  Topic: Devilish Quickie  (Read 495 times) ecoist Senior Riddler     Gender: Posts: 405 Devilish Quickie   « on: Jun 26th, 2006, 8:58pm » Quote Modify Show that there exist positive integers m and n such that 18m+37n is congruent to 1 modulo 666. IP Logged pex Uberpuzzler     Gender: Posts: 880 Re: Devilish Quickie   « Reply #1 on: Jun 27th, 2006, 4:13am » Quote Modify hidden: 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. « Last Edit: Jun 27th, 2006, 4:26am by pex » IP Logged ecoist Senior Riddler     Gender: Posts: 405 Re: Devilish Quickie   « Reply #2 on: Jun 27th, 2006, 5:08pm » Quote Modify Here's another solution.   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). IP Logged ecoist Senior Riddler     Gender: Posts: 405 Re: Devilish Quickie   « Reply #3 on: Jun 27th, 2006, 8:38pm » Quote Modify I thought my solution was shorter than pex's.  Wrong!  Here is my rewrite of his solution.   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. IP Logged Pages: 1  Reply Notify of replies Send Topic Print Forum Jump: ----------------------------- riddles -----------------------------=> easy   - medium   - hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board