1
$\begingroup$

I am reading the following problem:

For the sequence $T=3, 7, 11, 15, 19, 23, 27 ...$ prove that every number in $T$ has a prime factor that is also in $T$

My approach:
The sequence is of the form $4\cdot n + 3$
Each of the numbers in the sequence has a unique decomposition of prime factors $2^a\cdot 3^b \cdot 5^b \cdot 7^d ...$
We can express the prime factors as follows:
$(4\cdot n + 2)^a \cdot (4\cdot n + 1)^b \cdot (4\cdot n + 3)^c$ for $n \ge 0$

If we assume that we do not have any prime factor that is also part of $T$ then we would have prime factors of the form:
$(4\cdot n + 2)^a \cdot (4\cdot n + 1)^b$
For the simple case that $a = 1 \space b = 1$ we have:
$(4\cdot n + 2) \cdot (4\cdot n + 1) = 16 \cdot n^2 + 4 \cdot n + 8 \cdot n + 2 = 4n(4n + 3) + 2 = 4k + 2$ (where $k = 4\cdot n+ 3)$

Which means that we can not get a number in $T$ without having a prime factor of the form $(4\cdot n + 3)^c$

Update based on the comments of @Peter and @Asher2211:
The prime factors can be only of the form $(4\cdot n + 1)$ or $(4\cdot n + 3)$
If we assume that we can have a number in $T$ with prime factors not in $T$ we would have:

$x = (4\cdot n + 1)^a = 1 + a\cdot (4n) + \frac{a(a-1)}{2!}\cdot (4n)^2 +... = 1 + 4nk\space$ where $k = a + \frac{a(a-1)}{2!}\cdot (4n)....$
hence we can not get a number that is in $T$

$\endgroup$
11
  • $\begingroup$ No need to consider primes of the form $4n+2$ as $2$ does not divide any of the given numbers. $\endgroup$
    – Asher2211
    Commented Jun 30, 2021 at 9:15
  • 1
    $\begingroup$ Hint : The sequence contains exactly the positive integers of the form $4k+3$. Why cannot all prime factors of such a number be of the form $4m+1$ ? $\endgroup$
    – Peter
    Commented Jun 30, 2021 at 9:17
  • $\begingroup$ @Asher2211: I just realized that the only prime factor of the form $4n + 2$ is just $2$ $\endgroup$
    – Jim
    Commented Jun 30, 2021 at 10:15
  • $\begingroup$ @Peter: So I think you ignore the form $4n + 2$ because the only prime factor is $2$ and as was mentioned in a previous comment wont divide any number in $T$. So if I focus on the form $4m + 1$ isn't how I prove it using the multiplication like my post? $\endgroup$
    – Jim
    Commented Jun 30, 2021 at 10:17
  • $\begingroup$ First of all, the entries in the sequence are odd, hence $2$ cannot be a prime factor. All other prime numbers have the form $4m+1$ or $4m+3$. I have some difficulties to follow your solution, but you need not make your life difficult , if you just apply an easy proof by contradiction. $\endgroup$
    – Peter
    Commented Jun 30, 2021 at 10:23

1 Answer 1

0
$\begingroup$

An experimental approach:

We rewrite expression as:

$4n+3=3(n+1)+n$

$[n, (n+1)]=1$

So if 3 divides n we can have numbers which are divisible by 3 in the sequence. These numbers make following progression:

$15, 27, 39=3\times 13, 51=3\times 17, \cdot\cdot\cdot 12k+3$

That is the terms of this progression have at least one prime other than 3 as a factor.

Now suppose 3 does not divide n, so we may consider following cases:

1): $\begin {cases}n=3m+1\\n=3m-2\end {cases}or: n\equiv 1\bmod 3\equiv -2\bmod 3$

which gives this progression:

$19, 31, 43, 55=5\times 11, \cdot\cdot\cdot 12k_1-5$

The terms of these progression are a multiple of 5 or have at least a prime other than 3 and 5.

2): $\begin {cases}n=3m-1\\n=3m+2\end {cases}or: n\equiv -1\bmod 3\equiv 2\bmod 3$

which gives this progression:

$23, 35=5\times 7, 47, 59, 71, 83, 95, \cdot\cdot\cdot 12k_2-1$

similar to case 1 the terms of this progression are a multiple of 5 or have at least a prime other than 3 and 5.

We can see that the factors of $4n+3$ cover all primes and we can conclude that any term of resulting sequence from $4n+3$ contains a prime already exist in the factors of previous terms.

$\endgroup$

You must log in to answer this question.

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