4
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ That looks good for part a. You may also do it one shot by noticing $$(5k\pm 1)(5l\pm 1) = 5m \pm 1$$ $\endgroup$ – AgentS Sep 8 '16 at 16:38
  • 1
    $\begingroup$ 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$. $\endgroup$ – Omnomnomnom Sep 8 '16 at 16:42
  • $\begingroup$ Thanks @ganeshie8, @Omnomnomnom! $\endgroup$ – kojak Sep 8 '16 at 17:07
  • $\begingroup$ 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. $\endgroup$ – fleablood Sep 8 '16 at 17:37
  • $\begingroup$ "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). $\endgroup$ – fleablood Sep 8 '16 at 18:34
0
$\begingroup$

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.

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

$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$

$\endgroup$
0
$\begingroup$

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]$
$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.