elementary-number-theory

[errant otter]

[torn escarp]

there are about 3 separate cases I considered in order to funnel it into that

they're not too serious tbh

[sterile pumice]

_basudev

[static cedar]

Any idea ?

Pls ping me if you know anything

[static cedar]

That's means 10 | X

Is that leading somewhere?

[green quail]

d(100-n) is small, so try to check cases of 9(n-2) close to a multiple of 170

This problem is quite an annoying case check, old bmo1 was more like this

There are at most 90 cases for naive brute force

Therefore the problem is to just reduce the case checking

[static cedar]

Yes bmo1 2001

I funking hate case work dude

[barren garden]

waaaa i hate that i struggle so with even the most elementary number theory problems… they’re so freaking elegant i feel left out

can someone rec me a book with REALLY simple number theory exercises?

[errant otter]

but simple exercises only mean u ain't gonna learn and be challenged much

[barren garden]

well

i am challenged even by simple exercises

[quaint gate]

i have the exact same problem 😭

i did the ones in judson and rotman the first chapters lol

[grand umbra]

sorry for late response but.. It's actually quite easy I'm just dumb, here's my take (2 different approaches) $$$$

1. Check all the intervals
   $$ab \geq 0$$ and $$ab \leq 0$$
   So basically if a and b are of the same sign, or different sign
   For $ab \geq 0$, it's simple: $|a+b| = |a| + |b|, |a-b| \geq 0 \implies |a+b| + |a-b| \geq |a| + |b|$.
   For $ab \leq 0$, it's quite the same: $|a| + |b| = |a-b|, |a+b| \geq 0 \implies |a+b| + |a-b| \geq |a| + |b|$.
   $$$$
2. Just dig right in
   I don't know what it's called in your country, but in my country it's called the absolute value inequality, it states
   $$|a+b| \leq |a| + |b|$$, equality is achieve when a and b are of the same signs.
   Hence: $|a + b + a - b| \leq |a+b| + |a-b| \implies 2|a| \leq |a+b| + |a-b|$.
   Note: $|a-b|$ = $|b-a|$, so we do the same thing but for $|b-a|$ $$$$.
   Finally, $|a+b| + |a-b| \geq 2|a|$ and $|a+b| + |a-b| \geq 2|b|$, in other words: $2 \cdot |a+b| + |a-b| \geq 2|a| + 2|b| \implies |a+b| + |a-b| \geq |a| + |b|$.

[errant otter]

as for your pointer 2, we call it the triangle equality

[grand umbra]

oops messed up texit

[grand umbra]

oh rlly

like the $$|a+b| \leq |a| + |b|$$ you mean

[errant otter]

,w triangle inequality

[sterile pumice]

Results provided by WolframAlpha

Click here to refine your query online
Upgrade to WolframAlpha Pro!

Requested by kiameimon

Atom

[errant otter]

....

[grand umbra]

oh yeah it is

[errant otter]

THE STATEMENTS

ok but yes

[grand umbra]

k thanks

[sterile pumice]

Atom

[grand umbra]

oh my god ykw im gonna stop editing that

[open mist]

7 being coprime with ten, it generates the entirety of Z/10^2023 Z
Then you easily know its order

[open mist]

oh nvm, I had that property in mind for the additive group

we're looking for the number of elements in the multiplicative subgroup generated by 7

yes it divides phi(10^2023) = 10^2023 * 1/2 * 4/5

I think in general finding the order of an element is very hard, unless n is prime

[native monolith]

If $\pi^2$ is irrational then surely $\pi$ is irrational?

Contrapositive $\pi=\frac{a}{b}\Rightarrow \pi^2=\frac{a^2}{b^2}$

[sterile pumice]

Max

[still flare]

Yup

[torn escarp]

Silverman's A Friendly Introduction to Number Theory might be what you want, the exercises vary between easy but also some open ended questions

[barren garden]

wonderful, thank you

[jagged mauve]

@opal obsidian

[eternal shoal]

What

[errant otter]

ignore

spam pinger

[wheat tinsel]

You can do exercises from the AMC competition

https://artofproblemsolving.com/wiki/index.php/Category:Introductory_Number_Theory_Problems

[proper folio]

for Euler's totient function, why is this the case?

how do they get the $p^{k-1}$ term in that equation?

[sterile pumice]

Kalgar

[proper folio]

I am not seeing it

I can observe that they are crossing out mulitples of p

so are they saying that there are $p^{k-1}$ multiples of p from 0 up to $p^{k}-1$?

[sterile pumice]

Kalgar

[proper folio]

I don't see how

[patent acorn]

yep

the fact that it's a power of a prime isn't really relevant here, for any two numbers n and m there are n multiples of m up to nm

[proper folio]

is this supposed to be an obvious fact lol

I don't see

seems pretty unintuitive ...

[patent acorn]

wait hang on i'm getting mixed up about what n and m are, sorry

[glass verge]

Lol

[patent acorn]

the multiplies of m less than nm are 0m, 1m, 2m, 3m, 4m, ..., (n-2)m, (n-1)m

and 0, 1, 2, ..., n-2, n-1 is n numbers

[torn escarp]

yeah, since p^k is a multiple of p, it means exactly 1/p of them are divisible by p.

[proper folio]

Wait, why must the gcd always be positive?

[torn escarp]

is this based on a previous discussion or is this a new question

on its own, it really doesn't matter if you include -1 or not in the gcd, since -1 is an invertible integer

you could always divide it out or multiply it in without affecting the other integer divisors

[proper folio]

new

[torn escarp]

every positive number n could be rewritten as (-1)(-1)*n to make it appear to have -1 as a divisor, if that feels better to you too

[proper folio]

oh

so a negative number can never be the greatest divisor?

[still flare]

Yes.

[acoustic parrot]

Any help will be appreciated

[open mist]

1, c, 7c-8
So u2 | u3 is already a big constraint.
Then I guess going a bit further limits it to probably just one case where it actually works and for which you find a proof

Next term is 9(7c-8) - 15c = 48c - 72 = 24(2c-3) adds even more constraints, etc...

[torn escarp]

my preliminary guess is all divisors of c must be of the form +-1 mod 12

[proper folio]

Is a complete system of residues a powerset, or simply a set

i.e. are the set elements equivalence classes (sets) or only the equivalence class representatives themselves

[torn escarp]

sounds like you're using the term 'powerset' incorrectly, the powerset of A is the set of all subsets of A

I think I see what you're asking, is the set of residues a set of integers or is it a set of sets of elements of the same equivlance class

maybe your book or whatever cares about this, but in practice you can interchange between either thinking of your operations on the equivalence classes or just by using a single representative

for instance even + odd = odd, i.e. thinking of these as the operations on the equivalence classes, you could just as well just pick a representative from these sets and use that, 2+1=3 and replace 3 with 1 since they lie within the same equivalence class

[acoustic parrot]

How?

[torn escarp]

I don't think that original guess is worth thinking about anymore, at least I think this is probably better to pursue

[open mist]

How do you come up with this ?

Cause the first few terms immediately reduce it to 1 value

Then I didn't attempt to prove it for this one

[torn escarp]

I only looked at the first term u_3 and then after seeing that restricted it to 4 terms I didn't bother looking further than that

[torn escarp]

I came to this roughly 2 ways but I didn't think them through very far, I don't feel like they'd be helpful here to sigmascribe so I won't distract them with it

it's probably wrong too

[open mist]

||u4 further restricts it to 2, so that would make it not a solution, which is kinda sus||

||cause I think c=2 still holds after u6||

[torn escarp]

||unless I just programmed it wrong I have u_3=12 and u_4=98 for c=2, which doesn't work||

[open mist]

||u3 is clearly 7c-8 = 6 so ...||

||then u4 = 96 - 152 = 24||

[torn escarp]

Ah yep I forgot ^ is not exponentiation in python lol

[open mist]

Bitwise AND moment

[torn escarp]

when c=2, I think u_n=n!, I think we can probably confirm that by plug and chug

[errant otter]

coincidence? I think not

let's see...

[torn escarp]

yeah that works if you plug it into the recursive formula and work it out

just confirmed it

[open mist]

(2n+1)(n-1)! - (n^2-1)(n-2)!
= (n-1)!(2n+1 - (n+1)) = n!

[errant otter]

yey

[torn escarp]

nifty, I suppose if we wanted to be devious we could have made arbitrarily bad k-term recurrence relations by pulling n! apart

probably where this problem originated from originally

just some asshole cooked this idea up

[errant otter]

asshole 😭

[torn escarp]

take simple thing -> mess it up for no good reason -> slap "olympiad/competition problem on it" -> torture children

I think we could generalize this method of torture by taking any function we like, preferably one that already satisfies some other recurrence relation, then expanding it out and separating terms, adding and subtracting random junk, then removing the function we used and placing it with some random one with some free parameter

[errant otter]

why are you coming up with the torture mero

[torn escarp]

takes one to know one

[errant otter]

okay geez still tho we only know a few values which work for this

[torn escarp]

yeah, but as long as we're making a trapdoor we can take our time to try random stuff, if it's too difficult/annoying to confirm we can just pick something else

[proper folio]

Can someone please explain how they got gcd(a,q)=1?

in that case 3.

[open mist]

q is prime so otherwise gcd(a, q) = q

Then by Gauss's theorem gcd(a, pq) = pq

[proper folio]

What is gauss's theorem

[errant otter]

,w gauss theorem number theory

......

[proper folio]

Surely they're not expecting me to use a theorem that I haven't even heard of ... in the proof of a proposition right?

[patent acorn]

gcd(a, p) divides gcd(a, pq), because p divides pq

