elementary-number-theory

[flat scarab]

These examples you have given, c did not divide d

to divide d is to give a remainder of 0

[leaden stream]

to divide means it can be written with no remainder, not that every number added is automatically 0.

[leaden stream]

are you saying 5 does not divide 17 - 7?

[flat scarab]

no

just giving the definition of “divides”

[leaden stream]

this example shows two numbers written as 5q + r subtracted, and obtain a version of 5(q1 - q2) + (r1 - r2) where r1 - r2 is not 0.
So why is it 0 in your proof (it is, and there is a reason for it based on how you constructed your numbers, but you skipped that justification entirely)

Because, again, all you have right now is n | x + y
and you jumped to the claim that y = 0 without stating how you know y is not a multiple of n.

[flat scarab]

The qs group together

[leaden stream]

yes

what do you know about r1 and r2?

[flat scarab]

r1 and -r2 are cumulatively the the remainder of when a- b got divided by n

[leaden stream]

you don't know that, you only know that they are the remainder of a and b when divided by n.

[flat scarab]

Let u = q1 - q2 and v = r1 - r2, a - b = un + v

[leaden stream]

you don't have that v = r1 - r2, because you haven't explained why r1 -r2 is not a multiple of n

[patent acorn]

let n = 3, a = 15, b = 12
a = 3*4 + 3
b = 3*4 + 0
u = 4 - 4 = 0, v = 3 - 0 = 3, so 15 - 12 = 3*0 + 3, therefore 3 = 0

[leaden stream]

and here n = 5, a = 17, b = 7
and 17 - 7 = 5(1) + 5, so r1 - r2 = 5.

[flat scarab]

why do you use 3 times 0 in the example?

[patent acorn]

well it's u*n+v

n is 3, u is 0, v is 3

[flat scarab]

im not so sure this example fits, divides implies a remainder of 0, you have a remainder of 3

[patent acorn]

well yes, that's because 3 doesn't divide 15, right?

and also that 3 doesn't divide 3

[flat scarab]

n divides a - b

so the remainder is 0

[patent acorn]

well in my example we got a remainder of 3

[flat scarab]

im not too sure how else I can explain it

[patent acorn]

well clearly you can't explain it because it's wrong

unless you're claiming that 3 = 0

because i used the exact same logic that you did

n divides a - b, a - b is 3*0 + 3, the remainder is 0, therefore 3 = 0

what step did i do wrong?

[flat scarab]

if n divided a number c, that remainder is 0

[patent acorn]

alright so if we take a simpler example

3 divides 15

15 = 3*4 + 3

therefore 3 = 0

so what did i do wrong

[flat scarab]

3 divided 15, the remainder is 0, not 3

I don’t understand

[patent acorn]

so are you saying that 15 isn't equal to 3*4 + 3?

what is 3*4 + 3 then?

[flat scarab]

Let me try again: 15 = 5*3 + 0

[patent acorn]

that is true

15 = 3*4 + 3 is also true

and so 0 and 3 are both equal to 0

[flat scarab]

but when 3 divided 15, you get 5 not 4

[patent acorn]

well is 15 = 3 * 4 + 3 true?

since according to you, that's all you need to check

in the original proof you didn't check that "when n divided a - b you get q1 - q2", whatever that means

[flat scarab]

I can acknowledge your statement: 15 = 3(4) + 3

yes, above is true

[patent acorn]

so because 3 divides 15, that means 3 = 0?

[flat scarab]

3 divided 15

[patent acorn]

because the definition of "x divides y" that you're using, as far as i can tell, is "if y = nx + r, then r = 0"

so if 15 = 3*q + r, then r = 0

set q = 4 and r = 3 and you get 3 = 0

[flat scarab]

if 5 divided 15, q = 3, r = 0

[patent acorn]

so if q = 4 and r = 3, then "5 didn't divide 15"?

[flat scarab]

oh ok sorry when 5 divides 15, q = 0

[patent acorn]

ok that makes even less sense

[flat scarab]

why?

[patent acorn]

...at this point i think you just don't know what "divides" actually means

ok so let me explain

a divides b if there exists some n such that b = n * a

largely unrelated except in the sense that its name also contains "division", for any two numbers a and b (with b nonzero), there exist unique integers q, r, with the property that a = bq + r, and r is nonnegative and strictly less than |b|, and the process of finding this pair of q,r is called "Euclidean division"

[flat scarab]

b = n *a + 0

Where r1 - r2 is the zero

[patent acorn]

because this pair is unique, b divides a iff the (q,r) obtained by Euclidean division satisfies r = 0

but note that there are always infinitely many (q,r) satisfying a = bq + r, and in particular infinitely many distinct values of r

exactly one of these pairs has the property 0 <= r < |b|, the others all have r != 0 regardless of whether b divides a or not

so if all you know is that a = bq + r and b divides a, you cannot conclude that r = 0

because there are examples like 15 = 3 * 4 + 3

and that is exactly what you did in your original proof

[flat scarab]

r1 - r2 = 0 seems fairly straightforward in this case

[patent acorn]

you went from "a - b = n(q1 - q2) + (r1 - r2)" to "r1 - r2 = 0", which is not valid

like what if it's n

and in fact in the proof as written that is entirely possible

[patent acorn]

by an example like this one

because you didn't constrain q1, r1, q2, r2, at all, you never said that it can't be something like 15 = 3 * 4 + 3

[flat scarab]

ok, let me ask this. prove r1 - r2 not equal to zero?

[patent acorn]

well it isn't always not equal to zero

it's sometimes not equal to zero

and the way i can prove that is by giving an example where it's not zero

[patent acorn]

which i did here

[flat scarab]

but in this case, it’s equal to 0

[patent acorn]

in this case, it isn't equal to 0

and nothing in your proof says that it can't be that case

if you write a = nq_1 + r_1 and b = nq_2 + r_2 using euclidean division, then yes, r1 - r2 = 0, but you don't

you never said anything about division anywhere

[flat scarab]

I’m trying to follow your logic, I just can’t figure it out

[patent acorn]

15 = 3*4 + 3

this equation is true

it is not an equation you would obtain by Euclidean division, but it is true

therefore, if someone is running your proof, that never mentions Euclidean division in any way, it would be valid for them to write 15 like that

[leaden stream]

you are jumping to the conclusion that r1 - r2 is a remainder, and thus 0 <= r1 - r2 < n, and so is obviously 0.
The point we've been trying to make is that r1 - r2 does not need to be a remainder with that condition. You haven't shown that it is actually a remainder either. So your proof is missing a step of justification.

[patent acorn]

oh wait hang on sorry, i misread, you do actually have the assumption from way earlier that 0 <= r1 < n

you just never mention it ever again

which actually isn't any different from not having it at all, because if you want to do a step that's only correct with that hypothesis, you need to use that hypothesis to justify that step

[flat scarab]

I know r1 - r2 is greater than 0, less than n, but what does that have to do with anything?

[patent acorn]

do you know that?

you don't know that. you never proved that. you didn't even mention that at all

and you needed to, because otherwise it doesn't make sense to jump to r1 - r2 = 0

because again, 15 = 3*4 + 3

this doesn't imply 3 = 0, because 3 doesn't satisfy 0 <= r < 3

[leaden stream]

a - b can be written as nu + v where 0<= v < n, but nothing says r1 - r2 = v, and in many cases it isn't. You would need to justify that in some way here.

and in general r1 - r2 does not need to positive.

n = 3, a = 3(1) + 1, b = 3(1) + 2
Then a - b = 3(0) + (-1), so r1 - r2 is not positive.

[flat scarab]

If n got divided by a number, the remainder is smaller than n

[leaden stream]

correct, you haven't divided a - b by n. you've written it out using their individual remainders and claimed those numbers are equal. they don't need to be

[flat scarab]

n divided a - b is given

[leaden stream]

so a -b = nu + v
you don't know that r1 - r2 = v.

[patent acorn]

