Question

ok polpak i got a question for you
how to solve x^2=6x mod 8

Answer 1

we can't do this
x^2-6x-8n=0 for n integer
why?

Answer 2

ho ho ho. guess what you have to do?!

Answer 3

i tried and the answer failed

Answer 4

because 8 is composite. i will be quiet now

Answer 5

you don't have to be satellite
he was just showing me how to do one last night

Answer 6

you got satellite all excited ;)

Answer 7

you have to....
COMPLETE THE SQUARE, your favorite. that is why i got excited. because this is myininayas favorite job

Answer 8

lol

Answer 9

so thats why learning to complete the square over doing -b/2a is more important lol

Answer 10

satelitte , how about middle of two roots? lol

Answer 11

x^2-6x=0 mod 8
(x-3)^2=9 mod 8
(x-3)^2=1 mod 8

Answer 12

really that is what you will do
\[x^2-6x\equiv 0 (mod 8)\]

Answer 13

there that took a while to find /equiv

Answer 14

\[(x-3)^2+9\equiv 1(mod 8)\]

Answer 15

\[\equiv \]
:)

Answer 16

adding nine twice on one side?

Answer 17

added nine to both sides

Answer 18

\[x^2-6x\equiv 0 (8)\]
\[x^2-6x+9\equiv 9 (8)\]
\[x^2-6x+9\equiv 1(8)\]

Answer 19

so
\[(x-3)^2\equiv 1 (8)\]

Answer 20

which means you have several choices for
\[x-3\] since any square is congruent to 1 mod 8 i believe

Answer 21

well, that is provided it is odd.

Answer 22

in any case you can just check now because you have only 7 numbers to check, but since
x - 3 is odd it means x is even so you have a few choices

Answer 23

you are good from here right? i love that you asked a question that required completing the square. made my day in fact!

Answer 24

lol

Answer 25

@polpak sorry if i butted in but i couldn't help myself

Answer 26

ok thanks satellite :)
for showing me how

Answer 27

i can do the rest
x=2,4,6,8

Answer 28

I think 0 is a solution

Answer 29

yep

Answer 30

it is

Answer 31

do all even numbers work?

Answer 32

Actually I may be interpreting this differently.. Lemme see here..

Answer 33

i think they do

Answer 34

Was the question \(x^2 = (6x\ mod\ 8)\) or was it \(x^2 \equiv 6x (mod8)\)

Answer 35

i believe lagrange meant the second one

Answer 36

0 is a solution be because we really do not say 8 mod 8

Answer 37

ok

Answer 38

then satellite's interpretation is the right one.

Answer 39

if you are working mod 8 you are working with the numbers 0,1,2,3,4,5,6,7
or at least with their equivalence classes, depending on how pedantic you want to be

Answer 40

I like to be very pedantic ;p

Answer 41

ok then you are working with
\[\bar{0},\bar{1},\bar{2},\bar{3}...\]

Answer 42

\[(2n-3)^2 \equiv 1 \mod 8=> 4n^2-2n(2)(3)+9-1=8k\]
\[=> 4n^2-12n+8 = 8k\]
\[=>4(n^2-3n+2) = 8k ?\]
k is integer by the way

if we can show n^2-3n+2 is even then the answer is any even number

Answer 43

n^2-3n+2=(n-1)(n-2)
lets try induction
for n=1 it is even
for n=2 it is even
for n=3 it is even
ok
now let's assume it is even for some integer k=> so we have for (k-1)(k-2)=2j (j is an integer)
now we need to show it is even for k+1
(k+1-1)(k+1-2)
=(k-1+1)(k-2+1)
=(k-1)(k-2)+(k-1)1+(k-2)1
=2j + k-1+k-2
=2j+2k-3
=2(j+k)-3
but that means for k+1 it is odd
so maybe not every even number

Answer 44

what are you trying to show? i am lost

Answer 45

that even even number is a solution to the congruence equation

Answer 46

every even*

Answer 47

i wanted to show n^2-3n+2 is even for any number
if i could haven shown that then i could haven shown any even number is a solution
to x^2=6x mod 8