and the only positive integer that divides 1 is 1

[torn escarp]

ok help me test this new problem I just made.

For integers $c$, the sequence $u_n$ of integers is defined by $u_1=1$, $u_2=c$, and $u_n=-(n-1)u_{n-1}+nu_{n-2}+n^2$ for $n\ge 3$. For which values of $c$ does this sequence have the property that $\gcd(u_n,u_{n-1}) = n$ when $n \ne 2 \mod 4$?

[sterile pumice]

Merosity

[errant otter]

why me- aaaaaaaa fine

you devil

[torn escarp]

no idea how difficult this problem is for the record, I'm going to be attempting it myself, but I have a distinct solution in mind

I just don't know if it's unique or not

you know what I messed up on that gcd condition damn

should be the gcd is n when n is odd, n/2 when n is even

[errant otter]

😭

[torn escarp]

hopefully that's right now, I'm tired lol

[torn escarp]

ok I think I've effectively proven that it's unique

[errant otter]

WHAT

😭

[torn escarp]

actually I'm pretty sure the gcd condition is superfluous too

[errant otter]

I'm still trying to freaking write the code to compute the sequence ffs smth is WRONG WITH MYU COMPILER ISTG

[torn escarp]

but whatever, red herrings are nice

err, wait that doesn't make sense without that condition we'd just be able to put all values of c, jeez I'm tired w/e

[barren garden]

i picked up the silverman and will dig into it once i find the time, but if anyone else comes asking for a very simple introduction i just stumbled across this:

it is VERY simple

just what i need

[normal heart]

seeing it is by Weil makes me doubt

[barren garden]

well they were originally lecture notes from a course he gave in the university of chicago, and seeing the introduction he was mocking the target audience and was very much against these lecture notes being published at all haha

sounds more like him?

[tired jasper]

hey guys apologies if this is rude but Im stuck on a question in the probability -statistics channel if anyone has a moment to help me, only asking because I noticed this channel was active and im in a rush

[errant otter]

is this a uni library?

[errant otter]

still working this sht out

[barren garden]

aye

they’ve a wonderful collection

[errant otter]

ah ic pog

[barren garden]

honestly i can’t get over how big it is

and i still i always ask for more

admittedly, brainlessly

hedonistically, mwahaha

[errant otter]

[errant otter]

so

[barren garden]

i’m sure i could phrase that more erotically if i wanted to without losing the originally intended, innocent interpretation

[eternal shoal]

What

[errant otter]

ok well c must be a multiple of 3 and odd

is that all?

[torn escarp]

no, just $\gcd(u_n,u_{n-1}) = n$ when $n$ is odd and $\gcd(u_n,u_{n-1}) = n/2$ when $n$ is even. no extra mod 4 conditions after that either

[sterile pumice]

Merosity

[errant otter]

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

ok

ah

where n is any integer?

[torn escarp]

yeah

[errant otter]

The sequence $u_n$ of integers is defined by $u_1=1$, $u_2=c$, and $u_n=-(n-1)u_{n-1}+nu_{n-2}+n^2$ for $n\ge 3$. For which values integer of $c$ does this sequence have the property that for every $n$, $\frac{\gcd(u_n,u_{n-1})}{2} = n$ when if the gcd is even and is equal to $n$ if it is odd?

[torn escarp]

no

not if the gcd is even, if n is even

[errant otter]

o h .

[sterile pumice]

Kiameimon | Welt Rene

[torn escarp]

wot

if n is even, then $\gcd(u_n,u_{n-1})=n/2$. If n is odd, then $\gcd(u_n,u_{n-1})=n$.

[sterile pumice]

Merosity

[errant otter]

😭

Me no comprehend

oh

wait

[torn escarp]

here, this is fool proof now: $\gcd(u_{2k},u_{2k-1})=k$ and $\gcd(u_{2k+1},u_{2k})=2k+1$

[sterile pumice]

Merosity

[torn escarp]

for all integers k

well, as long as u_n is defined for that value ofc

[sleek spire]

I'm having a brain fart here

why is $k(\floor{n/p^k} - \floor{n/p^{k+1}}) = \floor{n/p^k}$

[torn escarp]

who says it is?

take k=1 and the floor(n/p^k) parts drop off leaving floor(n/p^2)=0 which is false when n>=p^2

[sleek spire]

here's the full context

[still flare]

Telescoping sum

[sleek spire]

🤦

how did I not see that

thx

[acoustic parrot]

Has anybody done with my question?

[still flare]

Mate, we're not going to do it for you; people have given you ways to approach it so maybe you should look into those

[fringe tide]

what's the name of the subset S ⊆ Z^2 of coprime pairs

[barren garden]

S

[still flare]

The set of coprime pairs of integers

[minor orchid]

Does my proof work, and do I actually need the highlighted line to complete the proof?

[celest cloud]

yes its necessary so you dont have any overlaps which make the ei non even

[proper folio]

how do you prove this inverse statement

I am not familliar with the structure of a claim being "P => q1 OR q2 OR q3 OR ... OR qn"

do I do ... induction?

but I have a final case

n= m2-m1

[torn escarp]

I think it's annoying how they've written it, I'd rather write it as a=b mod m_1 and then a=b + c*m_1 mod m_2 then with c ranging from {0, 1, ..., m_2/m_1 - 1}

maybe it'd be a bit clearer if I defined d = m_2/m_1 so that you can see m_2 = d*m_1 and c ranges from {0, 1, 2, ..., d-1}

idk, maybe how they've written it is fine too, it's a matter of perspective/taste I suppose. The way they've written it makes it pretty clear that they're adding multiples of m_1 until eventually they run out, if they add another m_1 it will be m_2 which is the same as the first case which adds 0 mod m_2

hopefully this at least helps make it clearer what you're supposed to prove here

[proper folio]

Thanks!

btw, can such statements of the structure "P => q1 OR q2 OR q3 OR ... OR qn" mentioned above be proven directly?

where p and q_i are individual statements themselves

[torn escarp]

depends, it's sort of too generic of a question to answer

[proper folio]

ah ok

I thought there would be a general method that works most of the time

like with the "...then the following are equivalent" statements

where you prove q1 => q2 => q3=> q1 type thing

[torn escarp]

I guess I'd probably seek to try to find a common pattern among the q_i at least

to try to find some commonality to focus on rather than do each one individually if I could help it

[patent acorn]

...there's never really a "general method" to proving anything interesting

[loud maple]

What is the issue?

[loud maple]

Seems trivial enough

[acoustic parrot]

the prime factorization of m and n:m = p₁^a₁ * p₂^a₂ * ... * pₖ^aₖ n = q₁^b₁ * q₂^b₂ * ... * qₖ^bₖHere, p₁, p₂, ..., pₖ are distinct prime factors of m, and q₁, q₂, ..., qₖ are distinct prime factors of n.

Am I on right way?

let's consider the divisors of mn. Any divisor of mn can be written as d = p₁^x₁ * p₂^x₂ * ... * pₖ^xₖ * q₁^y₁ * q₂^y₂ * ... * qₖ^yₖ, where 0 ≤ xᵢ ≤ aᵢ and 0 ≤ yᵢ ≤ bᵢ for all i.

σₖ(mn) = Σ (p₁^x₁ * p₂^x₂ * ... * pₖ^xₖ * q₁^y₁ * q₂^y₂ * ... * qₖ^yₖ)^k

[echo light]

But you didn't finish the prove. Now you have to show its equal to sigma_k(m) *sigma_k(n)

[proper folio]

Wait

I just realised I did the profo werong

i can't use induction can i

since it's not true **for all **c

this is wrong right?

[acoustic parrot]

I know but am I on right way?

[echo light]

I mean yeah, you used and transcribe in mathematics all informations and this is always a good way to start. But it is not a waste of time to sometime try blindly a problem and make mistake, especially if the proof is not to long ( as in this case ).

[acoustic parrot]

we need to obtain terms like (p₁^x₁)^k * (q₁^y₁)^k and so on. These terms are present in both σₖ(m) and σₖ(n)
σₖ(m) * σₖ(n) corresponding to common prime factor

factors of m, we can write them as σₖ(m) = Σ (p₁^x₁ * p₂^x₂ * ... * pₖ^xₖ)^k

σₖ(n) = Σ (q₁^y₁ * q₂^y₂ * ... * qₖ^yₖ)^k.

Since the individual prime factors are raised to the power of k, these terms are multiplicative in nature. And since the prime factorizations of m and n are coprime, their corresponding terms in σₖ(m) and σₖ(n) are also coprime.Therefore, when we multiply σₖ(m) and σₖ(n) together, we get σₖ(m) * σₖ(n) = σₖ(mn), which proves that the function σₖ(n) is multiplicative for all real numbers k.

[acoustic parrot]

anybody is alive?

[verbal cedar]

i think it'd be easier to prove it for distinct primes sigmak(p^aq^b) and then you can do general m and n by induction

[sterile pumice]

nix (axler hater)

[acoustic parrot]

Thanks for the suggestion but please check my further work

[acoustic parrot]

This is right?

[verbal cedar]

that doesn't look right

[verbal cedar]

your work is hard to read and doesn't look like it's actually proving it. why is sum(p's and q's)=sum(p's)sum(q's)?

[acoustic parrot]

σₖ(n) (the sum of the k-th powers of divisors), we have:
σₖ(p^a * q^b) = 1 + (p * q)^k + (p * q)^(2k) + ... + (p * q)^(ak) + (p * q)^(k + k) + ... + (p * q)^(bk)
σₖ(p^a) * σₖ(q^b) = (1 + p^k + p^(2k) + ... + p^(ak)) * (1 + q^k + q^(2k) + ... + q^(bk))

