Welcome to congruence

For students of class 6-8 (age 12 to 14)
User avatar
Phlembac Adib Hasan
Posts:1016
Joined:Tue Nov 22, 2011 7:49 pm
Location:127.0.0.1
Contact:
Welcome to congruence

Unread post by Phlembac Adib Hasan » Sun Feb 19, 2012 11:50 am

Find the reminder if $25!$ is divided by $37$.
Welcome to BdMO Online Forum. Check out Forum Guides & Rules

sakibtanvir
Posts:188
Joined:Mon Jan 09, 2012 6:52 pm
Location:24.4333°N 90.7833°E

Re: Welcome to congruence

Unread post by sakibtanvir » Tue Feb 21, 2012 10:57 am

I like the remainder... :lol:
An amount of certain opposition is a great help to a man.Kites rise against,not with,the wind.

User avatar
Phlembac Adib Hasan
Posts:1016
Joined:Tue Nov 22, 2011 7:49 pm
Location:127.0.0.1
Contact:

Re: Welcome to congruence

Unread post by Phlembac Adib Hasan » Tue Feb 21, 2012 12:21 pm

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

User avatar
Phlembac Adib Hasan
Posts:1016
Joined:Tue Nov 22, 2011 7:49 pm
Location:127.0.0.1
Contact:

Re: Welcome to congruence

Unread post by Phlembac Adib Hasan » Tue Feb 21, 2012 7:05 pm

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)\]
Welcome to BdMO Online Forum. Check out Forum Guides & Rules

User avatar
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

Unread post by Perseus n Harry » Sun Feb 17, 2013 5:53 pm

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.

User avatar
Fahim Shahriar
Posts:138
Joined:Sun Dec 18, 2011 12:53 pm

Re: Welcome to congruence

Unread post by Fahim Shahriar » Sun Feb 17, 2013 8:49 pm

$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)$
Name: Fahim Shahriar Shakkhor
Notre Dame College

User avatar
Phlembac Adib Hasan
Posts:1016
Joined:Tue Nov 22, 2011 7:49 pm
Location:127.0.0.1
Contact:

Re: Welcome to congruence

Unread post by Phlembac Adib Hasan » Mon Feb 18, 2013 9:28 am

Perseus 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).
Download this file: http://www.matholympiad.org.bd/forum/do ... php?id=425

বি. দ্র. গতকাল থেকে জুম আলট্রা আমাকে অতি উচ্চমার্গীয় পেইন দিচ্ছে। এদের নেটওয়ার্কে সম্ভবত কোন সমস্যা হয়েছে, স্পিড এত কম যে আধঘণ্টা বসে থাকলেও গুগোল আসে না। মেজাজ এমন গরম হয় যে... তবু আজকে নানা কাহিনী করে, সব ইমেজ ডিজঅ্যাবল করে, একসাথে পঁচিশটা ট্যাব খুলে ফোরামে ঢুকে গেলাম। সৌরভদার সাথে বড় কয়েকটা পোস্ট দেওয়ার কথা ছিল, মনে হচ্ছে আজ আর দেয়া যাবে না। সো কালকে দেখি। :roll:
Welcome to BdMO Online Forum. Check out Forum Guides & Rules

Prosenjit Basak
Posts:53
Joined:Wed Nov 28, 2012 12:48 pm

Re: Welcome to congruence

Unread post by Prosenjit Basak » Mon Feb 18, 2013 9:44 pm

Phlembac Adib Hasan wrote: বি. দ্র. গতকাল থেকে জুম আলট্রা আমাকে অতি উচ্চমার্গীয় পেইন দিচ্ছে। এদের নেটওয়ার্কে সম্ভবত কোন সমস্যা হয়েছে, স্পিড এত কম যে আধঘণ্টা বসে থাকলেও গুগোল আসে না। মেজাজ এমন গরম হয় যে... তবু আজকে নানা কাহিনী করে, সব ইমেজ ডিজঅ্যাবল করে, একসাথে পঁচিশটা ট্যাব খুলে ফোরামে ঢুকে গেলাম। সৌরভদার সাথে বড় কয়েকটা পোস্ট দেওয়ার কথা ছিল, মনে হচ্ছে আজ আর দেয়া যাবে না। সো কালকে দেখি। :roll:
আমারও তো একই প্রবলেম। গুগল কেন? আমার তো যেকোনো পেজ ওপেন করতেই দিন কাবার হইয়া যায়। শুধু জুম আলট্রা না আমার গ্রামিন ফোনের ও একই অবস্থা। :cry: আর Novho(Perseus n Harry) তুই MPMS এর website থেকেও পড়তে পারিস ।
http://testzone.comuf.com/pdf/congruence.pdf
Yesterday is past, tomorrow is a mystery but today is a gift.

User avatar
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

Unread post by Perseus n Harry » Mon Feb 18, 2013 10:56 pm

Thanks for the tip :lol:
What matters most is what you do,rest all are TRASH.

Post Reply