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? 
 A: $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$
A: 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: 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.
A: The other answers deal with part (a) of  your question. 
I think you are trying to do part (b) and starting with

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$.
Here's a way to start (b).
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. 
A: 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.
