Welcome to congruence
- Phlembac Adib Hasan
- Posts:1016
- Joined:Tue Nov 22, 2011 7:49 pm
- Location:127.0.0.1
- Contact:
Find the reminder if $25!$ is divided by $37$.
Welcome to BdMO Online Forum. Check out Forum Guides & Rules
-
- Posts:188
- Joined:Mon Jan 09, 2012 6:52 pm
- Location:24.4333°N 90.7833°E
Re: Welcome to congruence
I like the remainder...
An amount of certain opposition is a great help to a man.Kites rise against,not with,the wind.
- Phlembac Adib Hasan
- Posts:1016
- Joined:Tue Nov 22, 2011 7:49 pm
- Location:127.0.0.1
- Contact:
Re: Welcome to congruence
Give your complete solve because junior students are unfamiliar with such problems.Otherwise I'll need to do so.
Welcome to BdMO Online Forum. Check out Forum Guides & Rules
- Phlembac Adib Hasan
- Posts:1016
- Joined:Tue Nov 22, 2011 7:49 pm
- Location:127.0.0.1
- Contact:
Re: Welcome to congruence
This problem involves a theorem named ''Wilson's Theorem".It's one of the fundamental theorems of classical Number Theory.(Actually my intention behind giving this problem was to inform junior students about it.)This theorem states if $p$ is a prime, then $(p-1)!\equiv -1 (mod\; p)$.Or simply I can say if $p$ is a prime, then $p$ always divides $(p-2)!-1$.
Now in this problem $37$ is a prime.(Any doubt?) It follows that \[(37-2)!-1\equiv 0 (mod\; 37)\]\[\Rightarrow 35!\equiv 1(mod \; 37)\]Now there is a problem.We need to divide $25!$, not $35!$.We can solve it in the following way: \[35\equiv -2 (mod\; 37)\]\[34\equiv -3 (mod\; 37)\]\[:\]\[:\]\[:\]\[26\equiv -11 (mod\; 37)\]After multiplying them\[26.27...35\equiv (-2).(-3)...(-11)\equiv 11!(mod\; 37)\]\[\Rightarrow 35!\equiv 25!.11!\equiv 1(mod\; 37)\]Now \[11.10=110\equiv -1 (mod\; 37)\]\[4.9=36\equiv -1(mod\; 37)\]\[5.8=40\equiv 3(mod\; 37)\]\[6.7=42\equiv 5(mod\; 37)\]\[\therefore 11!\equiv (-1).(-1).3.5.6=90\equiv 16\; (mod\; 37)\]\[\therefore 25!.11!\equiv 25!.16\equiv 1 \equiv 112=16.7(mod\; 37)\]Dividing both sides by $16$ we find our desired result:\[16.25!\equiv 16.7(mod\; 37)\]\[\Rightarrow 25!\equiv 7\; (mod\; 37)\]
Now in this problem $37$ is a prime.(Any doubt?) It follows that \[(37-2)!-1\equiv 0 (mod\; 37)\]\[\Rightarrow 35!\equiv 1(mod \; 37)\]Now there is a problem.We need to divide $25!$, not $35!$.We can solve it in the following way: \[35\equiv -2 (mod\; 37)\]\[34\equiv -3 (mod\; 37)\]\[:\]\[:\]\[:\]\[26\equiv -11 (mod\; 37)\]After multiplying them\[26.27...35\equiv (-2).(-3)...(-11)\equiv 11!(mod\; 37)\]\[\Rightarrow 35!\equiv 25!.11!\equiv 1(mod\; 37)\]Now \[11.10=110\equiv -1 (mod\; 37)\]\[4.9=36\equiv -1(mod\; 37)\]\[5.8=40\equiv 3(mod\; 37)\]\[6.7=42\equiv 5(mod\; 37)\]\[\therefore 11!\equiv (-1).(-1).3.5.6=90\equiv 16\; (mod\; 37)\]\[\therefore 25!.11!\equiv 25!.16\equiv 1 \equiv 112=16.7(mod\; 37)\]Dividing both sides by $16$ we find our desired result:\[16.25!\equiv 16.7(mod\; 37)\]\[\Rightarrow 25!\equiv 7\; (mod\; 37)\]
Welcome to BdMO Online Forum. Check out Forum Guides & Rules
- Perseus n Harry
- Posts:18
- Joined:Mon Jan 28, 2013 11:30 pm
- Location:Mymensingh,Bangladesh,The Earth,Solar system,Milkyway,Universe and third dimension(l think)
Re: Welcome to congruence
Adib Bhaiya,please make me understand the matter of congruence again,and also describe the modular equation.(it's me Navho from MPMS).
What matters most is what you do,rest all are TRASH.
- Fahim Shahriar
- Posts:138
- Joined:Sun Dec 18, 2011 12:53 pm
Re: Welcome to congruence
$36! \equiv -1 (mod 37)$
$31 \equiv -6 (mod 37) $
$31^2 \equiv -1 (mod 37)$
$(31+1)(31-1)=31^2-1 \equiv -2 (mod 37)$
$(31+2)(31-2)=31^2-4 \equiv -5 (mod 37)$
.........
$(31+5)(31-5)=31^-25 \equiv 11 (mod 37)$
$25!*(-6)*(-2)*(-5)*(-10)*20*11 \equiv -1 (mod 37)$
$25! * 21 \equiv -1 (mod 37)$
$25! * 21 \equiv 147 (mod 37)$
$25! \equiv 7 (mod 37)$
$31 \equiv -6 (mod 37) $
$31^2 \equiv -1 (mod 37)$
$(31+1)(31-1)=31^2-1 \equiv -2 (mod 37)$
$(31+2)(31-2)=31^2-4 \equiv -5 (mod 37)$
.........
$(31+5)(31-5)=31^-25 \equiv 11 (mod 37)$
$25!*(-6)*(-2)*(-5)*(-10)*20*11 \equiv -1 (mod 37)$
$25! * 21 \equiv -1 (mod 37)$
$25! * 21 \equiv 147 (mod 37)$
$25! \equiv 7 (mod 37)$
Name: Fahim Shahriar Shakkhor
Notre Dame College
Notre Dame College
- Phlembac Adib Hasan
- Posts:1016
- Joined:Tue Nov 22, 2011 7:49 pm
- Location:127.0.0.1
- Contact:
Re: Welcome to congruence
Download this file: http://www.matholympiad.org.bd/forum/do ... php?id=425Perseus n Harry wrote:Adib Bhaiya,please make me understand the matter of congruence again,and also describe the modular equation.(it's me Navho from MPMS).
বি. দ্র. গতকাল থেকে জুম আলট্রা আমাকে অতি উচ্চমার্গীয় পেইন দিচ্ছে। এদের নেটওয়ার্কে সম্ভবত কোন সমস্যা হয়েছে, স্পিড এত কম যে আধঘণ্টা বসে থাকলেও গুগোল আসে না। মেজাজ এমন গরম হয় যে... তবু আজকে নানা কাহিনী করে, সব ইমেজ ডিজঅ্যাবল করে, একসাথে পঁচিশটা ট্যাব খুলে ফোরামে ঢুকে গেলাম। সৌরভদার সাথে বড় কয়েকটা পোস্ট দেওয়ার কথা ছিল, মনে হচ্ছে আজ আর দেয়া যাবে না। সো কালকে দেখি।
Welcome to BdMO Online Forum. Check out Forum Guides & Rules
-
- Posts:53
- Joined:Wed Nov 28, 2012 12:48 pm
Re: Welcome to congruence
আমারও তো একই প্রবলেম। গুগল কেন? আমার তো যেকোনো পেজ ওপেন করতেই দিন কাবার হইয়া যায়। শুধু জুম আলট্রা না আমার গ্রামিন ফোনের ও একই অবস্থা। আর Novho(Perseus n Harry) তুই MPMS এর website থেকেও পড়তে পারিস ।Phlembac Adib Hasan wrote: বি. দ্র. গতকাল থেকে জুম আলট্রা আমাকে অতি উচ্চমার্গীয় পেইন দিচ্ছে। এদের নেটওয়ার্কে সম্ভবত কোন সমস্যা হয়েছে, স্পিড এত কম যে আধঘণ্টা বসে থাকলেও গুগোল আসে না। মেজাজ এমন গরম হয় যে... তবু আজকে নানা কাহিনী করে, সব ইমেজ ডিজঅ্যাবল করে, একসাথে পঁচিশটা ট্যাব খুলে ফোরামে ঢুকে গেলাম। সৌরভদার সাথে বড় কয়েকটা পোস্ট দেওয়ার কথা ছিল, মনে হচ্ছে আজ আর দেয়া যাবে না। সো কালকে দেখি।
http://testzone.comuf.com/pdf/congruence.pdf
Yesterday is past, tomorrow is a mystery but today is a gift.
- Perseus n Harry
- Posts:18
- Joined:Mon Jan 28, 2013 11:30 pm
- Location:Mymensingh,Bangladesh,The Earth,Solar system,Milkyway,Universe and third dimension(l think)