Monday, July 25, 2011

Number Theory - Concrete Mathematics 4.9 (2/10)

The text of the question is:
Show that the number $(3^{77}-1)/2$ is odd and composite.
The hint proposed in the question text is to compute $3^{77} \mod\  4$ (mod means division reminder: $ 13 \mod\ 5\ =\ 3$). Let's do that then. The useful think is that there is only a small number of possible reminders mod 4 (four exactly), so we if we calculate first, second, third etc. power of 3 we will have some cycle:
$ 3 \mod\ 4\ =\ 3$
$ 3^2 \mod\ 4\ =\ 1$
$ 3^3 \mod\ 4\ =\ 3$
$ 3^4 \mod\ 4\ =\ 1$
Bum! Pattern spotted. Therefore: $3^{77} \mod\  4\ =\ 3$. Now by simple transform:
$3^{77}-1 \mod\  4\ =\ 2$
$(3^{77}-1)/2 \mod\  2\ =\ 1$
So the number is odd. If any of above transformations confuses you please read about modular arithmetic. The prove that it's composite you have to know some of the less popular quick multiplication formulas:
In our case formula is a little simpler:
$a^n-1 = (a-1)(a^{n-1}+ .. + 1)$
Now how to use it? $a = 3$ gives factor of 2 but we divide by two in the formula, so that's not helpful, right?



And I have to admit a fall for this a the beginning, but after consultation with a friend I went back on the right path:
Let's consider $ a = 3^{7}$. It gives us
$(3^7)^{11}-1 = (3^7-1)*((3^7)^{10} + (3^7)^9.. + 1)$
Where X is some integer greater than one. So then 
$( (3^{77}-1)/2 = (3^7-1)/2 * ((3^7)^{10} + (3^7)^9.. + 1) $,  so it's composite. Eureca!

OK. I have to admit this question was boring. I am sorry I picked up question at random just to write some test thing on blog. It was a little challenging but come on, who likes tedious arithmetic? 


  1. نحن نعمل علي تقديم شركة نقل اثاث بجدة وتوفير افضل خدمات شركة نقل عفش بجدة واهم شركات نقل العفش بجدة
    شركة نقل عفش بجدة
    نقل العفش بجدة
    نقل عفش بجدة
    نقل اثاث بجدة
    شركة نقل اثاث بجدة
    ارخص شركة نقل اثاث بجدة

  2. افضل شركة تنظيف منازل بالرياض شركة تنظيف بيوت بالرياض
    سرعان ما تتعرض البيوت لانتشار الشوائب والأتربه والاتساخات الخطيرة ؛لذلك فكافه أجزاء البيوت تحتاج الى أعمال تنظيف دورية ومستمرة ؛فالبيوت من اثاث سواء مجالس أو غرف نوم أو سفر أو صالونات تحتاج الى أعمال تنظيف ؛كما تتمكن شركة تنظيف منازل من القيام بأعمال تنظيف البيوت ومكافحة الحشرات وتنظيف الخزانات وكشف تسربات الماء وغيرها من الأجزاء الأخرى ؛لذلك من الأن لا داعى للقلق بشأن أعمال تنظيف البيوت ؛نحن شركة تنظيف بالرياض التى تعتمد على فريق عمل متخصص لديه خبرات واسعه فى القيام بأعمال تنظيف البيوت .

    تتراكم الأتربه والشوائب فى البيوت مسببة فى تعرض البيوت للعديد من الأمراض الخطيرة التى تؤثر سلبيا على الأفراد ؛فالبيوت تتعرض للنوافذ والشبابيك وغيرها من المنافذ التى سرعان ما تتعرض للعديد من الشوائب والعوالق الخطيرة ؛لذلك يتم الاعتماد على مجموعه من الألات والمعدات الحديثة وأجهزة البخار التى تساعد على التخلص من الشوائب والعوالق سريعا ؛فقط شركة تنظيف منازل بالرياض تعتمد على أحدث وأفضل الأساليب... اقرأ المزيدشركة-تنظيف-منازل-بالرياض/

    المصدر: شركة تنظيف منازل بالرياض

    المصدر: شركة تنظيف بيارات بالرياض