My Math Forum Can anyone help me solve these questions? modulo questions

 Number Theory Number Theory Math Forum

 May 23rd, 2016, 11:24 PM #1 Newbie   Joined: May 2016 From: London Posts: 1 Thanks: 0 Can anyone help me solve these questions? modulo questions I am struggling with several questions, hope someone could help me!! 1. Find the number of solutions of x^2 + 3x + 1 = 0 (mod 131) What is the algorithm for this kind of questions?? Because 131 is so large that you cannot try numbers... 2. Show 9^55 = 1 (mod 2783) I know 2783 is 11^2 * 23, but if I apply Euler's theorem, I can only get 9^10 = 1 mod 11 and 9^22 = 1 mod 23... multiply together I can't see how I can get to 9^55 3. Which of the numbers are primitive roots modulo 257: 2,3,5,6,7 For large number, how do I check if a number is its primitive root? Thank you so much!!!!!!!!!!!!! Last edited by skipjack; May 24th, 2016 at 12:17 AM.
 May 24th, 2016, 01:05 AM #2 Global Moderator   Joined: Dec 2006 Posts: 19,968 Thanks: 1850 2. By direct calculation, 9^5 ≡ 1 (mod 11²) and 9^11 ≡ 1 (mod 23). (Alternatively, if you would prefer easier calculation, first show that 3^5 ≡ 1 (mod 11²) and 3^11 ≡ 1 (mod 23), which imply the previous congruences.) It's easy from there.
 May 24th, 2016, 07:40 AM #3 Senior Member   Joined: Dec 2007 Posts: 687 Thanks: 47 For 1., a useful fact related is a theorem of Lagrange, which says that for any polynomial the equation $$a_nx^n+...+a_1x+a_0=0$$ cannot have more solutions modulo a prime number than its degree. So, there are at most $n$ solution for $$a_nx^n+...+a_1x+a_0\equiv0\pmod p.$$ Thus $x^2 + 3x + 1\equiv0\pmod{131}$ has no more than two solutions. Notice that $x^2 + 3x + 1\equiv0\pmod{131}\Rightarrow x^2\equiv-(3x + 1)\pmod{131}\Rightarrow \left(x^2\right)^{65[=\frac{131-1}{2}]}\equiv1\equiv-(3x + 1)^{65}\pmod{131}$. Hence $(3x + 1)^{65}\equiv-1\pmod{131}$ will find solutions where $3x+1$ is a primitive root modulo 131. Now, get the list of primitive roots modulo 131 and check which are of the form $3x+1$, that is, whether in the list $$4,7,10,13,16,19,22,25,...,127,130$$ we have no more than two primitive roots.
 May 24th, 2016, 01:48 PM #4 Global Moderator   Joined: Dec 2006 Posts: 19,968 Thanks: 1850 1. Obviously, x =10 (mod 131) works. By trial and error, x = 118 (mod 131) also works. Thanks from al-mahed
May 24th, 2016, 08:20 PM   #5
Senior Member

Joined: Dec 2007

Posts: 687
Thanks: 47

Quote:
 Originally Posted by skipjack 1. Obviously, x =10 (mod 131) works. By trial and error, x = 118 (mod 131) also works.
True, but the problem asked the number of solutions. But yes, trial and error and Lagrange show the same in fewer lines.

 Tags modulo, questions, solve

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post mohan Probability and Statistics 7 December 22nd, 2014 11:38 AM Honey01 Elementary Math 4 October 12th, 2014 09:41 PM thinkdougie Algebra 26 January 19th, 2012 08:09 AM r-soy Physics 1 January 4th, 2011 10:59 AM r-soy Calculus 7 December 21st, 2010 10:04 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top