Assume that σₖ(m) * σₖ(n) = σₖ(mn)
m = p₁^a₁ * p₂^a₂ * ... * pₖ^aₖ
n = q₁^b₁ * q₂^b₂ * ... * qₖ^bₖ.
By induction
σₖ(p^a) * σₖ(q^b) = σₖ(p^a * q^b)

[verbal cedar]

you still haven't shown that σₖ(p^a * q^b)=σₖ(p^a) * σₖ(q^b). and your σₖ(p^a * q^b) is missing a lot of terms. where is +p^k or +q^k?

as a hint, try to separate $\sigma_k(p^aq^b)$ in terms of the powers of $p$. so you have $p^0$(stuff with $q$'s)$+\ldots+p^a$(stuff with $q$'s)

[sterile pumice]

nix (axler hater)

[acoustic parrot]

σₖ(p^a * q^b) = p^0 (1 + q^k + q^(2k) + ... + q^(bk)) + p^k (1 + q^k + q^(2k) + ... + q^(bk)) + ... + p^(ak) (1 + q^k + q^(2k) + ... + q^(bk))Notice that the expression in each parenthesis is the sum of k-th powers of q^k, q^(2k), ..., q^(bk), which is σₖ(q^b).
Hence, we have:σₖ(p^a * q^b) = σₖ(q^b) + p^k * σₖ(q^b) + ... + p^(ak) * σₖ(q^b)
we have:σₖ(p^a) * σₖ(q^b) = p^0 * σₖ(q^b) + p^k * σₖ(q^b) + ... + p^(ak) * σₖ(q^b)

[verbal cedar]

are you using chatgpt

[verbal cedar]

lol i guess so. i thought it was odd putting so much effort into writing like σₖ and p₁^a₁, since that's not easy on a keyboard. but that's what you get if you copy chatgpt output

[acoustic parrot]

Nahhhhh

I swear

[calm summit]

Nope

[verbal cedar]

well. yeah. i got suspicious because there was a lot of writing/symbols with very little substance. that's what chatgpt does when it tries a hard proof. it just sort of flails around writing a lot of things that don't show what you need to show.

[verbal cedar]

this looks like they copied what i said into it, and then it tried to write something that sounds like it. this is the complete reverse of what i suggested. "assume sig(m)*sig(n)=sig(mn)" and then show that "sig(p^a)*sig(q^b)=sig(p^a q^b)"? that's silly.

if it isn't chatgpt well, then... that's very unfortunate. and i'd recommend they put more time into writing a better proof than using ascii to write math instead of latex.

[simple thorn]

I wonder why it’s ascii math…

[normal tangle]

wdym ascii math

[eternal shoal]

σₖ as opposed to \sigma_k

[normal tangle]

Do we consider variables like A as 65

[vast cliff]

#prealg-and-algebra message

Can anyone suggest any idea?

[eternal shoal]

huh

what is k

also x^2 \equiv 1 (mod p^1) should not have 2^(1+1) = 4 solutions for p prime??? It's a field: it has at most the degree of the polynomial (so in this case, it has at most 2)

[vast cliff]

Can you tell me 2here is this particular topic. I want to learn it@eternal shoal

They didn't describe what us K in the question

[verbal cedar]

https://media.discordapp.net/attachments/326138737606262786/1145083651550355496/IMG-20230826-WA0023.jpg

for reference

wtf is e in this question

did they mean n and it's a typo?

[verbal cedar]

probably some positive integer

[eternal shoal]

wtf is any of this question?

[verbal cedar]

right??

[eternal shoal]

Maybe I'm being obtuse, but I don't immediately see how CRT is relevent unless there's a fair bit of info missing

[verbal cedar]

is the CRT even applicable to this?

lol

[eternal shoal]

And even then... It just seems wrong?

whatever

[eternal shoal]

Don't worry too much about this question then. Seems pretty bogus to me

[verbal cedar]

but you can look into the Chinese remainder theorem, and maybe quadratic residues.

nvm quadratic residues is overkill

[verbal cedar]

perhaps it's like how many solutions are there to x=±1 mod p where p divides n

I suppose if you know the number of prime divisors...?

[eternal shoal]

Sure, if you know the prime decomp of n you could make an argument with CRT, that makes sense. We don't have that here

[vast cliff]

That's true

[verbal cedar]

@vast cliff do you have the rest of the solution to post

[vast cliff]

of course

[verbal cedar]

wh... what?? how can there be two solutions mod 1?? this is so wrong it's baffling.

[errant otter]

https://tenor.com/view/obi-wan-perhaps-the-archives-are-incomplete-impossible-star-wars-gif-14446376

[vast cliff]

I don't know what they are doing. I am totally confused with this question

I tried to learn it

[dusty dragon]

well, the equation x^2 = 1 (mod 2^k) has four (incongruent) solutions so something is definitely fishy here

[verbal cedar]

if p is an odd prime, x^2=1 mod p^k has exactly two solutions for all k≥1. if n=2 there is one solution, n=4 has two, and n=2^m for m≥3 has four solutions.

so it depends on how many unique prime divisors there are. it'd be a lil annoying to get a formula because of how wacky things are for even n. but the number of solutions will be a power of 2.

but as to how one is supposed to pick 2^k+2? that's just silly. there's no k even given in the problem. and there's still that random e≥3 like wtf

[wheat tinsel]

[eternal shoal]

Yeah taking p=2 this is extra fishy... Only, 2^k elements but 2^{k+1} solutions

[proper folio]

Prove: There are no integers b and c such that $7b^2-c^2=2$

[sterile pumice]

Kalgar

[proper folio]

Can I get some help please? My working so far:

[normal heart]

7b^2-c^2=0 is not equivalent to 2=-c^2 mod 7. It implies 2=-c^2 mod 7
Anyway, you can try all values of c mod 7 to see that there are no c such that 2=-c^2 mod 7

(alternatively use legendre symbols if you know that but if not nvm)

[verbal cedar]

$\legsym{-2}{p}=1\iff p\eq1,3\bmod{8}$

[sterile pumice]

nix (axler hater)

[verbal cedar]

if you can use that

[proper folio]

Where does the modulo 8 come from?

[verbal cedar]

quadratic nature of 2 and -1

[proper folio]

What does that mean lol

I am not familiar with quadratic residue

[verbal cedar]

look up the supplements to quadratic reciprocity

[proper folio]

Is this what they mean here too?

[verbal cedar]

no that's a different 8. though they probably pop up for similar reasons

[proper folio]

Why are they allowed to consider mod 8 in their example then

"As an alternative, consider modulo 8"

why is that allowed

[verbal cedar]

if two integers are equal, they should be congruent mod any integer

[verbal cedar]

I think from an application of Gauss' lemma
https://en.m.wikipedia.org/wiki/Gauss's_lemma_(number_theory)

yea see under "Applications"

this is just one of those number theory problems that you can either have a mildly long direct proof (from having to compute all the options) or basically a one line verification as long as you can use the quadratic nature formulas

these were all the ones my number theory prof let us use on exams

7 was too complicated lol

[torn escarp]

never heard of this 'quadratic nature' thing before

as long as you know how to derive them from quadratic reciprocity I guess it's just a handy shortcut table or something

for fun, try to see if you can work out the 'quadratic nature of q' table entry

[nocturne token]

I've seen them referred to as supplements to reciprocity before.

[dense valve]

I am trying to show that there exists some integer x where x is congruent to a mod n and gcd(x,n) = 1 iff for all integers x with x congruent to a mod n we have gcd(x,n) = 1.

I can do the <- direction but I need a hint on the other one. Maybe assume that d = gcd(x,n) but im not sure what that does for me.

maybe the contrapositive would help?

[west glade]

gcd(a,b)=gcd(a+bk,b) for all integers k

[dense valve]

i dont see how that helps me

[still flare]

Maybe you should spend some time thinking about it, because as it happens it is the key observation needed.

[dense valve]

I have been lol. d = gcd(x,n) = gcd(x,n + xk) implies there is integers a,b such that d = ax + b(n+xk) = ax + bn + bxk = x(a + bk) + bn

a + bk is an integer, say p, so xp is congruent to d mod n

[white lion]

Note that if a = b (mod n) then (a,n) = (b,n).

[white lion]

So since we have an integer x = a (mod n) such that (x, a) = 1, then lets suppose that l is an integer such that l = a (mod n). then we know that x = l (mod n) implies that (l,n) = (x,n) = 1.

[dense valve]

shouldn't it be (x,n) = 1? other than that I am following.

your hint also gives (a,n) = 1 since i am assuming (x,n) = 1 so i think thats where it comes from

[white lion]

You repeated the variable twice which is confusing, there exists an say x with that property, we want to show that for all integers (it could be different than x)

[white lion]

that could work also

[dense valve]

im lost on what to do. I dont know how to show that this will hold for all integers.

I want to use bezout but I dont know if thats the right direction

'[

[white lion]

I just proved it for all integers that are congurent to a mod n

[proper folio]

any tips?

I tried grinding it out directly with algebra but it didn't work

[still flare]

My dude you have been going through a whole buttload of stuff involving Z[sqrt(2)]

Maybe you should try using stuff you know about Z[sqrt(2)]

[sacred junco]

what does this question means?

[still flare]

[proper folio]

I have

but I don't think it's applicable here is it?

I don't have a unit in Z[√2]

[still flare]

I'm gonna spoil this wildly(!) and say yes, it is applicable.

[proper folio]

I tried my butt off

[proper folio]

where are my units!?!

