# Show that if $a,b \in \mathbb{N}$ have remainders in the set $\{1,4\}$ after division by $5$, then so does their product.

a) Show that if $a,b \in \mathbb{N}$ have remainders in the set ${1,4}$ after division by $5$, then so does their product.
b)Show that there are infinitely many primes which have remainders $2$ or $3$ when divided by $5$.

Hint: Imitate the proof of Euclid's Theorem by forming a product involving primes (each with remainder $1$ or $4$) and possibly something else so that when we add, say, $2$, we obtain a number $N$ with remainder $2$ after division by $5$. Then apply part a).

What I've tried:

Let $a$ be equal to the product of two primes $p_1 \text{ and } p_2$, such that $p_1p_2$ is divisible by 5. That is:
$a=p_1p_2$

If we add $1$ to the right-hand side of the equation, we will get that $a$ is divisible by $5$, with a remainder of $1$:

$a=p_1p_2 + 1$

Similarly, if we let $b$ equal the product of two primes with a remainder of $4$, we have:

$b=p_3p_4 + 4$

Now suppose we let $c$ equal the product of $a$ and $b$, we get:

$c= p_1p_2p_3p_4 + 4p_1p_2 + p_4p_3 + 4$

Since $5 \mid p_1p_2$ and $5 \mid p_3p_4$, we know that $5 \mid p_1p_2p_3p_4$.

Similarly, we know that $5 \mid 4p_1p_2$ and it's already given that $5 \mid p_3p_4$.

Since all terms that are products of primes are divisible by $5$, we are left with the remainder of $4$, which is indeed in the set $\{1,4\}$

Does this make sense? Am I making any assumptions here that I shouldn't be?

• That looks good for part a. You may also do it one shot by noticing $$(5k\pm 1)(5l\pm 1) = 5m \pm 1$$ – AgentS Sep 8 '16 at 16:38
• Yet another approach: note that $a$ has such a remainder if and only if $a^2$ has a remainder of $1$ upon division by $5$. – Omnomnomnom Sep 8 '16 at 16:42
• Thanks @ganeshie8, @Omnomnomnom! – kojak Sep 8 '16 at 17:07
• I think the hint was only for question 2. question 1 is much easier without primes. If n has remainder 1 then n = 5k + 1. If m has remainder 4 then m = 5j + 4 = 5(j+1) - 1. So if z and w have remainder 4 or 1 then $z = 5k \pm 1; w = 5j \pm +1$ and $zw = 25kj + 5(k+j) \pm 1 = 5(5kj+k+j) \pm 1$ which has remainder 4 or 1. – fleablood Sep 8 '16 at 17:37
• "That looks good for part a". I don't want to be discouraging but case one only did cases of (5*prime + 1)(5*prime + 4). We need a lot more cases. (Hint: primes is totally irrelevant). – fleablood Sep 8 '16 at 18:34

You are working way to hard.

"What I've tried:

Let $a$ be equal to the product of two primes $p_1$ and $p_2$, such that $p_1p_2$ is divisible by $5$. That is: $a=p_1p_2$"

for the product of two primes to be divisible by $5$ then one of the primes must be $5$. You should simply have written "$a = 5p$".

"If we add 1 to the right-hand side of the equation, we will get that a is divisible by 5, with a remainder of 1"

:

"a=p1p2+1"

... or much simpler $a = 5p_1 + 1$.....

"Similarly, if we let b equal the product of two primes with a remainder of 4

, we have:

b=p3p4+4"

or simply $b = 5p_2 + 4$

"Now suppose we let c equal the product of a and b

, we get:

c=p1p2p3p4+4p1p2+p4p3+4"

or simply $c = 25p_1p_2 + 5(p_1 + p_2) + 4$

"Since 5∣p1p2 and 5∣p3p4, we know that 5∣p1p2p3p4"

which goes without saying as two of the primes must be $5$

.

.

