
Number Theory Number Theory Math Forum 
 LinkBack  Thread Tools  Display Modes 
May 23rd, 2016, 10: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 23rd, 2016 at 11:17 PM. 
May 24th, 2016, 12:05 AM  #2 
Global Moderator Joined: Dec 2006 Posts: 19,291 Thanks: 1683 
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, 06: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{1311}{2}]}\equiv1\equiv(3x + 1)^{65}\pmod{131}$. Hence $(3x + 1)^{65}\equiv1\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, 12:48 PM  #4 
Global Moderator Joined: Dec 2006 Posts: 19,291 Thanks: 1683 
1. Obviously, x =10 (mod 131) works. By trial and error, x = 118 (mod 131) also works.

May 24th, 2016, 07:20 PM  #5 
Senior Member Joined: Dec 2007 Posts: 687 Thanks: 47  

Tags 
modulo, questions, solve 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Here are 2 questions out of 3, which I don't know how to solve. Please help.  mohan  Probability and Statistics  7  December 22nd, 2014 10:38 AM 
Please Solve These Questions  Honey01  Elementary Math  4  October 12th, 2014 08:41 PM 
Can somebody help me solve these few questions  thinkdougie  Algebra  26  January 19th, 2012 07:09 AM 
How can I solve these two questions?  rsoy  Physics  1  January 4th, 2011 09:59 AM 
How I can solve these two Questions  rsoy  Calculus  7  December 21st, 2010 09:04 AM 