Thread: A Factorization Algorithm View Single Post

Recognitions:
Homework Help
 Quote by Playdo, 1st post Clearly for certain special numbers N we have a one to one map of factor pairs of N and factor pairs of n+1 which is much smaller.
Why is that? If N is of the form 1 + ... + an, then how do we know all factor pairs of N contain one factor of the form 1 + ... + am? In other words, why is it clear that if a number has a base-a expansion 111....111 that any factor pair of that number has at least one of the factors also being in the form 111....111 (but with fewer 1's normally, of course)?

Also, for your interest, $\beta$ is not a capital letter. Capital Beta looks just like the captial roman B. When using LaTeX, if you write a greek letter in lower case, like so \pi, then you'll get the lower case $\pi$ and if you write it like \Pi then you'll get $\Pi$. Also, when using LaTeX in the same line as your text, use "itex" tags instead of "tex". So you'd write [ itex ]\phi ^2 - \phi - 1 = 0[ /itex ] to have the markup right in line $\phi ^2 - \phi - 1 = 0$. To have it bigger and on a separate line:

[ tex ]\phi ^2 - \phi - 1 = 0[ /tex ]

$$\phi ^2 - \phi - 1 = 0$$
 Quote by Playdo, 3rd post For every composite natural number $$N$$ there must be a reducible polynomial $$p(x)$$ over the natural numbers and a natural number $$a$$ for which $$N=p(a)$$ and at least one factor pair $$s$$ and $$t$$ of $$p$$ evaluated at $$a$$ satisfy $$N=p(a)=s(a)t(a)$$.
The last part, that at least one factor pair s and t satisfies N = p(a) = s(a)t(a) seems redundant from the fact that p is reducible and N is composite. I don't quite understand the point of your proof, the result seems trivial.

Let N be composite, say N = nm for n, m > 1. If you define 0 to be a natural, let a be any natural less than or equal to min{n,m}. Otherwise, let a be any natural strictly less than min{n,m}. Let p(x) = (x + (n-a))(x + (m-a)).

I'm in a rush right now, but I'll look at posts 2, 4, and 5 later.