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

 

[kurt.physics]

_07Yes, the solution to (1) is best solved using Euler Algebra. You can solve it by guessing x and y, but it is important to remember that there may be more than one solution to the equation. For (2), your proof is well-formulated. The idea you are trying to express is that if there are a finite number of primes in the form of 4k+3, then you would be able to construct a number from that set of primes that is also in the form of 4k+3. However, since that number is divisible by all of those primes, it would also have to be divisible by 1. This is impossible, so there must be an infinite number of primes in the form of 4k+3.