ok you know what

[patent acorn]

can you explain the same argument, without ever using any word that contains the string "divide"?

let's say that a is a factor of b if there exists an n such that b = a * n

we are given as a hypothesis that n is a factor of a - b

[leaden stream]

you know a - b = nu + v = n(q1 - q2) + (r1 - r2). You don't know that u = q1 - q2 or v = r1 - r2. They don't need to be equal.

[patent acorn]

and Euclid's Theorem That Shall Not Be Named is the statement that for any a, b with b != 0, there exists a unique pair q,r such that a = bq + r and 0 <= r < |b|

if what you're saying is correct then changing the language shouldn't affect it, so can you explain it using these names instead?

[flat scarab]

yes!

there exist some q and r which makes it true

[patent acorn]

yep, in fact there are infinitely many

by the definition of factor, one of those (q,r) pairs has r = 0

we also have the pair (q1 - q2, r1 - r2)

and somehow you conclude from this that r1 - r2 = 0?

[flat scarab]

I think when we said divided, it is good enough

[patent acorn]

no it wasn't

because your logic is still wrong and i think the issue is you were using "divide" to mean two different things

now i've given those two things different names

which means you can explain the same logic again and it will be perfectly clear this time and i'll look pretty silly for having made a confident wrong claim about the problem

...or you can't explain it which means i was right and the issue is that you're getting confused over what "divides" means

[flat scarab]

in my proof, divides just means to leave a remainder of 0

[patent acorn]

ah well that's the problem then

because the hypothesis wasn't that the remainder is 0, the hypothesis was that n is a factor of a - b

[flat scarab]

the question never used the word factor

it said divides

if the question said factor, 15 = 3(4) + 3

[patent acorn]

...i guess you do have a point there

well would the result be wrong if it said factors instead of divides?

[flat scarab]

yes

[patent acorn]

is there a pair of numbers a,b for which a is a factor of b, but a does not divide b? or the other way around?

[patent acorn]

do you have a counterexample?

[flat scarab]

yes

[patent acorn]

what is it

[flat scarab]

15 = 3(4) + 3, r need not be 0

[patent acorn]

oh right sorry i was unclear

i meant would the theorem they originally asked you to prove, be false, if they said factors instead of divides

so are there numbers a,b,n such that a = b mod n, but n is not a factor of a - b

or such that n is a factor of a - b, but a != b mod n

[flat scarab]

The theorem would be false

[leaden stream]

so a - b can be written as a - b = nq, not that it automatically is, just that it can be.
You have a - b = n(q1 - q1) + (r1 - r2). You have given no justification for why you are not in a situation were r1 - r2 = nk
Which would make a - b = n(q1 - q2 + k), and not r1 - r2 = 0.

[patent acorn]

what would a counterexample be then?

[flat scarab]

Given a little time I could work that out

Suppose we have a = 20 and b = 5

[patent acorn]

...and what's n?

[flat scarab]

Let b be 3

sorry n

[patent acorn]

alright so 20 = 5 mod 3 is true

20 - 5 = 15, and 3 is a factor of 15, because 15 = 3 * 5

they're both true so that isn't a counterexample

[flat scarab]

ah yeah you’re right

[flat scarab]

in number theory, when a number divides another number, it does so with a remainder of 0

[lilac bronze]

What happened?

[leaden stream]

If I tell you 5 divides 10 + x, what is x?

[flat scarab]

$5y$ where $y \in \mathbb{Z}$

[sterile pumice]

computerman4774

[leaden stream]

right.
so if n divides nq + v, all you know is that v is a multiple of n.
Even if you have n divides n(q1 - q2) + (r1 - r2), you have r1 - r2 is a multiple of n.

in your problem, with a line of justification, you can show that it is 0. But, for the same reason you didn't do it above, you cannot jump from n | n(q1 - q2) + (r1 - r2) directly to r1-r2 = 0.

[flat scarab]

r1 and r2 are unique

[leaden stream]

yes

what else?

[flat scarab]

less than n

greater than 0

[leaden stream]

ok, so what can you say about r1 - r2?

[flat scarab]

r1 - r2 is 0

[leaden stream]

nope

[flat scarab]

r1 - r2 is not 0?

[leaden stream]

you haven't shown that it has to be, no

[flat scarab]

r1 - r2 = 0 it follows that, r1 = r2, thus a = b mod n

[leaden stream]

so remainders are unique, that doesn't mean equal

how can you say, for certain, that there isn't any combination of r1 and r2, so that r1-r2 is a non-zero muliple of n?

[flat scarab]

because n divides a - b

[leaden stream]

some bizarre choice of a and b that give that give those r1 and r2?

[flat scarab]

what is your definition of divides?

[leaden stream]

that a-b is a multiple of n

[flat scarab]

me too

we agree on the definition of divides

[leaden stream]

so in n(q1 - q2) + (r1 - r2), why is r1 - r2 not some other multiple of n?

you're just saying it's 0 without explaining why it can't be some other multiple of n

[lilac bronze]

So specifically - why cannot it be the case that r1 - r2 = n?

[flat scarab]

let’s be clear, r1 - r2 is or is not 0?

[leaden stream]

ultimately, it is 0.
But you're just saying that it is, which isn't a proof.

[flat scarab]

at this point I wasn’t sure if you thought it was 0

so we agree on 2 things, definition of divides, and ultimately r1 - r2 is 0, we can go from there 🙂

[flat scarab]

r1 - r2 is a multiple of n, n*0

[leaden stream]

why not n*1?

that would still meet the definition of n | a-b.

so why isn't it possible?

for this entire conversation, your argument for why r1 - r2 = 0 has basically been 'because it is.' which isn't a proof. I'm asking you for a logical or mathematical reason why it is 0, or why it can't be some other number.

[flat scarab]

r1 - r2 is not a multiple of n

[leaden stream]

why?

[flat scarab]

it’s the remainder

[leaden stream]

how do you define remainder?

[flat scarab]

< n

[leaden stream]

so if n = 5 can I have a remainder of -12?

[flat scarab]

this would depend on the context

what does n get divided into?

[leaden stream]

in that case
n = 5
a = 14 = 2(5) + 4
b = -1 = 0(5) - 1
a - b = 5(2) + 5 and r1 - r2 = 5

[leaden stream]

why does the definition depend on the numbers i'm using?

[flat scarab]

when I wrote that message I wasn’t defining anything

[leaden stream]

anything? how about 33, since 33 = 9(5) - 12

[flat scarab]

5 doesn’t divide 33

neither does 9

[leaden stream]

i haven't said it does. I've just asked if n=5 is -12 a valid remainder.

[flat scarab]

why do you give me that ex?

[leaden stream]

you said remainders only need to be < n

[flat scarab]

remainders are less than n when you do division

Don’t take offense, I’m not sure what you were doing

[leaden stream]

you haven't done division. You've subtracted two numbers.

[flat scarab]

33 = 9(5) - 12, what is this?

[leaden stream]

a question about what you consider a remainder to be.

[flat scarab]

This is y = ax + b

[leaden stream]

what do you think a = nq + r is?

[flat scarab]

q and r are unique, 0 <= r < n

[leaden stream]

ah, so not just < n, it must also be non-negative

[flat scarab]

I’m just regurgitating the def

Let me try this: if r reached n, it would roll back to 0

[leaden stream]

in a sense, sure. You'd have a different remainder than r

but that's not the same as r = 0

[flat scarab]

let’s say r was a multiple of n, well then its not a remainder

is something else, idk, 🤷🏻‍♂️

[leaden stream]

you know 0<= r1 < n, and 0<= r2 < n
Just from that, can you bound r1 - r2? Forget everything else about the problem.

[flat scarab]

what do you mean? for example: $c \le r_1 - r_2 < d$? find $c$ and $d$?

[sterile pumice]

computerman4774

[leaden stream]

yes

[flat scarab]

no, I don’t know how

[leaden stream]

