Waste less time on Facebook — follow Brilliant.

Requesting assistance regarding unique factorization representation of numbers by s_p primes

Let \( S_p := \{np+1 | n \in \mathbb{N_0} \} = \{1, p+1, 2p+1, \dots \} \)

An element \( s_p \in S_p \) is called \(s_p\) prime, if and only if it's only divisors in S_p are \(1\) and \(s_p\) .

In Apostol's book "An Introduction to Number Theory" I found an exercises, in which one had to show that every number in \(S_4\) is either an \(s_4\)-prime or a product of \(s_4\)-primes.

A number \(p\) that suffices this property be now called \(p\)-complete. Respectively such a set \(S_p\ will be called complete.

Now one can ask: Which \(p \in \mathbb{N}\) suffice this property?

Well, let \( x,y \in S_P \), then there \( \exists \) unique \( m,n \in \mathbb{N} \) with \( k(np+1) = mp+1 \) for a yet unspecified \( k \in \mathbb{N} \)

\(k\) itself has unique representation: \(k = p*s+t\) with \( s \in \mathbb{N} \) and \(0 \le t \le p-1 \)

Thus one gets the equation:

\((sp+t)(np+1) = mp+1 \Leftrightarrow spnp +sp+np+t = mp +1 \Leftrightarrow p(nsp +sp+np-m) + t = 1 \) and can immediately confirm: \(S_p\) is complete for any \( p \in \mathbb{N} \)

Now I am interested in all sets \(S_p\), in which all numbers have a unique prime factorization. I would call such a set \(S_p\) perfect. However which sets \(S_p\)are perfect?

How do I tackle this problem? What is a good approach? Any constructive help, recommendation of reading material, comment or answer is appreciated. Thanks in advance.

Note by Alisa Meier
2 years ago

No vote yet
1 vote


Sort by:

Top Newest

What have you tried?
Is \( S_2 \) complete? Why, or why not?
Is \( S_3 \) complete? Why, or why not?
Is \( S_4 \) complete? Why, or why not?
Is \( S_5 \) complete? Why, or why not?

The areas that this involves is Modular Arithmetic and related concepts.

Calvin Lin Staff - 2 years ago

Log in to reply

I also got a result now: \(S_p \) is only perfect for p = 1 or p = 2

The proof of that was also not too difficult. Maybe this can be turned into a nice problem for brilliant..

Alisa Meier - 2 years ago

Log in to reply

That's great! It's not too hard, once you figure out the slight trick involved. Looking at small cases can help, which is why I asked.

I look forward to seeing the question that you pose. It could be made really interesting :)

Calvin Lin Staff - 2 years ago

Log in to reply

You should clarify the definition of " \( s_p \) prime". I believe what you mean is that "the only divisors of \( s_p \) that are in \( S_p \) are 1 and \( s _ p \)".

For example, \( 9 \in S_ 4 \), and the only divisors are not 1 and 9 (since it has a divisor of 3).

Calvin Lin Staff - 2 years ago

Log in to reply

Yeah, that edit was necessary.

Alisa Meier - 2 years ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...