Euler: Please verify my result !

mathboy20

Hi

I got two tasks which I have some trouble with.

1)

A guy has 1770 dollars to shop food for. One bread costs 31 dollars and a jar of jam costs 21 dollars.

How many loafs of bread and jar's of jam can the guy buy?

I'm suppose to calculate it using Euler Algebra

31x + 21y = 1770

Do I solve this by guessing x,y ?

2)

a) Show that an integer, is congruent 3 mod 4, and which has a prime factor which is congruent modulo with 4.

How do I do that?

b) show that infinit many prime numbers are congruent 3 mod 4.

Solution (1)

I calculate,
gcd(21,31)

31=1*21+10
21= 2*10+1
10= 9*1+0
Thus,
gcd(21,31)=1

Working backwards,
21-2*10=1
21-2(31-1*21)=1
Thus,
21-2*31+2*21=1
Thus,
21(3)+31(-2)=1
Thus,
21(5310)+31(-3540)=1770
So,
x=5310 and y=-3540
Is one solution of,
21x+31y=1770
Thus, all solutions are:
x=5310+31t
y=-3540-21t
We require that,
x,y>0
Thus,
5310+31t>0
-3540-21t>0
Solving both of these inequalities we get,
t>-171.2
t<-168.5
Thus,
-171.2<t<-168.6
Since t is in integer I have,
t=-171,-170,-169
Corresponding to 3 solution of x and y which are:
(x,y)=(9,51)
(x,y)=(40,30)
(x,y)=(71,9)

Altenate Solution for (1)

I have: .. 31x + 21y .= .1770 .[1]

Then: . . . .31x - 1770 .= .-21y

By definition: . . . 31x .= .1770 (mod 21)

And I have: . . . 10x .= .6 (mod 21)

Divide by 2: . . . . . 5x .= .3 (mod 21)

Multiply by 17: . 17·5x .= .17·3 (mod 21)

and I have: . . . 85x .= .51 (mod 21)

which equals: . . . . .x .= .9 (mod 21)


Hence: . x .= .9 + 21k . for some integer k.


Substitute into [1]: . 31(9 + 21k) + 21y .= .1770 . → . y .= .71 - 31k


There are three solutions.

If k = 0: .(x,y) = (9,71)

If k = 1: .(x,y) = (30,40)

If k = 2: .(x,y) = (51,9)

Which of my two solutions for (1) is best?

Solution (2)

Actually I know I can use Dirichlet's Theorem. (One of my favorite mathemations).
But, my professor says I need to prove this without that.
---
Assume there are finitely many primes of form 4k+3

P1 P2 P3 ... Pn
Form the number,
N=4*P1*P2*...*Pn-1=4(P1*P2*...*Pn-1)+3
Prime factorize this number,
N=Q1*Q2*...*Qm
Since,
N is odd it is either of form 4k+1 or 4k+3
But, N takes the form of4k+3.
Now, if all Qk's in the factorization have form 4k+1
Then, N would have form 4k+1 (As explained in other post).
Which is not true, thus it must have at least one prime Qk which is of form 4k+3.
Since we have equality and the left is divisible by Qk so does the right. But since P1*P2*...*Pn contains all primes of form 4k+3 it is divisible by Qk. But then Qk divide 1!!!! which is impossible. Thus, there most be infinitely many (OR NONE) primes in form of 4k+3.


I know proof is not well formulated, but is there anybody here who maybe could assist me in making it better?

Cheers.
Mathboy