4

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)$.
dmtri
  • 3,270
Kai
  • 89

1 Answers1

2

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?

Ross Millikan
  • 374,822
  • 1
    Oh!!! Thank you so much. I got it right now. – Kai Mar 04 '19 at 03:45
  • 2
    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. – Ross Millikan Mar 04 '19 at 03:48
  • 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? – Kai Mar 05 '19 at 05:40
  • 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. – Ross Millikan Mar 05 '19 at 05:44