4
$\begingroup$

For a positive integer $k$, let $S_k$ be the set of numbers $n > 1$ that are expressible as $n = kx + 1$ for some positive integer $x$. The set $S_k $ is closed under multiplication. That is: If $a, b$ ∈$ S_k $then $ab $∈ $S_k$. Definition. Suppose $n ∈ S_k$ . If $n$ is expressible as $n = ab$ for some $a, b ∈ S_k$ , then $n$ is called $k$-composite. Otherwise $n$ is called a $k$-prime. For example, $S_4 = \{5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, . . . \}$ . The numbers $25, 45, 65, 81, . . . $ are $4$-composites, while $5, 9, 13, 17, 21, 29, . . . $ are $4$ -primes.

  1. For which $n ∈ S_4$ are $4$-primes? (Answer in terms of the standard prime factorization of $n$. Show: Every $n∈ S_4 $is either a $4$-prime or a product of some $4$-primes. But “unique factorization into $4$-primes” fails. To prove that, find some $n = p_1p_2 · · · p_s $ and $n = q_1q_2 · · · q_t $ where each $p_j $and $q_k $ is a $4$-prime, but the list $(q_1, . . . , q_t)$ is not just a rearrangement of the list $(p_1, . . . , p_r)$.
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Hint: think about $441=3^2\cdot 7^2=4\cdot 110+1 \in S4$. It is 4-composite, how does it factor? Can you generalize?

$\endgroup$
4
  • 1
    $\begingroup$ Oh!!! Thank you so much. I got it right now. $\endgroup$
    – Kai
    Commented Mar 4, 2019 at 3:45
  • 2
    $\begingroup$ The FAQ encourages you to write an answer to your question, which you can accept after some delay (two days?). It will give us a full answer and show that you have really solved it. I am glad my hint helped, but writing up a full answer may help your thinking as well. I have found holes in my arguments in that process. $\endgroup$
    – Ross Millikan
    Commented Mar 4, 2019 at 3:48
  • $\begingroup$ If for original Q=p1p2p3p4*...*pn+1, and there isn't any unique factorization in there. Could we suggest that the prime in 4k+1 is Q=4(p1p2p3p4*...*pn)+1. But if like that, how do we know that there is no unique factorization in that? $\endgroup$
    – Kai
    Commented Mar 5, 2019 at 5:40
  • $\begingroup$ It is important that if you multiply two numbers that are equivalent to $3 \bmod 4$ you get a number that is equivalent to $1 \bmod 4$. Most numbers that have at least four factors of the shape $3 \bmod 4$ will fail to have unique factorization. That is how I found this example. To prove there is no unique factorization you just need to find one example that has two factorizations, and $441$ is one example because $441=9 \cdot 49=21^2$ and all the things on the right cannot be factored. $\endgroup$
    – Ross Millikan
    Commented Mar 5, 2019 at 5:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .