[quote=R.D. Silverman;211884]

Show your work.



problems.[/quote]
Ok so, the function is:
F(N)=F(N-1)+N.

By the chinese reminder theorem (as I understood), for N=pq...z
for p,q,...,z primes.
The number of numbers a such that x=a(mod N) is the number of prime factors of N.
Why won't it be the same with x^2? (I'm really not sure I understood the chinese reminder theorem...).

[QUOTE=blob100;211888]Ok so, the function is:
F(N)=F(N-1)+N.

[/QUOTE]

And? Express F(N) as a polynomial in N. Prove it by induction.

[QUOTE]

By the chinese reminder theorem (as I understood), for N=pq...z
for p,q,...,z primes.

The number of numbers a such that x=a(mod N) is the number of prime factors of N.
[/QUOTE]

This is not a correct statement. And you have not defined x.

[QUOTE]
Why won't it be the same with x^2? (I'm really not sure I understood the chinese reminder theorem...).[/QUOTE]

I thought you said that you understood quadratic residues? This problem
tests that knowledge.

Firstly, x^2 = a mod N may not HAVE a solution (depending on N).
Under what conditions does a solution exist?

Suppose N = pq, p,q, are odd primes. Under what conditions does
x^2 = a mod N have a solution? Now ask how many solutions exist.
Note that if x0 is a solution, then so is -x0. Also consider what happens if
N is prime.

Now ask:

if x^2 = a mod p has k solutions and
x^2 = a mod q has k1 solutions, how many solutions are there to
x^2 = a mod p*q??????? Apply the CRT!

Now generalize to when N has more than 2 prime factors!

[quote=R.D. Silverman;211891]And? Express F(N) as a polynomial in N. Prove it by induction.


[/quote]

The polynomial: F(N)=N^2-((N-1)N)/(2)+1 for even N.
and for odd N, F(N)=N^2-((N-1)N)/(2).

[quote=wblipp;211876]A promising start. You really should define all the terms - you have used N, f, and F. You could wiggle away on the grounds that they are implicit in the problem statement and a typo to have both f and F, but it's better get in the habit.