Answer 48

but my proof by induction failed
so n^2-3n+2 is not even even for any number
and therefore x^2=6x mod8 does not have solution x=2m for m is integer

Answer 49

it only works for some even integers

Answer 50

not all

Answer 51

what hold on.
you want to show
\[n^2-3n+2\] is even if n is even?

Answer 52

no i wanted to show n^2-3n+2 is even for any number

Answer 53

oh if n is any number, not any even number

Answer 54

ok got it. forget the 2

Answer 55

if n^2-3n+2 is even for any number, then we could haven shown any even number is a solution to x^2=6x mod 8

Answer 56

you are working too hard i think

Answer 57

you can clearly ignore the 2 so you want to show that
\[n^2-3n\] is even
but
\[n^2-3n=n(n-3)\] so if n is even you are done, and in n is odd then n-3 is even so you are done

Answer 58

Number of solutions of P(x) = 0 (mod n) is number of integers b where P(b) = 0 (mod n) and b is a residue modulo n.

Answer 59

\[(2n-3)^2 \equiv 1 \mod 8=> 4n^2-2n(2)(3)+9-1=8k \]
\[=> 4n^2-12n+8 = 8k \]
\[=>4(n^2-3n+2) = 8k ? \]
this was what i working off

Answer 60

anyway we already showed that
\[n^2\equiv 6n (8)\] if n = 0, 2, 4, 6

Answer 61

or maybe you were unhappy with the 'complete the square" solution and you are looking for another one

Answer 62

no
i wanted to find all the answers

Answer 63

a general solution

Answer 64

what do you mean by "all" you are working modulo 8 so there are 8 equivalence classes

Answer 65

general solution is n = 0, 2, 4, 6, mod 8

Answer 66

ok lol

Answer 67

which is another way of saying n is even

Answer 68

it doesn't work for all even numbers though
i proved that it didn't

Answer 69

name one

Answer 70

i did a proof by induction that failed why do i have to name one

Answer 71

because just because your proof failed doesn't mean it is not true. it means your proof was wrong. if you want to show it is false you don't show it is false by saying my proof didn't work. you show it is false by exhibiting a counter example.

Answer 72

i mean if i cannot prove fermat's last theorem, it doesn't mean it is wrong!

Answer 73

ok let me scroll up and look at what i did again

Answer 74

btw these things are almost never proved by induction

Answer 75

if the the answer is all even numbers then my proof should i have worked

Answer 76

i see nothing wrong with my approach

Answer 77

i like that argument. it is not a valid one, but i like it.

Answer 78

i will prove now that any odd number is congruent to 1 modulo 8

Answer 79

no i'm just saying not all even numbers are solution to x^2=x mod 8

Answer 80

but there are a lot of even even numbers that are

Answer 81

as we seen by pluggin in

Answer 82

\[1^2=1=\equiv 1(8)\]
\[3^2=9\equiv 1(8)\]
\[5^2=25\equiv 1(8)\]
\[7^2=49\equiv 1(8)\]that is my proof

Answer 83

i thought it was
\[n^2\equiv 6n (8)\]

Answer 84

it is i forgot the 6

Answer 85

my bad

Answer 86

ok so what did we do? rewrite as
\[(n-3)^2\equiv 1(8)\] and solve this

Answer 87

which is the same thing as saying
\[z^2\equiv 1(8)\] with n - 3 replaced by z

Answer 88

we see from my list above that this means z = 1, 3, 5, 7

Answer 89

which mean n =0, 2, 4, 6

Answer 90

dont forget you are working mod 8, so your universe is {0,1,2,3,4,5,6,7}

Answer 91

congruent mod 8 is an equivalence relation, so you are working with equivalence classes.

Answer 92

like cosets. you have for example
\[71 \in \bar{7}\]

Answer 93

ok satellite
give me another equation and let me see if i can solve it

Answer 94

off the top of my head? ok

Answer 95

\[x^2\equiv 2x (11)\]

Answer 96

maybe there is no solution, i don't know.

Answer 97

ok

Answer 98

oh there are two, but easy ones. let me try again