i would like to solve these 2 problems ..

let be p and q two primes so n=p.q is known and we must determine the primes p and q is so easy as solving the system

$$n=p.q$$ and $$\sigma _{1} (n)=1+p+q+n$$

with 'sigma' the divisor function that gives us the sum of the divisors of a certain number 'n' but is really so easy?

the second question is given the congruence $$f(x)=0 mod(p)$$ and N(x) the number of solutions of the congruence above on the interval [0,x] is there a generating function (of any type) to compute N(x) ??

Related Linear and Abstract Algebra News on Phys.org
HallsofIvy
Homework Helper
It's not clear to me what you mean by "so easy". You can't know $\sigma_1(n)$ until you know the factors of n, in which case you already have p and q. In other words, determining the two primes p and q is "just as easy" as factoring n!

But according to Wikipedia (here is the apparent paradox) you can compute the divisor function as a double series involving cosine

$$\sigma_x(n)=\sum_{\mu=1}^{n} \mu^{x-1}\sum_{\nu=1}^{\mu}\cos\frac{2\pi\nu n}{\mu}$$

http://en.wikipedia.org/wiki/Divisor_function

CRGreathouse
Homework Helper
Factoring by trial division takes at most $\sqrt n$ divisions (or at most $2+\sqrt n/3$ divisions with 2, 3, and numbers 1,5 mod 6, or at most $\pi(\sqrt n)$ with a precalculated list of primes), while that double sum takes $n^2/2$ trig evaluations. That's a serious slowdown over an already slow method of factoring -- not the mention the roundoff error!

i think that the sum over $$\nu$$ can be evaluated exactly , so the expression becomes a simple sum over 'mu'

CRGreathouse
Homework Helper
i think that the sum over $$\nu$$ can be evaluated exactly , so the expression becomes a simple sum over 'mu'
If you can calculate $sum_{\nu=1}^{\mu}\cos\frac{2\pi\nu n}{\mu}$ in unit time, computing
$$\sum_{\mu=1}^N\mu^{x-1}\sum_{\nu=1}^{\mu}\cos\frac{2\pi\nu N}{\mu}$$
takes time
$$O(2^n)$$ (with $2^{n-1}\le N<2^n$)
which is not nearly competitive with the
[tex]O\left(2^{n^{1/3+\varepsilon}}\right)[/itex]
of GNFS.