The answer is incomplete because there isn't any way to start evaluating the f's (or F's). We usually handle that by giving the value for some small value of N - perhaps 0 or +1 or -1. With that, it's possible to calculate f (for larger integral N).

The proof is incomplete because you haven't offered any rationale for the statement.

And a closed form solution, so that we could calculate f(100000000000) without all the intermediate terms, would be nice if you can find one.

Your next assignment is to see how many of these shortcomings you can fix and post again.

William[/quote]
A keyboard mistake, I was about to write F instead of "f".

[QUOTE=blob100;211927]The polynomial: F(N)=N^2-((N-1)N)/(2)+1 for even N.
and for odd N, F(N)=N^2-((N-1)N)/(2).[/QUOTE]

This is two different polynomials. Express it as a SINGLE polynomial.

[QUOTE=blob100;211927]The polynomial: F(N)=N^2-((N-1)N)/(2)+1 for even N.
and for odd N, F(N)=N^2-((N-1)N)/(2).[/QUOTE]

Hint - it's always a good idea to test two or three values. With two formulas, you should test two or three values in each formula.

[quote=R.D. Silverman;211932]This is two different polynomials. Express it as a SINGLE polynomial.[/quote]
I don't know how to express it as a single polynomial, I found these:

F(N)=(N^2+N)/2+1 for N=2n.
F(N)=(N^2+N)/2 for N=2n+1.

Maybe I can show a symbol? is it what you want?
Like (N|1) means if N=2n (N|1)=1, and if N=2n+1, (N|1)=0.
So:
F(N)=(N^2+N)/2+(N|1).
I guess not..

[QUOTE=blob100;211948]I don't know how to express it as a single polynomial, I found these:

F(N)=(N^2+N)/2+1 for N=2n.
F(N)=(N^2+N)/2 for N=2n+1.

Maybe I can show a symbol? is it what you want?
Like (N|1) means if N=2n (N|1)=1, and if N=2n+1, (N|1)=0.
So:
F(N)=(N^2+N)/2+(N|1).
I guess not..[/QUOTE]

Your recursive formula is correct. The rest is not.

Hint: With N = 1, there are 2 regions.
with N = 2, there are 4 regions
with N = 3, there are 7 regions,
with N = 4, there are 11 regions
etc.

Letting N --> N+1 increases the value of the polynomial [b]linearly[/b] with
N.

What can you say therefore about the degree of the polynomial? Can
you not find a polynomial that fits these values?

Now prove your result by induction using the recursion.

[QUOTE=R.D. Silverman;211891]And? Express F(N) as a polynomial in N. Prove it by induction.



This is not a correct statement. And you have not defined x.



I thought you said that you understood quadratic residues? This problem
tests that knowledge.

Firstly, x^2 = a mod N may not HAVE a solution (depending on N).
Under what conditions does a solution exist?

Suppose N = pq, p,q, are odd primes. Under what conditions does
x^2 = a mod N have a solution? Now ask how many solutions exist.
Note that if x0 is a solution, then so is -x0. Also consider what happens if
N is prime.

Now ask:

if x^2 = a mod p has k solutions and
x^2 = a mod q has k1 solutions, how many solutions are there to
x^2 = a mod p*q??????? Apply the CRT!

Now generalize to when N has more than 2 prime factors![/QUOTE]

Allow me to add a further hint. The number of solutions depends on whether
(a,N) = 1. If (a,N) != 1, then the number of solutions gets reduced
depending on how many factors of N divide a.

[quote=R.D. Silverman;211966]Allow me to add a further hint. The number of solutions depends on whether
(a,N) = 1. If (a,N) != 1, then the number of solutions gets reduced
depending on how many factors of N divide a.[/quote]
Let me ask you some questions:
The solution in a congruent arithmetics is the N for a=b(mod N) right?
And the residue classes are the group of b numbers such that a is (a,N)=1, a<N.
And quadratic residue classers are for a=x^2.
In the chinese reminders are the x for x=a(mod N) is (x,N)=1, x<N?
More than it, In your problem, is (x,N)=1 and x<N?
Thanks.

[QUOTE=blob100;212019]Let me ask you some questions:
The solution in a congruent arithmetics is the N for a=b(mod N) right?

[/QUOTE]

You need to learn how to pose a question completely.
You say "the solution". Which solution? What is the problem?

[QUOTE]
And the residue classes are the group of b numbers such that a is (a,N)=1, a<N.

[/QUOTE]


No. A residue class is an equivalence relation (look up 'equivalence relation'
in Wikipaedia.)

Basically, if we have a modulus N, and an integer a [a is NOT required to
be co-prime to N], then the residue class equal to a is the set of ALL
integers that are equivalent (not equal, but equivalent, hence 'equivalence
class) to a mod N. The class is therefore

.....a-2N, a-N, a, a+N, a+2N, etc.

example. Consider the integers that are in the class 2 mod 5. These are

....-8, -3, 2, 7, 12, ....17

The REDUCED residues mod N are those integers that are in [0, N-1].

[QUOTE]
And quadratic residue classers are for a=x^2.
[/QUOTE]



One usually does not see the expression 'quadratic residue classes'.
A quadratic residue mod N is an integer a such that a solution exists to
x^2 = a mod N. a is an equivalence class just like any other equivalence class.
[QUOTE]

In the chinese reminders are the x for x=a(mod N) is (x,N)=1, x<N?

[/QUOTE]

This question shows confusion. There is no such thing as "chinese remainders". May I suggest that you look up the Chinese Remainder THEOREM
and read it carefully?



[QUOTE]

More than it, In your problem, is (x,N)=1 and x<N?
Thanks.[/QUOTE]

Once again, you need to learn how to pose questions completely.
I gave 3 number theory problems. To which one do you refer?