Question

How to solve? 17x =9 (mod 276)
Please, help

Answer 1

You could use your favorite way the euclidean way
sometimes that can get pretty long though depending on the numbers

Answer 2

I break 276 into 3*4*23
Then it equivalents
17x = 9 mod 3
17x = 9 mod 4
17x =9 mod 23

Answer 3

then, it becomes x= 0 mod 3
x =1 mod4
x =13 mod 23
but can't get the right answer

Answer 4

oh, x = -13 mod 23

Answer 5

the euclidean way:
\[276=17(16)+4 \\ 17=4(4)+1 \\ ... \\ 17-4(4)=1 \\ 17-4[276 - 17 \cdot 16]=1 \\ 17-4(276)+17(4 \cdot 16)=1 \\ -4(276)+17(4 \cdot 16+1)=1 \\ -4(276)+17(65)=1\]

Answer 6

oh, I got the right answer with it. Damn!! silly mistake.

Answer 7

and you can multiply both sides of my by 9

Answer 8

Yes, we can use Euclidean, but I would like to solve it by congruence.

Answer 9

By Euclidean, we establish 17x - 276 y =9 and solve diophantine, right?

Answer 10

yes
I was call is solving the congurency equation by using the extended euclidean way

Answer 11

always*

Answer 12

\[276(-4 \cdot 9)+17(65 \cdot 9)=9 \\ x=65 \cdot 9 \mod 276\]

Answer 13

I need practice that way also. Tomorrow, I have test for both.

Answer 14

I don't think I ever practiced the other way much

Answer 15

it looks like you wrote the prime factorization for 276
and then setup 3 separate congruncey equations?

Answer 16

Yes, I did

Answer 17

the first one gives:
17x = 9 mod 3
2x = 0 mod 3
x=0 mod 3
second one gives:
17x=9 mod 4
x=1 mod 4
third one gives:
17x=9 mod 23
17x-23k=9
23=17(1)+6
17=6(2)+5
6=5(1)+1
---
6-5=1
6-(17-6*2)=1
6(3)-17)=1
(23-17)(3)-17=1
23(3)-4(17)=1
So x=-4 mod 23
--
So once you get x=0 mod 3 from first one
and x=1 mod 4 for second one
and x=-4 mod 23 for last one
what do you do?

Answer 18

For the last one
17x = 9 (mod 23)
-6x = 9 (mod 23
-2x = 3 (mod 23)
-2x = 26 (mod 23)
x = -13 (mod 23)

Answer 19

I think there is a theorem somewhere that says you can do that one thing you did from line 2 to 3 but I can't remember what it said

Answer 20

anyways i will let you study for your test

Answer 21

just divide both sides by 3

Answer 22

i made a little mistake
or forgot to multiply both sides by 9 again errr
x=-4(9) mod 23 =-36 mod 23 which is the same as -13 mod 23

Answer 23

We can divide both sides by 3 iff (3,23) =1, if not, we can't do that.

Answer 24

k thanks for reminding me :)