you know how r1 and r2 are bounded. try to play around find the bounds for r1 - r2. Combining it with your division assumption, you should ifnd why r1-r2 can only be 0

[flat scarab]

another r1 - r2 is a remainder, it is less than n

it is greateror equal than 0

[leaden stream]

n = 5, r1 = 1, r2 = 2
r1 - r2 = -1
Not greater than 0

[flat scarab]

$0 \le r_1 - r_2 < n$

[sterile pumice]

computerman4774

[leaden stream]

that's not always true given these bounds

[flat scarab]

ok, so the answer i gave is wrong?

[leaden stream]

yes

[flat scarab]

then what are the bounds?

[leaden stream]

you saw me make a -1 here, how negative could it go?

[flat scarab]

this is incorrect, because n divides a - b

r1 - r2 is 0

unless we forget about the problem like you said

but at this point, this is too far from the original question

now we’re not even considering the original problem

[leaden stream]

okay

[flat scarab]

this is what 3 people have basically said so far

[lilac bronze]

You didn’t actually answer my question - if I say “actually r_1 - r_2 = n”, how do you know I’m incorrect?

[bold badge]

this is the question?

If $a$ and $b$ are integers and $n$ is a positive integer, prove that $a$(mod $n$) = $b$(mod $n$) if and only if $n$ divides $a-b.$

[sterile pumice]

chipotle

[bold badge]

i just rewrote so i dont have to scroll

[flat scarab]

yes

[glass verge]

$a\equiv b \pmod n \iff n \mid (a-b) \iff a-b=kn$

[sterile pumice]

normalAtmosphericPa=101,325

[flat scarab]

at the end of the proof when we have $a - b = n \left ( q_1 - q_2 \right ) + \left ( r_1 - r_2 \right )$, since $qn$ appears when we do the subtraction, we know that $r = r_1 - r_2 = 0$ is unique, by the uniqueness of the remainder in the division algorithm, $r_1 - r_2$ is not a multiple of $n$ as some others have suggested, unless we are talking $r_1 - r_2 = 0 \cdot n$

[sterile pumice]

computerman4774

[patent acorn]

nobody has claimed that it is, they've just pointed out that you haven't proven that it isn't

[flat scarab]

i don't need to prove that it isn't

by uniqueness of the remainder, and how the division algorithm works, i get 0

[patent acorn]

by uniqueness of the remainder
the remainder isn't unique though

it only becomes unique if you have the condition 0 <= r < n

here you haven't proven that that condition is true

[flat scarab]

where in the definition did it say that?

[patent acorn]

in the definition of what?

[flat scarab]

of the division algorithm

[patent acorn]

well the division algorithm isn't exactly "defined", it's a theorem

[flat scarab]

right, and i use that theorem, in my proof

[patent acorn]

but ok here's the statement of it: for any integers a, b with b != 0, there exists a unique q,r such that a = bq + r and 0 <= r < |b|

if you remove the "and 0 <= r < |b|" then the statement is trivially false, because for instance 15 is both 3*4 + 3 and 3*5 + 0

[flat scarab]

so, $0 \le r < |b|$ follows from uniqueness

[sterile pumice]

computerman4774

[flat scarab]

not the other way around

[patent acorn]

(well this isn't exactly the division algorithm, if you want "algorithm" in the name then you also want to know how you find q,r, but that part of it isn't useful in this situation)

[patent acorn]

...what? what does that even mean?

and also no it doesn't

[flat scarab]

i just read what you wrote

i didn't put that definition in the chat

[patent acorn]

ok maybe the problem here is with the word "unique" then, let me rephrase without that

for any integers a,b with b != 0, there exist q,r such that

1. a = bq + r and 0 <= r < |b|

[flat scarab]

you said "it follows that"

not me

[patent acorn]

2. for any other two integers q_2, r_2 satisfying a = bq_2 + r_2 and 0 <= r_2 < |b|, q = q_2 and r = r_2

[patent acorn]

in what message did i say that

according to discord search the last time i said "it follows that" in this server was over a week ago

[flat scarab]

yes, you are right, i misread the definition you wrote, i apologize

but in any case, the way this reads, it sounds like the bounds come from the uniqueness: there exists a unique q,r such that a = bq + r and 0 <= r < |b|

[patent acorn]

yeah that's because we don't agree on what the word "unique" means

[patent acorn]

use this version instead

[flat scarab]

?

[patent acorn]

it's equivalent by my definition of "uniqueness"

[flat scarab]

i never even defined what i meant by uniqueness

so how can you say that?

[patent acorn]

well you said things about uniqueness that don't make any sense

[flat scarab]

example?

[patent acorn]

admittedly i am kind of just randomly flailing around but it seems like a reasonable guess that the word "unique" is part of the tangle here

[patent acorn]

this

[flat scarab]

what do you mean randomly flailing around?

[patent acorn]

well i don't know what you're failing to understand so i'm just doing random things to see what works

[flat scarab]

well, i dont think this approach will be helpful

[patent acorn]

what else is there that i could do

[flat scarab]

you need to state exactly what i am missing in the proof

[patent acorn]

i have done that several times

[flat scarab]

where?

[patent acorn]

.

there's one example

[flat scarab]

no, you're claiming that i haven't proven that the condition is true, which may or may not be the case, what would you add to the proof to make it so?

ok, just one second

here's where i am at: a - b = q*n

we know this, because n divides a - b (hopefully we agree on what divides means)

when we do the subtraction...

a - b appears on one side

n*(q_1 - q_2) appears on the other side

[patent acorn]

(i have no idea at this point, but i do agree that for some q, a - b = q*n is true and that it follows from n dividing a - b)

[flat scarab]

r_1 - r_2 (or whatever it was i forgot) also appears

please, let me finish my thought

sorry that was rude

[patent acorn]

this isn't a voice conversation, me sending messages doesn't actually prevent you from typing

but alright sorry

[flat scarab]

so if we know n goes into a - b evenly, that leaves r_1 - r_2 leftover

n(q_1 - q_2) goes into a - b evenly

so what is r_1 - r_2?

[patent acorn]

(was that rhetorical or are you expecting me to answer)

[flat scarab]

i am expecting an answer

[patent acorn]

well, the answer is: not enough information

again consider the example

15 = 3 * 5

15 = 3 * 4 + 3

"therefore 3 = 0"

[flat scarab]

yeah but with the example you gave, we will just start the whole conversation over again

unless one of us chooses not to continue having the conversation

[patent acorn]

yeah that's because you keep not addressing it

[flat scarab]

what is there to address? ive said a few things about this already

yeah it may be true that 15 = 3*4 + 3, but 4 doesn't divide 15

q and n must divide 15

[patent acorn]

so your claim is that q_1 - q_2 divides a - b?

how do you prove that?

[patent acorn]

also, alright, 15 = 3*3 + 6, therefore 6 = 0

[flat scarab]

3 * 3 doesn't equal 15, so i don't understand your point

3 * 5 = 15

[patent acorn]

well all of these objections that you're bringing up now, how do you know they don't apply in your proof?

you didn't prove that n(q_1 - q_2) = a - b

[flat scarab]

when we are talkin about number which divides another number, it must do so evenly

[patent acorn]

we know that nq = a - b for some q, but not that that q is q_1 - q_2

[flat scarab]

you are giving examples which does not divide the other number

[patent acorn]

3 does divide 15 actually

[flat scarab]

of course it does

but q = 5

not 4 or 3

[patent acorn]

so in my example of 15 = 3 * 3 + 6

what number is failing to divide what other number

[flat scarab]

$3(3) \neq 15$

[sterile pumice]

computerman4774

[patent acorn]

what number is failing to divide what other number

[flat scarab]

but you didn't write the equation correctly

[patent acorn]

what number is failing to divide what other number

you said

you are giving examples which does not divide the other number
so what isn't being divided

[flat scarab]

a = nq +r

[patent acorn]