"Since all terms that are products of primes are divisible by 5 , we are left with the remainder of 4, which is indeed in the set {1,4}"

All that work and you have only proven one case. What if both have remainder $1$? Both have remainder $4$. What if $n = 5k + 1|4$ but $k$ isn't prime? Indeed what the heck do primes have to do with anything.

Much simpler:

If $n$ has remainder $1$ or $4$ then $n = 5k + \{1,4\}$. Likewise $m = 5j + \{1,4\}$.

So $n*m = 25jk + \{1,4\}5k + \{1,4\}5j + \{1*1, 1*4, 4*4=16=3*5 + 1\}$

$= 5*[5jk + \{1,4\}k + \{1,4\}j + \{0,3\}] + \{1,4\}$

So $n*m$ has remainder $1$ or $4$.

If that notation is weird you can do it in 3 cases:

$n = 5k+1; m=5j + 1; nm = 25jk + 5j + 5k + 1$:: $n=5k + 1; m= 5j + 4; nm = 25jk + 20k + 5j + 4$::$n=5k + 4; m = 5j + 4; nm = 25jk + 20j + 20k + 15 + 1$.

I'm pretty sure that the hints about primes was only for the second part.

Let $p_1,p_2,..... p_n$ be a finite list of primes not containing $2$ with remainder $2$ or $3$ when divided by $5$. Let $N =5*p_1......p_n +2$ which is odd; is not divisible by 5 or by 2; is not divisible by any $p_i$, has remainder $2$ when divided by $5$.

So $N$ does not have remainder $1$ and $4$ and by $a$ must, therefore have a prime factor that has remainder other than $1$ or $4$. As the prime is not $5$ it must have remainder of $2$ or $3$. As it is not on the list and as it is not $2$, that list must have been incomplete.

So no finite such list will list all odd primes with remainders $2$ or $3$ there must be an infinite number of such primes.

• This is indeed much simpler. Thank you very much! – kojak Sep 8 '16 at 18:49

$1^2\equiv4^2\equiv1 \pmod 5$

$1\times4\equiv4\times1\equiv4 \pmod 5$

So yes, the remainder of the product is always either $1$ or $4$

Consider the following cases:

• $[a\equiv1\pmod5]\wedge[b\equiv1\pmod5]\implies[a\cdot b\equiv1\cdot1\equiv1\pmod5]$
• $[a\equiv1\pmod5]\wedge[b\equiv4\pmod5]\implies[a\cdot b\equiv1\cdot4\equiv4\pmod5]$
• $[a\equiv4\pmod5]\wedge[b\equiv1\pmod5]\implies[a\cdot b\equiv4\cdot1\equiv4\pmod5]$
• $[a\equiv4\pmod5]\wedge[b\equiv4\pmod5]\implies[a\cdot b\equiv4\cdot4\equiv1\pmod5]$

a = either 1,4 (mod 5). b= either 1,4 (mod 5).

Multiplying, both equations a.b = either 1,4(mod 5) Because product has either 1,4,6 in units place. 6 is 1 in mod5. And there are infinite primes ending in 7, 3. So there are infinite primes giving remainder 2,3 when divided 5.

Let a be equal to the product of two primes $p_1$ and $p_2$, such that $p_1p_2$ is divisible by $5$.
That's not going to be helpful, since if a product of two primes is divisible by $5$ then at least one of them must actually be $5$.
There are some primes with remainders $2$ or $3$, for example, $2$, $3$ and $7$. Suppose there were only finitely many. Multiply them all except $2$ together to get $N$. Then $5N+2$ leaves a remainder of $2$ when you divide it by $5$. Then part (a) shows that at least one of its prime divisors is not congruent to $1$ or $4$, so must be congruent to $2$ or $3$. Now you're almost done: show that prime isn't $2$ or $3$ or any of the other primes you used to find $N$. It must be another one you didn't count in your supposed finite list.