My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Thanks Tree1Thanks
  • 1 Post By skipjack
Reply
 
LinkBack Thread Tools Display Modes
May 23rd, 2016, 10:24 PM   #1
Newbie
 
Joined: May 2016
From: London

Posts: 1
Thanks: 0

Question 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.
vickyc95 is offline  
 
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.
skipjack is offline  
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{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.
al-mahed is offline  
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.
Thanks from al-mahed
skipjack is offline  
May 24th, 2016, 07:20 PM   #5
Senior Member
 
Joined: Dec 2007

Posts: 687
Thanks: 47

Quote:
Originally Posted by skipjack View Post
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.
al-mahed is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

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? r-soy Physics 1 January 4th, 2011 09:59 AM
How I can solve these two Questions r-soy Calculus 7 December 21st, 2010 09:04 AM





Copyright © 2018 My Math Forum. All rights reserved.