what number is failing to divide what other number

a number is written as a sequence of the characters 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

[flat scarab]

your asking the wrong question

[patent acorn]

well you said it was the right question

you are giving examples which does not divide the other number

in my example of 15 = 3*3 + 6, what's "the other number", and what doesn't divide it?

[flat scarab]

let's say we have a number, 15... let's say $15 = nq + r$ where $0 \le r < n$, let's say n divides 15, if n divides 15 then r must be 0, meaning q must be 5

[sterile pumice]

computerman4774

[flat scarab]

whoops ^

messed it up

n = 3

again, im just using the definition of divides

[patent acorn]

yep, that's correct

although in my example, 0 <= r < n is false, so that doesn't apply

[flat scarab]

but again, i dont understand why you keep giving that example

i dont really think it applies

[patent acorn]

well if you look at where all this started

$a-b = n(q_1 - q_2) + (r_1 - r_2)$

[sterile pumice]

bee [it/its]

[patent acorn]

and also $n$ divides $a-b$

[sterile pumice]

bee [it/its]

[patent acorn]

this does not imply that $r_1 - r_2 = 0$

[sterile pumice]

bee [it/its]

[patent acorn]

and $15 = 3 \cdot 3 + 6$ is a counterexample to that, because $3$ divides $15$ but $6 \neq 0$

[sterile pumice]

bee [it/its]

[patent acorn]

it would if you had the additional condition that $0 \leq r_1 - r_2 < n$, which fails in my example because $6 \not< 3$

[sterile pumice]

bee [it/its]

[patent acorn]

you have not proven that this additional condition is true, and so your inference that $r_1 - r_2 = 0$ isn't valid

[sterile pumice]

bee [it/its]

[patent acorn]

because if it was valid, it would also be valid to apply it in the case ``$3$ divides $15$ and $15 = 3 \cdot 3 + 6$'' and conclude $6 = 0$

[sterile pumice]

bee [it/its]

[flat scarab]

this is not a counterexample

[patent acorn]

yes it is

it's a counterexample to the logic you actually did

which was ``$n$ divides $a - b$, and $a - b = n(q_1 - q_2) + (r_1 - r_2)$, therefore $r_1 - r_2 = 0$''

[sterile pumice]

bee [it/its]

[flat scarab]

it's not a counter example, because 15 / 3 is 5

[patent acorn]

well you never mentioned that

[patent acorn]

this is what you said

[flat scarab]

you wrote an algebraic equation

[patent acorn]

you didn't say "and also n(q_1 - q_2) = a-b because [...]"

you just said

n divides a - b

a - b = n(q_1 - q_2) + (r_1 - r_2)

therefore r_1 - r_2 = 0

leaving aside the question of whether that's actually what you did, if that was all there is to it, with no further context, do you agree that that is not a valid inference?

[flat scarab]

i agree that's what i wrote, but what's the point? im sorry i really dont understand

[patent acorn]

well because take this example

3 divides 15

15 = 3*3 + 6

therefore 6 = 0

[flat scarab]

no stop it

your not doing division

i dont know what youre doing

[patent acorn]

and you aren't either

[flat scarab]

oh 15 / 3 = 5 isn't division?

[patent acorn]

$a - b = n(q_1 - q_2) + (r_1 - r_2)$ isn't division

[flat scarab]

whats the + 6 all about?

[sterile pumice]

bee [it/its]

[flat scarab]

what is $+ 6$?

[sterile pumice]

computerman4774

[flat scarab]

why add that on there?

[patent acorn]

it's 5 + 1, and i don't understand the point of the question

[patent acorn]

why not

[flat scarab]

because again, we are talking about a - b getting DIVIDED by n

[patent acorn]

i'm the universe, i don't have to explain myself to you
when you're writing a proof you don't get to say "if n is a number, it isn't 4. proof: let n be a number. there is no reason you would make n equal to 4, what even is that. therefore n is not 4. Q.E.D."
a proof has to be able to handle any value that might get thrown at it

[flat scarab]

the counter example just doesn't follow the definition of division algorithm

[patent acorn]

no we aren't

you never said that

you said that n divides a - b

[flat scarab]

i didn't say that

[patent acorn]

and separately you said that a - b = n(q_1 - q_2) + (r_1 - r_2)

[flat scarab]

it's given

[patent acorn]

well sure but still

[flat scarab]

n divides a - b is a given

[patent acorn]

we have that n divides a - b

we also have that a - b = n(q_1 - q_2) + (r_1 - r_2)

these statements are not related in any way

they are just two things that are both true

[flat scarab]

of course they are

[patent acorn]

...they are what

[flat scarab]

they are related

[patent acorn]

no they aren't

or more specifically

[flat scarab]

why?

[patent acorn]

the fact that we're considering them together doesn't cause any additional meaning

like if we look back at the example i keep going back to

3 divides 15

15 = 3*3 + 6

each of these statements is true in isolation, right?

[flat scarab]

true in isolation sure

[patent acorn]

so if i put them next to each other, they are still both true

right?

[flat scarab]

i just can't agree

if i divide 15 by 3 i get 5

we are talking about division right?

6 isn't a remainder

it's just not valid

6 is "something else"

[patent acorn]

ok so suppose we have two statements, P and Q

and we have proven that P is true

and we have proven that Q is true

can we therefore prove "P and Q are both true"?

[flat scarab]

no absolutely not

[patent acorn]

alright yeah that's the issue then

[flat scarab]

you keep giving this example 15 = 3*3 + 6 over and over

that's not division

i don't know what that is

[patent acorn]

well we can stop talking about division now

because we've found the problem and it doesn't actually involve division

it's with the meaning of the word "and"

[flat scarab]

im not following

[patent acorn]

well here

you're saying that it's possible that "P" is true, and "Q" is true, but "P and Q" is false

this is not possible by the standard definition of "and"

[flat scarab]

don't take this the wrong way but none of this is helpful

[patent acorn]

well it's helped me at least, i understand a lot better what the issue is now

anyway

[patent acorn]

indeed it isn't, so that means 3 doesn't actually divide 15, right?

because "15 = 3 * 3 + 6" is true, but "3 divides 15 and 15 = 3 * 3 + 6" isn't, according to you

[flat scarab]

3 divides 15

[flat scarab]

15 = 3(3) + 6

both are true

[patent acorn]

i thought earlier you said they weren't

[flat scarab]

come on, ive had algebra, i know 15 = 3(3) + 6

[patent acorn]

well then you claimed that "3 divides 15 and 15 = 3*3 + 6" is false

...well ok fine

looking back at "n divides a - b, and a - b = n(q_1 - q_2) + (r_1 - r_2)" again

you see the problem now, right? even if those statements are both true, that doesn't imply that the second statement is actually what happens when you divide a - b by n

same as how that's not true in the case of "3 divides 15, and 15 = 3 * 3 + 6"

[flat scarab]

no, that's a stretch, leaving out context

[patent acorn]

well context doesn't matter

that's kind of been my entire point here

either a mathematical statement is true or it's false, its meaning isn't affected by the context

(if it is then that's because you're using ambiguous/bad terminology or notation, and actually conflating multiple different statements by writing them the same way)

[flat scarab]

this isn't entirely mathematical, there is some english language involved as well as interpretation of what the other person said

[patent acorn]

well the thing we're trying to talk about is entirely mathematical

so if what the things we're saying mean depends on the context then that's going to cause miscommunications

[flat scarab]

$q_1 - q_2$ is unique

[sterile pumice]

computerman4774

[flat scarab]

$r_1 - r_2$ is also unique

[sterile pumice]

computerman4774

[patent acorn]

...what do you mean by "unique"

is 5 unique?

[flat scarab]

only when paired with 3

[patent acorn]

...ok, well, is 5 paired with 3?

[flat scarab]

in the context of 15 = (5)(3)

3 and 5 as a pair are unique

[patent acorn]

what's a "context"

stop saying things that are only meaningful given a context

