modular arithmetic

Coefficient

New member
Joined
Jan 30, 2020
Messages
8
Hi,

I am working on this exercise that says:
1- Decompose 1995 into prime factors.
2- Find all pairs (x,y) ∈ ℕ² so that : x+7y = 1995 and gcd(x,y) = 19

Here is what i've come to so far :

1995 = 3*5*7*19

x=19*x′ and y=19y′ so that gcd(x′,y′)=1
by pluggin this in my equation :

19x′+7*19y′=1995
19(x′+7y′)=1995
x′+7y′=105
x′=105-7y′
x′=7(15-y′)
so i concluded that: x′=7 and 15-y′=1
so y′=14 then x=7*19=133 and y=14*19=266
But after looking at the solution i found out i was wrong, because there is 6 pairs of numbers that satisfy the previous conditions.

Can you please help me on this ?
 

Dr.Peterson

Elite Member
Joined
Nov 12, 2017
Messages
6,203
x′=7(15-y′)
so i concluded that: x′=7 and 15-y′=1
How can you conclude that? Why not x'=14 and 15-y' = 2, and so on? Don't stop with one possibility, when you know you were asked for all pairs.

For any value of y', you can find a value of x'. List them, and find those for which gcd(x',y') = 1. They will include y' = 1, x' = 98, and others.
 
Top