I have a^2-2b^2 as a diff of two squares (a+b√2)(a-b√2)

[still flare]

Units are not relevant.

[proper folio]

but those aren't necessarily units, so I can't use the property of the norm N(x)=±1

[proper folio]

before we go, on could you at least tell me what "properties" I should be expected to know?

becuase I actually haven't taken an abstract algebra class yet

this is from number theory

in fact, this is all that the Q actually tells me

[still flare]

The question told you everything you need to know.

[proper folio]

$x\bar{x} y \bar{y}=\bar{x}\bar{y}xy=\overline{xy}xy$

[sterile pumice]

Kalgar

[proper folio]

$(a+b\sqrt{2})(c+d\sqrt{2})=ac+ad\sqrt{2}+bc\sqrt{2}+2bd=(ac+2bd)+(ad+bc)\sqrt{2} \in \mathbb{Z}[\sqrt{2}]$

[sterile pumice]

Kalgar

[proper folio]

Hence we can take $z=xy$

[sterile pumice]

Kalgar

[proper folio]

then $z\bar{z}=e^2-2f^2$ for $e,f\in\mathbb{Z}$ as req.

[sterile pumice]

Kalgar

[proper folio]

that ok? : D

[still flare]

Yup

[proper folio]

Thahnk so you much !

[stable peak]

Can you help me ?

Find all integers $n$ such that $$\prod_{k=0}^{n-1} (2k+1)+\sum_{k=1}^n (2k-1) +1$$ is a perfect square

[sterile pumice]

Joseph.P

[stable peak]

$$\prod_{k=0}^{n-1} (2k+1)+\sum_{k=1}^n (2k-1) +1=\dfrac{(2n)!}{2^nn!}+n^2+1$$

[sterile pumice]

Joseph.P

[stable peak]

So for me the only solution is n=3 but how do I prove it

[torn escarp]

simple observation, if n is even then it's congruent to 2 mod 4 which is never a square, so we can work under the assumption n is odd

pushing that a little bit further and looking at it mod 8, it'll be 3 mod 8 when n is 1 mod 4 and it will be 1 mod 8 when n is 3 mod 4, so we know now that n must be 3 mod 4.

I think there are some interesting things to say about that product of odd numbers mod 2^m in general, but I don't have time to look into it

[white lion]

that's saying every even number has the remander of 2 when divided by 4 which is not true 4k = 2(2k) is not congruent to 2 mod 4

[torn escarp]

I'm not sure if you're misunderstanding or agreeing with me, but whe n is even, then the expression is 2 mod 4 which is not a square

[eternal shoal]

I think merosity meant the expression, not n lol

[torn escarp]

I could be wrong, someone check, I'll be busy for a while tonight so can't check now

[white lion]

Oh my bad lol

[torn escarp]

unfortunately this is where the trail runs dry because once you have a number that's 1 mod 8, there's nothing stopping it from being a square mod 2^k for arbitrarily large k

so probably best to stop thinking about 2 to solve this problem I think

maybe some kind of quadratic reciprocity approach is what it needs

@stable peak where'd this problem come from

[stable peak]

I created it

So maybe it’s not possible

[torn escarp]

thought that might be the case

kinda smells like a variant of Brocard's problem

[stable peak]

What can I change that would make it possible

[torn escarp]

well it might still be possible

another approach might be to try to look at gaps between squares, unforutunately since the product grows too fast, we can't use n^2 as a kind of wedge

like if we were lucky we could have said something like, $$(n+1)^2-n^2 > \frac{(2n)!}{2^nn!}+1$$

[sterile pumice]

Merosity

[torn escarp]

and that would preclude it from hitting a square again, if this approach makes sense to you

maybe it can be fixed somehow

I think I'm being vague, so as an example problem if I asked you to find all the times n^2+5 is a perfect square, you could immediately see that once (n+1)^2 - n^2 > 5 we have that the gaps are just too large between consecutive squares to work

[stable peak]

Thanks

[silent rock]

@midnight walrus

If you're still around, I'm available for a little bit

[dusky aspen]

could anyone suggest any good resources on quadratic diophantine equations?

[silent rock]

General quadratic diophantine equations? ax^2 + bxy + cy^2 + dx + ey + f = 0

If so then I do not know. I do know how to solve equations in the form x^2 - ny^2 = 1 which is a Pell equation, and solved via continued fractions.

https://math.stackexchange.com/a/1041345

Seems to give a technique

If you have more than two variables, I really have no idea.

[midnight walrus]

Omnipotentenity

U free now?

[dusky aspen]

Thanks!

[silent rock]

Yw

[neon pumice]

HOW

[potent torrent]

FLT

[neon pumice]

how 2023 isn't prime

[potent torrent]

*Euler totient function

[neon pumice]

oh i thiink i get it, thanks

[whole bronze]

Why is it impossible for there to be integers such that

|b-a| = |c-b| = |d-c| = ... = |g-f| = |a-g|

[still flare]

Well that's not true, there do exist integers with that property

a = b = ... = g = 0

[whole bronze]

distinct sorry

the equation says to place k distinct integers around a table and take absolute differences with the right neighbor

probably some use of the triangle inequality

[still flare]

Hint: Fix delta = |b - a|. Then suppose b is greater than a. Then c cannot be equal to a, so where does this leave space for c?

[whole bronze]

oh I see

that's a nice way to think of it intuitively

but you have to use induction

on the number of variables

to actually prove it

I think

[white lion]

Im trying to prove if $p$ is prime and $ a^2 = 1$ (mod p) then $a = +/-1 $(mod p) , the proof is as follows, suppose $a^2 = 1$ (mod p) \implies $a^2 - 1 = pl$ for some $l \in \mathbb{Z}$ then $a^2 - 1^2 = pl$ \implies $(a - 1) (a + 1) = pl$ so since we have that $(a^2, p) = (1, p) =1$ it follows that $(a^2,p) = (a , p) = 1$ (this is obvious because if the prime $p$ does not show up in the canonical representation of $a^2$ then it clearly doesn't show up in $a$ hence they are relatively prime)

[sterile pumice]

jayz
Compile Error! Click the reaction for more information.
(You may edit your message to recompile.)

[white lion]

so there is a fact that states for $(a,b)$ if $b|c$ then $(a,b) = $ $(a + c, b)$. since we have that $p$ clearly does not divide 1 or -1 \implies $(a,p) = 1 \neq (a + 1, p) and (a,p) = 1 \neq (a - 1, p)$ there fore $(a + 1, p) = d$ and $(a - 1, p) = k$ such that $g,k > 1$ hence $p$ shows up in their canonical representations and hence $p|(a+1)$ and $p|(a-1)$ therefore $a = +/- 1$ (mod p) as needed.

[sterile pumice]

jayz
Compile Error! Click the reaction for more information.
(You may edit your message to recompile.)

[smoky plume]

does anyone know how to solve this problem? I simplified the expression to the following $$11(m^2 + 10m + 35)$$ and from there I just tried to find an m (by optimised trial and error) that gave a factor of 11 when substituted into the inside quadratic but that seems really inefficient, anybody got other tips?

https://media.discordapp.net/attachments/919118366864707634/1147475066049794098/image.png?width=1395&height=103

[sterile pumice]

CrazyCuber217

[torn escarp]

idk random idea,
(m+n)(n-m)=5(2m^2+22m+77)

[brave citrus]

Hi, i have a question: If i have two positive numbers a and b that a<b. Let M=a(a+1)..(b-1)b, how many pair of (x,y) (x,y>0, x,y in N*) that x,y is divisors of M and lcm(x,y)=M?

[torn escarp]

looks like we can break it down for each x|M, we can count the number of divisors y that divide M/x. I denote the number of divisors of n as tau(n):

$$\sum_{x|M}\sum_{y|\frac M x} \tau(y)$$

[sterile pumice]

Merosity

[torn escarp]

whoops I think I've written that wrong, should be
$$\sum_{x|M}\tau(\frac M x)$$ since for each $x|M$, there are $\tau(\frac M x)$ possbilities for what $y$ can be to satisfy the lcm condition

[sterile pumice]

Merosity

[torn escarp]

so long as that's correct, there's a fair bit we can go further than this but I don't want to rob you of the fun of working it all out

[brave citrus]

😳

[torn escarp]

you know what a multiplicative function is or dirichlet convolution?

[brave citrus]

sorry i dont know

[torn escarp]

how'd you come to this problem

[brave citrus]

i am solving a problem in competitive programming

its a math problem

[torn escarp]

so you're trying to get a computer to get the answer quickly for a single number or multiple numbers or what

[brave citrus]

than i came to this problem😳

[torn escarp]

what are you actually doing as your goal here

for the competitive programming problem

that changes what we are satisfied with saying "done" pretty substantially

[brave citrus]

😳

[torn escarp]

like this won't mean anything to you, but to me I was content saying the answer is: $$\prod_{p\le b}\frac{b-a+s_p(a)-s_p(b)}{2(p-1)}$$

[sterile pumice]

Merosity

[torn escarp]

like that gives us something that's gross to compute on a computer and not worth implementing in that form imo

[brave citrus]

Thank you, i just got a hint from that @torn escarp

[torn escarp]

I'd probably just stop at recognizing this is the number of ways to write M as a product of 3 numbers which is a multiplicative function and using the fact that prime factors will always be <= b will help us look at each individually should prevent us from computing large factorials which I assume is the issue

there's a good middle ground between these two

I would recommend learning about Dirichlet convolutions and multiplicative functions, you can probably find info about them online like brilliant.org or something like that @brave citrus

[brave citrus]

oh thanks

[torn escarp]

a multiplicative function satisfies f(mn)=f(m)f(n) when gcd(m,n)=1

lots of number theory functions have this property

it lets you focus on just how it behaves for powers of a prime

examples are: number of divisors function, sum of divisors function, euler phi function, and many more

[white lion]

where did you find this question?

[smoky plume]

it was a question for last year's IOQM exam

got it

should I explain?

[white lion]

What is the IOQM?

[white lion]

sure.

[smoky plume]

if you expand the expression you get 11(m^2 + 10 + 35) = n^2
m^2 + 10m + 35 has to be divisible by 11
m^2 - m + 2 has to be divisible by 11
Use trial and error to find m = 5 mod 11, 7 mod 11
from there I just did trial and error to get m = 18, n = 77, m + n = 95

[nocturne token]

Maybe try transforming it into Pell’s equation. You would be able to parametrize all integer solutions that way.

[smoky plume]

it's the indian version of the AMC, you qualify for the IMO via the IOQM series of exams

[nocturne token]

Probably not good for a contest problem though.

[smoky plume]

not familiar w pells equation, but i've seen some people use it as a solution for similar problems so it might be pretty viable

[nocturne token]

Oh that’s good. Still, my primary concern would be that the solution you care about corresponds to the fundamental solution, which would make Pell’s equation a pretty useless approach. Something to keep in mind as you learn about it / use it.

[quiet monolith]

Our framwork will be N^2. Let A=(x_1,x_2) , B=(y_1,y_2) in N^2 , instead of measuring in the usual way we will consider the distance d(A,B)=gcd(x_1-y_1, x_2-y_2).

Q1: Let ABC be the triangle of sides a=d(AB) , b=d(BC) and c=d(AC) , then gcd(a,b)|c , gcd(a,c)|b and gcd(b,c)|a.

Q2: Given a,b,c in N such that gcd(a,b)|c , gcd(a,c)|b and gcd(b,c)|a , then there exists a triangle with those sides.

[torn escarp]

What's your question, what have you tried so far

[quiet monolith]

I try to prove both statements. So far I have not thought much of it

[dusky nebula]

is anyone here familiar with mann's theorem? i am quite confused about the motivation behind some parts of his original proof (primarily the construction of additional sets, similarly for artin and scherk's proof)

