Question

If p = 2k − 1 is prime, show that k is an odd integer or k = 2.

Hint: Use the difference of squares 22m − 1 = (2m − 1)(2m + 1).

Answer #1

Hence k is odd or k=2.

1. Prove that {2k+1: k ∈ Z}={2k+3 : k ∈ Z}
2. Prove/disprove: if p and q are prime numbers and p < q,
then 2p + q^2 is odd (Hint: all prime numbers greater than 2 are
odd)

Let m = 2k + 1 be an odd integer. Prove that k + 1 is the
multiplicative inverse of 2, mod m.

Let p be an odd prime and let a be an odd integer with p not
divisible by a. Suppose that p = 4a + n2 for some
integer n. Prove that the Legendre symbol (a/p) equals 1.

Suppose p is a positive prime integer and k is an integer
satisfying 1 ≤ k ≤ p − 1. Prove that p divides p!/ (k! (p-k)!).

Let b be a primitive root for the odd prime p. Prove that b^k is
a primitive root for p if and only if gcd(k, p − 1) = 1.

Suppose that a random odd integer p is chosen from {1, … ,
2^1024} and p passes Miller’s test for 10 different
values of a. What is the probability that p is prime?

Let p be an odd prime of the form p = 3k+2. Show that if a^3 ≡
b^3 (mod p), then a ≡ b (mod p). Conclude that 1^3,2^3,…,p^3 form a
complete system of residues mod p.

Supose p is an odd prime and G is a group and |G| = p 2 ^n ,
where n is a positive integer. Prove that G must have an element of
order 2

Prove that for any integer a, k and prime p, the following three
statements are all equivalent: p divides a, p divides a^k, and p^k
divides a^k.

let x be a discrete random variable with positive integer
outputs.
show that P(x=k) = P( x> k-1)- P( X>k) for any positive
integer k.
assume that for all k>=1 we have P(x>k)=q^k. use (a) to
show that x is a geometric random variable.

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 19 minutes ago

asked 36 minutes ago

asked 45 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 2 hours ago