elementary-number-theory

[jovial hemlock]

It's

wait hang on I know I did something to solve that issue let me look over this again really quicklu

okay so the way it works is

Once you have a number which is Y base C, all numbers that stem off of that, so to speak, will still be Y base C

so as you increase the base you're working with from C, you'll still be carrying along numbers of the form Y base C with you, ever-increasing

and so you're increasing the prime factors that this number isn't 1 or -1 mod of, and so you're keeping a number of the form Y base C but it's also not mod 1 or -1 from all of the prime factors you eliminate

and- and it looks like I accidentally deleted this step from my proof now that I'm double checking- the maximum rate at which you would have to increase C is multiplying it by a factor of 2 on each step, because even assuming 0C + Y and 1C + Y were the mods 1 and -1, then you still couldn't be caught in an infinite cycle before going through all the mods, so 2C+Y would have to be something which would go on the list

and, yknow, you let (2C + Y) be W, and then maybe the next step you have to do 2K + W where K is the list size before the step, but you're going at this until your 2K + W number is verified past the biggest prime below itself

and then you know it worked

oh but you're saying the issue is that you don't know it will be verified that far

because for example, if you had something mod 7 and tried verifying it, it could be 1 mod 11, and then incrementing it would give 1 mod 13, and etc, never stopping? is that right?

I see a way to solve this issue, but it'll require a bit of work to make it understandable to read

I'm tired I need to sleep on it, I'll continue tomorrow okay? Goodnight!

If I can ping you tomorrow, Zopherous, please ping me after this message

[alpine jasper]

Can I read it too?

[brisk shoal]

anyone knows how I can prove that for ab ≅ 1 (mod c)... where 1 <= b < c , a and c have to be relatively prime?

[light flicker]

ab = 1 (mod c) means that ab = 1 + kc for some integer k

so that ab - kc = 1

which by bezout's theorem implies that a and c are coprime

[brisk shoal]

ah okay... thank you!

[brisk shoal]

was trying to find all the integer points on an elliptic curve
There is a function for it in Sage... S-Integral points, but it requires some sort of input for some set of primes
Which I don't understand why?
I am pretty confused by all the literature when I search it up
I am guessing they only calculate it over finite fields...

[light flicker]

You can just do E.integral_points()

[brisk shoal]

oh... couldn't find the documentation so I thought it didn't exist

Thank you @light flicker

[jovial hemlock]

okay

I think I've solved the issue @light flicker

I used a different path to get through the second half of the proof

Please ping me when you can check it out!

This time I made sure to avoid doing the thing where I defined conditions the number has to meet and then accidentally used my definition as a claim that it existed. I did it differently this time, and actually via a different route as well.

oh hmm actually your time zone looks like we'll have a conflict

judging by when you've been active

okay, so can someone else help me and ping me? I think I have a proof of the twin prime conjecture, I probably did something wrong, I don't know what though.

[jovial hemlock]

Any help would be appreciated

[jovial hemlock]

https://www.reddit.com/r/askmath/comments/gernpo/can_someone_explain_whether_this_is_a_valid_proof/?utm_source=share&utm_medium=ios_app&utm_name=iossmf

[severe bone]

@jovial hemlock Your fourth remark there is unnecessary, N will always be even and thus 0 mod 2

What do you mean by "Consider that you have determined there are X ways possible to write N in base B"

[jovial hemlock]

Proof by induction style

@severe bone

the fourth remark establishes base case

and the fifth remark begins establishing higher cases

[severe bone]

@jovial hemlock I'll bite, you can message me privately and I'll help you find the error 🙂

[jovial hemlock]

OKay

I'm ready

I have the proof laid out in a nice, readable PDF format

Can someone check it to see where any errors are or if it is correct?

And ping me when they're ready?

Brouwers had to leave while we were discussing it but he gave me some tips for how to better format it.

[jovial hemlock]

Oh shoot I forgot to actually link the thing here it is

Again I figure this is most likely false but I’d like to know why

[fervent crest]

$N-1\not\equiv0\pmod{P}$

[sterile pumice]

Whoever:

[fervent crest]

@jovial hemlock

[jovial hemlock]

oh is that like how you format it?

[fervent crest]

Yes

[jovial hemlock]

Thank you. I lost my ability to format it as time went on as I began having to use words in my variables (G’th prime, for example) and the formatting wouldn’t work with that

[fervent crest]

Latex is created for this purpose lol

Well

You could’ve say $p_G$

[sterile pumice]

Whoever:

[fervent crest]

The G’th prime

[jovial hemlock]

I also don’t know how to put ... in something, like A * B *.... * Z

[fervent crest]

$AB\cdots Z$

[sterile pumice]

Whoever:

[jovial hemlock]

$p_G-1$

[sterile pumice]

Notchmath:

[jovial hemlock]

$p_(G-1)$

[sterile pumice]

Notchmath:

[fervent crest]

$p_{G-1}$

[sterile pumice]

Whoever:

[fervent crest]

Sorry this should not belong here

[jovial hemlock]

oh thanks

[fervent crest]

If you want to test the bots, do it in #bots

Ping me if you need anything

[jovial hemlock]

when I can get to a computer I’ll reformat it and make a couple of edits for clarity

Thank you!

[jovial hemlock]

okay

finally

I finally have this in full LaTeX format

it's easy to read

organized

...hopefully anyway

Now, can someone check it for errors please?

As I've said before, I'm sure it's probably wrong, but I myself cannot find any errors in it, so anyone willing to look at it would be very much appreciated.

[wide shuttle]

Are there any assumptions that you've made? There could be things that were overlooked.

[jovial hemlock]

well, I don't think so

but it's easy to make assumptions and not be aware of it which is why I'd like an outside perspective

[wide shuttle]

Also

You said "$N\equiv I(\mod A)$ and $N\equiv I(\mod B)$"

[sterile pumice]

Yeat:

[wide shuttle]

Was the second I supposed to be a J?

[jovial hemlock]

Yes, sorry, typo when converting to LaTeX

[wide shuttle]

The 4th para btw