[flat scarab]

context = division

[patent acorn]

if a statement means anything at all, then you can write it in a way that doesn't depend on the context

[flat scarab]

please dont order me around

[patent acorn]

ok well, from now on i'm just going to ignore anything you say that depends on context

you can do whatever you want about that

[flat scarab]

i dont know why you think context doesnt matter and then expect me to believe the same

[patent acorn]

...because this is maths

in a fully written out formal proof, "context" doesn't exist at all

people often don't actually expand it out that far (although they sometimes do https://us.metamath.org/mpegif/cnv0.html), but anything that can't be expanded like that, is wrong

so if your logic is correct, you can write it without ever using anything context-dependent

[flat scarab]

im going back to the original question and ignoring the philosophical discussion for a moment

i think the idea was, in order to prove $r_1 - r_2 = 0$, i need to use $0 \le r_1, r_2 < n$ in some way

[sterile pumice]

computerman4774

[patent acorn]

yes

[flat scarab]

since $n$ divides $a - b$, there exists an integer $k$ such that $a - b = kn$

[sterile pumice]

computerman4774

[patent acorn]

yep

[flat scarab]

then $a$ is congruent to $b \pmod n$

[sterile pumice]

computerman4774

[patent acorn]

yep

[flat scarab]

$QED$

[sterile pumice]

computerman4774

[patent acorn]

what

[flat scarab]

thats it, thats the other direction

no need to subtract $a$ from $b$

[sterile pumice]

computerman4774

[flat scarab]

hmm, no i dont think this is proving anything

if i go back to the original proof i did, what if i assume $r_1 - r_2$ is a multiple of $n$?

[sterile pumice]

computerman4774

[leaden stream]

that is certainly something you should consider, and you can show that the only possible multiple is 0. But you do need to show that.

[flat scarab]

this is something I’ve considered quite a bit

even if r_1 - r_2 is some multiple of n, the whole expression still divides evenly into a - b, the whole discussion has not covered this

[leaden stream]

i've said that too you multiple times.

[flat scarab]

so if I did that, then the remainder is 0

on the other hand if r_1 - r_2 is not a multiple of n we are done

Hmm no I don’t think this solves it either

[leaden stream]

that certainly doesn't guarantee r1 - r2 = 0

[flat scarab]

what guarantees $r_1 - r_2 = 0$

[sterile pumice]

computerman4774

[leaden stream]

the fact that 0 <= r1, r2 < n gives you that -n < r1 - r2 < n
Combined with the divisibility condition on a-b, you have that r1 - r2 is a multiple of n and therefore = 0

[flat scarab]

I could see how -n is less than each of those remainders individually but how is it less than $r_1 - r_2$?

[sterile pumice]

computerman4774

[leaden stream]

the smallest r1 can be is 0, the largest r2 can be is n-1, so min - max = 0 - (n-1) > -n

or, the biggest difference between any two values in that interval is n-1 (positive or negative), so you have between -n and n

[flat scarab]

why does $r_1 - r_2$ have to be less than $n$? my guess is because all remainders ($r_1 - r_2$ included), have to be less than $n$

[sterile pumice]

computerman4774

[flat scarab]

this makes sense

[leaden stream]

you're subtracting two positive numbers < n, that certainly can't increase to larger than n. Since r2 >=0, you know r1 - r2 <= r1 < n

[leaden stream]

r1 - r2 is not a remainder, as you have defined it. It is the result of subtracting two remainders, which is not necessarily a remainder itself.

[flat scarab]

So the end result is, a multiple of n between -n and n, must be 0?

[leaden stream]

yes

[flat scarab]

how do we know r1 - r2 is a multiple of n?

[leaden stream]

n divides a-b

[flat scarab]

so r1 - r2 is either 0 or a multiple of n

And in either case, it ends up being 0

[leaden stream]

yes, because it between -n and n

[flat scarab]

unless q1 - q2 divides n evenly, in which case r1 - r2 is zero and we’re done

[leaden stream]

0 is a multiple of n

[flat scarab]

ok, so I don’t need to say case I case II?

[leaden stream]

nope

[flat scarab]

because it’s the same case

[leaden stream]

yes

[flat scarab]

okay, it’s starting to make sense

I think my confusion came from, we weren’t doing division, we didn’t know what q1 - q2 was

[edgy jacinth]

is this depends on the operation?

or just i have to assume it multiplication?

3x=1mod7 which will be A

someone is saying to me that it depends to operation

[weary rune]

“modular inverse” is typically understood to be “modular multiplicative inverse”

[whole bronze]

for integers a,b,c

is an identity from the first answer in this stack exchange post: https://math.stackexchange.com/questions/362975/concise-proof-that-every-common-divisor-divides-gcd-without-bezouts-identity/363030#363030

This formula easy to verify:

for the => direction we can notice ab/c = a(b/c) = (a/c) b where b/c and a/c are integers by assumption.

for the <= direction, we have that a k1 = ab/c and b k2 = ba/c for integers k1 and k2 so k1 = b/c and k2 = a/c which means c|a,b

What I'm having trouble with is proving the analagous formula a,b|c <=> ab/c | a,b

The reason this doesn't immediately follow from the first is that ab/c must be an integer for it to do so

For example, for the => direction, we could write c = ab/(ab/c), but if we try to apply the proposition from the screenshot, we would need (ab/c) to be an integer.

3,4|24 <=> 3*4/24 | 3*4 is not well formed

I suppose we really do need the assumption that ab/c is an integer.

I guess that answers my question..., it would still be interesting if given something like ab/lcm(a,b) | a,b, we could prove it via involution because a,b|lcm(a,b) while avoiding having to verify ab/lcm(a,b) is an integer.

Of course with the version of a,b|c <=> ab/c | a,b I have, ab/c has to be checked to be an integer separately

[lilac bronze]

Yes it’s not obvious to me that ab/c is an integer

the way i usually do it for lcm is with prime factorisation

because the fundamental theorem of arithmetic doesn’t actually need lcm

[lilac bronze]

anyway this stackexchange post reminded me of how I’d want to describe the “universal property of gcd”

given two naturals $a, b \in \mathbb{N}$, you can define $\text{gcd}(a, b) = \max {d \in \mathbb{N} \text{ such that } d| a \wedge d | b }$

[sterile pumice]

Pseudonium

[lilac bronze]

indeed that’s the literal meaning of “greatest common divisor”

and what this gives you is $d | a \wedge d | b \implies d \leq \text{gcd}(a, b)$

[sterile pumice]

Pseudonium

[lilac bronze]

but using bezout’s identity, $\text{gcd}(a, b) = ax + by$ for some integers $x$ and $y$

[sterile pumice]

Pseudonium

[lilac bronze]

so you can strengthen this result to $d | a \wedge d | b \implies d | \text{gcd}(a, b)$, and of course $d | \text{gcd}(a, b) \implies d \leq \text{gcd}(a, b)$

[sterile pumice]

Pseudonium

[lilac bronze]

and then what’s nice is that this becomes an if and only if, so $d | a \wedge d | b \iff d | \text{gcd}(a, b)$

[sterile pumice]

Pseudonium

[lilac bronze]

this is the “universal property of gcd”, how it relates to every other natural in the “universe” through divisibility alone (and is taken as the def of gcd more generally), and characterises it essentially uniquely

[flat scarab]

after a lot of arguing, debating, and much help, here is what i have written up for the proof i was trying to do the other day, more feedback is welcome. im a little bit unsure about the multiple of n part. thank you @leaden stream @patent acorn @rugged pasture

[whole bronze]

When you have a-b=n(q1-q2)+r1-r2, it may be even better to rewrite as r1-r2=(a-b)-n(q1-q2)

n divides the RHS and since the LHS is equal to the LHS, n divides r1-r2

You can skip the stuff with the inequalities and max etc.

[flat scarab]

