Answer to Question #269281 in Algebra for Random

Question

(a) What are quadratic residues and nonresidues?

(b) Write down the denition of elite primes in mathematical terms.

(c) Prove that

Q2t

i=0

Fi = 222t+1 􀀀 1.

(d) What does the  in the Brun-Titchmarsh inquality represent?

(e) Explicitly show that (x; 2t; 1)  x

2t .

(f) What can you say about the upper bound of E(x) for numbers of the form 32n + 1?

Answer 1

a)

Let m be a positive integer. An integer a is a quadratic residue of m if (a,m)=1and the congruence $x^2≡a(mod\ m)$  is solvable. If the congruence $x^2≡a(mod\ m)$  has no solution, then a is a quadratic nonresidue of m.

b)

A prime number p is elite if only finitely many Fermat numbers $F_m = 2^{2m} + 1$ are quadratic residues of p.

c)

$i=0$

Fermat numbers:

$F_i = 2^{2^i}+1$

$F_0 = 2^{2^0}+1 =3$

d)

Brun-Titchmarsh inequality is an upper bound on the distribution of prime numbers in arithmetic progression. Primes in arithmetic progression are any sequence of at least three prime numbers that are consecutive terms in an arithmetic progression.

let $\pi(x,q,a)$ count the number of primes p congruent to a modulo q with p ≤ x. Then

$\pi(x,q,a)\le \frac{2x}{\varphi(q)log(x/q)}$ for all q < x

where $\varphi(q)$ is Euler's totient function that counts the positive integers up to a given integer q that are relatively prime to q.

e)

for arithmetic progression:

$x_t=1+2t$

primes are: $x_1=3,x_2=5,x_3=7$

so, this is primes in arithmetic progression.

f)

for 32n + 1:

$\pi(x,32,1)\le \frac{2x}{\varphi(32)log(x/32)}$

relatively prime to 32: 1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31

so, $\varphi(32)=16$

then:

$\pi(x,32,1)\le \frac{x}{8log(x/32)}$