I'll try first to solve problem number 4.
x^2=a(mod p)
For (x,p)=1 and x<p, we have (p-1)/2 numbers a which agree the phrase.
((p-1)/2 quadratic residue classes modulo p).

We define R(n) as the set of the quadratic residue classes of a prime number p_n where (p_n,N)=p_n. (n counter).
N=(p_1)(p_2)...(p_n)
#(R(n))=(p_n-1)/2.
We have the number of the quadratic residue classes of N:
#((R(1))U(R(2))U(R(3))...U(R(n)))
Where # means the number of units in a set, and U as the uninon sign.

Is this the direction?

[QUOTE=blob100;215493]I'll try first to solve problem number 4.
x^2=a(mod p)
For (x,p)=1 and x<p, we have (p-1)/2 numbers a which agree the phrase.
((p-1)/2 quadratic residue classes modulo p).
[/QUOTE]

a is GIVEN. How many values of [b]x[/b] satisfy the congruence?
And you have not defined p here. Is it prime?

BTW, restricting p to be prime is a good start on the problem.
Then look at x^2 = a mod pq where p and q are prime. Think
about the Chinese Remainder Theorem.


[QUOTE]
We define R(n) as the set of the quadratic residue classes of a prime number p_n where (p_n,N)=p_n. (n counter).
N=(p_1)(p_2)...(p_n)
#(R(n))=(p_n-1)/2.
We have the number of the quadratic residue classes of N:
#((R(1))U(R(2))U(R(3))...U(R(n)))
Where # means the number of units in a set, and U as the uninon sign.

Is this the direction?[/QUOTE]

No.

[quote=R.D. Silverman;215494]a is GIVEN. How many values of [B]x[/B] satisfy the congruence?
And you have not defined p here. Is it prime?

BTW, restricting p to be prime is a good start on the problem.
Then look at x^2 = a mod pq where p and q are prime. Think
about the Chinese Remainder Theorem.
[/quote]
I understood that the direction is using the Chinese Reminder Theorem.
My problem is finding the connection.
The Chinese Reminder Theorem assumes that:
For a,b any positive integers and p,q co-prime positive integers
We have an integer N such that:
N=a(mod p).
N=b(mod q).
I guess this gives:
N=c(mod pq).
But I can't find the connection to the problem which is:
How many numbers x stisfy the congruence x^2=a(mod N)
(For x,a,N defined on the last posts, not as it defined on this post)).

I'll try now to solve the fermat factors problems.
We have q|2^(2^n)+1 (q not nessecarily a prime).
We found that: q|2^((q-1)/2).
q|2^p-1.
2 is of order p modulo q.
(2^(2^n)+1)(2^(2^n)-1)=2^(2^n+1)-1.
q|2^(2^n+1)-1.
(2^(2^n+1)-1,2^((q-1)/2))=q.
q|2^p-1.
(2^(n+1),(q-1)/2)=p.
2^(n+1)=(q-1)/2(mod p).
q-1=2^(n+2)(mod p).
2^(n+2)|q-1.
q=2^(n+2)k+1.

[QUOTE=blob100;215503]I understood that the direction is using the Chinese Reminder Theorem.
My problem is finding the connection.
The Chinese Reminder Theorem assumes that:
For a,b any positive integers and p,q co-prime positive integers
We have an integer N such that:
N=a(mod p).
N=b(mod q).
I guess this gives:
N=c(mod pq).
But I can't find the connection to the problem which is:
How many numbers x stisfy the congruence x^2=a(mod N)
(For x,a,N defined on the last posts, not as it defined on this post)).[/QUOTE]

Well, if there are multiple values of x for which

x^2 = a mod p

and there are multiple values of y for which

y^2 = a mod q,

How many DIFFERENT values z are there for which

z^2 = a mod pq??????

[quote=R.D. Silverman;215524]Well, if there are multiple values of x for which

x^2 = a mod p

and there are multiple values of y for which

y^2 = a mod q,

How many DIFFERENT values z are there for which

z^2 = a mod pq??????[/quote]

Maybe (pq-1)/2?

[QUOTE=blob100;215532]Maybe (pq-1)/2?[/QUOTE]

No. How can the answer possibly depend on p and q, but NOT on
the number of solutions for p,q, individually???

You need to LEARN the CRT.

[quote=R.D. Silverman;215542]No. How can the answer possibly depend on p and q, but NOT on
the number of solutions for p,q, individually???

You need to LEARN the CRT.[/quote]
What CRT is?
I guess Chinese Reminder Theorem.
I think I know what it is:
for two positive integers (p,q)=1, and other two positive integers a,b, we have a positive integer x such that:
x=a(mod p).
x=b(mod q).
Moreover, we have x=c(mod pq).

[QUOTE=blob100;215547]What CRT is?
I guess Chinese Reminder Theorem.
I think I know what it is:
for two positive integers (p,q)=1, and other two positive integers a,b, we have a positive integer x such that:
x=a(mod p).
x=b(mod q).
Moreover, we have x=c(mod pq).[/QUOTE]

You can state the theorem. Can you USE it? Apply it to my earlier question.
If x^2 = a mod p and y^2 = a mod q, how many solutions are there
to z^2 = a mod pq??

[quote=R.D. Silverman;215559]You can state the theorem. Can you USE it? Apply it to my earlier question.
If x^2 = a mod p and y^2 = a mod q, how many solutions are there
to z^2 = a mod pq??[/quote]
By symetric relation we have:
a=x^2(mod p)
a=y^2(mod q)
a=z^2(mod pq)
So, for every pair of two solutions for p,q we have a simple solution for pq.

[QUOTE=blob100;215590]By symetric relation we have:
a=x^2(mod p)
a=y^2(mod q)
a=z^2(mod pq)
So, for every pair of two solutions for p,q we have a simple solution for pq.[/QUOTE]

No. You are missing it. I will explain.

You get FOUR (4) solutions for pq.

We have x^2 = a mod p. Say this is satisfied by x1, x2.
We have y^2 = a mod q. Say this is satified by y1 , y2

Now we combine x1, y1, x1, y2, x2, y1 and x2,.y2 together mod pq
to get 4 solutions.

Why is this so hard? Once again, it just comes down to the good use
of VARIABLES. Identify your variables! Define them!