[west glade]

just as a general note (I am not familiar with this theorem/proof): not everything is always "motivated". sometimes it's just the result of hours upon hours of work. and the only motivation is that it works

[dusky nebula]

fair enough, but honestly some parts of the proof just seem so out of the blue that i cant help but feel like im missing some critical insight

[errant otter]

Mmm, ik this is a programming problem but I wonder how I could involve a bit of NT trickery to write an efficient algorithm.
To state the problem, given 2 natural numbers a and b which are >= 1 and <= 10^9, find the smallest value of x+y such that (a+x) | (b+y), where x and y are both nonneg integers

[full atlas]

Can I get numerical methods help here?

[errant otter]

what sort of numerical method?

also,

[full atlas]

So
I have f(x)=2-x-ln(x)
I need to separate the roots and identity some [a,b] interval

I followed an example report, separated the function into
2-x=ln(x) and made the graph, found an intersection

It's not some easily identifiable number but whatever

What next?

If anything makes sense of what I wrote

[errant otter]

1. this doesn't require numerical methods. Simply set the function equals zero and solve for x.
2. #precalculus seems to be more appropriate for this

[full atlas]

It's a prerequisite

[errant otter]

#precalculus

[full atlas]

I found x it's not a problem

[nocturne token]

You don’t really need it but the number is W(e²) where W denotes the Lambert W function.

[dusky nebula]

do u think that (B+Y)/(A+X) must be either ceil(B/A) or floor(B/A)? i have a guess that it is like this but not sure how to prove

[full atlas]

Thanks but this will probably confuse me more or make no sense

For now

[errant otter]

Interesting... oh lemme provide some test cases to come up with hypothesis-es

A, B
11, 23 , output 2
8, 16 output 0
4394, 993298361 output 65
95392025, 569922442 output 2429708
8399283, 10293 output 8388990

[soft salmon]

hello

can you help me with a question

29

pls

[dusty light]

just count for d | n, how many k in {1,2,...,n} will satisfy gcd(k,n) = d

[junior swallow]

hello

my number theory is very bad

if gcd(a, b) = d does that imply that we can find integers x and y such that ax + by = d

ah

yes

[patent acorn]

https://en.wikipedia.org/wiki/Bézout's_identity

[junior swallow]

i need to take a number theory course what i learned in discrete i completely forgot my god

thank you

[dusty monolith]

hi all, does anyone have some general tips for problem solving in number theory

im in this advanced nt course, first year uni, and the hw questions are pretty hard. 5 possibly olympiad level problems

[sudden hemlock]

How does $b^3 = a^2 + 1 \implies \exists c, d \in \mathbb{N} ( b = c^2 + d^2)$

[still flare]

I think you need more context

[sudden hemlock]

We're working in Z[i], so I assume this is something to do with the norm N(b) = bb̅

[wheat tinsel]

If p divides b then -1 is a quadratic residue mod p

[sudden hemlock]

That holds in Z[i]? Also I don't see how that helps?

[wheat tinsel]

are a and b integers?

well

b must be an integer

is a an integer

if a is not an integer, and can be complex, then this is false

I think

wait nvm

a,b will be integers

well do you know fermats theorem? @sudden hemlock

[sudden hemlock]

fermat's little theorem?

[wheat tinsel]

no

there is a theorem that says when can an integer n be written as the sum of two squares

in this case, all the prime divisors of b are congruent to 1 mod 4

so you could show that an integer all whose prime factors are congruent to 1 mod 4 can be written as the sum of two squares

[sudden hemlock]

rip

[wheat tinsel]

I mean

you can find all solutions to y^3=x^2+1

that is probably easier, but I dont really see the point of the exercise

[sudden hemlock]

yeah, someone just said that when finding the solutions the thing I posted above was "obvious"

which ig, if you consider the theorem

[analog raptor]

can someone help me out with this? tau is the number of divisors (natural divisors)

i have noticed when you plug in n=p, p is prime, you get a prime p out

[still flare]

What is tau(n)?

[analog raptor]

that means that the set 4n/tau(n)^2 is infinite

[analog raptor]

number of natural divisors of n

if n=p1^a1*...*pk^ak

then tau(n) = (a1+1)...(ak+1)

tau(6)=4 bcs 1, 2, 3, 6 divide 6

[dusty dragon]

tau(p) is 2 since there are only two natural divisors of p: 1 and p. So tau(p)^2 = 4 which means 4p/(tau(p))^2 = 4p/4 = p

[analog raptor]

yeah

but that doesnt solve the problem

i mean the set of the numbers of the form 4n/tau(n)^2 is infinite

but that doesnt mean that the wanted set is finite

[placid condor]

could anyone help me get started with this problem, im not even sure where to begin

[torn escarp]

start by writing out some Hasse diagrams for simple numbers like 6, 7, and 8

see if you can figure out any patterns or what causes them and then make more examples to check and keep iterating on what you think is happening

[placid condor]

Am I drawing the diagram correctly for 8 and 9?

[eternal shoal]

yes

[placid condor]

I don’t see where the middle one comes up so far

[dusty dragon]

If the second one were to be the Hasse diagram representing the divisors of some integer N, then you can firstly observe that such an integer N must have two prime divisors (why?). Then think about what this tells you about the multiples of these primes

It might help to relate this back to the illustrations you’ve drawn up for each of the integers that you’ve come up with

eg 8 only has one prime divisor (2), 6 has two prime divisors (2, 3)

[wooden glen]

