elementary-number-theory

[crystal agate]

and show that these count the same things

[feral olive]

Hello. The person in the video is not using the birthday paradox to guess the key combination max to try to ensure to have 100% of luck to reach the number. https://youtu.be/FAaki7d5vvY?si=A6lxWWvYxR3GXmFW is he telling something (mostly) wrong as we could have a lot of less to reach 50% of keys combination?

wrong channel sorry

let's move to #probability-statistics

[sacred junco]

elementary number theory is boring because it is elementary

[torn escarp]

thanks for sharing

[runic token]

we appreciate ur opinion

[still flare]

speak for yourself...

[runic token]

ur rightt

i appreciate ur opion sordie

[crystal agate]

boring is debatable

[hoary shell]

@unique cypress

[unique cypress]

L

[limpid crystal]

I’m confused, why does this definition of the sum of a geometric sequence lack a first term, shouldn’t it be $a(\frac{r^{n+1}-1}{r-1})$ ?

[sterile pumice]

zaglaz

[west glade]

after you have shown this you can just multiply both sides by a

[limpid crystal]

Ohh I see thanks

[sacred junco]

Is there no typo in 8.5.4?

p^(a-1) instead of p^a-1 is true

[torn escarp]

sounds reasonable to me

probably a typo

[unkempt void]

There's also another funny way for this I was just playing around with lol

If you expand (1 + x + xy)^n in two different ways i think

[warm dust]

?

[crystal agate]

I've been struggling with a pretty hard number theory problem this weekend - "if a is a perfect square modulo every prime p, then a is a perfect square in Z". I am 99% this is true, and have managed to reduce the problem to the a squarefree case. Assuming a isn't divisble by 2 (I assume I can just play around until I find some contradiction in that case), with some help I've concluded that:

If we can find q such that q = 1 mod 4, q is a non-QR for some prime factor r of a, and that q = 1 mod every other prime factor of a, then we will be done.
Now, the q = 1 mod 4 and q = 1 mod every other prime factor of a stuff can be found via a special case of Dirichlet's theorem on arithmetic progressions that I've proved in the past, where we can find infinitely many primes 1 mod n for any n
but I have no clue how to combine this with the q is a non-QR modulo r fact
I've been trying to find a modulus m such that that if q = 1 mod m, then q is a non-QR modulo r
but I've had no success with this

any help would be greatly appreciated

[latent tusk]

Any hint how to prove that if a, b are positive integer > 2 then 2^a + 1 is not divisible by 2^b -1.

We can show that for a= b it cannot be possible but for other cases ?
If a > b then 2^(a-b) + 1 is divisible by 2^b - 1

[forest plank]

Found a comment on stackoverflow that says it is proved in Ireland Rosen's book in chapter 5 section 2 theorem 3

[crystal agate]

Hmm

Sus

[long lion]

i'll attempt this when i get the opportunity to

but i seem to remember the solution requiring the law of quadratic reciprocity

interestingly though ||if we replace square with any generic kth power, then it's not true: 16 is a 8th power mod all primes p but 16 is not an 8th power in Z||

[crystal agate]

Hmm

[crystal agate]

Yeah the thing I mentioned about the q = 1 mod m stuff relies on QR

Alternatively if I prove reciprocity for Jacobi symbols I’m also done

But it’s very tedious to do that

[long lion]

oh sorry didn't properly read it

[crystal agate]

Nah dw abt it

I appreciate any and all help :DD it’s a good problem though

The nth power case failing is very interesting

Although I suspect it works for most sorts of things with a recirprocity statement (like cubic)

[feral olive]

Hello I am trying to understand my book that claims the following picture. Now does it tries to mean that:

If $a_1 \equiv b_1 \mod m $ then $b_1 - a_1 = m \cdot x_1$

Please?

[still flare]

No, it does not mean that.

It means b_1 - a_1 is divisible by m.

If what you wrote were the definition, then modular arithmetic would just be arithmetic.

[sterile pumice]

superctf

[feral olive]

Like this?

[still flare]

For some x_1, yes.

Some whole number x_1.

[feral olive]

Great thabk you very much!!! I was trying to fix https://discord.com/channels/268882317391429632/1286756553646411817

[keen pagoda]

guys I want to prove that the sum of all the remainders mod p (p = 4k +1) that are quadratic residues is (p-1)p/4, only thing I know is that that's half of the sum of all remainders
any hints on how to do that?

I'm really stuck

maybe I should try proving the sum of all qr is the same as the sum of all nqr

[torn escarp]

hint, if q is a qr, then -q is also a qr

[keen pagoda]

I think I found it out act

[keen pagoda]

YES YES I THINK I FOUND OUT HOW TO USE THAT

like

[torn escarp]

sorry if I sniped you figuring it out by a split second there haha I won't spoil any further

[keen pagoda]

I only wrote act because of how desperate I was to write it

before you

which didn't work

the sum should be the same if you go negative which would be like
(all squared numbers are actually remainders)
(p-1)/2 - 1² - 2² - .... = the sum
so 2the sum is p-1/2

damn that's such a pretty argument

I love number theory my god

[keen pagoda]

