Euler: Please verify my result !


by mathboy20
Tags: euler, result, verify
mathboy20
mathboy20 is offline
#1
Oct11-06, 09:00 AM
P: 30
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: . 175x .= .173 (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
Phys.Org News Partner Science news on Phys.org
NASA's space station Robonaut finally getting legs
Free the seed: OSSI nurtures growing plants without patent barriers
Going nuts? Turkey looks to pistachios to heat new eco-city

Register to reply

Related Discussions
Can you verify this please??? Calculus 3
Stochashic variable result(Please verify) Urgent Calculus & Beyond Homework 0
Results same w/ Euler, Improved Euler, & Runge-Kutta Differential Equations 14
can someone verify this Calculus & Beyond Homework 0
Someone verify? Introductory Physics Homework 8