If the prime factorization of $n$ is $p_1^{\alpha_1}\cdots p_k^{\alpha_k}$ we know that $\tau(n) = (\alpha_1+1)\cdots(\alpha_k+1)$. So we're looking for numbers that can't be written in the form $$m=4\cdot\frac{p_1^{\alpha_1}}{(\alpha_1+1)^2}\cdots\frac{p_k^{\alpha_k}}{(\alpha_k+1)^2}.$$
We can immediately see that every odd prime factor in $m$ must come from $n$.
Furthermore, the only way to make one of the $\frac{p^\alpha}{(\alpha+1)^2}$ factors contribute less than 1 to the product is for $p=2$ and $p=3$. The smallest product we can get from this is $\frac{2}{4}\cdot\frac{3}{4}=\frac{3}{8}$.
(Edit: No, 4/9 · 3/4 = 1/3 is smaller -- but no matter, the important thing is that we can't get arbitrarily close to 0.)

[sterile pumice]

Troposphere

[torn escarp]

just for fun I computed powers of 2 that appear in the first 10^something in gp
for(n=1,10000000000, m=4*n/sigma(n,0)^2; if(isint(m)&&Mod(m,2)==0&&!isprime(m)&&isprimepower(m), print(n, " ", m)))

1 4
9 4
128 8
1152 8
8100 16
10000 64
32768 512
64800 32
90000 64
294912 512
320000 512
1679616 1024
2880000 512
4147200 512
6350400 256
9144576 1024
12960000 1024

interesting problem, reading your work now

[wooden glen]

I think I had a good argument that squares of large enough primes cannot arise as 4n/tau(n)² -- then I thought I saw a simpler way around it and deleted what I'd written before noticing that what I wanted to replace it with wouldn't quite work ... :-(

Rescuing from the deletion log.

Now let's look at $m=p^2$ for some large prime $p$. We must then have $p^2\mid n$. If $n$ contains more than two factors of $p$, its $\frac{p^\alpha}{(\alpha^p)}$ is already at least $p/16$ times as large as $m$, and when $p$ is large, there's no way the other contributions can cancel that out. (Not to mention the additional factor of $4$ in the expression for $m$).

[sterile pumice]

Troposphere

[wooden glen]

On the other hand, if $n$ contains exactly two factors of $p$, their contribution is $p^2/9$, so we need the contribution of other prime factors to cancel out $\frac{4}{9}$ -- or in other words, we must have $n=p^2b$ with $b/\tau(b)^2 = \frac{9}{4}$.
We can now do a somewhat sprawling analysis on the number of factors of $3$ in $b$, but I'm fairly sure the outcome is that this is impossible.
So all squares of sufficiently large primes are in your set: it is countably infinite.

[sterile pumice]

Troposphere

[wooden glen]

Oh! Instead of the sprawling case analysis, rewrite to $4b=9\tau(b)^2$ which implies that $b$ must be a square. But then $\tau(b)$ is odd, so $4b=9\tau(b)^2$ is impossible.

[sterile pumice]

Troposphere

[torn escarp]

oh niiiiice

ok I think I see, suppose m is an odd square, then tau(n)^2 m = 4n implies n is a square. Then this implies tau(n) is odd. But tau(n)^2 m can't be odd and a multiple of 4, contradiction. So all odd squares are not touched

[wooden glen]

Yeah, we don't need my initial musings about the particular formula for tau, or wanting squares of primes in particular.

[analog raptor]

thanks a lot guys

[fervent grove]

mm does one hit a positive natural density of naturals?

the only sets considered so far seem sparse in some way

[wooden glen]

How about the set of even numbers?

[still flare]

One channel is enough for your question

[jovial plinth]

Sorry i was not sure which channel to post to

[midnight river]

I don't know where to ask this so i feel this is the best place to ask

does the sum of the set of all real numbers equal 0?

[eternal shoal]

that is not a well defined notion, to sum all real numbers together

When we defined what an infinite sum is, 1) we usually consider only countable sums (indexed by integers or natural numbers typically) and 2) we must take some sort of limiting process for it to make sense. This is done by considering the limit of the sequence {a_0, a_0 + a_1, a_0 + a_1 + a_2, ...}, and defining it to be the sum of the sequence if the limit exists. You can't sum over all real numbers with this notion of infinite sum then

[midnight river]

Thanks!

[midnight river]

Other question, if you have an infinite set and remove an element from said set, does it maintain the same cardinality?

[still flare]

Yes

[midnight river]

how can i explain it to a dense reddit mf

he claims
"You cannot remove an item from an infinite set because infinity is not a value,"
"Infinity is a concept. It is not a countable number and it's not within the set of all real numbers. You cannot perform operations on it, and any that you do is merely a hypothetical. You cannot derive any conclusions from that."

[still flare]

The answer is to log off

Don’t bother with fools on the internet

[midnight river]

honestly based

brother claimed he had two mathmatics related degrees

[patent acorn]

i'm pretty sure they don't, and if they do i'm very impressed

[eternal shoal]

ultrafinitists

[patent acorn]

getting a mathematics degree both without understanding what an infinite set is, and without knowing how to acknowledge that you don't know the definition of a technical term instead of confidently making stuff up...?

[midnight river]

reddititis

[still flare]

Likely they are lying and simply trying to appear to have more credibility.

[midnight river]

other question
does the numbers between 2 and ∞ have the same sum as 1 and ∞

[patent acorn]

what's "∞"

[still flare]

There is no such value

There is no real that is the sum of 1, 2, 3, etc.

[midnight river]

exactly

thanks

[vestal pawn]

There is something interesting here though for the integers
The meaning is clear: one can group the integers st the series (0) + (1 + -1) + (2 + -2) + ... converges to 0
So presumably if we want to show that such a definition would be ill-defined, we want to come up with another grouping of Z that converges to a different sum

[eternal shoal]

That series does not converge to 0.
In fact, unless the series absolutely convergent, then rearranging the terms will, in general, change what the sum converges to

You can't "group the terms together" either

[vestal pawn]

ugh fine Ill do it formally
Define a grouping of a countably infinite set S to be a partition into countably infinite finite parts P_i,
and define p_i = sum(k for k in P_i). Then we say that the sum of S partially converges to x if the partial sums of the sequence (p_0, p_1,...) converges to x.
So Z partially converges to 0 under the grouping P_0 = {0}, P_1 = {1,-1}, P_2 = {2,-2}, ... . The question is if we can construct another grouping of Z that implies that Z partially converges to another number also, which will show that our definition of partial convergence is not unique and therefore not worth considering as a notion of convergence.

[distant stag]

Interesting ideas! I’m pretty sure there is no grouping that results in it converging to another number, but you can make groupings that cause it to diverge to infinity and to me it seems like that’s also an issue for this definition

[vestal pawn]

https://math.stackexchange.com/questions/3472833/the-sum-of-all-integers-is-equal-to
This answer provides an idea that shows how to construct rearrangements converging to other numbers

[white lion]

It’s a symbol with properties your probably already familiar with

[eternal shoal]

Well infinity is many concepts so it really matters what you actually mean when you write infinity

[patent acorn]

well i'm not familiar with them

[distant stag]

oh yes, cool! Thanks!

[prisma star]

So, this question was in an Algebra book but this feels more of NT so here it is -

Define $f : {0, 1, 2, ..., 10} \to {0, 1, 2, ..., 10}$ by $\$
$f(n) = (4n^2 - 3n^7)$mod 11 $\$
(i) show that $f$ is a permutation.

[sterile pumice]

numbily

[patent acorn]