i think i understand, what you have is simpler and replaces the min/max stuff, but i think the inequality may be important to show that the only multiple of $n$ between $-n$ and $n$ is $0$.

[sterile pumice]

computerman4774

[whole bronze]

No need - the question wanted n|a-b

Bounding it is just something extra you're doing unrelated to the problem

[flat scarab]

it's not unrelated, it tells us that $r_1 - r_2$ falls within a range and ends up being $0$

[sterile pumice]

computerman4774

[whole bronze]

The question didnt ask for that

Oh wait lemme look at this again

[flat scarab]

so what? the actual solution from the author is way different than what i have, doesn't make it wrong, there are many ways to do a proof

there is no one right answer when it comes to proving something, i have found

when taking proof based math courses, i would work with a group of students, all of us had different answers to every problem

not all the time of course!

there are some trivial proofs where you will arrive at the same answer as others

[whole bronze]

In the second part of the proof r1 and r2 are undefined. Probably use the division algorithm again. The scope of r1 r2 q1 q2 was only the first part.

Otherwise it's perfect

I had flipped which part of the answer was proving which part of the question in my head

[flat scarab]

look im not arguing for the sake of arguing - i thought long and hard about that, i would like to define them once and scope them to the whole problem, i know it is possible to do, they are simple remainders for a and b... how would you reccomend going about it? do a separate paragraph at the top? i dont mind this proof being longer, it's more for me than anyone else, it's not a homework assignment or anything

[whole bronze]

Yea, you could separate it at the beginning or state it twice

Most people will know what you're talking about even if you leave it as it is since this is a short and simple proof

[flat scarab]

it's a short one, obviously i lengthened it a little for myself

[lilac bronze]

seems like this works yes

[whole bronze]