Of 1.2

[jovial hemlock]

no I know where you mean

[wide shuttle]

I'm not really qualified to say much else as I having done much number theory. But gl and also, if this proof is valid. Then someone could easily steal it

[jovial hemlock]

I have a record of it though don't I?

that I had it first?

[wide shuttle]

Yeah, but just so you know

😊

[jovial hemlock]

So where can I get it looked at?

[wide shuttle]

I don't know, I'd say professors, but I'm not in Uni yet

Ask some of the higher ups, they may know

Like mnip or zoph

[jovial hemlock]

It's difficult because if I were to say "I think I proved the twin prime conjecture" people would generally just assume I'm a crank basically

and for all I know I am

but if I am, I'd like to learn why, and if I'm not, then I'd REALLY like to know that lol

So can I ping them, or...?

I'm sorry I'm not familiar with the way this server in particular works

[wide shuttle]

[light flicker]

To be completely honest

[jovial hemlock]

some servers have "I can ping specific people who are best suited to answer my question" and some don't

[light flicker]

It's just not worth my time to try to wade through the bad mathematical writing and notation to figure out what the error is

[jovial hemlock]

oh

what's bad about my writing and notation?

I'm sorry, I don't have much experience formatting things

[sacred junco]

you haven't explained what some of the variables are, for instance

[jovial hemlock]

Really? What?

[winter bear]

it just

ok would you read that?

like its just tedious to read

[jovial hemlock]

I don't know how to make it better is the thing

[sacred junco]

e.g. the second page first paragraph

what are a_i s

[jovial hemlock]

oh

[sacred junco]

are they the primes below B?

[jovial hemlock]

damnit, I transferred my proof from one document to another and accidentally left out some explaining details

[wide shuttle]

Also, starting a sentence with "because". Specifically "Because P is prime...". I would say "By definition, the factors of prime P are 1 and P" or something like that

[jovial hemlock]

I made sure all the equations stayed but I forgot about some definitions ig, I'm sorry

[wide shuttle]

Learning is good

[jovial hemlock]

So like

how would I say "Because $AB$ is the product of all primes up to and including $B$, the proof by induction that there are arbitrarily many values of $K$ such that (N\equiv K\pmod{Q}) where $Q$ is the product of all primes up to and including an arbitrary $P$ is complete. "?

[sterile pumice]

Notchmath:

[wide shuttle]

[jovial hemlock]

also, how do I write something like P sub G is equal to the G'th prime

[wide shuttle]

Yeah, I would like to help. But I'm not qualified enough. "...the proof by induction that there are..."

[jovial hemlock]

I know the math looks tedius, but I don't know how to make it not tedius

[wide shuttle]

The phrasing there sounds wierd, but I've never referenced induction before either

[jovial hemlock]

what about the P sub G is the G'th prime bit?

[wide shuttle]

And one could say "Let $p_g \coloneqq $g'th prime"

[sterile pumice]

Yeat:

[jovial hemlock]

is the apostrophe good then?

[wide shuttle]

But maybe one could specifically build the g'th prime which might be preferred

[jovial hemlock]

what's the := mean?

[wide shuttle]

"Defined as "

[jovial hemlock]

oh wait

that's defined as

I remember now

[sacred junco]

i don't get it, there are always arbitrarily many $k$ such that
$$a \equiv k \pmod b$$
given literally any $a$ and $b$

[sterile pumice]

EvilRobotOverlord:

[jovial hemlock]

at what step are you referring to?

[sacred junco]

the one you just sent

[jovial hemlock]

oh

that's another thing I don't know how to phrase

I meant k between 0 and b-1 inclusive

but arbitrary isn't the right word

[sacred junco]

yeah

arbitrarily many means you can go on indefinitely

[jovial hemlock]

basically I mean that as b gets higher, the number of K-values increases

so as b gets arbitrarily high K goes arbitrarily high with it, but k is limited by b

I don't know how to express that in math language

[sacred junco]

B is just any prime below N right?

[jovial hemlock]

um

the message was actually as Q goes arbitrarily high K goes arbitrarily high with it

and Q is the product of all primes to a certain point

[sacred junco]

doesn't have to be true

let N = 2 mod all primes less than or equal to some prime B

[jovial hemlock]

a.k.a. (Q+1) has more values of K then Q does

[sacred junco]

so using CNT you have N = 2 (mod product of all those primes)

[jovial hemlock]

okay

and I'm assuming it's 0 mod 2

[sacred junco]

yeah

i did that too

[jovial hemlock]

and by CNT you mean CRT?

[sacred junco]

woops yes

it's chinese remainder theorem not number theorem rip me

anyways

i don't get what you mean by this statement, but if you mean "if i multiply all the primes below an even number N, then for all N, the value of N mod that product grows bigger and bigger" then it's not correct

[jovial hemlock]

no

and this is the other hard part, I don't know how to formulate what N is

N is basically

N is a representative of the set of numbers that satisfy the characteristics of N

[sacred junco]

oh you mean it's a number between twin primes?

[jovial hemlock]

um

No

[sacred junco]

you referenced something like that earlier in your article

[jovial hemlock]

a number between twin primes satisfies all the characteristcs of N

[sacred junco]

using the same variable N

[jovial hemlock]

but there are numbers that satisfy all the characteristics that are not twin primes

and one of the characteristics of N is being bigger than the biggest prime number being used to define N

[light flicker]

I feel like you've got this backwards

[sacred junco]

hmm i guess these characteristics don't make sense until you tell us what these a_i s are

[jovial hemlock]

and I don't know how to express that idea

[light flicker]

Just because the number satisfy the characteristics

doesn't mean it has to be a twin prime

[jovial hemlock]

right

[light flicker]

or the number between a twin prime

[jovial hemlock]

and I'm aware of that

the first part is establishing the characteristics of N so I can work with N

and then I figure out what additional characteristics N must have to be a the number between twin primes (in this case that means it must be smaller than P^2)

and then I show that there are infinitely many numbers N with that additional characteristic

like

think of it like this