(that's cus each remainder negative will be like, p-r, so you sum all p-1/2 different p's and subtract the remainders

[torn escarp]

oh interesting I had a different argument in mind

[keen pagoda]

Oh really?

Which one

[torn escarp]

there are (p-1)/2 QRs and since p=1 mod 4 then they come in pairs of q and p-q, so there are (p-1)/4 pairs of q + (p-q) = p

so p(p-1)/4

[keen pagoda]

Oh

I mean ig if you do some algebra you can interpret these arguments similarly

[torn escarp]

I have to think through yours a bit more, cause I didn't see where you used the p=1 mod 4 condition

[keen pagoda]

So that the negatives are also all the qr

Like

r1 + r2+... = p-r1 + p-r2 +...

Cus I'm summing over the same set

Aka the set of all qr

And there are p-1/2 remainders so p-1/2 p's

[keen pagoda]

I mean, the negatives of the qr

[torn escarp]

I'm kinda confused on how the sum is working out, I guess to lay it down a bit more concretely I'm thinking roughly in this area $$S=\frac{p(p-1)}{2} - \sum_{k=1}^{\frac{p-1}{2}} (i^2)_p$$ I'm using $( \cdot )_p$ to mean reduction mod p to the set ${1,2,..., p-1}$

[sterile pumice]

Merosity

[torn escarp]

pretend I put index i not k on the sum

I think I sort of see what you're saying, switch the bounds from - p(p-1)/4 to +p(p-1)/4 maybe

[keen pagoda]

I'm literally summing the same thing two times

since sum (i²)p is the same as sum p- (i²)p

I'm basically switching every number to its "negative", which is p-number

[torn escarp]

can you write out the full thing in latex

[keen pagoda]

sure ig

how do you do normal brackets in latex

like

without it interpreting anything

oh shit

[torn escarp]

oh escape them like \{

[keen pagoda]

let $S{1} = {(1²){p}, (2²){p}, ..., ((p-1)²){p}}$, since multiplying the set by -1 gives us also the set of all quadratic residues after reducing the numbers back mod p, we can say $S{2} = {p - (1²){p}, p - (2²){p}, ..., p - ((p-1)²){p}} = S{1}$, then you sum both of them and equate the result

[keen pagoda]

oh ok

[sterile pumice]

gabi the ancient

[keen pagoda]

oh squared doesn't owk normally

[torn escarp]

i replaced the ^2 for you let $S{1} = {(1^2){p}, (2^2){p}, ..., ((p-1)^2){p}}$, since multiplying the set by -1 gives us also the set of all quadratic residues after reducing the numbers back mod p, we can say $S{2} = {\p - (1^2){p}, p - (2^2){p}, ..., p - ((p-1)^2){p}} = S_{1}$, then you sum both of them and equate the result

[sterile pumice]

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

[keen pagoda]

yeah, there

that's the argument

I forgot dividing p-1 by 2

anyways

[torn escarp]

I think it broke some other formatting when I copied yours lol

[keen pagoda]

the only thing not working is you saying what you replaced

oh no the brackets too

aaaa

let $S{1} = {(1^2){p}, (2^2){p}, ..., ((p-1)^2){p}}$, since multiplying the set by -1 gives us also the set of all quadratic residues after reducing the numbers back mod p, we can say $S{2} = {p - (1^2){p}, p - (2^2){p}, ..., p - ((p-1)^2){p}} = S_{1}$, then you sum both of them and equate the result

[sterile pumice]

gabi the ancient

[keen pagoda]

nice

just pretend p-1 is divided by 2 too

basically the set of all qr negated is, mod p, the same as the set of all qr, so you just sum both after doing the p- thingy to be sure it's actually the set of remainders

[torn escarp]

I believe I see what you're saying here, it just doesn't line up with what I was reading here

I guess that doesn't matter anymore since what you're saying now makes sense to me haha

[keen pagoda]

I was trying to type real quick to show I actually just found out the solution lmao

[torn escarp]

but I'm still not sure how that works out

[keen pagoda]

well, are you aware that if you multiply the set of all qr by another constant qr, you get the set back mod p?

like, you just permute the elements around

cus that's the main part of the argument

[torn escarp]

I see, cause -1 is a QR is what you're saying, gotcha that makes sense and I see how that uses p=1 mod 4 now

[keen pagoda]

yeeey

that was all, actually, to finish solving this problem btw

it's a cool problem, and I got stuck in the end cus all I needed was to prove the fact I just proved

[torn escarp]

interesting, yeah never heard of this result before

[keen pagoda]

it feels like it should be a known theorem tbh

like, doesn't it have a "lemma 3.4:" vibe?

(well, a known lemma, in this case)

[torn escarp]

how "bad" do the p=3 mod 4 primes get in terms of D = (sum of QRs) - (sum of NRs) how far from 0 is D?

[torn escarp]

lol idk what lemma 3.4 is

[keen pagoda]

nothing

I'm just saying it seems to fit in a lemma

I feel like I should have seen this fact in some textbook somewhere yk

[torn escarp]

oh yeah probably

[keen pagoda]

cus it's very simple and a natural question to ask ig

[torn escarp]

wel even this Vietnam problem seems weird and unnatural to me on its own, why are people asking this question really

feels like it's probably a lemma to something actually being used or thought about

[torn escarp]

yeah, definitely. I was surprised when you asked it, I guess can we generalize the result to let's say cubic residues for primes 1 mod 3 or whatever etc?

[keen pagoda]

maybe

[keen pagoda]

idk how cubic residues work

I mean I know what it is but

oh actually

-1 is always a cubic residue so we really only need that to guarantee multiplying by -1 will give the set back

so ig the argument should work the same

problem is that idk where we should "stop"

like when are two cubes equal

oh I think that's the prime 1 mod 3

[torn escarp]

I'm thinking partition by cosets

[keen pagoda]

or not

idk

[torn escarp]

yeah that's why

like more generally I'm thinking add the elements of each coset for the subgroup of nth powers for primes p=1 mod n

but wanted to at least check a specific case before we got too crazy

for instance p=7 appears to work, if you break it into the cosets {1,6}, {2,5}, {3,4} then they all sum to 7

so that's following the general formula p*(p-1)/(2n) I guess?

[keen pagoda]

(btw if you're curious you can write for ex floor(2i²/p) as 2i²/p - r2i²/p (where r2i² is the remainder of 2i² divided by p so stuff cancels out and the question becomes only about sums of remainders)

[keen pagoda]

oh that's interesting

[torn escarp]

ah, ok cool, I'll play around with that after this one

[keen pagoda]

after that and the question I asked I kinda gave the solution away

[torn escarp]

yeah haha, well maybe if I'm feeling into it I'll try to generalize that problem in a way that makes the generalization of this stuff give the answer there too

[keen pagoda]

damn

[torn escarp]

why not lol

[keen pagoda]

I should maybe play with this too I'm too seriously studying for math olympiads I miss this type of ""useless"" playing around

[torn escarp]

yeah I think the more we dig into this sort of thing, we'll end up getting into more group/ring theory stuff on accident, which is probably healthy haha

[keen pagoda]

I mean, they sum to 7 cus they are negatives of eachother ig

[torn escarp]

yeah

[keen pagoda]

and actually just realised about the cubes

{1³, 2³, ...} will give us the entire residue class

I think if p = 1 mod 3

[runic token]

useless playing around is the kind that matters most fr

[keen pagoda]

or if not

[torn escarp]

so now does that happen just cause it's cyclotomic polynomial is quadratic like x^2+1

or is this something that happens for other roots of unity too

or at least, I'm sort of conflating with my language here, I'm really just thinking of cosets of the cyclic group with p-1 elements and p=1 mod n

since that's effectively the multiplicative group

[keen pagoda]

h m

I'm not fresh enough with group theory sadly

and I do not know what a cyclotomic polynomial is, even tho I know I will have to some time

[torn escarp]

you know what an irreducible polynomial is?

[keen pagoda]

ye

[torn escarp]

so there's a cyclotomic polynomial for every primitive root of unity, for instance x^2+1 is the one for the 4th root of unity

x^2+x+1 is for 3rd root of unity

x^4+1 for 8th root, x^4+x^3+x^2+x+1 for 5th root

there's a formula for them but the point is just that they exist

[keen pagoda]

so they're irreducible polynomials on R for the other roots of unity?

[torn escarp]

irreducible on Q

[keen pagoda]

oh

on Q

therefore on Z

[torn escarp]

well you can sort of ignore the irreducibility aspect

like we can talk about x^2+1 in the field with 5 elements Z/5Z

[keen pagoda]

ok what's up with them

why are they cool

[torn escarp]

but since it's 1 mod 4, it factors as, let's just say (x+2)(x+3)

[torn escarp]

good question

I guess maybe one of the main algebra reasons people care is the Kronecker Weber theorem but that might be a hard sell

as far as neat stuff you can do maybe more immediately, you can derive a formula for them with Dirichlet convolutions

[keen pagoda]

(btw, merosity, do you like, work on number theory? cus everytime I ask anything here you appear as an ancient mage and starts rambling and wondering about the beauties of number theory, and you seem to know a l o t about it, and love it a lot too)

[torn escarp]

haha well I appreciate the compliment

[keen pagoda]

I love that you're so curious too like you never stick just to the question you always want to see where it goes

[torn escarp]

I used to tutor a lot of Indian students and so I started learning number theory to help with that too. I ended up spending a lot of time over the years thinking about elementary number theory

[keen pagoda]

this is quite amazing

[torn escarp]

the main things that struck me were dirichlet convolutions and hensel's lemma and that kinda got me hooked

like "oh they're using derivatives with some modulo condition wtf?"

[keen pagoda]

I've heard of hensel's lemma

watched an evan chen's introduction to it

a video

[torn escarp]

yeah, I think that's one of the best parts of math. I know with other subjects it tends to be restricted. Like biology they're stuck to growing flies to study, or you're just stuck with kind of philosophizing but you can't really get to the hands on to see the truth

[keen pagoda]

oh yeah you only need pen and paper

to study any math basically

[torn escarp]

ah, yeah I think I've seen his AG channel on YT but idk if I've seen anything on there

are you familiar with Dirichlet convolutions?

that's sort of what led me to learn more about analytic number theory personally, some fun stuff there

[keen pagoda]

I watched a video that had it

I think

but I don't remember precisely what they were

it was about the moebius function

oh ok I know what a dirichlet convolution is

[torn escarp]

yeah

so ok just to bring it back to the irreducible polynomials, I gotta head out soon so might be a bit quick but at least a basic thing to see

x^n - 1 has roots of unity as its roots if their order divides n

for instance x^6 - 1 has -1 as a root because -1 has order 2 and 2 divides 6

hopefully that's pretty clear

so you can imagine factoring x^n - 1 into the irreducible cyclotomic polynomials

[keen pagoda]

oh yeah yeah

[torn escarp]

$$x^n - 1 = \prod_{d|n} \Phi_d(x)$$

[sterile pumice]

Merosity

[torn escarp]

now you can log and do a mobius inversion for a formula for the cyclotomic polynomials

[keen pagoda]

:0

number theory is really amazing damn

[torn escarp]

yeah 😄

[granite mica]

lol is this MONT?

Good book.

[keen pagoda]

ye

[granite mica]

Good book.

[keen pagoda]

ye

[granite mica]

Good book.

[feral olive]

Please

[feral olive]

Could you help me to reexpress the mention "the difference a - b is divisible by m please"? I did

theorem: \[
if $a_1 \equiv b_1 \mod m$ and $a_2 \equiv b_2 \mod m$ then\ $a_1 \pm b_1 \equiv a_2 \pm b_2 \mod m$ and $a_1 \mul b_1 \equiv a_2 \cdot b_2 \mod m$
\]

proof: \[
If $a_1 \equiv a_2 \mod m$ then $b_1 - a_1 \mod m =$ 
\]

Is m it correct?

[sterile pumice]

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

[forest plank]

$a_1 \equiv b_1 \pmod{m}$ means $m \mid a_1 - b_1$

[sterile pumice]

🤗🤗

[feral olive]

Oh great! I now understand!

[feral olive]

theorem: \[
if $a_1 \equiv a_2 \mod m$ and $b_1 \equiv b_2 \mod m$ then\ $a_1 \pm b_1 \equiv a_2 \pm b_2 \mod m$ and $a_1 \cdot b_1 \equiv a_2 \cdot b_2 \mod m$
\]

proof: \[
If $a_1 \equiv a_2 \mod m$ then $ a_2 - a_1 \mod m = 1$ for x is any integer $1 | x$. \newline
As $(a_2 \cdot b_2 ) - (a_2 \cdot b_2) \mod m = 1$ \newline
then $(a_2 \cdot b_2 ) - (a_2 \cdot b_2) \mid m$ \newline
then $a_1 \cdot b_1 \equiv a_2 \cdot b_2 \mod m$
\]

I am confused

[sterile pumice]

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

[feral olive]

theorem: \[
if $a_1 \equiv a_2 \mod m$ and $b_1 \equiv b_2 \mod m$ then\ $a_1 \pm b_1 \equiv a_2 \pm b_2 \mod m$ and $a_1 \cdot b_1 \equiv a_2 \cdot b_2 \mod m$
\]

proof: \[
a_1 \pm b_1 \equiv a_2 \pm b_2 mod m
If $a_1 \equiv a_2 \mod m$ then $ a_2 - a_1 \mod m = 1$ for x is any integer $1 | x$. \newline
As $(a_2 \cdot b_2 ) - (a_2 \cdot b_2) \mod m = 1$ \newline
then $(a_2 \cdot b_2 ) - (a_2 \cdot b_2) \mid m$ \newline
then $a_1 \cdot b_1 \equiv a_2 \cdot b_2 \mod m$
\]

Is it correct?

[sterile pumice]

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

[feral olive]

theorem: \[
if $a_1 \equiv a_2 \mod m$ and $b_1 \equiv b_2 \mod m$ then\ $a_1 \pm b_1 \equiv a_2 \pm b_2 \mod m$ and $a_1 \cdot b_1 \equiv a_2 \cdot b_2 \mod m$
\]

proof: \[
$a_1 \cdot b_1 \equiv a_2 \cdot b_2$

If $a_1 \equiv a_2 \mod m$ then $ a_2 - a_1 \mod m = 1$ for x is any integer $1 | x$. \newline
As $(a_2 \cdot b_2 ) - (a_2 \cdot b_2) \mod m = 1$ \newline
then $(a_2 \cdot b_2 ) - (a_2 \cdot b_2) \mid m$ \newline
then $a_1 \cdot b_1 \equiv a_2 \cdot b_2 \mod m$
\]

$a_1 \pm b_1 \equiv a_2 \pm b_2 \mod m$
\[
$a_1 \equiv b_1 \pmod{m}$ means $m \mid a_1 - b_1$ \newline

Ok i am entierely confused.
Then in this case, as $ a \pm b$, then $m \mid (a_1 \pm b_1) - (a_2 \pm b-2)$
\]
Is it correct?

[sterile pumice]

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

[feral olive]

Ok let me redo it again entierely then! Step by step

[forest plank]

Uh oh

Your latex didn't compile

Maybe you're actually correct.. I just can't read it

[feral olive]

$a_1 \equiv b_1 \pmod{m}$ means $m \mid a_1 - b_1$

If $a_1 \equiv b_1 \pmod{m}$ means $m \mid a_1 - b_1$ and

$a_2 \equiv b_2 \pmod{m}$ means $m \mid a_2 - b_2$


Then $a_1 - b_1 \pm a_2 - b_2 \pmod{m}$ means $m \mid a_1 - b_1 \pm a_2 - b_2$

[sterile pumice]

superctf

[feral olive]

I fear i am very confused

[forest plank]

$m \mid a_1 - b_1$ and $m \mid a_2 - b_2$ implies that $m \mid (a_1 - b_1) \pm (a_2 - b_2) = (a_1 \pm a_2) - (b_1 \pm b_2) $

[sterile pumice]

🤗🤗

[feral olive]

If yes ok i confused both priorities

[feral olive]

is it the full proof for the full exercise? O_o

[feral olive]

what is the natural density

[sterile pumice]

budder

[feral olive]

I can not call helpers anymore. Why.

[feral olive]

@forest plank @quaint gate I would like to understand because I am confused. could you clarify please?

[forest plank]

Uhmm.. the proof is very very simple.. if you can't come up with the proof means that you don't understand what a = b (mod m) means

I would suggest to find and watch some videos on youtube

About it

Found a video series that seems good https://youtube.com/playlist?list=PLug5ZIRrShJHPX-OyMNLLCQfKXchdZKpE&feature=shared

[feral olive]

I am entierelely ok with the proof. I just would like to ensure it proove the full exercice.

[feral olive]

could we focus on my own math book please?

@forest plank except if really really you have a good reason

[feral olive]

Hello I am sorry. I asked many many questions about my current issue. I absolutely must have to read the book. I want to progress very much.I just would like to know if the following is enough to proove the theorem stated in the book:

$a_1 \equiv a_2 (\mod m)$ and $b_1 \equiv b_2 (\mod m)$

$m \mid a_1 - a_2$ and $m \mid b_1 - b_2$ implies that $m \mid (a_1 - a_2) \pm (b_1 - b_2) = (a_1 \pm a_2) - (b_1 \pm b_2) $

Definitely sorry for the spam. I just would like to success.

[sterile pumice]

superctf

[charred anchor]

just use the definitions of what it means for a|b

a|b implies there exists a k such that b=ak

[feral olive]

b = a *x

[feral olive]

could we make a pointr please? is the statement with +/- already proven and are we moving to the * please?

[unborn flower]

I'm confused by big O

$\sin(x) = O(x) \ x = O(x) \ \therefore \sin(x) = x$

[sterile pumice]

someone1010

[unborn flower]

i know this argument is wrong but wouldn't this be implied by big O?

[still flare]

You are right, the notation sucks doesn't it

Really what's going on is O(x) represents a set of functions with a certain property

and they mean that sin(x) is in that set of functions

[unborn flower]

I get that, but using equals sign implies sin(x) and x are in the same equivalence class?

[still flare]

Unfortunately this notation is (1) very helpful and (2) so baked-in that you can't really get away with not using it

[still flare]

It's just notation and you should, like I say, keep in mind that they really mean here that sin(x) is part of a set of functions with a certain property.

[unborn flower]

I get that, but i'm confused when it's used as a number

O(f(x)) \pm O(f(x)) = O(f(x))

how are you supposed to interpret this?

[still flare]

Whenever you see O(f(x)), you should take this to mean that there is "Exists a function g such that g is has property blah ..." at the start, and substitute that occurence of O(f(x)) with g(x)

So here it is saying that

If we take the sum of two things with behaviour O(f(x)) then we get another thing with behaviour O(f(x))

This is not perfect unfortunately

[unborn flower]

agh this is like making equals sign a set operator, this is kind of horrible notation

[still flare]

I agree.

But it's useful because it gives us these shorthands

[still flare]

Sometimes they mean forall, and you kinda just have to see it from context

[unborn flower]

but it also sometimes means exists

[still flare]

Like I was saying, yes

[unborn flower]

yea, i guess it's not that confusing but i hate this. thank you

[tribal palm]

I wrote a paper back a while ago about a formula for the prime number sequence. I rewrote it in the form of a simple Power Point presentation. Let me know what you guys think. I'm attaching it here as a pdf.

Looking for feedback.

[iron quartz]

I don't know why the red part implies the blue part. Could someone explain this to me? Thank you!

[long lion]

do one divided by the other

y/-y = a^2/b^2

i.e. -1 = a^2/b^2

[iron quartz]

but it's not = I mean it's congruence are we allowed to to do division on congruence?

[long lion]

well we're never truly 'dividing' when we do modular arithmetic

we're just multiplying by it's multiplicative inverse

[torn escarp]

that's where the y != 0 mod p assumption comes in

personally I take the perspective that we're working in the field Z/pZ for p a prime, which means we do have division. Everything is commutative so there's no ambiguity about left vs right division. We also know we can multiply by inverses, so this is really as good as division.

[sacred junco]

What does X(q) mean

[sacred junco]

Given the equation $3x^2 + 2 = y^2$ it is easy to show that it could not admit integer solutions (by taking the equation mod 3 we find a contradiction as $y^2 \in {0, 1 }$) yet I am finding some difficulties to show that the equation does not admit rational solutions (which most probably stems from a lack of number theory rudiments)
by supposing that it does admit rational solutions then the equation $3x^2 + 2y^2 = z^2$ must admit integer solutions yet I do not know how to show that it can't

[sterile pumice]

Saïd

[forest plank]

Again, look mod 3

[sacred junco]

would you please share more insightfull details about your reasoning

[forest plank]

We can assume x,y,z are all coprime. In particular, y,z can't be both divisible by 3

2y^2 = z^2 (mod 3)

Has no solutions unless y,z are both divisible by 3

[wanton stream]

how so?

if y and z were both divisible by 3 that wouldn't mean x is divisible by 3

[forest plank]

If they aren't coprime, we can divide the equation by the gcd

[wanton stream]

I mean, gcd(x, y, z) = 1 doesn't mean y and z are coprime

[forest plank]

If y,z both divisible by 3, then squares are div by 9

3x^2 which is their difference is then also div by 9

So x is div by 3

[long lion]

possibly a dirichlet character?

but this belongs much more in #advanced-number-theory

[wanton stream]

aight that makes sense

[long lion]

#elementary-number-theory is much more for like very basic NT, analytic NT belongs there

[sacred junco]

@forest plank thank you so much it was a really nice proof

Could you send me some exercises where similar reasoning are employed so that I could learn the techniques

[torn escarp]

just for fun, the p-adics have a bit of machinery that makes solving the rational case "easy". I'll try to be a bit verbose here, let's say |.| is the 3-adic absolute value. So if there's a 3 in the denominator of x then |x|>1 and we have |3x^2+2| = |3x^2| by the strong property of the ultrametric inequality.
So simplifying this: |3x^2+2| = |y^2|
becomes: |3||x|^2=|y|^2 which is an odd power of 3 equal to an even power of 3, which is a contradiction.

[sacred junco]

Damnnnn that is in fact a beautiful proof provided that I understand all the terminology xP but thank you I’ll take it gladly
Thank you for your time and attention

[feral olive]

How could there be more than 1 congruence in the same line please?

What does a congruent b congruent c mod m means?

[forest plank]

Well congruence is an equivalence relation. In particular, if x~y and y~z, then x~z. In short, we can write this as x~y~z

[feral olive]

I am confused

Do you mean there could be multiple quotien?

[west glade]

just like a=b=c means that a=c, then also a congruent b congruent c means a congruent c

if a and b have the same remainder, and b and c have the same remainder, then a and c also need to have the same remainder

[forest plank]

This means a,b,c all have the same remainder modulo m

[novel jacinth]

Hi! Anyone who has any tricks for solving 2^23 mod 83 without a calculator

[unborn flower]

2^8 = 256 = 7 mod 83
2 * 42 = 1 mod 83
2^23 = 7^3 * 42 mod 83 = 343 * 42 mod 83 = 11 * 42 mod 83 = 462 mod 83 = 47 mod 83

idk if there's a better way

[patent acorn]

yeah basically it's just, "use modular arithmetic"

the extremely straightforward method is to just calculate 2^16, 2^4, 2^2, 2^1 by repeated squaring (2^4 is (2^2)^2, 2^8 is (2^4)^2, 2^16 is (2^8)^2, and you can reduce mod 83 at each step) and then multiply them together, but yeah for numbers this small you can often do better than that by kind of just taking any shortcuts you find and keeping the numbers small where you can

[vital dune]

Anyone familiar with Eisenstein primes?

https://rosettacode.org/wiki/Eisenstein_primes

[long lion]

yh somewhat

what's ur question?

[vital dune]

There's a piece of code that has two values graphlimitsquared and printlimit. So, printlimit is 100 and it's for how many eisenstein primes I want to display. graphlimitsquared is for creating an array for eisenstein integers and then apply a function for every eisenstein integer we have to check if it is a prime or not, and create another array of eisenstein primes which the function returned true.

The question is, limit = sqrt(graphlimitsquared) and the array is generated by the following loop: a=-lim:lim and b=-lim:lim

lim here is 100

and the loop combines all values in -100:100 as (a,b)

How does this ensures we have at least 100 primes in this eisenstein integer array %100?

[vital dune]

This loop apperantly generates 40401 Eisenstein integers, so my question is does 40401 Eisenstein integers ensures including at least 100 Eisenstein primes?

[long lion]

i'm not all that knowledgable about eisenstein primes, but it's entirely possible that 100 was chosen a bit arbitrarily

we expect there to be lots of eisenstein primes near 0

so if we just find eisenstein primes in that 200x200 area, it's likely that we'll encounter enough eisenstein primes

and if not, u can just increase that area

[vital dune]

I see

[long lion]

so each 1 mod 3 prime adds 6 eisenstein primes

and each 2mod3 prime adds 1 eisenstein prime

(+3)

so we wanna find like a vague bound on

• of 1 mod 3 primes

• of 2 mod 3 primes

[long lion]

by dirichlet's thm, it should be ~ n/2ln(n) for both

so that's ~ 7/2 n/ln(n)

so if we want N >> 1 eisenstein primes

the minimum nxn area we need should satisfy N < 7n/2ln(n)

[vital dune]

Wow thank you

[long lion]

but i really am not an expert on this subject

this question belongs much better in #advanced-number-theory

[vital dune]

I'm far away being an expert

I'm a physicist

Thanks for the help

[long lion]

nw

but try posting this in #advanced-number-theory

you'll get a much better answer there

[brazen leaf]

Find the smallest n>1 such that 3^n ends in 003

(Without CRT or Euler's Toient)

So I got that 3^n is congruent to 3 mod 8, so n is an odd number

and then there's x is congruent to 3 mod 125

not sure how to do that without euler's toient

(With Euler's Toient, 3^100 is congruent to 1 mod 3 so 101 would be the minimal n after checking that 20, 50 don't work)

[worn folio]

wouldnt 3^100 be 0 mod 3

oh mod 10

or 1000

[brazen leaf]

yea 1000

asking for the last 3 digits to be 003

[patent acorn]

well 3^n has to be congruent to 3 mod 5, so you can solve that first

you get n = 1 mod 4 i think

then you look at 3^n = 3 mod 25, and you already know that n = 1 mod 4 so that decreases the search space

3^(4k+1) = 3 mod 25, 3^4 is 81 which is 6 mod 25, so 6^k = 1 mod 25 is, uh, k = 0 mod 5?

(i am sleep deprived so while i think this method works i might not be computing the numbers correctly)

[brazen leaf]

oh that's a smart strat

so k is congruent to 5 mod 20?

and then do the same thing for mod 125?

[brazen leaf]

Oh hey I got it

Doing the same thing with 26^z gives z is congruent to 0 mod 5

And that gives all the values of n

Thanks for the trick

,rotate

[sterile pumice]

Couldn't find an attached image in the last 10 messages.

Oct 3, 2024, 12:54 PM

[brazen leaf]

,rotate

[brazen leaf]

For part a I proved there’s infinitely many terms that is divisible by 11
(Every n is congruent to 6 mod 11)

I’m not sure how to start b other than that every even digits palindrome is divisible by 11

[long lion]

nvm i can't read

[long lion]

wait yeah what is ur palindrome?

@brazen leaf

[brazen leaf]

Oh, 11

[long lion]

oh wait i'm dumb

i thought the palindrome was something in our arithmetic sequence

[long lion]

yh that works

[long lion]

so for b, rephrasing the problem

we want to show that there are infinitely many palindromes that are 1 less than a multiple of 9

(since a_n covers all numbers 1 less than a multiple of 19)

[long lion]

that's still a very daunting task

cus palindromes are weird

[long lion]

thinking along the lines of this, can u come up with a 'nice' sequence of palindromes?

[brazen leaf]

Ok thanks

I’m in class rn

[long lion]

kk

[brazen leaf]

Wait really?

Isn’t it congruent to n mod 9

So n is 9 will be a multiple of 9

[long lion]

sorry typo

19 rather than 9

[brazen leaf]

Oh yea

[brazen leaf]

I only got that palindromes with a factor of 11 in the sequence are congruent to 12 mod 19 when divided by 11

[long lion]

that's not particularly helpful

because it's hard to convert multiple of 11 into palindrome

it's much easier to start by thinking about a palindrome

and then proving it's in the sequence

also pls @me when u reply!

[brazen leaf]

Ok thanks

[forest plank]

Well

57000000...000075

Are all palindromes and with remainder -1 when divided by 19

[long lion]

interesting

that wasn't the construction i had

what did u do to prove +1 is divisible by 19? just write it all out & it works?

[forest plank]

I tried to find numbers of very simple form

570000000..000 is obviously divisible

And 76 is divisible

[long lion]

oh yeah 57 is a multiple of 19

[long lion]

yh yh makes sense

seeing that makes my construction seem a bit ott lol

[brazen leaf]

oh

I just used that example for my answer

but with no motivation

what was yours?

[long lion]

1111111111...111

i.e. look at (10^n - 1)/9

pray that (10^n - 1)/9 = -1 mod 19 has a solution mod 19

which it does

thus we have infinitely many n

[brazen leaf]

Oh

[vernal dome]

I have a basic question regarding the Cantor set. Each $x\in[0,1]$ has a base-3 expansion $x=\sum_1^\infty a_j3^{-j}$ where $a_j=0,1$ or $2$. Then the claim is that this expansion is unique unless $x=p3^{-k}$ for integers $p,k$. What's the problem when $x=p3^{-k}$ and why is it not unique? I'm trying to deduce this from the series expansion but I'm unable to.

[sterile pumice]

psie

[long lion]

in base 10

0.99999999999... = 1

basically that's the only time u'll run into problems

(or in base 3)

(0.22222222... = 1)

@vernal dome

[small sable]

Is that true, thought they aren't equal

[torn escarp]

they are equal

[north pagoda]

what's $\lim_{n\to \infty} \sum_{k=1}^{n} \frac{9}{10^k}$?

[sterile pumice]

Namington

[north pagoda]

or you may be more familiar with the binary analogue: whats $\lim_{n\to\infty}\sum_{k=1}^{n} \frac{1}{2^k}$?

[sterile pumice]

Namington

[north pagoda]

both of these limits are 1, and they correspond to the "decimal" expansions 0.9999... (in base 10) and 0.1111... (in base 2) respectively

[vernal dome]

Consider the above definition of a so-called proper expansion. The author goes on to prove every nonnegative real number has a unique proper expansion. I'm slightly confused about the condition a_k can not equal B-1 for infinitely many positive k. This is saying we don't allow e.g. 0.191919... in base 10, but what is the problem with this number?

It's not the case that it has trailing 9s, so isn't it the unique representation of some number?

[torn escarp]

it does allow it, but I think I see your confusion. When k is negative then B^{-k} is B raised to a positive power

so basically means it has only finitely many digits to the left, like you're used to

personally I would have just written this as a sum over a_k B^k and not a_k B^{-k}

[vernal dome]

yeah, I understand the first condition. Like you say, so we have finitely many digits to the left (otherwise the sum wouldn't converge either I think). But I don't understand the condition a_k not equal to B-1 for an infinite number of positive indices. Doesn't that not allow 0.1919...?

[torn escarp]

ah, they mean it's only B-1 for all k after some point

they're really just trying to get rid of the fact that 1=.999... effectively lets you represent any number two ways

looks like what they've written is just wrong

[silver oak]

it makes sense to me

0.1919... is allowed

there's an infinite number of 1s

which is what they want

it's all normal

infinite 9s is allowed as long as something else is infinite too

[small sable]

Keyword "limits"

Also isnt that first limit zero

Second limit too

Like denominator goes to infinity and that dominates the numerator

I also wonder if its indeed possible to represent that number as a limit, where the variable is indeed used. Like wouldn't this mean you can approximate irrationals really really well with just one limit

[north pagoda]

these are sums

they represent 0.9 + 0.09 + 0.009 + ... and 0.5 + 0.25 + 0.125 + ... respectively

we are taking the limit of the sum as we add more terms

so the sequences are 0.9, 0.99, 0.999, ... and 0.5, 0.75, 0.875, ...

both of these converge to 1

indeed, it is easy to prove that the limit cannot be less than 1, but also that the terms never exceed 1

therefore both limits must be exactly 1

and again, these correspond with infinite repeating decimals

0.999... is just compact notation for the series 0.9 + 0.09 + 0.009 + ...

which is 1.

[small sable]

Yea srry, just thought of changing it into a sum of limits, but ig that might not be allowed

But still, I thought infinite limits just define a value f(x) approaches (but never touches) as x grows. So kinda like defining the inconclusive upper bound of a function. Obviously if you round off the furthest 9 in that number, the result will be 1, which can explain why the limit is 1. But my thinking is that the number itself isnt 1

Ive seen other attempts of "proving" this by multiplying each side by 10^a, and then manipulating the results, but still that looked like a load of crap

[torn escarp]

do you agree that if |x-y|<k for every positive number k, then it must mean that |x-y|=0?

[small sable]

If you are restricting chaos regarding infinitesimals, then yea

and with the "for every positive number k" I assume infinitesimals are included. Which kinda changes my thinking in the text right above this

[torn escarp]

basically that's why I'm asking if you agree, since I'm just talking real numbers here, x, y, k are all real numbers only, no infinitesimals here

[small sable]

Ok, now I get where you are going at, it is indeed true that If we exclude infinitesimals (like just real numbers in standard analysis) then 0.999... = 1 (since we can't describe the difference between the two sides). But my argument is that we cant exclude that difference, and 0.999... = 1 - ε for some infinitesimal ε

[torn escarp]

idk anything about nonstandard analysis so you're on your own

I just accept |x-y|<k for all positive real k means |x-y|=0 so that means x-y=0, which for x=1 and y=.999... means they're equal to me

if you want to discuss nonstandard analysis you'll have to find a different channel cause this is just for elementary number theory so you're not really gonna find people who study that here

[small sable]

Yea, but that doesnt prove than 1 = .999, you just picked them and said "they're are equal to me". Like can you show |x - y| = 0 for those values

[torn escarp]

well I didn't give the values of k, I just outlined the idea

[small sable]

But isnt assuming they are equal implying k is 0

[torn escarp]

I didn't assume they are equal

1-.9=.1, 1-.99 = .01, etc so I'm saying |1-.999...| is less than .1, .01, .001, etc so any positive real k I pick will be either one of those or between any two

so it's based on that I'm saying |1-.999...| < k for all positive real k, and since |x-y|<k for all positive real k means |x-y| must be 0, then |1-.999...| = 0 and so 1-.999...=0 and so 1=.999...

I can see how that might not be true in nonstandard analysis, like I said idk any, but this is good enough for me

[small sable]

Ok cool I get your point, and your .1, .01 ... example is a good one. But my thinking is that the last "1" never disappears, if you understand what I am saying, as I said from the start, I might be wrong, but I haven't seen anything yet that really proves my thinking as such

[torn escarp]

well if you do that, I guess one way to put it is you're inventing new notation and you have to define what it means. Like if the 1 doesn't disappear I'm guessing you're saying there's something like 0.00...001

but what does it mean to have something after the ... or is that even a well defined idea at all just cause we can write it down?

I can only beat a dead horse and say I don't study nonstandard analysis so I don't know how that's defined if that's what they do or whatever haha

I'd be comfortable with saying something like real numbers are a special case of "rounding" hyperreal numbers or something in some sense, like real numbers are in the complex numbers.

[small sable]

Just because its not well defined doesn't mean it has no applications tho, its in a way something similar to i appr 200 yrs ago. Plus infinitesimals are greatly used in subjects such as calc

[torn escarp]

i didn't say that

[small sable]

Yea but 0.00.0001 is an infinitesimal

So am not inventing new notation or anything fancy

[lilac bronze]

Is this 0.99… vs 1 stuff?

[small sable]

But yea, we are indeed having trouble with standard vs non-standard analysis stuff, and thats what causing the confusion between both of us

[small sable]

mhm

[lilac bronze]

I think the thing here is like

You can totally consider the collection of decimal expansions, and put a lexicographic order on them

Lexicographic essentially being how words are sorted in a dictionary

This is usually how you compare numbers after all - you pretend 0-9 are the letters of some alphabet, and it’s essentially dictionary order

[lilac bronze]

In that case, the order on this set would have 0.999… < 1.000…, just because the first comes before the second in a dictionary

The issue is that the way we order real numbers is very close to a dictionary order, but not exactly the same as one

0.99… = 1 is essentially the only type of exception to that - the LHS clearly comes before the RHS in a dictionary order, and yet as real numbers they are equal

It’s not necessarily a weird thing to have two different ways to write down the same number

Like 1/2 is equal to 2/4 as rational numbers, but they also aren’t literally the same sequence of characters on a keyboard

There’s a sense in which 1/2 = 2/4 (as rational numbers), and a sense in which 1/2 does not equal 2/4 (as strings of characters)

[small sable]

Yea but you having like (n/(n+1)) = n/n for large n

Which is weird

[lilac bronze]

Similarly, there’s a sense in which 0.99… = 1 (as real numbers), and there’s a sense in which 0.99… does not equal 1 (as decimal expansions)

[lilac bronze]

This is false

[lilac bronze]

The key thing here is that real numbers are not the same as decimal expansions

[small sable]

Exactly

[lilac bronze]

Decimal expansions can be used to represent real numbers, but they aren’t typically how real numbers are actually defined by mathematicians

So it’s fine for the same real number to have two different decimal expansions, because decimals are not the fundamental object here

It’s like how the same place can have two different maps representing it

In this case, 1.000… and 0.999… are two different decimal expansions for the same real number

[lilac bronze]

It’s also unrelated to why 0.99… = 1, as real numbers

[small sable]

mhm

[lilac bronze]

The main reason why decimal expansions aren’t usually used to define real numbers is that it’s pretty hard to do arithmetic with them

Like how do you multiply 0.2735802937362… by 0.81929484762672…

Where they’re both infinite strings of digits

It’s not really obvious to me how you’d carry that out

And if you can’t even do addition and multiplication with the things, it feels pretty silly to call them “numbers”

[small sable]

I think it has something to do with zero multiplication

[lilac bronze]

So decimal expansions are representations of real numbers, but they aren’t usually what real numbers are fundamentally defined as

[small sable]

And multiples that result into a zero remainder

[lilac bronze]

Not entirely sure what you mean there

[small sable]

Was talking about concepts like √2 * √2 = 2,

[lilac bronze]

Right, but I’m talking about decimal expansions

Infinite strings of the digits 0-9

The main point is that it’s hard to implement addition, subtraction, multiplication, division on these

Like usually when you add whole numbers you start at the rightmost digit, and then do carrying

But for decimal expansions, there is no rightmost digit

So it’s unclear how to even try and do addition

Though it’s a good exercise to see how you might add two infinite decimals

[lilac bronze]

It’s easy to compare decimal expansions, cause you can just use a dictionary order

[small sable]

But what removes concepts and qualities of those from √2

[lilac bronze]

But +, -, x, divide are pretty fundamental to what numbers are

[lilac bronze]

This is kind of too vague for me to understand what you mean

[lilac bronze]

I’d recommend thinking about this

[small sable]

Its just adding the digits, ain it?

[lilac bronze]

How though

Because you can’t start at the rightmost digit

[small sable]

Obviously addition is complicated since it doesnt end

[lilac bronze]

That’s the point I’m trying to get at

[small sable]

But multiplication can terminate, i think

[lilac bronze]

How?

[small sable]

This

[lilac bronze]

If you can give an example of that, that would be useful

Remainders aren’t typically thought about when you do decimal expansions

[small sable]

I havent explored this so far, but there exists numbers a, b, where a * b = c*10^c + 0. And since you are supposed to move the ten component to the other side, you could have an expansion with all its digits having a zero remainder

Making it terminate the infinity, in a sense

Like think of the two expansions, a, b. Where h_d is the d-th digit of the expansion h. So am thinking you could have infinite expansions a, b. Where d is the subscript for all decimal digits of a,b and have a_d * b_d = c*10^k + 0.

[lilac bronze]

I’d want an actual example with actual numbers to follow what you’re saying

[small sable]

(NVM this, isnt valid) A trivial pair is z.0011001100110011... and y.11001100110011001100...

You can try figuring out the non trivial ones

[lilac bronze]

Are these a and b? Then what is c?

[small sable]

c is just a whole number, but ignore those values. I think they are wrong

Like c is what you are to carry on, and the 10^k is to show that its calculation in base 10

[lilac bronze]

Sure, the main issue here is that you have potentially infinite carries to do

[vernal dome]

but they say $a_k\neq B-1$ for an infinite number of positive indices. So $0.1919\ldots$ can not be allowed. There are infinite positive indices of $9$.

[sterile pumice]

psie

[silver oak]

yes
a_k = B − 1 infinite times, also a_k ≠ B − 1 infinite times

both are true, the second one is required the first one isn't

9 is the number they don't care about

[vernal dome]

ok 😅 that makes sense actually. Thanks for clearing up that confusion. The definition makes sense as it stands.

[silver oak]

so 0.2999... isn;t allowed

[calm hearth]

A classic

[warped coyote]

what are pirmitive roots

please

please

please

[crystal agate]

Primitive Roots are basically defined to be elements of U(n) of order phi(n)

[warped coyote]

why is it special

[crystal agate]

what that means is that their powers g, g^2, ..., g^{\phi(n)} = 1 are all distinct elements of U(n), because otherwise if two were the same we could divide to get g^k = 1 with k < phi(n)

but there are exactly phi(n) elements in U(n)

so these powers make up ALL the elements in U(n)

you could say that a primitive root generates U(n)

[warped coyote]

its when the smallest expoenent to the a is equal to 1 mod p is equal to phi (p) right

when does this come up

like why care about it

[crystal agate]

because like

these primitive roots generate the whole set of multiplicative units

so in a sense

we can study the group by just looking at one element

[warped coyote]

i dont know what you are talking about sorry

do you have a interesting easy number thoery problem

[patent acorn]

i mean sure, you could say that
or you could... not

an expression like "0.1111111111111111111..." just doesn't mean anything until you decide on what it means. you could declare that any infinite decimal expansion means the number 4 if you wanted to

even once you've said what finite decimal expansions are, if you try to extend that in the obvious way to infinite expansions you run into the issue that adding together infinitely many numbers doesn't have an obvious meaning

and so we just decided that, by definition, the value of an infinite decimal expansion is the limit of the values you get by chopping it off at finite places, where the "limit" is the real number that it gets arbitrarily close to; and so 0.99999999... is exactly 1, because its distance to 1 is less than every real number

we could have instead said that there is some fixed nonstandard natural number N, and the meaning of an infinite decimal expansion is that it's actually just N digits long and you take the nonstandard "finite" sum as a hyperreal, and then the difference between 0.9999999999999... and 1 would be an infinitesimal hyperreal number that you could reasonably write as "0.00000000...1"

and there isn't anything logically inconsistent about this notation, it's just not what we decided to do

[foggy aspen]

0/0=0 not undefined
You might tell me I’m wrong but hear me out
0/0 with repeated subtraction is undefined because we can’t subtract 0 because of the identity property of subtraction(n-0=n)
But division is also backwards multiplication
So let’s say:
6/0=C
A=6
b=0
Then we do:
Cx6=0
anything you multiply by 0 is 0
So C=0
0x6=0
Now if we flip it over to division
0/6=0

Therefore If we do the same for 0/0 we get 0(or undefined if your repeating subtraction)

[stuck mulch]

how do you divided by 0 tho

in 6/0=C

C is defined so that means 6/0 is defined

but its not

[stuck mulch]

you're back!?

[small sable]

Sorry for late reply, but tbh I don't understand anything that you wrote there, i might be just too tired or your text is jumpy. Could you clarify thx. Also an expression like "0.1111..." does indeed mean something, so I dont understand what you mean by your statement regarding that. I dont know how you can declare that any infinite decimal expansion means the number four, I believe this is impossible both partition-wise and arithmetic wise. By definition, a non constant limit is something a number approaches but never reaches, (i think). So defining an infinite expansion of this sort as its limit, is crazy to me, and I dont know who is "we" that you are referring to (am down for enlightenment). The last part of your text seems to partly support my thinking, except the last part where you bring back the "we" person. So overall, it would be a pleasure if you elaborated more, thanks.

[patent acorn]

Also an expression like "0.1111..." does indeed mean something
it means something because people decided it means something

what happened is not that humanity studied the cosmic microwave background and discovered that the meaning of an infinite decimal expansion was declared by God

like all notation it's just a convention, the only reason to prefer one notation over another is how useful it is, not whether it's "correct" because there is no objective standard to judge that against

[small sable]

Is this math philosophy?

[patent acorn]

i mean it's arguably closer to philosophy than most concrete mathematical arguments but not in the sense where you're going to find anyone reasonable who disagrees with what i said there

[small sable]

Coz factually that expression does mean something, and saying it doesn't, is somewhat a personal philosophical belief. Saying "it mean something because people said it means something" isnt a valid argument too, there exists a public reason why people decided it means something, and to counter that, you need to provide a reason why it absolutely means nothing. But thats just my thinking

[warm coral]

It is a valid argument, actually. Really, infinite decimals do not make sense until you define them to make sense, as decimals are given a value using addition and powers of 10, and infinitary operations aren't standardly defined

[patent acorn]

factually that expression does mean something
yes, it does, to humans, on earth, in this period of time

[small sable]

Yea somewhat similar thing can be said for imaginary numbers

[warm coral]

Yup

Quaternions too

[patent acorn]

notation is just at least partially arbitrary, even when there's a sort of reason for it it's not a mathematical fact in the same way, because the reasoning is more about it making sense from a human angle

[small sable]

But it doesnt mean that they mean nothing, they literally have applications, something that means nothing cant have applications. Apart from zero (which means something)

[patent acorn]

the natural numbers are $\mathbb{N}$, not because the set of natural numbers is actually made out of four lines in some mathematical way, but because our word for them starts with the letter N

[sterile pumice]

bee [it/its]

[patent acorn]

"they mean nothing" is not what i claimed

the string of symbols "0.11111..." does not have intrinsic meaning

[warm coral]

They dont mean nothing, but rather we've given them meaning which happens to be consistent and useful

Well "happens to be" isnt the right wording

[patent acorn]

as in, you can't take an automated theorem prover that only knows the symbols $\to$ $\neg$ $\forall$ $=$ $\in$ and the axioms of ZFC, and prove as a theorem that $0.11111... = \frac 19$, unless you use some mechanism of introducing definitions of new symbols to tell it what those symbols mean

[sterile pumice]

bee [it/its]

[patent acorn]

starting from absolutely nothing, you wouldn't even have the concept that "1" is supposed to represent the number one

[small sable]

Isnt that math

[patent acorn]

?

[small sable]

Like arent we the automated theorem provers, and haven't we evolved to prove/disprove that equation. What am saying is, is that prover is good enough, it will be able to prove/disprove/backoff any theorem you assign it to

No matter what base/foundation you give it

[patent acorn]

well that means the prover isn't very good at all

because it can prove things that aren't true, and that don't follow from the axioms you gave it, so it's not actually useful for discovering truth

[small sable]

I didnt say only prove

I stated three alternatives

[patent acorn]

ok well i don't know what exactly you mean by "backoff"

[patent acorn]

but no sound prover with the properties i specified here would either prove or disprove this statement

[small sable]

Incompleteness theorem

[patent acorn]

unless ZFC is inconsistent

[patent acorn]

because i mean that you would input the literal symbols "0.11111..."

and it would have absolutely no idea what this means, because you have only told it about five symbols and this is not one of them

[warm coral]

Well it's proven that given a statement you cannot generally prove whether it's true, false, or undecidable, as i believe that's adjacent to the halting problem?

[patent acorn]

yeah that is equivalent to the halting problem

[warm coral]

Yoo my limited knowledge is paying off

[patent acorn]

(unless the system is inconsistent in which case it's trivial)

[warm coral]

Lol

[warm coral]

Right, the specific statement one would be more interested in proving is that i.e. the cauchy sequence 0.1, 0.11, 0.111, ... converges to 1/9
as that is the meaning we've given to 0.111...

[patent acorn]

in the same way that no amount of mathematical knowledge would allow you to evaluate the truth of the statement "每个非负整数都是四个平方数的和" if you don't know enough chinese to understand what the statement actually says

[small sable]

Where did the statement come from

Eventually you will encounter or formulate an english/native version if it has meaning

[patent acorn]

languages are made up by humans, and mathematical notation is just a specialised somewhat-constructed language for conveying mathematical ideas

[patent acorn]

yes you will

and even after doing that you will still not be able to decide the truth of the statement in chinese

because you won't know which of the english statements you've discovered is equivalent

[small sable]

If its the same statement, why not?

You just wouldn't know that its the same statement

[patent acorn]

i mean in the sense that if someone asks you "is the statement '每个非负整数都是四个平方数的和' true?" you won't know the correct answer

[small sable]

Why are they asking me Chinese if they know I dont know chinese, obviously they would know that its true since they are bilingual

[patent acorn]

well they say that factually the phrase "每个非负整数都是四个平方数的和" does mean something, and that any sufficiently good prover should be able to prove/disprove/backoff any statement you give it

expecting you to understand chinese is exactly the same as expecting a formal theorem prover to understand "0.11111..."
it's not an issue of mathematical knowledge, it's an issue of just knowing what meanings have been assigned to the symbols

[small sable]

yea, but chinese isnt 0.1111...

[warm coral]

To the solver they're the same kind of nonsense

[patent acorn]

and you could instead just assign different meanings, maybe in some other language "每个非负整数都是四个平方数的和" has a completely different meaning

[patent acorn]

what's the difference?

[lilac bronze]

essentially there’s a difference between syntax (just symbols) and semantics (their interpretation)

[small sable]

I dont know how to answer this tbh. But i just thought its trivial

[lilac bronze]

like how the word “off” is the same sequence of letters - o, then f, then f, but can mean different things in different contexts

getting off something is different to turning off something

[warm coral]

"The proof is trivial and left as an exercise to the reader" isnt valid as an argument when you're explicitly asked for it x3

[patent acorn]

yeah i think the reason you don't know how to answer it is that the difference just doesn't exist

there was a point in human history when nobody had invented any mathematical notation, and if history had gone differently from that point then maybe today we would be using entirely different symbols

notation is just stuff humans invented to make communication easier, they're logograms in a language that just doesn't really have a spoken form

[small sable]

Ok, just thought of this. I think this is similar to our vision, even if there is all sorts of light around us, there is only specific lights that our eyes do see. So i think it would be similar to the solver, if the solver isnt capable of interpreting the statement, obviously it wont be able to prove it, and this would mean that the solver isnt the formulator of the statement, ot its a random false statement

Since any formulator of a statement has meaning attached to that statement

[lilac bronze]

the “meaning” here is what’s called semantics

but the actual symbols you use is what’s called “syntax”

[small sable]

And you cant give a solver an assignment to prove something, if its foundationally incapable to interpret the said thing

[lilac bronze]

yes, that’s the idea

semantics is all about interpretation

giving a meaning to a sequence of symbols

sometimes the same sequence of symbols can have different meanings in different contexts

[lilac bronze]

like here with “off”

conversely, sometimes different sequences of symbols can have the same meaning

like “one” and “1”

[small sable]

Yea correct

[lilac bronze]

that’s why there’s this separation between syntax and semantics

between the symbols you use, and how you interpret them

[small sable]

Or you could say its something humans invented to eliminate the Chinese scenario you brought up, so not "its just stuff"

And there exists reason why the "invention" occured, and many people, both including the chinese speakers and the english speakers agree to that same invention, even though their statements werent originally understandable by the other party

[patent acorn]

well still, none of that makes it not a human invention

and in particular none of it is a mathematical necessity at all

you can do mathematics using nonstandard notation and it won't change any of the actual mathematics

declaring that "0.111111..." is now your notation for the number 4 will confuse a lot of people but it won't make the theorem prover any more confused than using "0.11111..." for 1/9 would, because they are both just notational choices, when you ignore humanity and just look at the mathematics itself

[small sable]

But isnt that like standard for systems of the sort similar to n-adics. But obviously you would need to announce the system where you are defining 0.1111... as 4.

And this restricts the systems where this definition is valid

[patent acorn]

But isnt that like standard
it is standard for humans which means we're ignoring that

But obviously you would need to announce the system
you need to announce it either way

[small sable]

No

[patent acorn]

in practice, on Earth, people often do not announce that they are using the standard convention for what infinite decimals mean, and that's usually fine

[small sable]

There exists a global "default" system that people automatically relate to such announcements

[patent acorn]

yes, on Earth, among humans

[small sable]

Can you name a system thats not on earth

Or any non-human life thats not on earth

Dont try to say God, or aliens. Because those, in this context, are indeed regarded as "human inventions"

[patent acorn]

yes, several of them

or i don't know what exactly the systems would be called or what the details would be but i can at least identify them

[small sable]

Plus you dont need to announce you are using the standard convention for anything, i thought thats why standard conventions exist

[small sable]

Name some

[patent acorn]

how about: fully formal ZFC, it's entirely abstract and therefore not really located anywhere and therefore not located on earth

alternatively, the notation used in the fictional setting where i am approximately the median person

[small sable]

But you just invented it, isnt that then a human invention?

[patent acorn]

humans did discover it

but it still existed even before that

[small sable]

Can you prove its pre existence?

Without inventing new stuff

Also without inventing ZFC

[patent acorn]

well for ZFC in particular that might be a bit difficult, but the universe had been running on the laws of physics for billions of years before humans discovered the laws of physics, or even like, numbers

[small sable]

Just noticed, you are now shuffling between "invention" and "discovery"

[patent acorn]

humans still don't have a theory of everything and yet it clearly should exist

[patent acorn]

yeah that's because they're the same thing

or at least not as distinct as you might think they are

[small sable]

No it doesn't, you cant have a theory of everything

[patent acorn]

why not?

[small sable]

Would personally say its somewhat Similar to Godel's theorem

Aswell as the halting problem combined

[patent acorn]

did humans invent wheels, or discover wheels? at a certain point the answer is kind of just "both??", it is a fact about reality that humans discovered that wheels are useful

[patent acorn]

yeah that's not actually a reason

once again i suspect this is "you can't articulate the reason because there isn't one"

[warm coral]

I think you'd have to define what you mean by "theory of everything"

[patent acorn]

and/or "you have misunderstood what a theory of everything is supposed to be"

[warm coral]

Because i can see the definition being a bit fuzzy

And will differ from person to person

[patent acorn]

basically just "a complete description of the laws of physics"

[warm coral]

Ohh we're talking about physics

I thought you meant "theory of everything" relating to math x3

[patent acorn]

notably it doesn't have to be a computable description, or a description from which everything is derivable by FOL syntactic proof, and so the halting problem and incompleteness theorems are both not really applicable

[warm coral]

No that makes sense

[small sable]

You cant exclude them tho, thats not viable

Nor acceptable

[patent acorn]

...what do you mean by that

[small sable]

Do your regard the "everything" to be formal

[patent acorn]

what do you mean by that

[warm coral]

I do not regard "everything" to be an evening dress

[patent acorn]

i think a lot of things in the universe aren't done in accordance with convention or etiquette, aren't suitable for and don't constitute an official or important occasion, aren't officially sanctioned or recognised, and aren't clothing

[warm coral]

Idk about you tho

[small sable]

Also isnt it probable that the exotic "invention" isnt also invented by the natives there

[small sable]

So you are now going to have a theorem that says A is true, but also the negation of A is true, which implies A is nothing. And the negation of nothing is something. Which brings in a contradiction. Since both nothing and something cant be true

[patent acorn]

no i'm not going to do that actually

[small sable]

But then it isnt a theorem of everything really

[patent acorn]

well i wasn't talking about a theorem of everything

i was talking about a theory of everything

[small sable]

Do not proven?

So*

[patent acorn]

which is a complete description of the laws of physics

it has nothing to do with provability in any way

unless provability turns out to be a part of the universe's laws of physics, in which case it would have something to do with provability

[torn escarp]

this isn't number theory go to #math-discussion or somewhere else please - minimod merosity

[small sable]

Yea lol, we were talking about number theory in general but somewhere branched to other topics 😂

[small sable]

like from here towards now

[sacred junco]

can someone give a hint?

how to prove that if $p$ is prime then $p^{p+1}+(p+1)^p$ is not a perfect square?

[sterile pumice]

bucketbot

[long lion]

yay we've eliminated infinitely many primes!

that means we're left with...infinitely many primes

[long lion]

consider this:

we can eliminate the p=2 case by hand

now if p>2 that means p+1 is even

so p^(p+1) is a square

so consider trying to factorise using difference of 2 squares

[torn escarp]

I found a solution but I'm not really satisfied with it since I feel like there might be an easier way.

actually I jumped the gun I don't even have a solution 🤣

[sacred junco]

[sacred junco]

this doesn't seem to lead anywhere either

[torn escarp]

what I did was take the difference of squares and find the gcd of the two factors to be 2

that starts to tell us one term is divisible by 2 once and the other term has at a power of 2^{p-1} dividing it, since it has to match the power of 2 dividing (p+1)^p

[sacred junco]

makes sense so far

[torn escarp]

that's originally where I made my mistake in thinking I had a solution so haven't thought further than that

I guess the tricky part to getting there might be showing the gcd of the two factors of the difference of squares is 2, lmk if you're interested in that or not since it may or may not actually be useful but might be fun to know

[sacred junco]

I was thinking about using Euclidean algorithm

but

now that you're saying it's tricky I'm thinking it won't work

can you tell me your way?

[torn escarp]

yeah Euclidean algorithm

you might be good then, it's just they're variables not numbers that's really all I mean

[long lion]

huh i think i made a similar mistake to u

accidentally calculated gcd to be 1 instead of 2

[long lion]

where does this problem come from?

[torn escarp]

I guess the other two options I was thinking of trying is some kind of quadratic residue thing OR try some kind of bounding argument for where squares are on the real number line with an inequality

[sacred junco]

a friend told me about it, no idea where they got it from but they also don't have a solution

[runic token]

wait omg ive seen this one before

i actually couldn't figure this one out on my own sad to say

i know a solution tho

[long lion]

do u remember the source?

[runic token]

yeah my senior year prof gave it to me

[long lion]

ic

do u remember roughly what to do?

i tried a bunch of values on wolframalpha and it seems to always be squarefree

[runic token]

anyways the hint i needed at the time but didn't know was that the ||gaussian integers are a ufd||

[long lion]

yeah ok thought about that but i didn't see how ||gaussian integers came into this cus we could factorise as DOTS rather than doing that||

[runic token]

use contra

[white turtle]

Hey, I have a number theory question with application in group theory:
if n is an integer and l is arbitrarily fixed between n and 1,
Can you guys help me find the number of the solutions to xl = l mod n, where x must be coprime with n

any ideas would be really appreciated

[runic token]

oh, wait

i misread the question, sorry

my question was a little different i dont think the same method will apply

[sacred junco]

I was confused for a moment because afaik it's supposed to be solvable using more "elementary" methods

but still I'm not sure

[torn escarp]

I'd divide out the gcd(n,l) from n and l since that part of the solution is already "made"

so call g=gcd(n,l) and l' = l/g and n' = n/g you'd have xl'=l' mod n' so now everything is relatively prime, you see where to go from here?

[white turtle]

Thank you! mm let me think

no I dont see actually

so if everything is relatively prime, what does that tell us on the number of solutions?

[little trench]

How can you prove that there are infinite primes that are also the sum of two squares? This is true since it is equivalent (I think) to asking if there are infinite gaussian primes (since all gaussian primes have prime norms, gaussian norms are sums of two squares) which is true, but I want to know how to prove it without using that fact.

[torn escarp]

they're all of the form 1+4n and there are infinitely many primes of this form by Dirichlet's theorem

I'm pretty sure there's an elementary way to prove there are infinitely many primes of the form 1+4n without appealing to dirichlet, but I forget how it goes

something with quadratic reciprocity and/or cyclotomic polynomials I think

[little trench]

What about 9 + 4 = 13? can write that as 1+4n

[torn escarp]

1+4*3

[little trench]

Oh right

[torn escarp]

it's called Fermat's christmas theorem

[little trench]

So can 1+4n always be written as a sum of two squares or just in terms of the primes of that form?

[white turtle]

@torn escarp sorry to bother, so can you give me hints to my problem?

[torn escarp]

yeah sure, this means l' is in the multiplicative group (Z/n'Z)*

[white turtle]

oh okay so then l'=1

I mean x sorry

[torn escarp]

yeah, sort of be careful, x=1 mod n'

[white turtle]

oh yes!

[torn escarp]

and what you need is

ok cool

[white turtle]

I just realized as you wrote

[torn escarp]

I'm gonna go make some lunch I'll be back if you're still workin

[white turtle]

thanks a lot

Im good at other fields of math but somehow number theory feels a bit unnatural to me

any tips on how to get better?

[torn escarp]

honestly that's what attracted me to the field in the first place too

mainly I guess I just gained intuition by enjoying thinking about and working on things over time

[white turtle]

now im just stuck with finding the minimal k s.t kn'+1 < n

is there a way to explicity find it without floor function?

[white turtle]

thanks!

[torn escarp]

just to clarify, this is a different question right?

before you were counting number of solutions mod n, now you're finding a minimal one between 0 and n right

I guess you could just say k=0

although this won't always get you the minimal x, it'd get you x=1

I forget, can l=n? then x=0 is possible

I might have just been solving for counting in a more general case than you actually care about

[white turtle]

yes because then k gives the number of solutions to my problem

since x is of the form kn'+1 since x=1 mod n'

[torn escarp]

how I was thinking to do it is think of it as x=1+kn' mod n and let k=a+bg with 0<=a<g and 0<=b<n'

really just that kn' = (a+bg)n' = an' + bgn' = an' mod n is the idea, so now how many choices are there for a?

(I used the fact gn'=n = 0 mod n)

maybe seeing an example would help, we're sort of like trying to move "up" from mod 4 to mod 12 because of our work with simplifying with the gcd earlier

maybe picking 4 and 12 is too terse to call it a real "example" Lol

[white turtle]

sorry I gtg, are you open to discussing it more in dms some other day? But anyway thanks for you help!

[torn escarp]

this is a pretty dead channel for the most part, I prefer talking in here since there's latex too

just ping me whenever though

[torn escarp]

I'll go ahead and just put the solution I have in mind and spoiler it if you wanna look I don't want to leave it hanging so close to the end.

||We know that x=1 mod n' so now it's a matter of saying what can we pick for x=1+kn' mod gn'. So we can write k = a + bg with 0<=a<g and b can really just be any integer; we don't care at this point since gn' = 0 mod n. So all valid solutions will look like:

x=1+(a+bg)n' = 1 + an' mod n.

Since 0<=a<g we have exactly gcd(l,n) possible choices for a, which is the answer. Those will all work when we reduce back down to 1 mod n'.

As a sanity check, if l=n then we'd have xl=l mod n become 0=0 mod n so everything is a solution. gcd(n,l) = n in that case which is what we expect.

Similarly if gcd(n,l)=1 then we can just safely multiply by l^-1 and get x=1 mod n getting that there is exactly 1 solution.||

[lethal cedar]

if we have three congruences, say x = a (mod q) and y = b (mod w) and z = c( mod e) and say x = r when solving first two of these equations then can we reduce the system to x = r (modqw) and z = c(mod e)?

[torn escarp]

not as you've written it, I don't see any reason to combine the info for the congruences for x and y

[lethal cedar]

is there a way to combine the two?

[torn escarp]

you haven't really given enough information

these are just unrelated facts so it doesn't really make sense

do you have some specific problem you're looking at trying to solve?

[lethal cedar]

lets take x = 5 mod 3, x = 4 mod 5, and x = 2 mod 7

then x = -1 solves the first two equations, and so I was wondering how we can simplify the first two using this x

[torn escarp]

ok this is a different thing altogether, before you had x, y, z and now they're all the same

so the good news is there is a way to combine them, it's called the chinese remainder theorem

[lethal cedar]

im really dumb sorry, this was the set up I wanted

[torn escarp]

since 3, 5, and 7 are all relatively prime to each other, you can combine them into one thing that's x= something mod 105

there's a handful of ways to do it, I guess the simplest is to just do it one at a time like x=5 mod 3 means you can take x=5+3n = 4 mod 5 and solve for n there, then repeat the idea for mod 7

so first off do you understand why x=5+3n comes from x=5 mod 3

[lethal cedar]

yes

[torn escarp]

then we can basically plug that in to the mod 5 congruence to get
5+3n = 4 mod 5

can you solve for n now

[lethal cedar]

ah right

wait

hm so can we not like simplify the first two only?

[torn escarp]

not really

there's a complicated way of doing it to combine them all but it's more work really

[lethal cedar]

so unlike in lin alg, we can't get a congruence of the form x = something (mod something) even if we solve two of them?

[torn escarp]

I have to go oven timer just went off

[lethal cedar]

ah ok thank you for your help

[torn escarp]

I'll be back in 30 min or hour or so, you're welcome

[river sphinx]

How many positive integer divisors does 7! have? (Also what is 7! I'm quite new to these types of questions)

[torn escarp]

! means factorial, it's the product of the positive integers less than it, for instance 3! = 1*2*3

as far as counting divisors, there's a trick for counting them based on the prime factorization of the number

I feel like you probably should read about those things or try to figure something out

[river sphinx]

I see, so it's the number multiplied by everything before it.

[river sphinx]

A trick?

Yeah, my school doesn't offer this class. I was just curious because my friend opt for it.

[torn escarp]

yeah, well I guess since this isn't your homework or something I can just show you a couple tricks

it might be easier to show the idea through the sum of divisors as an example

like the sum of divisors of 12 for instance, we can factor it as 2^2 * 3^1, the prime power factors are what we care about. Individually the sum of divisors of 4 are 1+2+4 and for 3 is 1+3. You can then multiply these to get all divisors of 12 are (1+2+4)(1+3) and you can see when you expand that out you'll get all combinations of all the prime power factors

[river sphinx]

woa

[torn escarp]

this kind of trick is pretty general and well studied, these are called multiplicative functions

but yeah, so same thing for counting the divisors of 12, except instead of literally putting the divisor in, we can just put a 1 there. So the number of divisors of 12 is (1+1+1)(1+1) = 3*2=6

of course you can just shortcut to using the exponents on the prime factors

2^2 * 3^1 the exponents were 2 and 1, so really we're doing (1+2)(1+1) (one more than the exponents on all the primes multiplied together)

so for your problem, you just gotta determine what power of 2 divides 7!, what power of 3 divides 7!, etc

there are some tricks you can try to figure out here or you can just grind it out cause 7 is small

but the fact that they're consecutive sort of helps make it a bit easier

[river sphinx]

I see

[torn escarp]

lemme know if you need help working any of that out I just kinda threw a lot of info at you lol

[river sphinx]

Yeah, I'm just trying to process the information.

[forest plank]

Hello guys 🤠👋

I've been thinking about bezouts identity (particularly, case gcd = 1), and I think I came up with something that I've never yet seen in a introductory textbook (maybe that's just because I haven't read a lot of textbooks). But I think, it provides some intuition and depth to the concept.

Uhmm any way, the idea is that finding the coefficients for the identity is actually about finding a rational approximation to the fraction a/b (or b/a) 😯😯

Also there's a cool way to find the coefficients, using a kind of a binary search/bisection algorithm, that also has quite a nice visualisation/geometric interpretation.

This may not be very rigorous, but at least I think it's more intuitive and visual than the 2 most common proofs found in textbooks? (The extended Euclid algorithm one, and the one using ideals)

I post on pastebin, so as not to flood the channel https://pastebin.com/TVELrswY

[west glade]

well there is the obvious disadvantage that it takes much longer to use that algorithm (at least for your example, dunno asymptotically)

but very interesting perspective

[torn escarp]

I think this is called the mediant for making farey sequences. I only vaguely remember reading about this a while back and didn't get into it, at least you might want to check out calkin-wilf trees and stern-brocot trees I think they're either what you're doing or related.

[urban dust]

I've seen this in Elements of Number Theory by Stillwell, Sections 2.7/2.8. He calls it the vector Euclidean Algorithm and connects it to Farey fractions and Stern-Brocot tree as mentioned by Merosity.

[torn escarp]

Find all primes p, q such that 5^p + 5^q = 0 mod pq.

Question was partially solved here but incomplete:
#help-48 message

[dusky aspen]

How dos this proof look

So We wish to prove the following axiomatically :- $lcm(a,b)= \frac{ab}{gcd(a,b)}$.|
\
We use the following definition to do the same:- A number $n$ is said to be the lcm of two numbers $a,b$ if
(i) $a \mid n \land b\mid n$
\
(ii) $e \mid n \land e \mid b \implies e \geq lcm(a,b)$.
\
Proof:- It follows that $a \mid \frac{ab}{gcd(a,b)} \land b \mid \frac{ab}{gcd(a,b)}$ trivially.
\
\
We now wish to prove :- $a \mid e \land b\mid e \implies e \geq \frac{ab}{\gcd(a,b)}$.
\
$e=ak_1; e=bk_2$
\
we thus have $e^2 =ab k_1 k_2 ; k_1,k_2 \in \N$
\
$\implies \frac{e^2}{\gcd(a,b)} = \frac{abk_1k_2}{gcd(a,b)}$
\
\
It's evident that
\
$\frac{e^2}{\gcd(a,b)} \geq \frac{ab}{\gcd(a,b)}$
\
\
so
\
$e^ 2\geq (ab) \implies e \geq \frac{ab}{e}$
\
But it's evident that $e \geq gcd(a,b)$.
\
so
$e \geq \frac{ab}{e} \geq \frac{ab}{\gcd(a,b)}$
\
Which proves that
$e \geq \frac{ab}{\gcd(a,b)}$
\
This proves $lcm(a,b) = \frac{ab}{\gcd(a,b)}$
\
\
I have to note this proof assumes $lcm(a,b) > gcd(a,b)$

[sterile pumice]

Veni, vidi, perii is $\R - \Q$

[torn escarp]

are you using two separate notations for gcd and lcm?

[dusky aspen]

wdym

[torn escarp]

these, I forget what they mean

lcm or gcd

[dusky aspen]

"AND" logical connector

[torn escarp]

I skimmed it and thought these were all in absolute value bars but they're "divides" lol

[dusky aspen]

Sorry, that was rude

[torn escarp]

lol no it was funny

personally I would remove as many logical symbols as possible, that's a pretty common stylistic choice. At least I can say I personally am not a fan but not too serious imo

well ok maybe you're not actally looking for that kind of critique, just first thing I notice as I get started actually reading it.

[dusky aspen]

So is it fine

[halcyon osprey]

Some symbols can be fine/useful, but outside of logic you should never ever be using ^ or V to denote “and” or “or”

[torn escarp]

sorry got distracted, gotta go

[halcyon osprey]

(Imo)

[dusky aspen]

Got it

[halcyon osprey]

@dusky aspen I just read through your proof and it was good up until the 4th line from the bottom. You say

e >= gcd(a,b)

Which of course I agree with. You then however use that to say

ab/e >= ab/gcd(a,b).

Because e and gcd are on the denominator, this inequality should be the other way. You’re going to need to be more economical with your bounds on e to show it’s greater than ab/gcd

You’re really probably going to need to make fairly significant changes. The main issue right now is that the statement is only true because k1 and k2 are not just any integers, but ones such that b | ak1 and a | bk2.

Without using this info somehow, you’re not going to be able to show what you want.

[dusky aspen]

I see. Thanks

I have a class now, will try correcting it after class

Is the key idea fine though

[forest plank]

Only case p,q odd ≠5 left

5^(q-1) = -1 (p)

This means -1 is a qr mod p. So p = 1 (4)

Likewise q = 1(4)

But then 5^(q-1) = 5^(4k) = -1 (p)

So -1 is a quartic residue mod p and q

🤔🤔

[halcyon osprey]

Maybe, it’s not how I would go about it

I would say this

The problem is stating a certain duality between gcd and lcm

This suggests you might want to show that e can’t be less than ab/gcd because then we would get something dividing a and b which is greater than the gcd

Tl;dr you need to use the fact that the gcd is the greatest common divisor

[dusky aspen]

Ah

okay

thanks

[dusky aspen]

So We wish to prove the following axiomatically :- $lcm(a,b)= \frac{ab}{gcd(a,b)}$.|
\
We use the following definition to do the same:- A number $n$ is said to be the lcm of two numbers $a,b$ if
(i) $a \mid n \land b\mid n$
\
(ii) $e \mid n \land e \mid b \implies e \geq lcm(a,b)$.
\
Proof:- It follows that $a \mid \frac{ab}{gcd(a,b)} \land b \mid \frac{ab}{gcd(a,b)}$ trivially.
\
\
We now wish to prove :- $a \mid e \land b\mid e \implies e \geq \frac{ab}{\gcd(a,b)}$.
\
$e=ak_1; e=bk_2$
\
we thus have $e^2 =ab k_1 k_2 ; k_1,k_2 \in \N$
\
$\implies \frac{e^2}{\gcd(a,b)} = \frac{abk_1k_2}{gcd(a,b)}$
\
\
It's evident that
\
$\frac{e^2}{\gcd(a,b)} \geq \frac{ab}{\gcd(a,b)}$
\
\
so
\
$e^ 2\geq (ab) \implies e \geq \frac{ab}{e}$
\
But it's evident that $e \geq gcd(a,b)$.
\
so
\
$e \geq \frac{ab}{\gcd(a,b)} \geq \frac{ab}{e}$
Which proves that
$e \geq \frac{ab}{\gcd(a,b)}$
\
This proves $lcm(a,b) = \frac{ab}{\gcd(a,b)}$
\
\
I have to note this proof assumes $lcm(a,b) > gcd(a,b)$

[sterile pumice]

Veni, vidi, perii is $\R - \Q$

[dusky aspen]

Is this better

[dusky aspen]

I tried another line of appraoch

[halcyon osprey]

As soon as you say e^2 >= ab, you’ve thrown away too much information

The e^2 thing as a whole may not be the way to go

Let me ask this perhaps