For proving ab/lcm(a,b) is an integer, you can avoid using prime factorization by noticing that lcm(a,b) | ab by the universal property of lcm. (of course if your universal property of lcm is based on the <= relation instead of the | relation, there's some extra work to do to see that lcm(a,b)<= ab implies that lcm(a,b) | ab)

If you're curious about any details I left out, just ask and I can fill them in

[lilac bronze]

Yeah this seems false surely

2 | 30000 and 3 | 30000

So you need that ab/c is an integer

Oh and you noticed that already

Sorry

[lilac bronze]

Oh cool you know about universal properties too?

[whole bronze]

To be honest, it's pretty annoying to prove identities about gcd's and lcm's without universal properties:

To prove lcm(a,b) gcd(a,b) = ab, isolate the gcd and use the universal property of gcd's
To prove gcd(ka,kb) = kgcd(a,b), the gcd is already isolated, so use the universal property of gcd's
To prove gcd(a,b) = a if a|b, again show the RHS satisfies the universal property

[lilac bronze]

Wow I didn’t realise there were other people who knew about them

[whole bronze]

To be fair this is a math server lol

[lilac bronze]

Yeah but still

Lotsa people don’t like categorical stuff

[still flare]

Category theory is like, the biggest meme subject lmao. I feel like every other undergrad I speak to knows what a universal property is

People know what a universal property is

[lilac bronze]

Really…?

It’s often seemed like a new subject when I’ve discussed it with undergrads here

[still flare]

Yes, really.

[lilac bronze]

Huh that’s so strange

I’d heard of it in undergrad but only got into it in my masters

[boreal lichen]

We had covered universal properties in linear alegebra for quotient spaces, tensor produc,outer product spaces,…

[lilac bronze]

huh wow I never did this in my undergrad

[boreal lichen]

I don’t have a big math backround, since I don’t study math, but this from an algebra profesor who teached linear algebra 2. He was quite cool, because he was very structured in his approach and a chill guy. And he put much emphasis on universal properties

So many things where universal properties

[robust prawn]

Given any two positive integers a and b greater than one, what is the smallest prime greater than ab that cannot be formed by a linear combination of a and b?

Is this a well-known problem?

[surreal tangle]

Well if gcd(a,b)=1, there is no such smallest prime (by beizouts lemma)

[robust prawn]

Sniped me

Yeah if they're relatively prime all the numbers greater than ab are reachable

[surreal tangle]

So, if their gcd was not 1, say d, any linear combination of a and b will not be prime

[robust prawn]

Because you'd be able to factor d out of the equation right?

[surreal tangle]

Yeah ~~ but youll need to be more careful in stating this. Because this is not entirely accurate~~

[robust prawn]

How so?

If both a and b are divisible by d then ax + by should still be divisible by d

[surreal tangle]

Oop, nvm i got confused for a sec (My main concern was what if d was a prime p then youd factor p out of ax+by and get ax+by=p(•) and that • could be 1, so youd have ax+by=p, But then the linear combination wouldnt be greater than ab. So its all good.)

[robust prawn]

Np, tysm for your help

[wooden glen]

If they're not coprime, then you're just asking for the smallest prime greater than ab.

Since in that case no combination of a and b (except possibly their gcd, which is at most ab) can be prime.

[flat scarab]

was hoping someone could take a look and critique another proof, it follows from a previous proof i did, i begin this proof explaining what that proof was, apologize it's a little lengthy. this is a problem from the preliminary section of gallian's abstract algebra book

edited (cleaned up, used \equiv in some spots)

[keen pagoda]

yeah this works

I feel like it's longer than it needs to be tho

but ig basic number theory can be kinda misleading and hard to do rigorously so if you think it's necessary...

[flat scarab]

would like feedback on another (shorter), proof. my answer was slightly different than what was in the back of the book, i would like to know if this would also work as an alternative proof. in the book, it says: ax = 1 + ns, d divides a and n, d also divides 1, thus d = 1. instead i used the linear combination and well ordered principle (or whatever says 1 is the smallest element of the set, and is thus the gcd).

[tight meadow]

last two non zeroes digits in 100!

[flat scarab]

@wooden glen

[wooden glen]

Don't ping random users.

[flat scarab]

sorry!

[flat scarab]

will not happen again

[leaden stream]

seems correct, a slight wording issue right at the end
"If d = 1 then ax = 1 (mod n)" should say something about a solution existing. It is not the case that ax = 1 (mod n) always, just that there is an x that makes that true.

[flat scarab]

@leaden stream thank you, updated with your suggestion:

[flat scarab]

another very short proof. if someone has some time to take a quick look, it would be much appreciated. this time using light theme

[brittle root]

The second sentence in the proof doesn't quite work because you're saying there's no prime p so p isn't even an object we can talk about

At least phrased in that way

But a small change should fix it

(is this from gallian?)

[flat scarab]

what about, let $p$ be a prime that divides $a$, then $p$ does not divide $bc$ (continue on from there...)?

[sterile pumice]

proofman

[brittle root]

yes

that's it!

[flat scarab]

yes, every problem i do is from gallian, i am self studying his book

[flat scarab]

i have been away from proof based math for a little while, getting back into the swing

[brittle root]

the 10th edition is quite typo riddled

[flat scarab]

i heard

plus i am not rich, so i got 6E

[brittle root]

i use the pdf lol

university access

it's not bad, has a lot of examples so it really helps with understanding

[flat scarab]

nice, i saw someone put it on a github, but i feel bad, i paid

[brittle root]

I quite liked it personally

[flat scarab]

10E?

[brittle root]

Gallian

Not 10E

Specifically

[flat scarab]

ok

[brittle root]

I do have my own typo list for the 10th edition

[flat scarab]

you're just saying you like Gallian in general

[brittle root]

Yeah I like that he gives loads of examples

[flat scarab]

love it

i actually went through chapters 1, 2, 3 a long time ago

[brittle root]

i'll probably see you in the groups channel soon then

[flat scarab]

hopefully, i wanted to skip the prelims in chapter 0 of Gallian, but it is obvious that i am very rusty

im getting my butt kicked on every problem just about

[brittle root]

if it's any consolation having a good strong understanding of the preliminaries will help you quite a lot later on in the book

[flat scarab]

yes, that helps

[flat scarab]

so most of them i need a hint or a brief look at how to start, some of them i figured out on my own... but i will keep going through them until i can get them without any help or hints, luckily there are plenty of problems

[flat scarab]

i used to breeze through these ☹️

[brittle root]

i spent longer than you did on these preliminaries when I first learnt this content

dw itll come back to you

[flat scarab]

appreciate it, yeah when i was doing the foundations of math university course i was getting them really fast, then i had to take a break due to life circumstance

[flat scarab]

@brittle root this may be a little bit better

[brittle root]

hmm that still doesn't quite work out

[brittle root]

continue from here

since p is arbitrary it follows that no prime that divides a divides b and c

oh actually sorry

yeah that's what you wrote

my bad

[flat scarab]

okay, here, take a look at this, it is the logical continuation from there, does this seem closer

[brittle root]

yes this is good

[flat scarab]

the last two steps i feel are a little hand-wavy

not intentionally

actually, the last 3 steps

intuitively, it makes sense based on the two theorems i used, but how to represent this in pure symbolic logic?

[brittle root]

well you don't have to do that

why do you find them handwavey though

[flat scarab]

maybe i dont, i may have just been staring at it for too long at this point and getting confused

[brittle root]

it seems fine to me

[flat scarab]

if a prime $p$ divides $a$ implies that $p$ does not divide $b$ and $p$ does not divide $c$, then $\gcd (a, b) = 1$ and $\gcd (a, c) = 1$, and that's that

[sterile pumice]

proofman

[flat scarab]

it kind of doesn't get too much simpler

[flat scarab]

@brittle root new and improved

[flat scarab]

Contemporary Abstract Algebra, by Joseph Gallian

I am using a cheap 6E copy I got on ebay

the preliminary section focus is on elementary number theory

lol I like it

it fits nicely with philosophy

it works well as a basis for understanding how to write proofs, and some abstract algebra concepts

cool! you should try Gallian, you can get a copy cheap

I’m just going through all the problems in 6E chapter 0, pretty much all ENT

I’m sure there are options for that

What is aops?

Oh ok, I see. Art of Problem Solving.

you going to take a element number theory course?

oh ok you just self study the ent book

very nice

[wheat tinsel]

Is this always impossible? I think it is.

[wheat tinsel]

wait it can happen for h=9,k=2,y=-5,x=1

yes, it is the same as taking the modulus with the absolute value

[patent acorn]

no

$a \equiv r \pmod n \iff a \equiv r \pmod {-n}$

[sterile pumice]

bee [it/its]

[flat scarab]

I have written a proof to show that there are infinitely many primes, i tried to leave out as much simple details as possible and not be too long-winded, any thoughts on this? did i leave out any crucial information?

[west glade]

you should elaborate a bit more why p_i divides 1 imo

[flat scarab]

hmm... i'm not too sure how i would break that down. say we divide $N$ by $p_i$, then we divide the other side of the equation by $p_i$ as well. so we are dividing the sum $p_1 p_2 \cdots p_n + 1$ by $p_i$. the sum $p_1 p_2 \cdots p_n + 1$ must be an integer multiple of $p_i$, which means that $1$ must also be a multiple of $p_i$, then we say ``we have a contradiction'' $p_i$ cannot divide $1$

[sterile pumice]

proofman

[west glade]

so because p_i divides N, there exists a k with N=kp_i = p1...pn+1

now subtract p1...pn

[flat scarab]

ok i subtracted $p_1 p_2 \cdots p_n$, i got: $p_i (k + p_1 p_2 \cdots p_{i - 1} p_{i + 1} \cdots p_n) = 1$

[sterile pumice]

proofman

[west glade]

and now you can conclude that pi divides 1

btw, for convenience, it would be fine to relabel all the primes and say wlog that p1 divides N

[flat scarab]

not trying to argue, but isn't this a case of "it is obvious"?

let me elaborate

if this showed up in a book, would i write that step?

[west glade]

I mean is it obvious? you werent able to properly fill in the details

[flat scarab]

yes, i would say it is obvious. what makes you say i couldn't fill in the details?

[west glade]

nvm i misread that part

but still, it would definitely need a bit more detail imo

at least the sentence I wrote

[flat scarab]

no, i was sure it was correct. i just wanted feedback on if i included enough detail

[west glade]

it would also be define to say a bit more loosely, pi divides N and N-1, hence 1. or stuff like that

but that connection was missing

but I mean even that uses some small lemma that a|b, a|c => a|b-c

[flat scarab]

it's ok, i think we are on the same page. i want to move on to something else. can you expand a bit more on this comment?

[west glade]

then you would be able to write $p_2\cdots p_n$ instead of $p_1\cdots p_{i-1}p_{i+1}\cdots p_n$

[sterile pumice]

Denascite

[west glade]

just makes it a bit more convenient to read and write

[flat scarab]

ok, without loss of generality, we take $p_1$, because there's really no difference between taking that prime or any other prime... right?

[sterile pumice]

proofman

[west glade]

Thus, $N$ is a product of primes, hence there exists some $i$ such that $p_i$ divides $N$. After relabeling the primes, wlog we assume $i=1$, i.e. $p_1$ divides $N$

[sterile pumice]

Denascite

[west glade]

and then continue the proof from there

sth like that

[flat scarab]

ok, you made it make sense

[flat scarab]

what was this comment referring to?

[west glade]

.

[flat scarab]

did you mean to say "fine"

[west glade]

I didnt write out "it was referring to this message"

[flat scarab]

sorry i dont understand

[west glade]

you asked what my comment was referring to. I replied which message it was referring to

[flat scarab]

ok. in that message which you were referring to: did you mean to say "fine" instead of "define"?

i suppose probably you did

[west glade]

oh. yes

[flat scarab]

ok thank you

[flat scarab]

let me see if i understand: we could have started with $N - 1$ instead of $N$?

[sterile pumice]

proofman

[west glade]

I mean N-1 is p1...pn

you obviously used that

but you need the specific p_i which divides N

so you need to start with N. if thats what you mean

[flat scarab]

you are trying to simplify how to show the division?

[west glade]

I mean just generally you dont really want to talk about division as an operation

divisibility, sure. but you dont really want to divide stuff, cause before that you have to take care whether thats actually a thing you are allowed to do

you dont generally wanna argue with "oh hey in the rationals you could divide, but the result is a proper fraction and not an integer". its much nicer to stay in the integers

at least imo

also generalizes better to other rings

[flat scarab]

i see

[flat scarab]

ok, this makes sense because when you say: $p_i (k + p_1 p_2 \cdots p_{i - 1} p_{i + 1} \cdots p_n) = 1$ (in your case with $p_1$ instead of $p_i$), you get to use multiplication, stay in the integers

[west glade]

yes exactly. my entire argument never uses division

and most of these basic arguments generally never need division

[flat scarab]

very nice

[flat scarab]

do you know why texit didnt compile that last message properly? it messed up the $p_{i - 1}$, i cant figure out what i did wrong

[sterile pumice]

proofman

[west glade]

notice how the "divides" definition a|b is "there exists integer k with ak=b" instead of "there exists integer k with k=b/a"

there doesnt seem to be an underscore I think?

[sterile pumice]

proofman

[flat scarab]

good catch

[flat scarab]

yeah good example

its a very basic example, i should have caught on to that

[west glade]

dw, few people do I think

a lot of these types of proofs I read actually use the second def

sadly

[flat scarab]

that i didnt see, for example in the Gallian book it uses the first one

[west glade]

*proofs by students. not books

[flat scarab]

oh ok

[flat scarab]

im going to re-write this proof quickly and post it in the chat, i like everything you said but i think i will stick with the $p_i$ for mine

[sterile pumice]

proofman

[flat scarab]

even though it isnt as clean as yours, i like the generality of using $i$

[sterile pumice]

proofman

[west glade]

yeah dw stick with that

[flat scarab]

here, i think this is better

[west glade]

the p_i-1 is again messed up. also there needs to be a minus after the k

also I just noticed you use the implicit assumption that pn is the largest of the primes

either write that down or say that it is larger than each of the primes individually

[flat scarab]

there are a few things messed up

[flat scarab]

you want me to say < < < <

@west glade

[west glade]

yes

note that now you couldnt just do the wlog i=1 stuff cause you need that the primes are ordered

so you gain a bit of convenience for assuming there are ordered but lose a bit in exchange

[flat scarab]

quick syntax question, should i use: \ldots or \cdots for the "< < <" stuff?

[west glade]

I would use ldots

[flat scarab]

because "<" is not an operation?

[west glade]

I only use cdots for repeated multiplication

and even for that I often see \cdot\ldots\cdot

[flat scarab]

$\cdot \ldots \cdot$

[sterile pumice]

proofman

[flat scarab]

oh i see

[flat scarab]

you dont say $n! = n \cdot (n - 1) \cdots 2 \cdot 1$ or something like that?

[sterile pumice]

proofman

[west glade]

I personally would but I am have seen other people not doing it. I dont know if there is a "correct" way

not that it really matters that much

if there is one thing I have seen in the past on the tex stackexchange is that people often have different opinions about how something should be typesetted

[flat scarab]

for sure, just want to work on my tex skills as well

[flat scarab]

appreciate all of the helpful little tidbits, i think i am good for now

there were a lot of things i was thinking in that proof and not writing down

it's like either i write too much, or too little, still trying to work on that

[west glade]

yes thats normal

[sterile pumice]

Vanellope von Schmugz

[cobalt hornet]

how do we have the last inequality

[sterile pumice]

Vanellope von Schmugz

Vanellope von Schmugz

Vanellope von Schmugz

[cobalt hornet]

Ah so, we could then also write it as $\frac{3}{2}\cdot (\frac{6}{5})^{k-1}$ right?

[sterile pumice]

Sentinel

[flat scarab]

posted an updated version of it

[flat scarab]

I think there was still something wrong with that proof, because $N$ would be greater than $p_n$ even without the $+1$, I’m trying to figure out where I went wrong.

[sterile pumice]

proofman

[flat scarab]

maybe we just add +1 to it because it’s like chess, and that’s the “move” that allows us to get the contradiction?

[stiff rivet]

i mean without the +1 you dont get the contradiction of some prime dividing 1

you dont need the fact that N is greater than the primes at all though (you only need to know its not on your list)

and the list doesnt need to be ordered by size

[flat scarab]

so just say: $N$ isn’t in the list, thus $N$ isn’t divisible by any prime $p_i$?

[sterile pumice]

proofman

[stiff rivet]

no

there are two cases:

either N itself is prime, then you immediately get a contradiction (as its not on your assumed complete list of primes)

or N is not prime, then it still has a prime factorization, so it must be divisible by some prime on your list

then you get a contradiction because that prime will also divide 1 (which is impossible)

[stiff rivet]

ofc arguing "N is greater than all primes on the list, so it cant be on the list" works

its just not strictly necessary

[flat scarab]

I understand where you are going with this. It sort of optimizes the proof. To carry out your idea, so then N has to equal: k + 1, where $k$ is also some integer not in the list?

[sterile pumice]

proofman

[patent acorn]

i don't think you really need to separately consider N being prime at all?

just, every number (that isn't 1) is divisible by some prime

but N can't be divisible by any primes

and N clearly isn't 1

[stiff rivet]

ah yes, sure

that simplifies the proof further

but the proofs you posted are correct too

[flat scarab]

which message are you referring to?

[stiff rivet]

what bee said

[stiff rivet]

this isnt needed, the proof also works if your list is just 1 element

[flat scarab]

yeah that first case thing, I don’t think it’s necessary either,

[stiff rivet]

with bee's optimization the proof is just defining N and then noticing that some prime p on your list divides N and thus 1, which is a contradiction

[flat scarab]

ok, I see where you’re going with it, but how do you define N?

[stiff rivet]

like you did

[flat scarab]

k + 1 thing?

[stiff rivet]

yes

[flat scarab]

and we don’t really care what k is, just that it isn’t in the list?

[stiff rivet]

no, it has to be the product of all the primes

otherwise you cant guarantee that some prime on the list divides 1

the whole divisibility argument relies on the fact that some p_i divides k

the only way guarantee this is true for some p_i is to just make k the product of all of them

[flat scarab]

I don’t understand

[stiff rivet]

did you not write this

[flat scarab]

yes I did write it

[stiff rivet]

you use the fact that k is divisible by p_i

and you dont know what i is

[flat scarab]

I mean yeah I didn’t call it k, I used k for something else

[stiff rivet]

so you have to make sure that k is divisible by p_1, p_2, ..., p_n

[flat scarab]

ok for me, $N = k p_i$ in the original proof

[sterile pumice]

proofman

[stiff rivet]

ah ok well, you used k for different things

[stiff rivet]

in the screenshot k is something else than what you said here

[flat scarab]

yes sorry I confused the issue

so maybe $m = p_1 p_2 \cdots p_n$ instead

[sterile pumice]

proofman

[flat scarab]

So then, $N = k p_i$

[sterile pumice]

proofman

[flat scarab]

$k p_i = m + 1$

[sterile pumice]

proofman

[flat scarab]

$p_i$ does not divide 1

[sterile pumice]

proofman

[stiff rivet]

from here you can just write $m = p_i k'$ for some integer $k'$

[sterile pumice]

Lochverstärker

[stiff rivet]

then $p_i(k-k') = 1$, giving you your contradiction

[sterile pumice]

Lochverstärker

[stiff rivet]

(and then you dont even need to care about the i and can just claim that p is some prime on the list)

[flat scarab]

I don’t understand how did you get this step?

[stiff rivet]

$kp_i = k'p_i + 1$ and just do algebra

[sterile pumice]

Lochverstärker

[stiff rivet]

-k'p_i on both sides

and factour out the p_i on the left

[flat scarab]

Isn’t this the same as when I wrote $m + 1$?

[sterile pumice]

proofman

[stiff rivet]

i mean sure

what you wrote is already correct

[flat scarab]

ok I got confused, I thought I did the wrong thing

[flat scarab]

yeah I understand that this is more elegant

[cobalt hornet]

can anyone see why this is true for uneven prim p

[stiff rivet]

more generally, you can show that this function is multiplicative

this is a consequence of the chinese remainder theorem

[cobalt hornet]

why is then $\phi(2) = 1$

[sterile pumice]

Sentinel

[stiff rivet]

i also just noticed this screenshot is german

well, look at the definition

[cobalt hornet]

ah okay

i understood 😄

[stiff rivet]

gcd(2, 1) = 1 and gcd(2, 2) = 2

[cobalt hornet]

i thought at first gcd(2,2) = 1

[stiff rivet]

so...

in fact you can alter the definition and have 1 \leq a < M

[cobalt hornet]

yep

[cobalt hornet]

and why is that true actually?

[stiff rivet]

do you agree that a^(p-1) = 1 (mod p)

[cobalt hornet]

yep since p is prim $\phi(p) = p-1 $ is the order of a mod p

[stiff rivet]

now a^((p-1)/2) squares to 1 (mod p)

x^2 = 1 has only two solutions, 1 and -1

[cobalt hornet]

oh we are just multiplying those two

[stiff rivet]

if its 1, it cant be a primitive root

[cobalt hornet]

oh nice reasoning

[stiff rivet]

this is called little fermat

"Kleiner fermatscher Satz"

[cobalt hornet]

this right? i know

[stiff rivet]

ye sure

then its called Euler's theorem

it directly follows from little fermat

[cobalt hornet]

oh i knew it in that form

[stiff rivet]

sure, same thing

[cobalt hornet]

yep but i didnt think of taking the quadrat of the square and argument it by euler

[stiff rivet]

this technically requires some further arguing

or some knowledge about basic field theory