# Proving a composite number is product of primes for a set

Let $A=\{4n+1:n\in\mathbb{N}\}=\{1,5,9,13,17,\dots\}$. We call a number $\alpha$ $\text{A-prime}$ if it doesn't have any divisors in $A$ aside from $1$ and $\alpha$, we define $\text{A-composite}$ being $A/\{\alpha:\alpha \text{ is A-prime}\}$. Prove that every $\text{A-composite}$ is the product of $\text{A-prime}$ numbers and determine if the composition is unique.

To solve this I took some $\alpha\in A$, what would happen if $\alpha$ is $\text{A-composite}$?. By definition, it must have some $\beta\in A$ divisor with $\beta <\alpha$, let's define $\gamma=\alpha/\beta$, seem this problem is about to prove that $\gamma \in A$. Proving my last statement is what is giving me some problems.

To clear things up: $\alpha\in A\implies \exists n_a:4n_a+1=\alpha$ and similarly $\exists n_{\beta}:4n_{\beta}+1=\beta$; using this, how can I prove that $\exists n_{\gamma}:4n_{\gamma}+1=\gamma$?. What I got until now is that $$\gamma=\frac{4n_{a}+1}{4n_b+1}$$

I advanced a few steps taking a $1$ out of the right side of the equation like this: $$\gamma=\left(\frac{4n_a+1}{4n_b+1}-1\right)+1\\=4\frac{n_a-n_b}{4n_b+1}+1$$.

But this leads to a new problem, showing that $\frac{n_a-n_b}{4n_b+1} \in \mathbb{N}$. Here is where I'm stuck, it doesn't seem that induction will work nor to be true.

• Can you improve the grammar issues above? "We call $A$-prime to every ..." doesn't seem to make sense. I think it should be something like "We call a number $x$ $A$-prime if ..." – mathse May 11 '14 at 0:50

We can start from where you left off: $4n_a + 1 = \gamma\cdot (4n_b + 1)$. So:

$4n_a + 1 = 4\gamma\cdot n_b + \gamma$.

So: $n_a = \gamma\cdot n_b + \dfrac{\gamma - 1}{4}$.

For $n_a \in \mathbb{N}$, we require that: $4|\gamma - 1$. This means:

$\gamma = 4k + 1$ for some $k \in \mathbb{N}$, but then this means that: $\gamma \in A$.

I think you can continue..

If $\alpha$ is $A$-composite, then $\alpha\in A$ and $\alpha$ has a divisor $\beta\in A$ with $1<\beta<\alpha$. Thus, $\alpha=\beta\gamma$ for some $\gamma$. We know that $\alpha\equiv 1\pmod{4}$ and $\beta\equiv 1\pmod{4}$. Thus, $\gamma$ must be $\equiv 1\pmod{4}$ ($\gamma$ can be $\equiv 0,1,2,3\pmod{4}$ but knowing that $\alpha\equiv \beta\equiv 1\pmod{4}$ only leaves $\gamma\equiv 1\pmod{4}$), so that $\gamma\in A$. If $\beta$ and $\gamma$ are $A$-prime we are done. Otherwise, $\beta$ or $\gamma$ are $A$-composite (assume $\beta$ is). Exchanging the role of $\alpha$ and $\beta$, we know that $\beta=\beta_2\gamma_2$ is a product of two elements in $A$, both strictly between $1$ and $\beta$. I think from this it is clear that you must end up at numbers $\beta_k\gamma_k$, both of which are $A$-prime since the numbers $\beta_k$, $\gamma_k$ are getting successively smaller.