number theory

[limpid plank]

can someone help me with task 10b?
thank you.

[plucky grail]

1. Ask your question and show the work you've done so far. If you've posted a screenshot of a question, specify which part you need help with.
2. Wait patiently for a helper to come along.
3. Once someone helps you, say thank you and close the thread with:

   +close
   

4. Feel free to nominate the person for helper of the week in #helper-nominations
5. Do not ping the mods, unless someone is breaking the rules.
6. If you're happy with the help you got here, and the server overall, you can contribute financially as well:

[glossy zealot]

what have you tried so far?

start with the definition of a ≡ b

[limpid plank]

thats what i have done so far

[limpid plank]

(a-b)/n

but just if a and b are integers

[limpid plank]

however, i think this is a mess (what i have done)

[heady minnow]

summation is straightforward

$$ n\mid b-a \ &\ n \mid d-c \Rightarrow n \mid (b+d)-(a+c) $$

[leaden bridge]

aL

[heady minnow]

multiplication requires some effort

you start from the same assumptions: n | b-a and n | d-c

and you have to show n | bd - ac

@limpid plank

[limpid plank]

yes this is what i have to show

[heady minnow]

does this equality suffice?

[limpid plank]

i mean i have to somehow prove that we can write it like that

[heady minnow]

$$ bd - ac = b(d-c) + c(b-a) $$

[leaden bridge]

aL

[heady minnow]

@limpid plank

is this enough?

do you see why n | bd - ac holds?

[limpid plank]

well i see that it would be the same, cause we would have to cancel bc out and then we have bd-ac

on the other side

[heady minnow]

correct

why is the right side divisible by n?

[limpid plank]

but why did u write this?

[limpid plank]

hmm wait

ohh

[heady minnow]

yes, adding 0 is very often a useful technique

$$ bd -ac = bd - bc + bc - ac$$

[leaden bridge]

aL

[limpid plank]

cause d-c and b-a is divisible by n?

[heady minnow]

yes!

and we already know that divisibility respects addition

[limpid plank]

yess

[heady minnow]

and you can conclude now also that when p is a polynomial with integer coefficients then

$$ a\equiv b\pmod{n} \Rightarrow p(a) \equiv p(b) \pmod{n} $$

[leaden bridge]

aL

[limpid plank]

ohhh right!

i see

but what does mod n mean?

[heady minnow]

$$ a\equiv b \pmod{n} \overset{\mbox{def}}\Leftrightarrow n\mid b-a $$

[leaden bridge]

aL

[heady minnow]

it's just notation

they don't write mod n here

because it's clear from context

[limpid plank]

aaa ok so it kinda just tells us that mod n means that n is the divisor?

[limpid plank]

yes

[limpid plank]

okok i see

[heady minnow]

yes

more accurately, the set of integers is chopped into equivalence classes modulo n

for example modulo 3, you have 3 equivalence classes

with 0 class being all the multiples of 3

[limpid plank]

i am still a little confused here… how do i prove it?

[limpid plank]

can we start from here?

if you have time

and thanks for the previous help, it made me come a step further

@heady minnow

[heady minnow]

$$ a\mid b\ &\ a\mid c \Rightarrow a \mid b+c $$

[leaden bridge]

aL

[heady minnow]

@limpid plank

can you prove this?

[limpid plank]

prove that if b/a and c/a then (b+c)/a?

[heady minnow]

yes

recall that a | b iff b = ka for some k

[limpid plank]

ok so, b = ka and c = ag. we can prove it by showing that (ka+ag)/a = k + g, where k is the answer for b/a while g the answer for c/a

[heady minnow]

ka + ga, can you factor this?

[limpid plank]

indeed yes

a(k+g)

[heady minnow]

and what is it equal to?

[limpid plank]

a((b/a)+(c/a))

i mean its the same

but were you looking for what i just wrote or something else?

@heady minnow

[heady minnow]

a(k+g) = b+c

do you agree?

[limpid plank]

oh yess

[limpid plank]

i basically said it here

but yes i agree

[heady minnow]

therefore a | b+c, which is what we wanted to show

@limpid plank

[heady minnow]

hence also this follows