1

This is an exercise in Bigg's Discrete Mathematics (Oxford Press).

It is stated roughly like this:

Suppose that there are finitely many primes of this form $(4n - 1): 3, 7, 11, 19,...,X$. Consider the number $$Y=4 \cdot (3\cdot7\cdot11\cdot19\cdot...\cdot X) - 1 $$ This is clearly a number of form 4n - 1, and since it is greater than X, it cannot be a prime. So it must have prime factors and they must be of the form 4n - 1 or 4n + 1. Explain why at least one of the factors is of the form 4n - 1 and why this gives proof by contradiction.

I correctly deduced that if all the factors were of form $4n+1$, then the result would also be of that form. This contradicts the constraints on $Y$, so at least one factor has to be $4n-1$.

Then I thought since $Y$ is of form $4n - 1$, this alone shows that $X$ is not the biggest possible prime of form $4n - 1$, but I realize that this won't work as a proper contradiction since it doesn't violate the conditions (and there's no guarantee Y is prime.). The book however simply states:

"A number of the form $4n - 1$ that is a factor of $Y$ must be greater than $X$."

...in the solutions part. Can somebody explain to me why this is? Why must the factor be larger than X?

I realize a billion similar questions have been asked and I checked a lot of them, but none really gave me an answer to this.

Skurmedel
  • 303
  • @RolfHoyer: Thank you! It was really that simple yet I missed it... :< (You should make an answer and reap some points!) – Skurmedel May 12 '16 at 06:48
  • 1
    It does not have to be greater than $X$ just different from the finitely many primes of the form $4n-1$. For example, suppose you thought that $7$ was the only prime of form $4n-1$, then you take $4\cdot7-1=27$ and discover that $3$ is also a prime of form $4n-1$. – almagest May 12 '16 at 06:51
  • @almagest: I see, that's a good point. Though, wouldn't in be very hard to generalize in a proof though? – Skurmedel May 12 '16 at 06:56

1 Answers1

1

Note that $Y+1 = 4(3\cdot 7 \cdot 11 \cdots X)$ is divisible by $3,7,11,…,X$, thus $Y$ is not divisible by any of $3,7,11,…,X$.

If the sequence $3, 7, 11, \ldots, X$ contains every prime of form $4n-1$ less than or equal to $X$, this implies that a prime divisor of $Y$ of form $4n-1$ is necessarily not on this list, and therefore strictly greater than $X$.

Rolf Hoyer
  • 12,399
  • That does not prove $Y$ has a factor greater than $X$. – almagest May 12 '16 at 06:53
  • Usually in this construction it is implicit that you don't miss any primes less than $X$ in your list. I have modified my answer to make this explicit. You can even replace the list $3, 7, 11, 19, \ldots X$ of primes with a less-sophisticated sequence such as $3,7,11,15,19,23,27, \ldots, X$ which merely contains the primes in a given range. – Rolf Hoyer May 12 '16 at 06:58