Number Theory: Let p be an odd number. Recall that a primitive root, mod p, is...

Number Theory:

Let p be an odd number. Recall that a primitive root, mod p, is an integer g such that g^p-1 = 1 mod p, and no smaller power of g is congruent to 1 mod p. Some results in this chapter can be proved via the existence of a primitive root(Theorem 6.26)

(c) Given a primitive root g, and an integer a such that a is not congruent to 0 mod p, prove that a is a square modulo p if and only if a = g^e for an even number e. Use this to prove Euler's criterion: a is a square mod p if and only if a^(p-1)/2 = 1 mod p.

Solutions

Expert Solution

Colby Messinger answered 1 year ago

Next > < Previous

Related Solutions

Let p be an odd prime. (a) (*) Prove that there is a primitive root modulo...

Let p be an odd prime. (a) (*) Prove that there is a primitive root modulo p2 . (Hint: Use that if a, b have orders n, m, with gcd(n, m) = 1, then ab has order nm.) (b) Prove that for any n, there is a primitive root modulo pn. (c) Explicitly find a primitive root modulo 125. Please do all parts. Thank you in advance

(a) Let n be odd and ω a primitive nth root of 1 (means that its...

(a) Let n be odd and ω a primitive nth root of 1 (means that its order is n). Show this implies that −ω is a primitive 2nth root of 1. Prove the converse: Let n be odd and ω a primitive 2nth root of 1. Show −ω is a primitive nth root of 1. (b) Recall that the nth cyclotomic polynomial is deﬁned as Φn(x) = Y gcd(k,n)=1 (x−ωk) where k ranges over 1,...,n−1 and ωk = e2πik/n is...

Recall that a∈Z/nZ is called a primitive root modulon, if the order of a in Z/nZ...

Recall that a∈Z/nZ is called a primitive root modulon, if the order of a in Z/nZ is equal to φ(n). We have seen in class that, if p is a prime, then we can always find primitive roots modulop.Find all elements of (Z/11Z)∗ that are primitive roots modulo 11.

Let P(n) := ” If n^3 is odd then n is also odd.” I.e., if ∃k...

Let P(n) := ” If n^3 is odd then n is also odd.” I.e., if ∃k ∈ Z, n3 = 2k + 1, ∃b ∈ Z, n = 2b + 1 a) Prove P(n) by contraposition b) Prove P(n) contradiction c) Prove P(n) using induction

let p = 1031, Find the number of solutions to the equation x^2 -2 y^2=1 (mod...

let p = 1031, Find the number of solutions to the equation x^2 -2 y^2=1 (mod p), i.e., the number of elements (x,y), x,y=0,1,...,p-1, which satisfy x^2 - 2 y^2=1 (mod p)

Let p be an odd prime and a be any integer which is not congruent to...

Let p be an odd prime and a be any integer which is not congruent to 0 modulo p. Prove that the congruence x 2 ≡ −a 2 (mod p) has solutions if and only if p ≡ 1 (mod 4). Hint: Naturally, you may build your proof on the fact that the statement to be proved is valid for the case a = 1.

Number Theory Show that 18! = -1 (mod 437 = 19x23)

In this problem, we will implement an nth root finder. Recall that the nth root of...

In this problem, we will implement an nth root finder. Recall that the nth root of x, written n√ x, is the number when raised to the power n gives x. In particular, please fill in the findNthRoot(int number, int n, int precision) method in the class NthRootFinder. The method should return a string representing the nth root of number, rounded to the nearest precision decimal places. If your answer is exact, you should fill in the answer with decimal...

An element a in a field F is called a primitive nth root of unity if...

An element a in a field F is called a primitive nth root of unity if n is the smallest positive integer such that an=1. For example, i is a primitive 4th root of unity in C, whereas -1 is not a primitive 4th root of unity (even though (-1)4=1). (a) Find all primitive 4th roots of unity in F5 (b) Find all primitive 3rd roots of unity in F7 (c) Find all primitive 6th roots of unity in F7...

Let the market demand curve for a good be: P = 50 – Q/10. a. Recall...

Let the market demand curve for a good be: P = 50 – Q/10. a. Recall that if the market demand curve is linear, the marginal revenue curve is also linear, with the same price-axis intercept and a slope equal to twice the slope of the demand curve. Write out the marginal revenue curve for this market demand curve. b. The elasticity of demand can be written as (1/slope)*(P/Q). Find the elasticity of demand for this market demand curve at...

Subjects