Assume you have a number N, which is bigger than 5, and is not 1 or -1 mod any prime up to and including 5

[sacred junco]

okay

[jovial hemlock]

then if you were to look at the numbers K so N = K mod 30

and look at those numbers K

those would be in this case 0, 12, and 18

and those numbers are what the a_is are

[sacred junco]

so it has to be divisible by 6

oh

okay

so you're saying that there are a lot of numbers that aren't +/- 1 mod prime

[jovial hemlock]

and in this case N is literally just defined as "Any number bigger than 5 which is not 1 or -1 mod any prime up to and including 5"

and I don't know how to express that mathematically

especially in the general sense of 5

[sacred junco]

ohh i think i get what you mean now

[jovial hemlock]

and I especially don't know how to express a_i mathematically

and the statement I'm having trouble expressing is that the size of the list of the a_i's always goes up as the prime N is based on goes up

the issue is that I can formulate the concepts in words and prove the concepts but I can't express the individual statements mathematically despite knowing they're true

[sacred junco]

$a_i$s are all the numbers that $N$ can be congruent to mod $A$ such that $N$ isn't $\pm 1$ mod any prime less than $N$

[sterile pumice]

EvilRobotOverlord:

[sacred junco]

is this what you mean?

[jovial hemlock]

and a_i is between 0 and A-1 inclusive

and N is bigger than A

yes

so I don't know exactly how to define N, because it isn't a constant as it depends on the size of the P below it, and it also isn't a variable, it's more of a representative of a larger group

it's not that the concept itself is wibbly it's that I don't know how to express it

[sacred junco]

why should N > A

[jovial hemlock]

because if N < A then you could have N = 5, which isn't 1 mod any prime number, but also shouldn't appear on the list to 30

[sacred junco]

it will never be 5 because 5 is 1 mod 2

[jovial hemlock]

okay then, how about this

on the list to 210

sorry, 2310

which is 2 * 3* 5 * 7 * 11

the number 12 is 11 + 1

but

[sacred junco]

if anything i think you should do N < B

[jovial hemlock]

actually

it's not even N>A

it's N-1>A

actually

[sacred junco]

i kinda lost you man

[jovial hemlock]

no I don't know if it has to be above anything but I know that it works if its above A + 1

[sacred junco]

can you like formulate all this in 1 way

and post it again

[jovial hemlock]

well, assuming I made no errors anyway

okay

A is the product of the first few primes (few being as many as you want)

N is any number bigger than A+1 where N is not 1 or -1 mod any prime which is a factor of A

the numbers a_i are the numbers that N could be congruent to mod A

that's the definitions I'm using

M is the number of unique a_i's

B is the first prime bigger than the largest prime going into A

oh wait, Jelly, you mean formulate like the actual proof?

Okay

Jelly

I did it

never mind I have some lines from old definitions

okay here, I think I mean it this time

@sacred junco

[sacred junco]

well there's a small issue

[jovial hemlock]

what?

[sacred junco]

what if N - 1 is divisible by a prime greater than B

we have no way to check

[jovial hemlock]

well we do

which is why I said N isn't the only condition a number must satisfy to be a twin prime center

N must also be < the square root of B

[sacred junco]

oh okay

can you guarantee that all the a_i's are < sqrt B

[jovial hemlock]

No

But

I can guarantee that for each of the a_i's, a number can be generated from them which is larger than them and is <sqrt its base

[sacred junco]

btw if this turns out to be a real proof you need to take credit

[jovial hemlock]

assuming my proof is correct, that is

[sacred junco]

upload it to GitHub or something

maybe make it private or something

[jovial hemlock]

do you want to move to PMs?

[sacred junco]

until you have the details ironed out

not really lol im not an expert on this subject or anything

far from it

[jovial hemlock]

so you can help me better formalize it? I know I need other people to review it and that's what I'm trying to have happen

[sacred junco]

hope someone else will read it and confirm it lol

[fervent crest]

[jovial hemlock]

but I've spent 4+ hours a day for the last 3 days just on formalizing it

[fervent crest]

If this turns out to be a real proof

[jovial hemlock]

and no-one is actually reading it

and obviously I know formalizing it is important

it's just, I don't want to spend another 12 hours formalizing it just to find out it's unfixably wrong

[winter bear]

lol mathmeticians with far more tools have taken a crack at this for 100s of years, i dont think basic modular arithmetic would prove this in the span of a few page

[fervent crest]

Um

[jovial hemlock]

I don't think so either

[winter bear]

like im sure theres something wrong with this, but like i really dont wanna read it

[fervent crest]

But I don’t think someone else is going to check your work for you

[jovial hemlock]

which is why I'm pretty sure it's wrong

but I keep checking every individual step and they seem right, and I'm probably making some sort of error that I don't know what it is

[dry sorrel]

let me look wait

where does the proof start and where does it end?

[jovial hemlock]

um

I can PM it to you

[hollow basalt]

No-one here is qualified to check your work @jovial hemlock , I recommend getting in touch with @glad nacelle , he does research on the twin prime conjecture. And also Collatz conjecture.

[jovial hemlock]

oh okay

[winter bear]

lmfao

[jovial hemlock]

can I just PM him and ask him directly??

[hollow basalt]

Good luck! I hope it is right

yeah just pm

[jovial hemlock]

okay thank you!

[sacred junco]

tell him gomez sent you

[jovial hemlock]

Thank you all so much!

I'm sure it's wrong- while it would be nice if it were right it probably isnt', but I just can't figure out what's wrong myself

[dry sorrel]

hey PM me too I wanna see it too

[fervent crest]

lmao

[frank wolf]

Buncho trolls lol

[jovial hemlock]

wdym buncho trolls

[fervent crest]

He thinks you're a troll

It's fine

Don't mind him

Just finish whatever you're doing

And send your proof to dami

[winter bear]

yeah finish proving the twin prime conjecture

[fervent crest]

Ping him, since he's kinda busy all the time

[hollow basalt]

I think he said he was already finished

[fervent crest]

He'll help you for sure

Oh

[hollow basalt]

am so excited for dami to verify!

[fervent crest]

