Prime numbers and prime factorization

Question

Can someone explain me this problem and how to approach it.

Suppose that for any n, the number r of primes that are ≤ 2^n was bounded by some fixed number c. Show that the function given by prime factorization cannot be one-to-one if n is sufficiently large.

that every positive natural x with x ≤ 2^n has a factorization into primes, so that x = (p1^e1) * (p2^e2) *.... (pr^er)

Thus we have a function from the set {1, 2, . . . , 2^n} into the set of tuples (e1, e2, . . . , er). (a) Explain why for any such x, each number ei must be in the range from 0 to n. (b) Why must this function be one-to-one?

Answer 1

(a) largest possible power is $n$ since it occurs on a factor $p_k^n$ where $p_k$ is a factor of $x.$ The prime $p_k$ here is at least $2,$ and so to get a large exponent must use the prime $2$ otherwise largest power must be even smaller. And you have already restricted $x$ to be at most $2^n.$

(b) Unique factorization, etc.

Answer 2

Let $p_1 = 2,p_2=3, p_3 =5,........,p_r$ where $p_r$ is the largest prime less than ore equal to $2^n$.

So for example if $n=7$ then $p_1=2,p=3,...., p_{30}=113, p_{31} = 127 < 128=2^7$.

So $r=31$.

Every integer $k < 2^n$ can be written as $p_1^{e_1}p_2^{e_2}....p_r^{e_r}$.

For example if $n =7$ and $k = 98$. Then $98 = 2^1*3^0*5^0*7^2*11^0*.....*113^0*127^0$. Or $42 = 2^1*3^1*5^0*7^0*.....*113^0*127^0$.

So there is a function $f: \{1,2,3,4,5,......,2^n\}\to \mathbb N^r$ so that $f(n) = (e_0,e_1,.....,e_r)$ where $n= 2^{e_0}*3^{e_1}*....$.

For example, if $n=7$ then

$f(1) = (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0)$

$f(2) =(1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0)$

$f(3)= (0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0)$

$f(4) =(2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0)$

$f(5) =(0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0)$

$f(6) =(1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0)$

...

$f(42) = (1,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0)$

....

$f(98) = (1,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0)$

.....

$f(125) =(0,0,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0)$

$f(126)= (1,2,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0)$

$f(127) =(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1)$

$f(128)=(7,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0)$

.....

Okay, got that?

Now:

(a) Explain why for any such $k$, each number $e_i$ in the $r$-tuple $f(n) = (e_1, e_2, ...., e_r)$ that $0 \le e_i \le n$.

(b) Why must this function be one-to-one?

and 3.4.8 Prove there are an infinite number of primes. Suppose that If there are $r$ primes less then $2^n$ and $r$ must be less than $c$ for every $n$. Then show the function above can not be one-to-one for some large $n$. That contradicts b) above.