the obvious thought is you could just check them all (there's only 11 numbers)
but if the question is interesting then i assume there's something quicker...? and i'm not sure what it would be

[prisma star]

Yeah that's exactly what I am thinking, is this just computational or is there some clever trick involved

[torn escarp]

I think this works, factor it as $f(n)=n^2(4-3n^\frac{11-1}{2}) = n^2(4-3 \left(\frac{n}{11}\right))$ here $ \left(\frac{n}{11}\right)$ is the legendre symbol. this means:

$f(n)=n^2$ when $n$ is a QR
$f(n)=7n^2$ when $n$ is a NR

since $11 \ne 1 \mod 4$ it means $-1$ is a NR and so $n$ and $-n$ are not both QRs. Further, $\left(\frac{7}{11}\right)=-1$. This proves f is an injection. Because this is a finite set, it's a bijection.

[sterile pumice]

Merosity

[torn escarp]

that formatted beautifully... lmao

[torn escarp]

for fun, we can generalize this to make permutations this way as, $$f(n)=\frac{d+1}{2}n^2-\frac{d-1}{2}n^\frac{p+3}{2} \mod p$$ with picking $p=3 \mod 4$ and $d$ a non residue mod $p$. Then the problem becomes a special case of picking $p=11$ with $d=7$.

[sterile pumice]

Merosity

[prisma star]

Bro, this was chapter 1, section 1 exercise in an Algebra book. No way I am supposed to use legendre polynomial, I should just use python or sage to compute it

Thanks for the interesting solution though

[torn escarp]

haha fair enough, was fun though

[west glade]

because I just saw something very similar by chance, do you perhaps have a reference to something about permutations of that form? or is this just something you wrote down now?

[torn escarp]

yeah, and afterwards I ended up deriving a more general version give me a min to type up my derivation

[sterile pumice]

Merosity

[west glade]

thank you

[torn escarp]

yeah I'd be interested to play around with this more myself, since it's kinda interesting

like what subset of permutations do we get from these, do these contain enough to always generate the full set of permutations?

I suppose it should be said this always fixes 0, so it might be worth trying to include that in too if we want

[torn escarp]

correction p=3 mod 4, since (-1 | p) = -1 is what we want

[west glade]

you are only switching the sets QR and NR so I can't imagine you generate all permutations

and inside those sets you basically only have linear permutations

[torn escarp]

yeah good point

[white lion]

Proof for Eulers-phi function

Using induction

Why is (4.3) that way? And why did we divide m by p_k+1?

[fallow zenith]

So if you're trying to show (\mathbb{Z}[\sqrt{d}]) where (d > 1) is squarefree rational has infinite units, I presume we're just stuck with Lagrange's solution to pell's equation?

[sterile pumice]

StarvinPig

[proper folio]

does anyone know what the "period" refers to ?

Mobius inversion formula

here is the solution

[torn escarp]

how often it repeats, 0101 has period 2 because it has the repeating substring 01 which is length 2

11101110 has period 4 for instance

[proper folio]

how often "what" is repeating?

the substrings within each string?

[torn escarp]

yup

the period of a periodic string means the minimum value such that the string repeats after that many places

[proper folio]

and what does "proper" in proper divisor refer to?

whole number divisors?

[torn escarp]

proper divisor means less than the number

6 is a divisor of 6, but it's not a proper divisor

1, 2, 3 are the proper divisors of 6

[proper folio]

is 1 considered a proper divisor

ok

thx

[torn escarp]

yw

[proper folio]

btw

for Mobius inversion formula

does it refer to the whole thing

or only the bottom line

that's two formulae right there

[torn escarp]

the second is the inversion of the first

[proper folio]

so is 'formula' a bit of a misnomer

i.e.

this is more like a Theorem statement

if the first line

then we have the second line

because normally when I think of a 'formula', I think of one equation

i.e. y=mx+b

[torn escarp]

idk

I don't really feel any strong attachment to either of those words

what's a formula anyways, I basically just think it's like a recipe for how to cook up something

first line is F in terms of f, so the second line is the recipe for how to get f back out from given F

feels like a formula to me

I guess there is some theorem there too to be proven, although it's not really presented as such as-is

like I would call it a theorem if I were to then try to carry out its proof following that maybe, idk

I wouldn't worry about this sorta linguistics about it too much

[proper folio]

when it says "the number of such strings", what is "such strings" referring to?

i.e., why is the the number of "such strings" given by B(d)?

[open mist]

Aperiodic strings of length d

Your second question requires that you define what B(d) is, since that's not a standard notation

[proper folio]

wait can someone please explain why getting to the last step of the EEA helps me find the modular inverse of 17?

I don't get this last line

[leaden stream]

the product is 1, so that number is an inverse of 17. But you're working in mods, so you typically want to keep to the positive integers. So you add your mod number to that inverse to find the equivalent positive number. So that new number is also an inverse of 17

[white lion]

I’m trying to find an integer solution for this equation $(10^{100} + 999)x + 1000y = 1$

[sterile pumice]

jayz

[white lion]

I used the Euclidean algorithm method but my answer was consistently wrong

Not sure what’s going on here

[eternal shoal]

What, did your prof assign this as some sort of medieval torture?

[white lion]

explain lol

[eternal shoal]

Unless Euclidean algorithm stops in like 2 steps that sounds like a pain to do and for no real reason for working with numbers those large

[white lion]

It does stop in 2 steps lol

[eternal shoal]

10^100 > {estimated atoms in known universe}

[white lion]

yeah there’s not many atoms irl

[dusty dragon]

10^100 + 999 = 1000*10^97 + 999
1000 = 999*1 + 1

[eternal shoal]

oh better than I thought lol

[white lion]

Yeah, I solved for the remainders and it still didn’t work

[torn escarp]

If you set it up as $ax+by=1$ with $b=10^3$ and $a=10^{100}+999$ $$10^{100}+999 = 10^{97}*10^3 + 10^3 -1 = (10^{97}+1)10^3 -1$$
At this point you have:
$$a=(10^{97}+1)b-1$$
rearrange
$$a(-1)+b(10^{97}+1)=1$$
so $x=-1$ and $y=10^{97}+1$

[sterile pumice]

Merosity

[torn escarp]

I'm really just doing a single step of the euclidean algorithm here

[white lion]

that’s very slick thanks @torn escarp

[whole bronze]

so I came across a fact that integral solutions to diophantine equations that are quadratic in one variable are only possible if the discriminant is a perfect square

I need help with trying to state this is a rigorous way and trying to convince myself it's true/prove it

I understand that if the discriminant is not the square of a rational, the the root will be irrational/complex and sums of rationals with irrationals are always irrations

I also know that with no conditions placed on the diophantine equation, you can get situations where the -b/2a part of the quadratic equation is irrational which may cancel the part of the quadratic equation with under the square root.

so I'm just concerned about conditions for exactly when this applies because I know it doesn't apply all of the time

[torn escarp]

I think once the coefficients are not rational numbers, people stop caring about if the solutions are rational anymore since we're already in the world of non rational stuff at that point

we can work backwards if the coefficients are now real or complex numbers, you can factor the polynomial directly as a(x-r)(x-s) with r, s the roots and then start looking at what the conditions are I guess

So if we expand it out, $a(x-r)(x-s)=ax^2-a(r+s)x+ars=ax^2+bx+c$
Then let's suppose the coefficients are not all rational, but both r, s are rational. This means that c/a and b/a are rational, and we can use the usual discriminant on it after dividing through by the leading coefficient.

[sterile pumice]

Merosity

[torn escarp]

now we have two more cases to try to understand, what if the coefficients are not all rational, but we have exactly one rational root? What if we have no rational roots? I guess we should try to stay consistent and divide through by a again to get (x-r)(x-s)=x^2-(r+s)x+rs and try to work from here.

[fervent grove]

I suspect this question is very naive
one can use continued fractions to somewhat efficiently solve pell equations
are there algorithms one can use (besides brute force) to solve equations of the form ax^2 + bxy + cz^2 = d when the discriminant is positive?

lattice basis reduction can do some cases, so I am especially hoping if there is a lattice basis reduction way to do this in general

(yes, you may assume that a solution exists, if that helps)

[proper folio]

Why is verfiying that the two sets are a bijection equivalent to proving the multiplicativity of Euler's Totient functoin?

Because, the goal statement is something like this right?
$\varphi(mn)=\varphi(m)\varphi(n)$

[sterile pumice]

Kalgar

[proper folio]

so this set encapsulates $\varphi(mn)$

[sterile pumice]

Kalgar

[proper folio]

but how does the set of order pairs $(y,z)$ encapsulate $\varphi(m)\varphi(n)?$

[sterile pumice]

Kalgar

[proper folio]

also, what are the motivations behind these restrictions on y and z?

[open mist]

This is the Chinese remainder theorem

[open mist]

These two sets have cardinals phi(m) and phi(n), so their product has the desired cardinal

[open mist]

By the CRT, there's exactly one x in [1, mn] that verifies that, hence the bijection

[proper folio]

why is $\mu(n)^2/phi(n)$ also multiplicative?

[sterile pumice]

Kalgar

[proper folio]

quotient of multiplication functions

[wooden glen]

Since both mu and phi are multiplicative we have mu²(nm)/phi(nm) = mu²(n)mu²(m)/phi(n)phi(m) = mu²(n)/phi(n) · mu²(m)/phi(m) when n and m are coprime.

[proper folio]

but why is the quotient mu²(n)/phi(n) still multplicative

[wooden glen]

Because it satisfies the definition of "multiplicative", as I argued in my post just above which you apparently ignored.

[proper folio]

oh

thanks

[proper folio]

so basically like, treat the entire quotient as a function

i.e. $F(d) = \frac{\mu(d)^2}{\phi(d)}$

[sterile pumice]

Kalgar

[wooden glen]

Hmm, well, you could be pedantic and say they should have said "the function defined by <such-and-such expression> is multiplicative" instead fo just "<such-and-such expression> is multiplicative", but I don't think there's much possibility for ambiguity.

[proper folio]

Is this a typo?

i.e. it should say $n$ is even

[sterile pumice]

Kalgar

[proper folio]

not $\phi(n)$

[sterile pumice]

Kalgar

[proper folio]

since we literally assumed $\phi(n)$ is odd at the start of our answer

[sterile pumice]

Kalgar

[torn escarp]

I think you're reading it too fast

[proper folio]

how so

and since we assume that $\phi(n)$ is odd, then it follows that all factors must also be odd, correct?

[sterile pumice]

Kalgar

[proper folio]

So each of $p_i^{\alpha_i-1}(p_i-1)$ is odd

[sterile pumice]

Kalgar

[proper folio]

or is this "one of the p_i" part significant?

because I don't get what's the point in considering only one factor

when considering the parity of $\phi(n)$ overall

[sterile pumice]

Kalgar

[torn escarp]

is this odd if one of the p_i is odd

[proper folio]

wat

[torn escarp]

let me rephrase that

[torn escarp]

is this odd if p_i is odd

[proper folio]

oops

that's even

[torn escarp]

yeah

[proper folio]

Wait, so all terms must be even?

So all p_i's must be even

[torn escarp]

yeah

how many even primes are there

[proper folio]

@torn escarp wait, so for this Q, why

Why can we conclude this?

this is part (c) of the same Q

[torn escarp]

I think one of the main concepts to understand is, if a function is multiplicative it means if you understand how it behaves on powers of primes, then you know how it behaves for all numbers

that's why they're relying on decomposing it into primes so much, main thing is phi(p^k) = p^(k-1) * (p-1) will always be how you decompose phi(n)

[torn escarp]

part of why this is true is because if you have and odd number m, then gcd(2,m)=1 so phi(2m)=phi(m). Do you see why?

[proper folio]

yeah

but where does the 2 come from?

[proper folio]

how does that generalise into this

[torn escarp]

the other way around, I wrote the more general version, let m=p^k

[proper folio]

I meant like, why is m odd

all I observe is that $4 \not | \phi(n)$

[sterile pumice]

Kalgar

[torn escarp]

every distinct prime factor of n gives you at least one 2 dividing phi(n)

that means the power of 2 dividing phi(n) is an upper bound on the number of distinct prime factors of n

[proper folio]

wat

[torn escarp]

[proper folio]

for r=2, how do they know for sure that k1 = 2, k2 =1?

oh is it because the only decomposition with 2 factors is 2 * 3

so k1 +1 = 2, k2 + 1 = 3 (or other way around)

[trim jungle]

https://media.discordapp.net/attachments/903486480985489478/1154079051401658368/image0.jpg

Can someone help me with this one

[torn escarp]

I'd try working backwards from (ax+by+c)(Ax+By+C) and expand this, equate the coefficients, then work through the possibilities to factor them

[torn escarp]

actually once you know that -18=C*c that's enough to work out what the sum of C+c can be by grinding through the divisors of -18. But this gets you two answers, although we can't actually exclude them because if fg=p, then (-f)(-g)=p so both answers will work as factorization lol

[trim jungle]

I didn't understood, can you elaborate further

[torn escarp]

sure, which part do you get stuck at, do you see why that factorization would exist?

[trim jungle]

I didn't understood anything

[torn escarp]

well you clearly understood something based on this picture you just sent

you didn't write out the one term that matters most though, the constant term

[trim jungle]

cc?

Yea

[torn escarp]

yeah, cC = ? what number - then use this to solve your problem by looking at what all the possibilities are

[trim jungle]

-18

now what

1, 2 and 3 you mean?

[broken bloom]

I used this method to prove that a^2 + b^2 = 3 c^2 has no solutions in the non-zero integers, but now that I'm looking at it... is this even valid? Like couldn't the same method be used to prove that a^2 + b^2 = 2 c^2 also has no solutions? (it obviously has) like wouldn't it always just lead to cancelling out the squared terms we substitute in like I did?

[open mist]

With 2c^2 you'd get solutions like 1+1 = 2*1

[broken bloom]

yeah but couldn't I apply the same technique of assuming that a = 4m, b = 4m, c = 4l and from there get to the conclusion that there's no solution of that form?

(there actually is, for example a = 4, b = 28, c = 20)

[open mist]

there's no contradiction here
What you're saying is if there's a solution of the form (0, 0, 0) mod 4, it induces the existence of a smaller solution.
That's a contradiction when all solutions are of this form, because there's no minimum.

But in the case a² + b² = 2 c², we have another possible form.
So all you show is that minimal (in the obvious sense I won't detail) solutions aren't of the form (0, 0, 0) but rather of the form (1, 1, 2)

[broken bloom]

there is a minimal solution of the form (0, 0 ,0) mod 4, it's (4, 28, 20)

also (0, 0, 0) and (4, 4, 4) but those are trivial

[open mist]

but it reduces to (1, 7, 5), which is a minimal solution, of the form (1, 1, 2)
All minimal solutions (the multiples of which generate all solutions) are of the form (1, 1, 2), or rather, (1 or 3, 1 or 3, 1 or 3) mod 4

[broken bloom]

so the infinite descent argument fails because there's more than 1 possible family of solutions?

[open mist]

yes

[broken bloom]

does that also mean that in order to prove that some similar equation has no solutions we'd have to find such mod n for which there'd be only 1 family of solutions?

[open mist]

for the infinite descent argument to work, you need to show the solution it reduces to is still reducible

then that's a contradiction due to you being on a well ordered set

[broken bloom]

you sure? cuz I'm pretty sure we can always reduce solutions from the (0, 0, 0) family

[open mist]

yes

we can

but you don't know what family they become

and it might be an irreducible one

at least not always reducible, idk if (a², b², 2c²) = (1, 1, 2) mod 4 is always irreducible

[broken bloom]

hmm

[open mist]

for example, take (16, 112, 80)
It's a solution
It reduces to (4, 28, 20)
Which reduces to (1, 7, 5)
Which is irreducible

[broken bloom]

I see

this clears things up a bit but I need time to digest it, still don't understand it fully

[open mist]

feel free to play around with it and let it sit yeah

or try to work it out for some other examples

some simple ones like a² + b² = 5c²
Or some very different ones like a^3 + 2b^3 = 3c^3, for which you should find a similar pattern (though maybe not mod 4, but there's probably a relevant mod to study, like 8 or whatever, I don't actually know)

[broken bloom]

I'll check those out too

thanks for the explanation

[open mist]

though thinking about it, do note that it may get very grindy

cause there's 512 different triplets of values mod 8

125 different cases for triplets of squares

[broken bloom]

lol fun

I'll start off with mod 2 3 4 5

and for bigger ones I might use python or something

[open mist]

and it might not yield anything at all

[broken bloom]

yeah that's a slight issue

[whole bronze]

I follow this except I don't know how they're justifying that a minimal element of Z(sqrt(d)) exists... as far as I can tell we don't get that for free and I don't see how to argue for it...

[whole bronze]

Trying to follow this - writing $k\alpha - c$ for ${k\alpha}$ and $l\alpha - d$ for ${l\alpha}$ pigeonhole gives that

$$|(k-l)\alpha - (c-d)|< \frac{1}{n+1}$$

[sterile pumice]

OW TOO SPICEE (ouchie!)

[whole bronze]

which is in the form we want so we match q to k-l and p to c-d

q must be in the set {1,2,...., n} so we take the absolute value (not sure how to justify that this is fine since it doesn't maintain equality to the LHS in general)

p is then c-d but this proof is saying it's the integer closest to k\alpha

I'm again not sure why c-d is the integer closest to k\alpha

[trim jungle]

ik, unrelated, but can you guys help me with this, nobody is helping in la channel xd

[iron surge]

are you familiar with ceiling and floor functions?

[whole bronze]

yes

[iron surge]

think about a set that lists all possible distances and then takes the minimum distance

and select that integer that kalpha is closest to as p and call such a k, q

[whole bronze]

distances between the {k\alpha}?

[iron surge]

yes

[whole bronze]

actually I can prove the |*| part because you just multiply the inside of |*| by -1 if k-l is negative

[iron surge]

collect all possible positive integer multiples of kalpha

[whole bronze]

I still don't see how c-d (or d-c) is the closest integer to k\alpha

[iron surge]

and find the minimum distance between that and the ceiling function of kalpha

bear with me lol

hang on I'm typing this up rn

@whole bronze

I'm thinking this^

My set S find all possible distances between kalpha (where k runs through values 1,2,...,n and nearest integers to it (floor of k alpha and ceil of k alpha), then r finds the smallest distance.

does that make sense?

let me fix a typo

done

[whole bronze]

sorry I probably have to think about this for a while and draw some pictures of small examples lol

thanks for the help!

[iron surge]

draw a number line

and u know that the distance between two consecutive integers is 1

place a dot between those two lines

call that alpha

then if u bump up kalpha, u can get either closer or further away from a line by adding an alpha

up to n alphas

does that make sense?

if alpha is negative u go down towards one line

if alpha is positive, u go up towards the line to the right of ur dot

we know alpha isn't 0 since 0=0/1 is rational

[whole bronze]

if you don't take everything mod 1 then things that should be close actually end up being far away (e.g. k\alpha and l\alpha) where k and l differ by a non-minuscule amount

[iron surge]

being technical...where I wrote "for some p...and q..." I should have swapped the order...should've been for some q in {1,2,...,n} and p in {floor qa,ceil qa}

[iron surge]

I would refrain from modular arithmetic here since alpha is irrational

draw a number line.....

that's my best advice

[whole bronze]

oh wait this is following the proof given in the first screenshot

yea you can def find a minimum distance for the k\alpha

min S is just that by definition

but does it have to be c-d?

[iron surge]

u can call it whatever u want...u just know that there has to be some integer it's gets closest to as k alpha runs through values k=1,2,...,n

u know the closest integers to kalpha are the ceiling and the floor

of kalpha

so as k runs through all it's values, u can find the multiple of alpha and the integer that it correspons to that gives the smallest distance

I reposted and edited^

now we must figure out why exactly we can't have r=|qalpha-p| being at least 1/n+1

remember, in my proof, r was the smallest distance

[whole bronze]

right, I don't see how you're arguing that it's less than 1/(n+1) by the minimality of r

is this pigeonhole?

actually I don't see how this follows from pigeonhole

[iron surge]

because if r is at least 1/(n+1), there must be different p and q than what we have that would be closer than our r was to an integer

because either p-1 or p+1 would be the other integer and q would be different

to make sense of this

fix p as the floor of q alpha for instance

then if this q and p aren't close enough

then

that means no other kalpha where k in {1,2,3,...,n} would be closer to p than qalpha was

however, one of those k's would yield a k alpha closer to either p+1 or p-1 or really another integer other than p

does that make sense??

[whole bronze]

no other k would have {k alpha}<{q alpha} right

[iron surge]

all we know is that some other positive integer multiple of alpha would be closer to another integer (the ceiling or floor of that integer multiple of alpha)

this means that r was not the closest such p and q

[whole bronze]

1/2+n is a sequence of points that don't 1/3 close to any integer so I feel this is missing something. 1/2 is at least 1/3 away from 0 but all the other points of 1/2+n are also 1/3 away from any integer

[iron surge]

but remember depending on what n we're given that's how many integer multiples of alpha we can look at

[whole bronze]

no proof that doesn't eliminate this can be correct so some assumption distinguishing this situation from the other must be used in the proof for it to be correct (no argument that proves a false fact can be correct)

[whole bronze]

just restrict the sequence from k=1 to some other integer

[iron surge]

$\left|\frac{1}{2+n}-0\right|<\frac{1}{n+1}$ for any positive integer $n>0$, so I'm not sure what you mean

[sterile pumice]

logician

[iron surge]

set p=0, voila

in that case

[whole bronze]

I'm not arguing with your conclusion

the conclusion is a theorem

[iron surge]

wait are we saying the same thing

[whole bronze]

I'm just arguing that the argument is incomplete because it proves false facts

[iron surge]

?

[iron surge]

I'll admit I glossed over why such and r works.....

[whole bronze]

for example if you have a consistent model of

(1) A and B

and

(2) A and not B

it will be impossible to prove B from A because then you would have proven (2) wrong, which was a valid model

if there's an underlying unspoken assumption C that forces you into the (1) model but it's never mentioned in the proof then the proof is not correct becuase the proof would go through the same way without every using C and contradict (2)

[iron surge]

i kind of see what ur saying?

sounds like ur pretty much saying, the proof just needs some more elaboration....instead of jumping to the conclusion thought that conclusion is correct

[whole bronze]

It's also a standard (and important) way in mathematical logic to see if a proof is valid - if there are models in which p is true and models in which p is false and assumption C forces p to choose only one of those truth values for p, then assumption C must be used in the proof for it to be valid

You say that C is a necessary assumption for the theorem to hold

[iron surge]

there's actually nothing wrong with what's written here aside from glossing over the "why r would not be minimal" part. The other parts of the proof are simply the given conditions in the problem statement, and a construction of a set, we would want to take the smallest element of...those are perfectly reasonable.

[whole bronze]

It's a meta argument - if this proof is valid it shouldn't go through in situations that give a false conclusion