Same!

[jovial hemlock]

I'm done if I'm correct but I'm probably not

[frank wolf]

You know very well I'm not calling notch math a troll

[jovial hemlock]

do you mean the guy called buncho is a troll?

[frank wolf]

Nvm

Dw about it

[hollow basalt]

yeah a bunch of people troll here because they have nothing better to do, try not to let them get to you.

[jovial hemlock]

Thank you, by the way, Gomez

JohnDS, I never said I think it's true

[winter bear]

nono im laughing cause

[jovial hemlock]

only that I myself am unable to find an error in it, which is very different from believing there are no errors in it

[winter bear]

gomez trolled u

[jovial hemlock]

wdym

[winter bear]

its an inside joke

but redirecting everyone to dami's pm is a joke lol

[wild zinc]

lol

[jovial hemlock]

oh

...but can he help me?

[winter bear]

lol

[jovial hemlock]

I mean I'm fine with being redirected to his PM if he can help I suppose

[winter bear]

he'll likely just umm be annoyed by it, hes busy

[jovial hemlock]

but if not I'd prefer not to be just waiting

oh

do you have any um, better ways I could get it looked at?

[winter bear]

i mean, not really

[wild zinc]

if you rewrite it with proper typesetting I'll have a look at it for you

[jovial hemlock]

you mean in LaTeX?

[wild zinc]

yeah

like

[jovial hemlock]

I already did rewrite it in LaTeX

[wild zinc]

good latex]

[jovial hemlock]

well

I'll PM it to you

and you'll tell me if it's good or bad okay?

[wild zinc]

I have one open

[jovial hemlock]

I sent you the most recent one

Thank you

[wild zinc]

oh, I didn't see the second one

[dry sorrel]

hey @jovial hemlock the pdf you posted like WAAAAAAY earlier, is that the correct one?

[jovial hemlock]

um

no

[dry sorrel]

aw

[fervent crest]

Bro....

John

Why did you spoil it

[jovial hemlock]

its okay dami already let meknow

[wild zinc]

without having read it properly

my guess is that it proves there are infinitely many numbers that don't have modular restrictions for being between twin primes

but I'll see when I've actually read it

[jovial hemlock]

that wouldn't be sufficient

to just prove that

[wild zinc]

yeah it wouldn't

[jovial hemlock]

it proves they don't have modular restrictions for any number below their own square root

[wild zinc]

that sounds dubious

[jovial hemlock]

not that every number does, just that there are infinitely many numbers like that

if I understand what you mean by "modular restrictions" anyway

[wild zinc]

what i mean is it just sounds far too strong

[jovial hemlock]

it isn't

[wild zinc]

to be true

[jovial hemlock]

what do you mean

that's literally the definition of a twin prime lol

that the number above and below it is prime

and a number is prime if it doesn't have any prime factors up to its own square root

[wild zinc]

well I mean you said "chinese remainder theorem" in it

so my guess before reading is that like

[jovial hemlock]

yeah, because rather than look at the primes themselves, I'm looking at the number between them

[wild zinc]

you get some bound modulo p_1p_2...p_k

[jovial hemlock]

and just saying that that number can't be one above a multiple of a prime or one below a multiple of a prime

[wild zinc]

that there are x many numbers N below p_1p_2...p_k such that N-1 and N+1 are not divisible by any of the p_i

[jovial hemlock]

?

that's not quite what I'm trying to prove

[wild zinc]

I know

but I don't think this approach can work

[jovial hemlock]

why not?

[wild zinc]

because p_1p_2...p_k grows too quickly

it's exponential

[jovial hemlock]

right

[wild zinc]

idk

I'll see when I read more

part 1.2 makes it seem like you only need the existence of a prime between p_1p_2...p_k and p_1p_2...p_{k+1}

[jovial hemlock]

um

let me see where you mean?

[wild zinc]

this is true but it's a bad sign for the proof being correct

[jovial hemlock]

I eventually show that from each value of K, a twin prime can be derived that is at least as big as K

however, K itself is not necessarily a twin prime, nor is actually any direct multiple of that specific K

[wild zinc]

you mean

you show for each value of K mod p_1p_2...p_k there exists a number N such that N is between two twin primes, and N = K (mod p_1p_2...p_k)?

[jovial hemlock]

no

I show that for each value of K mod p_1p_2...p_k there exists a number N such that it's between two twin primes and is Z mod p_1p_2...p_k...p_z

[dawn warren]

@wild zinc are u still here?

[wild zinc]

hi

I show that for each value of K mod p_1p_2...p_k there exists a number N such that it's between two twin primes and is Z mod p_1p_2...p_k...p_z
@jovial hemlock what does this even mean

[jovial hemlock]

that from each K mod p_1...p_k

[dry sorrel]

but what is Z

[wild zinc]

what is Z, what is z?

[jovial hemlock]

a number bigger than K

in this case

[dry sorrel]

hmm

[jovial hemlock]

again this is assuming I did it right and I probably made a mistake I'm missing somewhere

[wild zinc]

it seems very likely

[dry sorrel]

I think I'm missing something in 1.2 maybe

[wild zinc]

I'm not sure what the role of K taking a particular value mod p_1p_2...p_k is

[jovial hemlock]

it gets used later down the line

you use K to define Z

[dry sorrel]

yeah I saw that

[wild zinc]

oh, okay

Z is more specific than just "a number bigger than K"?

[jovial hemlock]

yeah

[wild zinc]

okay

I'll keep reading

[jovial hemlock]

it's a number derived from K and the later part of the proof shows how

[dawn warren]

oml the notation kills me

[dry sorrel]

So the basic outline of the proof is that you show that there are infinite K and for every K there is a twin prime centre right?

[jovial hemlock]

yes

[dry sorrel]

hmm

[wild zinc]

do you agree that the mod Q is unimportant?

like N = K (mod Q) and K < P^2 is the same as K = N

[jovial hemlock]

well yeah but that's sort of the point

it's just stating that

because the eventual idea is to be increasing Q and changing K until eventually K goes below P^2

[wild zinc]

