0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 ..." $\endgroup$ – mathse May 11 '14 at 0:50
1
$\begingroup$

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..

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.