Definitions of the last post:
given a, some x,y and z, p,q prime numbers.
__________

So for N a product of k distinct odd primes we have k^2 solutions for:
x^2=a(mod N)
For a given "a", x some integers.

[QUOTE=blob100;215619]Definitions of the last post:
given a, some x,y and z, p,q prime numbers.
__________

So for N a product of k distinct odd primes we have k^2 solutions for:
x^2=a(mod N)
For a given "a", x some integers.[/QUOTE]

Where do you get k^2?? You seem to be simply guessing.

k^2 is not correct. You also need to consider what happens when
one (or more) of the primes dividing N also divides a. However, you should
start with the simpler case of (a,N) = 1

[quote=R.D. Silverman;215649]Where do you get k^2?? You seem to be simply guessing.

k^2 is not correct. You also need to consider what happens when
one (or more) of the primes dividing N also divides a. However, you should
start with the simpler case of (a,N) = 1[/quote]
For N=pq:
p,q odd distinct prime numbers.
We have:
x^2=a(mod p)
y^2=a(mod q)
z^2=a(mod pq)
For a given a and x variable.
YOU said there are four solutions for z:
x1y1
x2y2
x1y2
x2y1
For N=pgq product of 3 distinct odd primes we have:
x^2=a(mod p)
y^2=a(mod q)
z^2=a(mod g)
v^2=a(mod pqg)
For a given a; x,y,z and v are equivallent defined as before,(where v is stated equivallently as z was defined for N=pq).
We have 2^3 solutions for v.
____________________________________
For x^2=a(mod N)
Given a and x variable.
There are 2^k solutions x modulo N (product of k distinct odd primes).

[QUOTE=blob100;215692]For N=pq:
p,q odd distinct prime numbers.
We have:
x^2=a(mod p)
y^2=a(mod q)
z^2=a(mod pq)
For a given a and x variable.
YOU said there are four solutions for z:
x1y1
x2y2
x1y2
x2y1
For N=pgq product of 3 distinct odd primes we have:
x^2=a(mod p)
y^2=a(mod q)
z^2=a(mod g)
v^2=a(mod pqg)
For a given a; x,y,z and v are equivallent defined as before,(where v is stated equivallently as z was defined for N=pq).
We have 2^3 solutions for v.
____________________________________
For x^2=a(mod N)
Given a and x variable.
There are 2^k solutions x modulo N (product of k distinct odd primes).[/QUOTE]

And if one or more of the primes dividing N also divide a, what happens?

[quote=R.D. Silverman;215709]And if one or more of the primes dividing N also divide a, what happens?[/quote]
I'm sorry for not writing: (a,N)=1.

[QUOTE=blob100;215721]I'm sorry for not writing: (a,N)=1.[/QUOTE]

OK. Noone has weighed in on problem 2. Here it is.

Let n \in Z+, q is prime. We want

2^2^n + 1 = 0 mod q.

Whence

2^2^n = -1 mod q
2^2^(n+1) = 1 mod q. (1)

q is 1 mod 8, hence 2 is a quad. res. By Euler's criterion we
have

2^(q-1)/2 = 1 mod q. (2)

But from Lagranges's theorem, the order of an element divides the
maximal order, thus we have from (1) and (2):

2^(n+1) divides (q-1)/2.

The 2 in the denominator of the rhs is what gives us:

q = k * 2^(n+2) + 1.

[QUOTE=R.D. Silverman;215709]And if one or more of the primes dividing N also divide a, what happens?[/QUOTE]

Have you looked at this? The answer is quite simple.

[quote=R.D. Silverman;215930]OK. Noone has weighed in on problem 2. Here it is.

Let n \in Z+, q is prime. We want

2^2^n + 1 = 0 mod q.

Whence

2^2^n = -1 mod q
2^2^(n+1) = 1 mod q. (1)

q is 1 mod 8, hence 2 is a quad. res. By Euler's criterion we
have

2^(q-1)/2 = 1 mod q. (2)

But from Lagranges's theorem, the order of an element divides the
maximal order, thus we have from (1) and (2):

2^(n+1) divides (q-1)/2.

The 2 in the denominator of the rhs is what gives us:

q = k * 2^(n+2) + 1.[/quote]

I'm so stupid...

[quote=R.D. Silverman;215931]Have you looked at this? The answer is quite simple.[/quote]
Again, I'm sorry for not writing (a,N)=1.

[QUOTE=blob100;215937]Again, I'm sorry for not writing (a,N)=1.[/QUOTE]

No need to apologize. But you need to address what happens when
(a,N) > 1.

[quote=R.D. Silverman;215944]No need to apologize. But you need to address what happens when
(a,N) > 1.[/quote]
If we have (a,N)=g>1,
Where x^2=a(mod N)
(for x,N defined on the last post).
(x,a)=g.
We said that N is a product of K distinct odd primes.
g is devided by k<\=K primes which devide N.
For example:
We give N=3*5*7. K=3.
k<\=3.
We may say that for g devided by K primes which devide N,
We have (K-k)^2 solutions for x.