why do you keep changing letters all the time

to mean essentially the same thing

[jovial hemlock]

because when working earlier, I accidentally made a circular definition by doing that and I'm trying to avoid that

[wild zinc]

it makes it like impossible to read

[jovial hemlock]

I'm trying to avoid doing something like "If a number N is a twin prime it must have these properties" and then accidentally assuming N exists

[dry sorrel]

true

[jovial hemlock]

and then using that to prove N exists

though really I mostly just change from K/Q to Y/X because K/Q was the general case whereas I wanted an easier way to increment it for Y/X for clarity

[wild zinc]

this would be fine if you also then defined your variables

[jovial hemlock]

wdym

what variable do I not define

[wild zinc]

like at some points N is general and some points it's specific etc.

[jovial hemlock]

no

N is always the same thing it was when defined at the start, except replace alpha with the largest prime in the group you're dealing with

[wild zinc]

M is not defined at all

[jovial hemlock]

M is

M is not defined

[dry sorrel]

M is defined tho

[jovial hemlock]

I messed that up

it's not explicitly defined but I thought it was fairly well implicitly defined

but you're right I should have explicitly defined it

[wild zinc]

yeah I can tell what it is but in general this is written very unclearly

[jovial hemlock]

sorry

I'm new to this

[wild zinc]

oh

I remembered what my complaint about N was

the possible values of N depend on what primes p_1p_2...p_k you're using

[jovial hemlock]

correct

[wild zinc]

but the same letter is used for them all

[jovial hemlock]

um, also correct

I should have used N_G or something like that

[wild zinc]

that works

[jovial hemlock]

but I think you can generally tell when N changes

[wild zinc]

it's like not too bad on its own but combining it with the switching of letters all the time

I need to mentally transfer like "okay which of these things do I need to remember about R,S,C,Z,etc."

every time you change letter

[jovial hemlock]

sorry about that

[wild zinc]

yeah nw, I'm just letting you know for general writing of maths purposes

[jovial hemlock]

yeah, no that's fine so I can do better in the future if I try to write anything up in the future

[wild zinc]

this is how I've written out section 1

[jovial hemlock]

I don't know what a lot of those symbols mean

to be honest

[dry sorrel]

me too

[jovial hemlock]

Is the one that's like a rectangle the product sigma?

like sigma for multiplication?

[wild zinc]

it's a capital pi

[dry sorrel]

what's the upside down A

[wild zinc]

but yes that's how it works

[jovial hemlock]

and what's the upside down A sorry

[wild zinc]

upside down A is "for all"

[jovial hemlock]

okay

[dry sorrel]

k

[wild zinc]

actually hang on I spotted a typo oops

[jovial hemlock]

where are you at reading-wise in my thing?

[dry sorrel]

at 2.1

[wild zinc]

yeah trying to get through the letters in 2.1/2.2

[jovial hemlock]

I'm switching to my phone now so I can eat something, may be a bit harder for me to respond

[dry sorrel]

2.2 is has lots of letters I'll check it tomorrow

[wild zinc]

I need to get up and do work now

so if you could rewrite in a way that's more readable and send it my way some time that'd be great, I'll finish reading it

[dreamy rain]

this is a bit of a big ask but can someone explain how youd prove the conjecture in part b? to save time, the conjecture is that only c=1,2,4,7 wouldnt work

i have a written solution, but i cant for the life of me, fully understand it

i can send it if that helps though

[sacred junco]

chicken mcnugget theorem @dreamy rain

the greatest positive integer that cannot be written as a positive combination of 3 and 5 is 7

and 1-6 can be reasoned through the same way as (a)

https://artofproblemsolving.com/wiki/index.php/Chicken_McNugget_Theorem

[dreamy rain]

thank youuuuu

why on earth is it called chicken mcnugget theorem LOL

[sacred junco]

I think the inspiration for the theorem was to find out the largest number of chicken nuggets that couldn't be bought from mcdonalds

[dreamy rain]

oh damb

[sacred junco]

oh yea it's on that page

[supple furnace]

Here’s a proof of the duality theorem:
Firstly, suppose k is representable as ax+by. Then if ab-a-b-k is representable as ax’+by’, we get ab-a-b=a(x+x’)+b(y+y’), contradiction.
Secondly, suppose k is not representable. Because (a,b)=1, there exist residues x,y such that ax=k mod b and by=k mod a. In addition, ax+by is at most 2ab-a-b, so if k is not equal to ax+by, then ab+k is. But then a(b-1-x)+b(a-1-y)=2ab-a-b-(ax+by)=ab-a-b-k, as desired.

[hollow basalt]

try asking @glad nacelle , he should be able to help you @sacred junco

[light flicker]

What have you tried?

[stuck lintel]

isnt this codeforces div 4 problem C?

there's a tutorial for this problem i think

[solid minnow]

i think this is the correct channel, need help with D in this problem

[burnt swallow]

Is anyone good at cryptography? Writing some short essays on the following questions, but I have a hard time understanding the theory behind it:

First question: Is it possible to have two distinct linear ciphers C ≡ a(1) P + b(2) (mod n), C ≡ a_(2) P + b_2 (mod n)

that send every plaintext letter to the same ciphertext letter? If you

Second question: If you modified the RSA procedure so that you encrypted each block of digits twice (that is, you raise a block of digits to the kth power modulo n, and then raise the resulting answer to the kth power modulo n yet again), will this result in a valid cipher? If so, how would you decrypt the encrypted message?

[wild zinc]

if I'm remembering RSA correctly this is exactly the same as doing it once

you just get a different result

i.e. you square the public key (which will still be coprime to phi(n))

like the decryption is the same and the security is the same

[sharp pagoda]

@sacred junco
n,2n,3n,...,tn are multiples of n less than or equal to tn
these are t numbers
and total numbers are tn
if you want to find "numbers not multiple of n" you need to subtract numbers multiple of n from total number
so tn-t=t(n-1)

also specify if 0 included or not

[sacred junco]

can anyone give me a hint for 2 part b?

[sacred junco]

use a)

[leaden compass]

@cerulean plover Do you know what Z/9Z is for example

[cerulean plover]

I know what Z is... and I know what \ stands for but not /

Except it means divide which wouldn't make sense tho

[leaden compass]

\ is setminus and / is usually quotient

So here's the thing

It is basically divisiom

But how do you make such an operation work in a similar sense to / for numbers, but for rings

Well you do it by considering equivalence classes

Here's what I mean

When you take Z/9Z, the elements of this guy are equivalence classes of 9Z in Z by the equivalence relation of x~y iff x-y in 9Z

Do you understand all these terms so far

[cerulean plover]

Ehm

Not really :/ sorry

[leaden compass]

Can you list the terms you haven't seen yet

[cerulean plover]

Equivalence class

[winter bear]

PSA: dont use \ for setminus pls, use -

[leaden compass]

Do you know what an equivalence relation is

[cerulean plover]

Yeah isnt it = for example

[leaden compass]

An equivalence relation is just a binary relation that is reflexive, symmetric, and transitive

But yes

The standard = is one for example

So reflexive means a ~ a, anything is equivalent to itself

Symmetric means a~b implies b~a

Ok for example ~ defined by "likes" is neither reflexive nor symmetric on the set of all people

(sadly)

[cerulean plover]

And transitive means a~b and b~c implies a~c right?

[leaden compass]

You ~ You is not true in many cases

Yes

You ~ Them doesn't imply Them ~ You

[cerulean plover]

So those are examples for cases that are not equivalence relations

[leaden compass]

Yes

[cerulean plover]

Ok I follow so far :)

[leaden compass]

You can also take ~ to be "likes spicier food than"

This is not reflexive, not symmetric, but it is transitive

[cerulean plover]

Right

[leaden compass]

So anyways those aren't equivalence relations

But something like triangle similarity is

~ by "is similar to" on the set of triangles

Right

[cerulean plover]

Yes

[leaden compass]

Ok so the cool thing about equivalence relations is that they partition sets— a partition of a set is just a disjoint set of subsets that unioned, give the set

Like for example define the equivalence relation a ~ b by a-b is an integer

On the set of real numbers R

Then for example 2 + pi ~ 55 + pi

And the partition induced by this relation is just, the subsets are Z + r for every r in [0, 1)

Right

Like Z + pi is an equivalence class

An equivalence class is a subset where all elements are equivalent to each other

Z+pi just means {... -1+pi, pi, 1+pi,...}

Okay so far?

[cerulean plover]

How is Z + pi an equivalence class?

[leaden compass]

Because it's elements are of the form a + pi for a an integer

So if you have a + pi, b + pi, then a-b is an integer right

So they're equivalent

[cerulean plover]

So an equivalence class is a group of numbers that kind of bridges a set to another set so it can match the equivalence relation?

Or wait I'm confused by this one > And the partition induced by this relation is just, the subsets are Z + r for every r in [0, 1)
@leaden compass

[leaden compass]

Well it's more general than that— consider the equivalence relation ~ by triangle similarity like I said before

The equivalence classes are just subsets of the set of all triangles

Where any two triangles are similar in the same equivalence class

[cerulean plover]

Oh ok so everything can be in the equivalence class as long as it is in the big set

And fulfills the relation

I think I got it but what do you need that for?

@leaden compass still here?

[leaden compass]

back

Note that "fulfilling the relation" is always with respect to another element

it's a binary relation

So anyways let's go back to my example of the real numbers and the equivalence relation ~ by x ~ y iff x-y is in Z

Now let's take some random dude in R

e

what's the equivalence class of e

Well 1 + e ~ e

since (1 + e) - e = 1 in Z

and 2 + e ~ e

etc

so basically n + e for any integer n

will be in the equivalence class of e

Here's another notion: a representative of an equivalence class

it's just a random dude in an equivalence class

but like, going back to our equivalence classes here

so it's clear that the equivalence class of e under this relation

is Z + e

Right?

@cerulean plover

[cerulean plover]

Yeah

I follow

[leaden compass]

So yeah, and for any real number r, Z + r is its equivalence class

So anyways how does this partition R?

Well for any r in [0, 1), and I restrict to [0, 1) because the equivalence class of e is the same as that of e-2 right

(And I want to have disjoint subsets)

(That's what a partition means)

So like let's just denote by E_r the equivalence class of r under ~

[cerulean plover]

Disjoint means like seperated?

[leaden compass]

Yep

{1, 2, 3} and {2, 3, 4} are not disjoint

but {1,2} and {3, 4} are

[cerulean plover]

Right

[leaden compass]

So anyways the partition is the set of E_r for r in [0, 1)

To check it's a partition you just need to make sure that

all of them are disjoint

[cerulean plover]

What's E_r

[leaden compass]

and that when you union them you get back the whole set

I just defined the notation E_r to be the equivalence class of r under ~

so E_r = Z + r

[cerulean plover]

Oh ok sorry got it now

[leaden compass]

Right so let's check it's a partition

the set of E_r for r in [0, 1)

So when we take the union of all of these subsets

We get back R right

[cerulean plover]

Yeah

[leaden compass]

yeah just visualize it as

Z but shifted by a real number amount

Like

. . . . . . . . .
. . . . . . . . .
. . . . . . . . .

etc

when you union those you get back R

Ok cool

Now are they disjoint

i.e. what is the intersection of E_a and E_b if a =/= b

it's empty

Right

[cerulean plover]

Yeah think I got it

[leaden compass]

Right

So remember that this is why I restricted r to [0, 1)

Since E_(e+1) intersect E_(e) is not empty

even though e+1 =/= e

(in fact E_(e+1) = E_e

Ok?

[cerulean plover]

Yep I follow

[leaden compass]

So anyways let's go back to what we really want

a ~ b if and only if a-b in 9Z

9Z just means {-9, 0, 9, ...}

it's Z multiplied by 9

So basically this is just

a~b iff 9 divides a-b

Right

Since a-b in 9Z means a-b = 9m for some m

Ok?

[cerulean plover]

Yes

[leaden compass]

Right so what does the partition of Z look like

What's the equivalence class of 0

[cerulean plover]

0+n ?

[leaden compass]

0 ~ a means 0 - a in 9Z

[cerulean plover]

0 + 10a ?

[leaden compass]

This isn't a set first of all

an equivalence class is a set

Can you tell me one number that is equivalent to 0

under this relation

[cerulean plover]

9

[leaden compass]

And -9

also 18

right

basically any multiple of 9

....and this set is just 9Z

Right?

[cerulean plover]

Yeah

[leaden compass]

Ok

What's the equivalence class of 1

[cerulean plover]

I'm still working on getting used to the term equivalence class

[leaden compass]

Yeah it's ok

It's just a set where all the elements are equivalent to each other

[cerulean plover]

1 + n?

[leaden compass]

For what n

1 + 2 is not equivalent to 1 for example

[cerulean plover]

Wow I am noticing that I have no clue

[leaden compass]

it just takes practice

remember

1 ~ a iff 1 - a in 9Z

[cerulean plover]

I'm so sorry for being so dumb although you're trying so hard 😭

[leaden compass]

dwai it just takes practice

so can you tell me some numbers equivalent to 1

Well 9+1 ~ 1 for sure

Right

Also 9*2 + 1

And 9*1243324124 + 1

So basically numbers of what form are equivalent to 1?

[cerulean plover]

So just 9n + 1

[leaden compass]

Yes

we denote this by 9Z + 1

= {...,-18+1, -9+1, 0+1, 9+1, 18+1...}

[cerulean plover]

Ok

[leaden compass]

So this is an equivalence class

Because if you have two guys of the form 9n + 1, 9m + 1

then (9n+1) - (9m+1) = 9(n-m)

which is in 9Z

Now how about the equivalence class of 2

[cerulean plover]

Ohhh ok just clicked in my head

[leaden compass]

Yeah

[cerulean plover]

Should be the same right? 2 + 9n

[leaden compass]

Yup

Notated as 9Z + 2

Also the notation [a] is fairly common, the equivalence class of a

Where a is just any element of the equivalence class, a representative

Usually we pick simple as though

Like I would say [2] instead of [9*123412431234 + 2]

(although these are the same)

So [2] = 9Z + 2

[1] = 9Z + 1

[cerulean plover]

When Z = 0 right

Wow I didnt think of 0

[leaden compass]

No Z is the set of integers

[a] is a set

it's an equivalence class

9Z + 1 is a set, an equivalence class

it's the equivalence class of 1

[cerulean plover]

Oh wow sorry

[leaden compass]

it's ok

[cerulean plover]

Ok I'm back on track

[leaden compass]

So [3] is what?

[cerulean plover]

An equivalence class? Of 9Z +3

[leaden compass]

Yes, it's the equivalence class of 3

and it is 9Z + 3

Since any guy in 9Z + 3 is equivalent to 3

Since they would be of the form 9m + 3

And (9m+3) - (3) = 9m in 9Z

[cerulean plover]

Right

[leaden compass]

Anyways, [4] is what

[cerulean plover]

Equivalence class of 4

Because 9Z + 4 is equivalent to all form of 9n + 4?

Including 4 itself

[leaden compass]

9Z + 4 is [4]

4 is equivalent to anyone in 9Z + 4

Ok so anyways you get it right

[5] is the equivalence class of 5 under this relation

it's just 9Z + 5

[6] is 9Z + 6

[7] is 9Z+ 7

[8] is 9Z + *

8*

Oh also [0] is 9Z right

So anyways can you tell me what [9] is

[cerulean plover]

9Z + 9

So it's kind of all about finding this 9Z + n relation

[leaden compass]

9Z + 9 is just 9Z though right

[cerulean plover]

Oh lol right

[leaden compass]

like that one is {..., 0, 9, 18, 27,..} and the other is {..., -9, 0, 9, 18,...}

but it's just the same

So anyways

The partition is, the set of [n] for 0 <= n <= 8

let's check that this is a partition

So {9Z, 9Z + 1, ..., 9Z + 8} is our partition

Now if we union all of these guys

we get back Z for sure right

[cerulean plover]

What does "getting back Z" mean?

[leaden compass]

Ah I just informally am meaning that $\bigcup_{n=0}^{8}9\bZ + n = \bZ$

oops

[sterile pumice]

Archsys:

[leaden compass]

This is true right

[cerulean plover]

Oh yeah I get it

[leaden compass]

I mean yeah, any integer can be expressed as like 9q + r

just divide by 9 and take the remainder

So it will belong to the equivalence class [r]

Right?

[cerulean plover]

Yeah

[leaden compass]

Ok they are definitely disjoint

9Z + a \cap 9Z + b have no elements in common if a=/=b

For 0 <= a, b <= 8 of course

Since again 9Z + 0 \cap 9Z + 9 is not empty

even though 0 =/= 9

Right?

[cerulean plover]

What's cap

[leaden compass]

$\cap$

[sterile pumice]

Archsys:

[leaden compass]

intersection

$\cup$

union

[sterile pumice]

Archsys:

[cerulean plover]

Oh

[leaden compass]

Right so their intersection is empty

Like [a] cap [b] is empty when a=/=b and 0 <= a,b <= 8

Right

[cerulean plover]

Yes

[leaden compass]

Ok so it's a partition

{9Z, 9Z + 1, ..., 9Z + 8} is a partition of Z

just like, your living room, bedroom etc partition your apartment

they are disjoint (unless studio apartment but wtv)

and the union of them is your whole apartment

[cerulean plover]

9Z +1 and 9Z + 10 are same right?

[leaden compass]

Yes

That's why we restrict [n] to 0 <= n <= 8

[cerulean plover]

Yeah just making sure

[leaden compass]

So anyways your original question was

https://cdn.discordapp.com/attachments/540211747613704221/709127663595552848/20200510_214000.jpg

Right so what is Z/9Z

How do we make sense of division in this context

Well we consider equivalence classes

The elements of Z/9Z are equivalence classes

[cerulean plover]

"mit" means with just in case you are wondering

[leaden compass]

Ok

[cerulean plover]

So you can ignore that

So here it means that 9x = Z

[leaden compass]

Yeah anyways F_17 is, it means it's a field

The F is for field

you might see F_p instead of Z/pZ or vice versa

when p is prime

I won't get into why for now

[cerulean plover]

Ok so the one on top means 17x = Z ?

[leaden compass]

Hmm I'm not sure what you mean

Let's start with Z/9Z

[cerulean plover]

Element of*

[leaden compass]

This is a ring— a ring is an algebraic structure consisting of a set and two binary operations +, x satisfying some axioms

hmm do you know what a group is

[cerulean plover]

Is it not the same as a set

[leaden compass]

uhh no it comes with a set and binary operations

a group is a set and just one binary operation

on the set

this means it's an operation *: GxG -> G

[cerulean plover]

Oh yeah I have it in front of me just didnt really understand what it said

[leaden compass]

Well so a group is a set coupled with a binary operation satisfying some axioms

First of all a binary operation is just one that takes two elements of the group and gives you another element of the group

For example consider the group with set Z and operation +

So like 1 + 2 = 3

3 is another element of the group (Z, +)

[cerulean plover]

Ohhh

[leaden compass]

Here I'm denoting a group by (G, *)

because a group is two pieces of information as I said

a set and an operation

but often you will see the ( , +) dropped

and just G

But you should understand that groups are not sets

they are sets coupled with binary operations

[cerulean plover]

Ok I understand now

[leaden compass]

Ok so the operation must satisfy some axioms

1. Closure (This means a*b in G, but this is part of the definition of a binary operation)

But just remember

Anyways

2. Associativity: (ab)c = a(bc)

Um here I am denoting a*b by ab

just for convenience

this is very common

Ok

?

[cerulean plover]

Ok yep got it

[leaden compass]

So (Z, +) is doing pretty good so far

closure, yep, associaty, yes since (a + b) + c = a + (b + c)

associativity*

Ok?

[cerulean plover]

Yes

[leaden compass]

The next thing is an identity

This is an element e of the group such that ae = ea = a

for any a in G

Hmmm so in our case

(Z, +)

Who's the identity?

a + e = e + a = a

What is e

[cerulean plover]

0?

[leaden compass]

Yep

The identity is just the guy that, when you take the binary operation with them and anyone else, you get back the other person

So just 0 here for (Z, +)

And the final axiom is

Inverses

Any element a in G must have an inverse a^-1

in G

Such that aa^-1 = a^-1a = e

Where e is the identity

So let's see

For (Z, +)

a + a^-1 = a^-1 + a = 0

Since 0 = e in our case

What is a^-1

[cerulean plover]

1/a

[leaden compass]

Nope

^-1 is just notation

it doesn't mean 1/a

it just means "the inverse of a"

What is the inverse of a

For (Z, +)

[cerulean plover]

Oh

[leaden compass]

a + a^-1 = 0

[cerulean plover]

-a

[leaden compass]

yes

exactly

[cerulean plover]

Damn I didnt know that was a notation

[leaden compass]

the inverse of any integer under the + operation is just its negative self

Yeah it's common

I mean

Notation is just that

shorthand for meaning

[cerulean plover]

Doesn't that get confusing if its (G,*)

[leaden compass]

No

In fact if the operation is multiplication

Then the inverse is a^-1 as usual

1/a

Since the identity is 1 right

[cerulean plover]

Yeah

[leaden compass]

a1 = 1a = a

Oops

Discord interpreted the two * as italics

Ok anyways

[cerulean plover]

Oh lol

[leaden compass]

So here's another group

The group of permutations on {1, 2, 3}

Denoted by S_3

let's denote the elements of this group by (123)->(abc)

So it's a permutation where 1 goes to a, 2 goes to b, 3 goes to c

Now is this really a group?

Our binary operation is composition btw

For example (123)->(321) o (123)->(231) is just

1 goes to 2 goes to 2

(Start from the right)

Brb

[cerulean plover]

Ok

I'll be working on this

[leaden compass]

here's some more convenient notation @cerulean plover

Let's represent the element (123)->(321) as (13) for example

This means 1->3 and 3->1

and any left out map to themselves

2->2

Ok so for example the element (12) is just, it's the permutation of {1,2,3} where 1 goes to 2, 2 goes to 1, and 3 stays fixed

[cerulean plover]

Ok

[leaden compass]

Anyways what is (12) o (13) for example, here o is composition

So you start from the right

1-> 3 on the right

[cerulean plover]

And theres no , between?

[leaden compass]

and then 3->3 since it's left out

hm?

[cerulean plover]

Just (12) and not (1,2) ?

[leaden compass]

Yeah it's easier to write

just don't get confused

[cerulean plover]

Ok hope I wont

[leaden compass]

I'll space it

(1 2)

Anyways

What is (1 2) o (1 3) for example

So start on the right

1 goes to 3

now where does 3 go to

To itself, that's what (1 2) maps 3 to

since it's just left out

Um and what happens to 2 under this composite permutation

Well first we map it to itself

That is (1 3) maps it to itself

then (1 2) maps 2 to 1

[cerulean plover]

Right

[leaden compass]

And anyways the composite permutation

what does it do to 3

Well first it takes 3 to 1

then on the left 1 goes to 2

So in sum

The composite permutation maps 1 to 3, 2 to 1, 3 to 2

So we write it as (132)

Or (1 3 2)

Okay?

[cerulean plover]

Right got it

[leaden compass]

Right anyways so

Let's check it is a group

well the elements are really just functions from {1, 2, 3} to {1, 2, 3}

and our operation is function composition

which is, of course, associative

it's closed obviously

So is there an identity

Yeah just ()

the permutation that maps everything to itself

() o (a b c) = (a b c)

Since a-> b and then b->b on the left

and so forth

and (a b c) o () = (a b c) of course

@cerulean plover Okay so far?

[cerulean plover]

Yeah

[leaden compass]

Ok are there inverses?

Hmm well what's the inverse of (123) for example