elementary-number-theory

[torn escarp]

and just think of it generically like $$\sum_{d|n, d\le \sqrt[3]{n}}\varphi(d)$$

[sterile pumice]

Merosity

[torn escarp]

or at the very least handle the perfect cube case separately idk

should we be throwing other stuff at this too like the abel summation formula

what kind of tools can we throw at this thing

[verbal axle]

abel might be overkill, at least given the context I got this problem from

[errant otter]

tools? you mean... murder weaponry?

[verbal axle]

ok tbh p^(1/3) is a very small number compared to p^(1/2) as p gets large

do the number of divisors of p^(1/3) are less than p^(1/3)

so $|{d \in \mathbb{N} \mid d | p^{1/3}}| < p^{1/3} < \sqrt{p}$

[sterile pumice]

ForJoke

[verbal axle]

oh wait

so $\sum_{d | p-1, d < p^{1/3}} \varphi(d)< p^{1/3}\times p^{1/3} < p$

actually this does not go to 0, nvm

[sterile pumice]

ForJoke

[verbal axle]

what instead of looking at this, we looked at $\sum_{d | p-1, d \geq p^{1/3}} \varphi(d)$

[sterile pumice]

ForJoke

[verbal axle]

but $\sum_{d | p-1, d < p^{1/3}} \varphi(d)< p^{1/3}\times p^{1/3} = p^{2/3}$

[sterile pumice]

ForJoke

[verbal axle]

which is good enought right?

cuz $\frac{p^{2/3}}{p-1} \to 0$ as $p \to \infty$

[sterile pumice]

ForJoke

[verbal axle]

@torn escarp I think instead of bounding it above by \sqrt(p) we bound it above by p^{2/3}

[torn escarp]

interesting idea

[verbal axle]

yeah p^{1/2} seemed too hard lol

[torn escarp]

unfortunately p^(1/2) < p^(2/3)

so I think that won't for us

[verbal axle]

its fine tho

my goal was to show that the sum divided by varphi(p) goes to 0

and p^(2/3)/p-1 goes to 0

thank you for the help

[torn escarp]

oh the final sum is bounded by that you're saying

[torn escarp]

I'm too tired ot check I didn't end up sleeping earlier, but I'll take your word for it, you're welcome 😛

[verbal axle]

Guys what is an elliptic curve? The definition used in my class makes 0 sense to me

“All rings contained in F”???

[still flare]

It says "containing," not "contained in"

There are some typos, for example there shouldn't be an 'and' there

It ought to be "An elliptic curve E over F is a planar cubic curve" (i.e. it is defined by a cubic polynomial f) "such that for all rings R containing F, we have (condition listed)".

[verbal axle]

I couldn't come up with any examples of elliptic curves

so if we look at F = Z/3 for example

what does it mean for a ring R to contain Z/3?

[verbal axle]

I see, sorry for that

[still flare]

it means Z/3 is a subring of R.

[verbal axle]

are there any notable rings that come up immediately to mind? Just so I can have a feel of what its trying to say

[still flare]

Sure, the algebraic closure of Z/3 comes to mind.

Or perhaps GF(9)

[verbal axle]

what is GF(9)?

[still flare]

You could keep it way simpler and let your field be Q, or maybe even C.

GF(9) is the unique (up to isomorphism) field of order 9

[verbal axle]

oh I see I see

[still flare]

Called GF for Galois Field

[verbal axle]

ok say we considered Q

[still flare]

I am going to sleep, so I hope someone else takes over.

[verbal axle]

ight np

[torn escarp]

might also help to see non-examples too like y^2=x^3 it's a planar cubic but is not smooth - graph it in desmos to see that

if it has a singular point it turns out we can just parametrize them, so we already can easily describe their rational points, so they're boring

[verbal axle]

What I don’t understand is the whole “rings that contain F” thing

The smoothness is a nice enough condition tbh

[torn escarp]

I dunno, probably they just are trying to say it can be seen contained in the larger rings if you want with no problem

the discriminant being nonzero is equivalent to this smoothness condition, and once it's nonzero in F, it's gonna be nonzero in all R containing F too

I guess they're just anticipating this to make it seem like it's some amazing strong extra condition you get for free, idk

[verbal axle]

So in R can i just treat them as smooth cubics in 2 variables?

[torn escarp]

R being reals or a commutative ring?

[torn escarp]

well, no that's not enough otherwise we might erroneously call y=x^3 an elliptic curve* because it's a smooth cubic curve in two variables

[verbal axle]

Reals

[torn escarp]

this is actually a projective transformation away from y^2=x^3, I've just pushed the problematic point to one of the points at infinity

[verbal axle]

Interesting

Don’t quite understand that still ngl

[torn escarp]

yeah I imagine you haven't really learned that yet about like homogenization and projective coordinates, but maybe

[verbal axle]

This was meant to be an “intro” number theory course where our prof assumed 0 abstract algebra knowledge 💀

[torn escarp]

you might not cover that stuff at all in this course for all I know then

[verbal axle]

Then they talked about groups and rings for like an hour and then straight into this

I was warned that taking abstract algebra before this would help, I didn’t realize to what extent tho lmao

[verbal axle]

Hope we at least talk about it

[torn escarp]

like they're probably just going to assume characteristic not equal 2 or 3 and start doing the group law with the weierstrass normal form with the identity at infinity, in the direction of the line y=0

cause you really don't need to know that much to start talking about the elliptic curve group law once you start in this form, you wont' need projective transformations

[verbal axle]

What’s wrong with fields of char 2 or 3?

[torn escarp]

just prevents you from putting it into the clean, nice weierstrass normal form y^2=x^3+Ax+B

[verbal axle]

I see

[torn escarp]

if you look at the discriminant it involves factors of 2 and 3, which sort of end up breaking it

yeah, there's a lot to get into with elliptic curves, but now that I see your prof taught some basic algebra stuff and it's an intro course I think I understand where they're going

you'll learn how drawing lines between points on an elliptic curve will intersect at a third spot which is nearly the binary operator for the group of putting in two elements to get the output

[verbal axle]

Bruh wtf

That’s so cool

[torn escarp]

and then start to work out ok, why is this associative and commutative?

etc and hear other cool results about it

I'd explain more but I'd rather do it at a chalk board and/or voice chat

[torn escarp]

and also I'm about to eat some food haha

[verbal axle]

I’m about to sleep, got a class at 9 am for which I gotta travel 1.5 hours 😀

[torn escarp]

that's a long commute lol

[verbal axle]

Yep, huge country lmao

[errant otter]

nani yes, me entering with another self-insert "nani Hi forjoke and mero

[verbal axle]

@errant otter this is one of the most cursed things i've ever typed

[normal heart]

$$\frac{1}{\varphi(p)} \sum_{\substack{d \mid p-1\ d<p^{1/3}}} \varphi(d) \to 1$$

[sterile pumice]

cflau_

[normal heart]

Maybe that looks better

[verbal axle]

idk really

both look cursed

[normal heart]

not really

quite common

[verbal axle]

I'm new to all this, so maybe thats why I think it looks cursed

[distant sandal]

Why does subtracting 2n works

[errant otter]

could you provide more context?

[verbal axle]

if we write it out

n | 2n + 1 means that there is an integer k such that nk = 2n + 1

but now this is the same as nk - 2n = 1 or n(k-2) = 1 but k-2 is an integer hence n | 1

[inner mist]

n divides 2n

n divides 2n+1

so n divides this minus that

[plucky jacinth]

Here's another nice sum (used in the proof of Chen's theorem)

[verbal axle]

Most normal looking number theory sum

[plucky jacinth]

It also makes you appreciate laTex

[errant otter]

💀💀💀💀

indeed

[zealous wind]

mfw iverson brackets exist but people still insist on using massive subscripts

[plucky jacinth]

Imagine using iverson brackets

[normal heart]

imagine using iverson brackets

[flat wind]

Shouldn't it say false on the last line?

[loud maple]

But Fermat's last theorem is true. Why should it say false then, for any subset of the natural numbers greater than or equal to 3?

[flat wind]

Ah, my bad. For some reason reasoned that whatever assumption we assumed must be false for n greater than that and then thought our assumption was that Fermat's last theorem is true, hence it would be false for those n

But it's precisely the opposite assumption

thx

[leaden stratus]

if i add two numbers 220 + 330 = 550 is it guarantee'd that the GCD will be the same for gcd(220, 330) and gcd(550, 330)

[wooden glen]

Yes -- it's fairly simple to prove that gcd(a,b) = gcd(a+b,b) always. This is the basis of Euclid's algorithm for finding the gcd.

[leaden stratus]

the book im going through asked this question before going through euclid's algorithm. Explain how we know that gcd(990, 720) = gcd(270, 720) without finding any common divisors. i know they have common divisors, but i can't prove that there is no GCD > 270 for gcd(990, 720)

the book's "proof" doesn't really connect it for me

[wooden glen]

The core observation is that "the common divisors of 990 and 720" and "the common divisors of 270 and 990" are the same set of numbers. So in particular, the greatest element of this set is the same in each case.

[leaden stratus]

That makes sense to me. They have common divisors

[wooden glen]

If some number divides a and b, it also divides a+b.
Conversely, if some number divides a+b and b, it also divides a.

[leaden stratus]

to get to this observation "the common divisors of 990 and 720" and "the common divisors of 270 and 990" are the same set of numbers. i would have to write down all the divisors? i definitely can't come up with this observation myself because i can't prove it

[wooden glen]

No -- this is the explanation why the two sets are the same.

[leaden stratus]

they wanted me to explain it without finding any common divsors, but i don't get how 😭

let me try to understan what you wrote

[leaden stratus]

so they mention something similar what you you're saying in the next question. i need to some how put this together

[verbal axle]

write out what it means for a number d to divide another number b

and see if you can make connections from there

[wooden glen]

Yes, that is exactly what I'm saying.

Are you asking for help seeing that each of those claims are true?
Or for help seeing that they imply gcd(a,b)=gcd(a+b,c)?

[leaden stratus]

so i understand this, n divides a and n divides b then n also divides a + b. i was able to understand that in the previous section.

this almost feels the same, but not quite

[wooden glen]

That's the first of the two points you quoted, yes.

The second can be proved in almost exactly the same way.

[leaden stratus]

yeah i can't figure out how to prove this. im able to understand na + nb = n(a + b) which shows a common divisor of a and b is also a common divisor of a + b and i was able to get to this myself

i guess if i substitute something like a for m - n and b for n then it just say any common divisor of a and b is also a divisor of their sum

[rancid cargo]

p is an odd prime number, n is a positive integer, A is a set composed of sequences from 0 to p-1 with a length of n, which does not contain non-trivial three-term arithmetic sequence, prove
|A|<=3m
m is the size of the set of all sequences whose sum is less than (p-1)n/3.

[torn escarp]

is a trivial arithmetic sequence the same as a constant sequence

[rancid cargo]

yes

I found a prove and it's pretty long……

[torn escarp]

I'm confused by "which does not contain non-trivial ..." does this mean it only contains constant sequences?

@rancid cargo

I guess I should just assume you mean the opposite, whoops lol

really I don't get the wording of this question at all, is it really asking about arbitrary sequences of length n where you don't have 3 consecutive terms all identical?

I don't get why you'd bring up the word 'arithmetic sequence' at all when describing just a simple constant sequence, unless I misunderstand something and that there are other arithmetic sequences here

[normal heart]

constant difference of 0

[wooden glen]

One possible reading would be that for every n we have either x[n] = x[n+1] = x[n+2] or x[n+2] - x[n+1] != x[n+1] - x[n].

Or perhaps (depending on what "contains" means), it says that for every m < n < k we have either x[m] = x[n] = x[k] or x[k]-x[n] != x[n]-x[m].

[leaden stratus]

did i answer this problem corectly?

[unique cypress]

This question is more of elementary NT that's why I'm posting

If m = a+qd then by definition m is congruent to a mod d but what about (m,n)=1?

[torn escarp]

the phrasing is a bit subtle I think

[unique cypress]

I agree

The chapter is supposed to be about Gauss sums and Ramanujan sums but they bring these stuff out of nowhere for some reason

[torn escarp]

idk I'd probably try doing some euclidean algorithm or bezout's lemma thing maybe

[fringe tide]

if m shares factors with n, then they also share prime factors. say p is a prime with p | m and p | n. then p | a, which is a contradiction.

i don't know why (a, d) = 1 wasn't used

[unique cypress]

m shares factors with n?

Are you supposing that or it's implied?

[fringe tide]

i'm supposing it

[unique cypress]

How did you do the contradiction?

I don't get it

If p is prime then assume p|n which means p|a (based on the definition)

[fringe tide]

if (m, q) > 1, then there exists a prime p with p | m and p | q. so a = m - qd implies p | a as well, which contradicts the definition of q.

oh i'm hallucinating lol

[fringe tide]

uh (m, a) = 1 and (m, q) = 1, so (m, n) = 1

[unique cypress]

?

[fringe tide]

this shows (m, q) = 1. if (m, a) > 1, then there exists a prime p with p | m and p | a, then qd = m - a means that p | d, which contradicts (a, d) = 1.

that shows (m, a) = 1

[unique cypress]

Damn that's confusing

[fringe tide]

i think that's my fault lol

[unique cypress]

So let's start from the assumption p|n

[fringe tide]

you mean p | n and p | m ?

[unique cypress]

p|n implies p|q right?

[fringe tide]

it could also be p | a

[unique cypress]

It says q is the product of primes that divides n

[primal escarp]

Yes

[fringe tide]

they have to also not divide a

[unique cypress]

[primal escarp]

Suppose p|(m,n)

[unique cypress]

ok so p|m and p|n

[primal escarp]

Then p|m and then p|q

[fringe tide]

wat

p could also divide into a, in which case it wouldn't divide into q

[unique cypress]

p|m, p|n and p|q?

[primal escarp]

Indeed, as you said before p|n implies p|q

[unique cypress]

Alright so far so good

[fringe tide]

i can't

[primal escarp]

wdym, q is the product of all primes dividing n

[fringe tide]

q is the product of all primes that divide n but not a

[unique cypress]

Yeah we never said p|a

[fringe tide]

wdym

you still have to account for it

[primal escarp]

Ah shit

My bad

Then two cases ig

[fringe tide]

i made the same mistake earlier lol, you're good

[unique cypress]

If we are starting from p|(m,n) then our end goal is to show p is actually not a prime (but rather 1) right?

[primal escarp]

We want to show that it doesnt exist

[unique cypress]

Yeah makes sense

[primal escarp]

Ok so if p|n we have either p|q and p not divide a or p|a and p not divide q

[unique cypress]

yep

That looks right to me

[primal escarp]

Good

In the first case, we deduce p|a from the equality m=a+qd which is a contradiction

[unique cypress]

[primal escarp]

we have p|m and p|qd so we must have p|a

[unique cypress]

If we assume p|n and if p|a then why p doesn't divide qd?

[primal escarp]

So is the first case clear?

[unique cypress]

No I don't think so

[primal escarp]

The first case is p|q and p doesn’t divide a

[unique cypress]

Yeah

[primal escarp]

since p divides q, p|qd

[unique cypress]

Oh yeah my bad

Makes sense

[fringe tide]

maybe another way of seeing it:

in fact qd and a are coprime

[unique cypress]

so we got p|qd now how do we get the contradiction?

[primal escarp]

we have m-qd=a

And p divides the left hand side

So p must divide the right hand side

Which is just a

And we assumed p doesn’t divide a

So we arrive at a contradiction

[unique cypress]

Yeah but how p|m?

[primal escarp]

We are still assuming p|(m,n)

[unique cypress]

Oh ok

Yep makes sense

[primal escarp]

Okay, for the second case since (a,d)=1 we cant have p|d

Since p|m and p|a we have p|qd

[unique cypress]

and since p|d doesn't exist so is p|qd

[primal escarp]

This implies p divides either q or d

[primal escarp]

I think you got it

[unique cypress]

yeah thanks for the clarification

[primal escarp]

No problem

[fringe tide]

hence qd + a cannot share factors with qd or a

but q and a cover the prime factors of n

so qd + a cannot share factors with n either

[sacred junco]

I kinda got curious. If (a,d)=1 then p|d doesn't exist but that doesn't mean p|qd doesn't exist, unless I'm missing something

[fringe tide]

that's the contradiction

[sacred junco]

For the second case you have p|a and p not divide q
since (a,d)=1 => p|d is false but p|qd is possible but that contradicts our assumption p not divide q?

[fringe tide]

ya

[sacred junco]

Oh ok

That's tricky lol

[fringe tide]

hard to keep track of

[unique cypress]

My book is weird

Is primitive character chi mod k more elementary or advanced?

[fringe tide]

i think it's still elementary

[primal escarp]

I would say otherwise lol

[unique cypress]

Dirichlet characters are more of ANT (analytic) so I was a little bit confused

[primal escarp]

Yeah

I feel it should be advanced since it is analytic nt

[unique cypress]

For some reason ANT feels easier than elementary NT

[primal escarp]

Elementary nt can be super tricky

[normal heart]

probably because you haven't studied enough ANT lol

[unique cypress]

True

I don't get sieve theory at all

[normal heart]

learn the necessary theory first

don't rush it

Sieve theory is quite intuitive

[unique cypress]

Yeah I just looked at it and I was like "nope maybe I need to work on previous stuff to establish the intuition"

[sacred junco]

@fringe tide @primal escarp wait for the proof since we proved p doesn't exist that doesn't mean (m,n) = 1 it just means f|(m,n) where f is not prime

[primal escarp]

But if f is not 1, then there exists a prime p such that p|f and we must have p|(m,n)

[sacred junco]

Hello I need help with understanding the notion of quadratic residues
Let's say we have mod 11 so with mod 11 we have
1^2=1
2^2=4
3^2=9
4^2=5
5^2=3
6^2=3
7^2=5
8^2=9
9^2=4
10^2=1

Now the question is why 1,3,4,5 and 9 are quadratic residues? All of the numbers do satisfy
x^2 = n mod p

[pale fjord]

$a(a^3+a)=3\implies {1\over a}={{a^3+a}\over 3}=2a^3+2a$

[sterile pumice]

aSome1gussy

[pale fjord]

Why is this so?

[sacred junco]

Divide by 3a

[torn escarp]

not sure I understand the question, 1,3,4,5,9 are quadratic residues because if you pick them to be n then x^2=n mod 11 has a solution

similarly x^2=2 mod 11 has no solution, so 2 is not a quadratic residue mod 11

x^2=2 mod 7 has a solution though, so 2 is a quadratic residue mod 7

if that's your confusion, being a quadratic residue is relative to which prime you're looking at

[sacred junco]

Oh I confused with the variables. I thought because all of the combinations are giving solutions then everything is a quad residue

So like 1^2=1 if you square it then you still get a solution and actually it's the same thing for all values so I was confused lol

[torn escarp]

I see, yeah, it's only the possible things you get after squaring, not before squaring

in fact mod p, exactly half of the nonzero residues are quadratic residues

[sacred junco]

Yeah so you need to find an x such that when you square it you get an existing value mod p
you can't get 2 from x^2 = 2 mod 11 for all values so it's not quad residue

Yeah I've noticed that too

I wonder if it is the same thing for cubic residues, if that even exists lol

Thanks for clarification

[torn escarp]

yeah definitely it does

[sacred junco]

(p-1)/3 cubic residues?

[torn escarp]

yeah

what about the case when 3 doesn't divide p-1

[sacred junco]

If 3 different types of numbers then I'd expect 1/3 cubic residues, 1/3 non-cubic residues and 1/3 something else I'm not sure what it is

[sacred junco]

Oh yeah good point

[torn escarp]

maybe think of it this way, when 3 | p-1 you have three solutions to x^3=1

[sacred junco]

so x^3 = n mod p only holds if 3|(p-1)?

[torn escarp]

no, not what I'ms aying, that was a response to this for how to think of partitioning them, but needs more elaboration

[sacred junco]

Oh

[torn escarp]

well, I suggest looking at an example

take p=5

how many cubic residues are there?

don't think too hard, just grind through computing all the numbers starting at 1^3, 2^3, ... and see what you get

[sacred junco]

1^3=1
2^3= 3
3^3= 2
4^3 = 4
So 1,2,3,4?

[torn escarp]

yeah, everything is a cubic residue

[sacred junco]

That's an interesting observation

[torn escarp]

you know from fermat's little theorem that x^{p-1} = 1 mod p, but since 3 doesn't divide p-1, it's unable to get the elements closer to 1, so it is forced to permute them essentially

[sacred junco]

I didn't go over FLT yet

[errant otter]

ok so we'll prove it now

[torn escarp]

yeah I was thinking we need to avoid talking about some complicated stuff haha

well, complicated might not be the right word, but it'll just take time to get there by taking simpler steps that take time, you'll get there

[errant otter]

yeah

[sacred junco]

I went over linear congruence, Euler theorem, Wilson theorem and other stuff

[errant otter]

wait

but euler theorem is a generalisation of LT

FLT

[sacred junco]

Oh wait

Oh yeah

[errant otter]

or am I thinking of a different Euler theorm?

he made a lotta shit

LOL

[sacred junco]

a^r=a mod p

[errant otter]

ye

[sacred junco]

I'm so dumb

[errant otter]

euler totient function bs

[errant otter]

[sacred junco]

How would you prove there are exactly (p-1)/2 quadratic residues?

My book is confusing

[errant otter]

which book is it?

[sacred junco]

Apostol

ANT

Its nice because it goes over elementary and analytic number theory but yeah I'm kinda regretting it sometimes

[errant otter]

funnily enough I gave the wiki a look and apparently it's like the 1st thing it brings up

[errant otter]

[torn escarp]

you can look at the number of roots of x^{(p-1)/2} - 1, this has all the quadratic residues as roots by euler's theorem

[sacred junco]

I'd go to Google at last when I'm desperate

[errant otter]

yessir

[torn escarp]

$x^{p-1}-1 = (x^\frac{p-1}{2}+1) (x^\frac{p-1}{2}-1)$

[sterile pumice]

merosity

[errant otter]

lmao be like opening a wiki page only to see whatever jargon they have inside utterly destroying u

[torn escarp]

that's 0 for every x, and if it's a nonresidue, it's not a factor of the right one, so it must be a factor of the left one

[sacred junco]

opening a wiki on distribution of prime numbers
sees weird logs
"What in the world is that?"

[torn escarp]

I'm also leaning on the field structure of Z/pZ

[errant otter]

lmao prime number theorem moment

[errant otter]

wiki being wiki

[torn escarp]

I'd recommend looking at Silverman's A Friendly Introduction to Number Theory, each chapter mostly stands on its own and answers fun questions like this

[errant otter]

"fun questions like this"
define "fun questions"

[torn escarp]

#elementary-number-theory 😎

[errant otter]

I swear tho wiki never helps 99% of the time, it just splashes you with a buncha new terminology and theorems you've never heard before

[sacred junco]

Couldn't agree more

[torn escarp]

depends on where you're at in your studies relative to the topic

[errant otter]

indeed

[sacred junco]

That's why I go into a wormhole of just clicking over terms that I don't understand then going back and still not getting it

[errant otter]

SAME

[errant otter]

hmmm

[sacred junco]

But 1<x+y<p

What

How?!?!

[torn escarp]

I think it's important to distinguish between tutorials, how-to guides, explanation, and reference

[errant otter]

ig i'ts because

[errant otter]

fr

[torn escarp]

so I see the wikipedia frustration as trying to look for a tutorial on the topic when wikipedia is roughly a reference

[errant otter]

yeah

[sacred junco]

Biggest mistake I did is buying Apostol
I spend most of the time watching YT videos then going back and be like "oh I get it now lmao"

[torn escarp]

like people learning to program the first time aren't going to just start reading documentation immediately from cover to cover

or we don't have kids learning english by having them read the dictionary starting with A lol

[errant otter]

XD

[errant otter]

well at least you look through it

I got Hardy's book but I haven't even FLIPPED THROUGH IT

[sacred junco]

1<x+y part makes sense but how about x+y<p?

[sacred junco]

I don't even know what is Hardy's book

[errant otter]

u haven't heard of hardy???

[sacred junco]

Can you literally just extract y by itself? I mean it is x+y, no?

[torn escarp]

oh notice that x^2 = (-x)^2 = (p-x)^2

[sacred junco]

Hardy with Ramanujan?

[torn escarp]

that's why we can pick the lower representative x since p-x also squares to the same thing

[errant otter]

this implies x+y <= (p-1)/2 + (p-1)/2

[torn escarp]

if that's what you're asking

[errant otter]

yeah, he's famous especially for his collabs with ramanujan

[sacred junco]

Yep I know him but I meant what book are you referring to

[errant otter]

it's hte intro NT book he wrote

yes, he did write one

[sacred junco]

yeah <= p-1 and where can you remove that extra -1?

[sacred junco]

oof

[errant otter]

since x+y <= p-1, x+y < p

[sacred junco]

[errant otter]

like

the largest value x+y can have is p-1

and p-1 is clearly < p

[sacred junco]

Oh gotcha

how about (x-y) = 0 mod p

[errant otter]

ima just send it again to bring it down

[sacred junco]

My mind is like take the conjugate of x+y

[errant otter]

let's see...

well

actually

[torn escarp]

first line

[errant otter]

yee

lmao mero sniped me

ouch

[torn escarp]

oh before this I mean the words, unless that's hwat you were going for too

[errant otter]

ah

[torn escarp]

they're distinct mod p

[sacred junco]

from x<= (p-1)/2 and y<= (p-1)/2?

[torn escarp]

x-y=0 mod p => contradiction

[errant otter]

ngl tho the wording is a bit weird I think? they make it sound like 1 < x + y < p implies x-y = 0 mod p when it follows from this (or does it?)

[sacred junco]

x-y <= 0/2 <= 0

I get it now

[errant otter]

https://tenor.com/view/smart-fella-when-fart-smella-walks-in-gif-24813411

wait

wrong GIF

but ok

[sacred junco]

Yes exactly and I hate it

[torn escarp]

hmm?

show a picture of what (2) is that they refer to

that's where it comes from to begin with

[sacred junco]

hmm ok

[torn escarp]

ok cool, so you know at lowest x, y are both 1, and 1 < 1+1

[sacred junco]

yep obviously

[torn escarp]

but this pic alone doesn't explain why they start off saying they're distinct

[errant otter]

1 < 1+1
Omg WHAT? /j

[errant otter]

[sacred junco]

I know 😭

[torn escarp]

ok back up, remember, what are we proving here

maybe send a larger picture or something earlier on haha

[sacred junco]

I'll just send the theorem

[torn escarp]

well I know the theorem

but I think you're like, losing sight of what we're doing here

maybe you should just say in words what we're trying to show or find out

[errant otter]

literally 99% of the proofs: We're gonna tell you they're distinct and then get you to take it to be a fact despite how it may not be true in the complex world but who cares because we're only dealing with Reals, and then use that fact to prove everything

[sacred junco]

That's me 90% of the time when doing proofs so I'm not surprised

[errant otter]

smh this is why u keep track of your goals by writing a section of the stuff you're given and another section for your endgoal/what you're trying to demonstrate

[torn escarp]

let's prove that those (2) are distinct mod p

[sacred junco]

There is a chapter where they say "the proof the contour integral representation of the Gamma function is left an exercise (an excellent exercise) to the reader."

[torn escarp]

lol

[errant otter]

pain 💀

[sacred junco]

I looked for the proof online and I almost had a stroke

[errant otter]

proofwiki moment

[sacred junco]

Yep

[torn escarp]

don't look it up, that's just cheating yourself

[errant otter]

true true

[torn escarp]

it's pretty easy but if you've never done it then it's worth taking the time to do it

[sacred junco]

Well depends on what do you mean by "pretty easy"

[torn escarp]

it's literally the proof that they carry out there lol.

[sacred junco]

But isn't it good to just look it up then actually understand the proof?

[torn escarp]

nah

not unless you want to just have people tell you what to do your whole life

[sacred junco]

[torn escarp]

you should try to figure it out yourself first before just giving up

like imagine someone give you a puzzle

[sacred junco]

I do try it by myself first

[torn escarp]

your first response shouldn't be to look up a guide for how to solve the puzzle and then put it together following the instructions

[sacred junco]

Like get stuck for 3 days then just look it up

[errant otter]

3 days relatable

[sacred junco]

Anyway let's move on the main topic

[torn escarp]

depends, finding a good balance of how long is good and is a waste takes time to figure out

I guess, what's the end goal of all this anyways?

at some point if you want to do research, then you'll basically be working on stuff that there aren't answers out there anymore for you to look up anymore

[sacred junco]

Yeah I'm pretty aware of that

[torn escarp]

ok sorry I think I'm getting a bit preachy my bad lol

[sacred junco]

Sometimes when I feel bad about myself not doing the proof then looking it up, I make another similar problem then prove it so that i feel good about myself again

[errant otter]

same

be like trying to make yourself feel good about your skillissue

[torn escarp]

I guess my process is more like, I come to a new problem, I throw everything I think I can at it and try to see them to their conclusion as best I can, maybe give it a little time in case some clever idea magically comes to me, then I'll give in and look up solutions.

I don't feel bad if I can't do it, but idk if that's just easy to say "don't feel bad" haha

but as long as I feel like I tried I feel good, and excited that I'm about to learn something new to extend the reach of my problem solving

idk if this helps

[sacred junco]

Sometimes the exercises that are in the book are not related to the chapter at all...

[sacred junco]

Yeah I definitely learn something new

[torn escarp]

yeah math books tend to be pretty uphill sadly lol

[errant otter]

lmao

spivak's calculus is literally that (tho I appreciate it for being like that)

[sacred junco]

Chapter 4: congruence
First 5 problems: hah easy
6 to 8: hmm tricky
Last one: prove the RH using simple arithmetic

[errant otter]

the exposure is smth I appreciate ig

[sacred junco]

ok so if 1<x+y<p and x-y = 0 mod p and hence x=y but then why (p-k)^2=k^2 mod p?

[torn escarp]

that's why we split it in the middle, (p-1)/2

like 1 and p-1 are "mirror images" across this

2 and p-2

3 and p-3, etc

...
(p-1)/2 and (p+1)/2

[sacred junco]

oh it's that

But did they conclude it from the previous results using something?

[torn escarp]

I think going in they either said it earlier or maybe assumed it was obvious and didn't state it that x^2=(-x)^2

x^2=(-x)^2=(p-x)^2 is where I see it coming from

[sacred junco]

hmmm yeah

Makes sense

[torn escarp]

if you go back to your mod 11 examples earlier, you can sorta notice that pattern too

eventually you would have found that out

[unique cypress]

I used Apostol before. It was very convenient to me lol

Wow this chat is more or less #discussion

And yes I agree some of the problems are raised by 10x in difficulty each time you go by but that's just how math books are

A really good example would be this

[errant otter]

mb

[sacred junco]

Yeah this one

I skipped it successfully

I'm guessing you had to use Wilson's theorem somewhere but idk lol

[errant otter]

what even is [n/p]

[sacred junco]

floor function

[errant otter]

oh, I thought that didn't have the line at the top

interesting qn

[sacred junco]

I was really confused too

Literally nobody;
Apostol: [x] denotes for floor function

[errant otter]

waittt

I think

I feel like my brain is functioning a bit

I've seen a proof of FLT by induction and I see some similarities

[sacred junco]

Your brain cells are back

[errant otter]

[sacred junco]

Oh yeah they also use a weird term "cross-classification"

[errant otter]

basically it was a vid by michael penn

[sacred junco]

Turns out it's just inclusion exclusion principle

[sacred junco]

Time to see Michael then

[errant otter]

he proved that binom(p n) is congurent to 0 mod p- it may or may not be linked

idk

[errant otter]

offtopic but while I was finding the vid I saw this- but anw here's teh vid https://youtu.be/WRL47F6VyRE

I'm just an inductive proof lover

[sacred junco]

The world is flat
Proof: left as an exercise to the reader

Okay thanks

[errant otter]

the REALLY annoying thing is that the p and n-s are flipped

[sacred junco]

Pain

[errant otter]

ok well this is trivial if n <= p but when n > p is pain

[torn escarp]

might be worth saying n!/(n-p)! = n(n-1)(n-2)...(n-(p-1)) = n^p-n mod p

[errant otter]

yeah

[torn escarp]

although we sort of need to care about mod p^2, since we see that's 0 mod p by flt, and we divide that by p

[errant otter]

I hate how innocent and easy elementary NT appears to be

[sacred junco]

elementary
Realization:

[torn escarp]

that's what makes it so fun

[errant otter]

true

[sacred junco]

I never said I dislike it

I love it because it's challenging and never makes me bored

[torn escarp]

oh I was responding to @errant otter haha

[sacred junco]

Yep

[torn escarp]

true same

[errant otter]

time to drag this down so that we don't have to keep scrolling up

so the case where n < p is trivial

[sacred junco]

binom(n,p)= n!/(p!(n-p)!) thank me later

[sacred junco]

I can sense that you are going to use induction

[unique cypress]

Use Lucas' Theorem (assuming you are not restricting yourself to what you know so far)

[errant otter]

reason being binom n, p would just evaluate to 0 and floor of n/p will evaluate to 0 too

[unique cypress]

But it is an overkill I'd say

[errant otter]

,w lucas theorem

[sterile pumice]

Results provided by WolframAlpha

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

Requested by kiameimon#0

[errant otter]

[unique cypress]

That looks different

[sacred junco]

That's definitely an overkill

[errant otter]

very different indeed

[sacred junco]

The proof is just immediate in this case

[errant otter]

"You say that, but I use ODEs to solve for an object's motion without air resistance

[errant otter]

now prove the thereom

[torn escarp]

I like the generating function proof of lucas's theorem pretty cool

[sacred junco]

Left as an exercise to the reader leaves

[errant otter]

ahhhhhhh shit

generating functin

I have yet to learn abt those stuff

[torn escarp]

like in this special case we can do the generating function proof and not feel too crazy if you want

[sacred junco]

I love how generating functions are so magical

[torn escarp]

$(1+x)^n$ you can then write $n=n_0+\lfloor \frac{n}{p}\rfloor$

[sterile pumice]

merosity

[torn escarp]

since it's only expanding out two terms

actually doing this would give us a recursive way to prove the full lucas theorem afterwards I believe too

[sacred junco]

What is n_0?

[torn escarp]

the first digits of n

oh I meant to put a p in there too

[errant otter]

[torn escarp]

$n=n_0+p\left\lfloor \frac n p \right\rfloor$

[sterile pumice]

merosity

[sacred junco]

[torn escarp]

$$(1+x)^n = (1+x)^{n_0}(1+x)^{p\left\lfloor \frac n p \right\rfloor}$$

[sterile pumice]

merosity

[sacred junco]

Wouldn't n_0 be 1?

[torn escarp]

now use the fact that (1+x)^p = 1+x^p to rewrite that lastmost term

n_0 could be any digit 0 to p-1 if written in base p

[sacred junco]

Examples

[torn escarp]

p=2

0, 1, 10, 11, 100, 101, ...

rightmost digit is 0 or 1

that's counting up 0, 1, 2, 3, 4, 5 in base 2

odd numbers are 1 mod 2, and even numbers are 0 mod 2

n mod p is exactly the same as the n_0 digit when n is written in base p

assuming you're picking your residues from the set {0, 1, ..., p-1}

[sacred junco]

Oh so instead of base 10 you are using base p?

[torn escarp]

yeah

[sacred junco]

Like binary for example

[torn escarp]

yup

[sacred junco]

Lol I would've never thought of that

[torn escarp]

in general you can think of getting the base b expansion of an integer this way

$n=n_0 + n_1b+n_2b^2+ ...$

[sterile pumice]

merosity

[torn escarp]

maybe that helps to see first, like $n=n_0 \mod b$ then once you have that, $$\frac n b = \frac{n_0}{b} + n_1+n_2b+n_3b^2+\cdots$$

[sterile pumice]

merosity

[torn escarp]

so then flooring throws out the n_0/b fractional part

$$\left\lfloor\frac n b \right\rfloor= n_1+n_2b+n_3b^2+\cdots$$

[sterile pumice]

merosity

[sacred junco]

Okay

[torn escarp]

ok I think that makes it clear that n=n_0 + b floor(n/b) cool

[torn escarp]

resuming here by flipping $(1+x)^p=1+x^p \mod p$, $$(1+x)^n = (1+x)^{n_0}(1+x^p)^{\left\lfloor \frac n p \right\rfloor}$$

[sterile pumice]

merosity

[torn escarp]

the coefficients on x^p on both sides are equal now

seems scarier than it really is

[sacred junco]

Yep

I just found out a mod p = a - p floor(a/p)

So what you said earlier now makes a lot of sense

[pale fjord]

No how is the last step true, i.e. 2a^3+2a?

[sacred junco]

It looks false for me

Unless you are assuming something I don't know of

[sacred junco]

I can see where you could potentially go with this. Use binomial expansion then somehow simplify stuff to get the desired result

[torn escarp]

yeah, we're actually almost done

since we only care about the coefficient n choose p from (1+x)^n, that's why we care about the x^p coefficient

but if you look on the right, x^p appears

if you expand out $$(1+x^p)^{\left\lfloor \frac n p \right\rfloor} = \sum_{k=0}^{\left\lfloor \frac n p \right\rfloor}x^{pk} \binom{\left\lfloor \frac n p \right\rfloor}{k}$$

[sterile pumice]

merosity

[torn escarp]

the only two terms that have a chance of mattering to us are the first two, k=0 and k=1, since the others have already passed p in their degree

[sacred junco]

Yep

[torn escarp]

so we just care about $1+\left\lfloor \frac n p \right\rfloor x^p$ and how that multiplies with the term $(1+x)^{n_0}$

[sterile pumice]

merosity

[torn escarp]

but since $0\le n_0 < p$ none of those $x^k$ in its binomial expansion can multiply with $1$ to make another $x^p$ term

[sterile pumice]

merosity

[torn escarp]

so that's pretty much it

I'm being a little terse on details

[sacred junco]

I see that's a brilliant proof

I like it

[torn escarp]

well I mean Id idn't come up with this, I just adapted the one on the lucas' theorem wikipedia page to your special case

but I think understanding this special case makes understanding the full proof easier to see how it works basically

[sacred junco]

Sometimes when you go complex you actually understand stuff more than before

[torn escarp]

can we prove the second part of the queston this way too I wonder

[sacred junco]

They used this lemma

[errant otter]

[sacred junco]

And together with Wilson's theorem they said
$\binom{n}{p}=q(-1)(-1)= q \text{ mod }p$

[sterile pumice]

queen_succubus

[errant otter]

I take a moment to look at stuff in another server and then come back to see #elementary-number-theory disfigured beyond recognition

[sacred junco]

The product term is confusing lol

[sacred junco]

Just like me looking at #calculus then seeing somebody posting elementary school math and
proceeding to call it calculus

[errant otter]

NAHHH U SAW THAT?

[torn escarp]

hmm

yeah idk if I like their proof I was working on figuring out how to adapt it to the toher case haha

$$n=n_0+p^{\alpha+1}m$$ with $\gcd(m,p)=1$

[sterile pumice]

merosity

[pale fjord]

They claim 1/2 is 3 in characteristic 5. over here: https://artofproblemsolving.com/community/q1h3087999p27906996 not sure what that means

[torn escarp]

then going through the same argument should work mod p^a

set a=0 to recover the original case we just did

actually gcd condition is not necessary, like specifically what changes is:

no I don't think it works haha

[sacred junco]

I'm gonna try working on understanding dirichlet characters tomorrow. Their definition is quite ambiguous

Thanks for helping @torn escarp @errant otter

[torn escarp]

oh I see, it does look like it works

[errant otter]

[torn escarp]

$$(1+x)^n = (1+x)^{n_0}(1+x)^{p^{1+\alpha}m} \mod p^\alpha$$
$$(1+x)^n = (1+x)^{n_0}(1+x^{p^{1+\alpha}})^m \mod p^\alpha$$

[sterile pumice]

merosity

[torn escarp]

looks like RHS has no x^p term, which means on the LHS the coefficient n choose p is 0 mod p^a

[sacred junco]

No x^p terms?

How so

[torn escarp]

I might be making a false statement in the middle there when I jump frm (1+x)^{p^k} to (1+x^{p^k}) mod p^{k-1}

I think something like that is true though that'll work if it isn't though lol

[sacred junco]

[torn escarp]

based on what's written, the (1+x)^{n_0} has none like previously since exponents are only from 0 to p-1

and (1+x^(p^k)) raised to a power with k>1 means you can't get exactly x^p either, since they're strictly higher degree

[sacred junco]

Oh yeah

[torn escarp]

ah ok I remember how to prove this now

$(1+x)^{p^n}=1 \mod p^n$ we can do a little induction argument since $$(1+x)^{p^n}=1+p^ny \mod p^{n+1}$$ now raise to $p$ power and you get $$(1+x)^{p^{n+1}} = \sum_{k=0}^p \binom{p}{k} (p^ny)^k = 1$$ since the $\binom{p}{k}$ terms have $p$ in all of them (except the k=0 and k=p terms)

[sterile pumice]

merosity

[pale fjord]

@sacred junco

@honest flicker lmao

[errant otter]

yayy induction

[torn escarp]

I totally mangled what I really wanted to prove by writing what I did though, but whatever

[pale fjord]

I actually need help, please, don't forget me

[torn escarp]

what's your question

[pale fjord]

Why is 1/2 = 3 in characteristic 5?

[torn escarp]

I guess one way to see it is multiply both sides by 2 and see that you get a true statement

is that satisfying enough or not, idk kind of hard to answer "why" questions

[pale fjord]

i meant how?

[torn escarp]

you can think of it symbolically

1/2 just means "multiplicative inverse of 2"

but 3 behaves as the multiplicative inverse of 2, since 3*2=6 = 1+5 = 1 in char 5

so they're actually the same cause inverses are unique

we can prove that more fundamental claim too if you want, but you should try to prove that too

[pale fjord]

yeh let's do it

[torn escarp]

ok let's say x has the inverses y and z

multiplication is associative so we can multiply them all together in two different ways:

(yx)z=y(xz)

since they're inverses we make the identity, yx=1 and xz=1

1z=y1

z=y

so actually they're the same

[pale fjord]

Nah I mean the 2a^3+2a?

part

[torn escarp]

I don't know what you're talking about I thought your question was just this

[pale fjord]

after that, i have nother Q. From
here

How'd they derive 2a^3+2a

[dusty dragon]

that's just saying the inverse of 3 is 2

[pale fjord]

gang, how?

[dusty dragon]

if you're working over characteristic 5, then 5 acts like 0

and we can see that 3 * 2 = 6 = 1 over characteristic 5

so we have some a, b such that a * b = 1 which means that a is the inverse of b and likewise, b is the inverse of a

[pale fjord]

Why does it have to be
2a^3+2a though?

Ohhhhhh I fucking get it

[pale fjord]

because 6a^3+6a is congruent to a^3+a right

Amirite?

Broski

[torn escarp]

yup

[pale fjord]

what is the relevance of 1/2 being 3 in characteristic 5. they might as well have not noted that, right?

Zhai Pan?

Oh no Zitong Hao?

Isn't that superfluous??

[torn escarp]

idk, 1/2 = 3 and 1/3 = 2 is basically the same statement to me, I wouldn't lose sleep over it

[errant otter]

So um, I don't understand how if d is a common divisor, it divides a-bq_1

[leaden swan]

a= a_1 d, b= b_1 d

So a-b q_1 would be (a_1-q_1b_1) d

[errant otter]

ahhhhhh

right

[flat wind]

This is a mistake, no? If say g=h=0, then any function f defined on N satisfies the convolution

Seems like they would need to be non-zero at 1 for it to be true

Ah, note: * denotes dirichlet convolution

[normal heart]

usually multiplicative functions have f(1)=1 in the definition

[flat wind]

Ye, this doesn't tho

[unique cypress]

I'm pretty sure f(1)=1 should be included too

[flat wind]

I mean, it's not necessary. The corollary can just be that if two of f,g,h are multiplicative and non-vanishing at 1, then so is the third

I believe

[unique cypress]

I mean you can prove it from the definition

[flat wind]

Huh?...

0 is multiplicative

[normal heart]

yeah then your definition is the same as the usual definition except it also allows the trivial function to be multiplicative, so yes in the corollary they should exclude the case when g and h are trivial

but it's not a big issue since trivial functions are trivial so not a big deal anyway

[flat wind]

Ye

[normal heart]

(just note f(1)=0 implies f(n)=0 for all n in your definition of multiplicative functions)

[unique cypress]

f(n) = f(1)f(n), since (n,1)=1
divide by f(n) (not equal to zero) and you get it

[normal heart]

why is f(n) necessarily nonzero?

[unique cypress]

Because something/0, no?

[normal heart]

you claimed f(n) is not equal to zero

why is that so?

[errant otter]

because division by 0 is undefined

if f(n) = 0

you screw up

[normal heart]

.

[flat wind]

.

[normal heart]

i mean f(n)=0 for all n is fine f(n)=f(1)*f(n) still holds

so f(1)=0 is allowed in CoffeeMan's definition

[unique cypress]

f is not identically zero

[normal heart]

why?

[unique cypress]

Is my proof incomplete?

[flat wind]

What proof?

[normal heart]

why can you assume f is not identically zero

[torn escarp]

if f(1)=0 it implies f(n)=0 for all n, proof: f(n)=f(1*n)=f(1)f(n)=0

[flat wind]

Indeed

[torn escarp]

I know other people already said this but seems like it's still being argued

[normal heart]

idk why it's still being argued

[torn escarp]

some misunderstanding I assume, that's why I wrote out the statement and proof in case something was missed

also f(1)=1 is not necessary to define, f(1)=f(1*1)=f(1)f(1) so now that we know f(1)=0 case uniquely determines the 0 function, we can look at when f(1) != 0 and divide by it to get f(1)=1

[normal heart]

yeah it depends on definition, some literature put f(1)=1 in the definition of multiplicative functions

but it doesn't quite matter at the end of the day since the only discrepancy is whether the trivial function is multiplicative, which is a trivial matter

[torn escarp]

yeah, I just figured it's nice to show that f(1)=1 is the same as excluding the 0 function

I agree we should exclude it so that we can say that multiplicative functions form a group under the dirichlet convolution

[unique cypress]

Okay f(n) = f(1*n) = f(n)f(1) holds true if f(n)=0 for all n or f(1)=1

[torn escarp]

wot

[normal heart]

?

[flat wind]

Ye, but if we don't include it we can simply say they form a semi-group

So we're just adding a little extra result

[torn escarp]

ew

[flat wind]

Indeed lol

[torn escarp]

wtf is a semigroup

[normal heart]

who introduced semi-groups into multiplicative number theory

[errant otter]

[torn escarp]

just give me the ring structure at that point heh 😛

[unique cypress]

Why semigroups?

[flat wind]

U can show that's the structure it forms under dirichlet convolution
f(1)=1 included => group
f(1)=1 not included => semi-group

Again, doesn't rly matter tho

[unique cypress]

[flat wind]

Read second sentence bro

[normal heart]

probably the not identically zero part is in your definition of multiplicative functions

which is not in CoffeeMan's definition

[unique cypress]

The set of arithmetical functions with f(1)=/=0 forms an abelian group under multiplication, no?

[normal heart]

no

how do you define inverse

[unique cypress]

I meant dirichlet multiplication mb

[torn escarp]

multiplicative functions, not arithmetical functions yeah

[flat wind]

No, arithmetic functions

[torn escarp]

are you saying all multiplicative functions are arithmetical functions

and vice versa

as long as that's your definition, sure

[flat wind]

No, I'm saying the set of arithmetic functions that are non-zero at 1 form an abelian group under dirichlet convolution

[torn escarp]

what does it mean to be an arithmetic function

[unique cypress]

Arithmetical functions have subgroups called multiplicative functions iirc

[flat wind]

f: N->C

[torn escarp]

f(n)=2

this is an arithmetic function according to you

[unique cypress]

I don't get it bro

[flat wind]

Yup

[torn escarp]

ok maybe I'm misunderstanding something else, I agree that f(1) !=0 has a dirichlet inverse

[unique cypress]

Another terminology would be number-theoretic function

It's kinda confusing so I use arithmetical instead

[flat wind]

You can pretty easily define an inverse recursively for any non-zero f

[torn escarp]

if that's what you're defining it as, then we're good

yeah, that I know how to do

[flat wind]

Seems all good then

[torn escarp]

the formula involves dividing by f(1), so that's all that matters yup

[unique cypress]

I just checked my book's definition and yep you're right

All good

[errant otter]

For a second I read that as "I checked GPT"

[unique cypress]

No no, we don't do that here

[sacred junco]

$n^{p-1}-1=(n^{(p-1)/2}-1)(n^{(p-1)/2}+1)\
\text{It follows that }n^{(p-1)/2}\equiv \pm 1 \text{ mod }p$

[sterile pumice]

queen_succubus

[sacred junco]

I don't see how n^((p-1)/2) = +-1

[open mist]

n^(p-1) is 1 by Fermat

[torn escarp]

p divides one of the terms on the right

I guess you could say euclid's lemma for that

or just say it's a field, or weaker ufd, so you have no zero divisors

[unique cypress]

Suppose (n|p) = 1 ((n|p) is legendre symbol). Then there is an x such that x^2=n mod p and hence
$n^{(p-1)/2} \equiv (x^2)^{(p-1)/2} = x^{p-1} \equiv 1 (Fermat)$

[sterile pumice]

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

[unique cypress]

Wow that's horrible

$n^{(p-1)/2} \equiv (x^2)^{(p-1)/2} = x^{p-1} \equiv 1 (Fermat)$

[sterile pumice]

despairful_deltoid

[unique cypress]

Now
Suppose (n|p)=-1 and consider the polynomial
f(x) = x^((p-1)/2) - 1
Since the degree is (p-1)/2 the congruence
f(x) = 0 mod p has at most (p-1)/2 solutions, but notice that (p-1)/2 quadratic residues mod p are solutions so the nonresidues are not. So we get,

$n^{(p-1)/2}\not\equiv 1 \text{mod p} \text{ If (n|p)=-1}$

[sterile pumice]

despairful_deltoid

[unique cypress]

But n^(p-1)/2 = +/- 1 mod p so n^(p-1)/2 = -1

[sacred junco]

That makes sense but I still don't get why they can conclude n^(p-1)/2 = +/- 1

[torn escarp]

ab=0 means a=0 or b=0, then they're moving the +-1 to the other side

[open mist]

It's a root of X^2 - 1
Of which there are at most 2

[normal heart]

(n^(p-1)/2+1)(n^(p-1)/2-1)=0 mod p

By definition of a prime number, n^(p-1)/2+1=0 or n^(p-1)/2-1=0 mod p

[sacred junco]

Oh I get it

But by definition of primes numbers?

[normal heart]

oops that depends on the definition

[sacred junco]

It looks something like (x-1)(x+1) = 0 so x = -1,1

[normal heart]

the fact that p divides ab implies p divides a or p divides b

ab=0 mod n does not always imply a=0 or b=0 mod n, but it is if n is prime

[open mist]

i.e. Fp is an integer domain

[sacred junco]

So here you literally showed (n|p) is congruent to n^(p-1)/2 mod p

An overkill

[unique cypress]

What's wrong with overkill?

[errant otter]

Well comeon

If it works

It works

[normal heart]

not elegant

[errant otter]

Ouch

Now that is um

A bit of a questionable statement

[unique cypress]

I'd say it's elegant if you prove the generalized version then use it

[errant otter]

Especially when proving a general case is generally more elegant

[unique cypress]

Usually generalized versions are easier to prove

[errant otter]

Ehhhhh

Well sometimes I'd agree

[normal heart]

do you truly believe it is easier to prove (n|p)=n^(p-1)/2 in this case

[unique cypress]

It's kind of obvious

[normal heart]

also i'm talking about 'overkill' not 'proving a general case'

[unique cypress]

But general cases => overkill, no?

[normal heart]

it's just etiquette to not overkill if possible

[normal heart]

no

[unique cypress]

yes usually

depending on the context

[normal heart]

sure, if you think so, doubt anyone would agree it's more obvious than the question posed though

it's just etiquette to not give an overkill solution if you know an easier and quicker solution

i don't wish to argue whether general cases are overkills as that is meaningless

[errant otter]

There was etiquette to maths?

[normal heart]

..why not?

[unique cypress]

Prove that math has etiquette

[normal heart]

but this is off topic in this channel so better cease this discussion

[errant otter]

What's meant by "etiquette" when it comes to math anyway

[normal heart]

ask a philosopher, i don't care enough to be rigorous with things outside of mathematics

[torn escarp]

lol I like the "fighting" it's good

I don't think it's irrelevant or off topic cause it's about the solutions

[unique cypress]

I really don't mind overkills as long as they are proven

[errant otter]

"Prove FLT and state that n=3 is a special case"

[normal heart]

it's more about philosophy rather than elementary number theory

better suited for channels for general discussions

[errant otter]

Proof techniques ™️

[torn escarp]

generally speaking if this started spontaneously I'd agree, but it naturally came up from this

sure it's a side tangent, but the rules aren't that strict I mean it's not like people are really clamouring to get into the elementary number theory channel to ask their question here haha

[errant otter]

lmao if this were deserving of a fine what I'm doing in #calculus is equivalent to war crimes

[torn escarp]

we're like, building an #elementary-number-theory subculture

[unique cypress]

3 of my books literally use an overkill to prove FLT

[errant otter]

oh by FLT I Meant fermat last theorem

Not little

I just realised they're the same

[normal heart]

I doubt anyone would think proving euler's theorem and deduce FlT as a corollary is an overkill

[unique cypress]

I've seen someone getting angry over people saying that his problem is not calculus related (and that's true)

[normal heart]

but I think anyone would agree proving (n|p)=n^(p-1)/2 to answer the question above is an overkill

[unique cypress]

Maybe the way we use the word overkill is different

[errant otter]

Ngl I just do a #(appropriate channel name) for that

Which reminds me of how many times I've seen integrals and derivatives (albeit mostly trivial) are seen in #precalculus

[unique cypress]

not me posting elem NT problems in #advanced-number-theory because my brain cells are not working

[sacred junco]

I know this is not #discussion but @unique cypress @normal heart are you guys more into analytic NT? It feels that way to me

[normal heart]

yes

[unique cypress]

yes

[sacred junco]

[normal heart]

[sacred junco]

I'm looking into both fields and to be honest analytic feels more familiar to me than algebraic

Maybe because I'm into analysis too

[errant otter]

What's the difference between the 2

[normal heart]

study both to a certain degree

until you know which one you like more

[torn escarp]

they can get pretty different depending on what you're focused on, but also have a fair bit of crossovers cause of dedekind zeta functions

[sacred junco]

I need to start abstract algebra first before going into algebraic NT

[normal heart]

yes

i would advise against banning all possibilities of algebraic NT before even studying abstract algebra

[sacred junco]

Which one is harder?

[unique cypress]

Depends on what are your strengths

[sacred junco]

I mean in my country analytic number theory is obsolete

There are courses for Algebraic but it's only one course and it's for graduate students

[unique cypress]

Analytic number theory is obsolete

[torn escarp]

lol

riemann hypothesis solved in their country

damn

[unique cypress]

I wouldn't give up on analytic just because unis don't have a course for that

Self studying exists

[sacred junco]

yes

That's what im doing

[sacred junco]

We are just too smart for you guys

[errant otter]

Breh

[sacred junco]

What's happening here exactly?!

[sacred junco]

Actually even for (-1|p) case too

Wait nvm I understand -1 case

Still not 2 tho

[celest cloud]

any1 have apostol handy

this might be a silly question but in theorem 2.1 does the second to last equality hold by binimial theorem Apostol seems to sweep plenty under the rug

[normal heart]

which step do you not understand?

[normal heart]

send a screenshot

or take a picture

[unique cypress]

I think he meant the sum of mobius function which is just floor(1/n)

some proofs use binom expansion for it

[normal heart]

uhh okay? I still don't know which step or which theorem it is but sure

since i don't have apostol with me rn lol

[unique cypress]

Same but I still somehow remember the number of the theorem xD

[celest cloud]

heres a photo

[sacred junco]

Are the congruences arbitrary?

[celest cloud]

It’s just the binomial expansion for the second to last equality

[normal heart]

Yes, binomial

[celest cloud]

Ok thanks 🙏

[normal heart]

(alternatively you can imagine you're grouping terms together and the binomial coefficients are the results of counting the number of terms grouped together, but tbf this is just the proof for binomial (with an integer exponent anyway))

[sacred junco]

Why binomial tho?

[normal heart]

no?

[celest cloud]

It’s the exact definition of (x-y)^n @sacred junco

[sacred junco]

Like how did they think of the sequence

[normal heart]

i wouldn't say definition but it's the expansion, yes

[celest cloud]

Yeah expansion better word for it

[sacred junco]

I don't get how they are related that's it

I saw another proof for that but never understood the binom one

[normal heart]

I don't think many people could think of this at first sight, but in hindsight I think it's because they want to get the term 2^(p-1)/2 out, which is 2 multiplied (p-1)/2 times, so a natural thing to think of would be the even number congruences, since there are (p-1)/2 integers in the sequence 2,4,6,...,p-1

[sacred junco]

What about r

The two possibilities of r

I don't get that too

[normal heart]

there are two possibilities for r depending on whether p is 1 or -1 mod 4

[sacred junco]

Does that come from (-1|p)?

[normal heart]

no

you can do some experiments

try n=11

and n=13

and see which r you stop on for these two n respectively

[sacred junco]

(11-1)/2=5
11 -(11-1)/2 = 6

(13-1)/2 = 6
13-(13-1)/2 = 7

[normal heart]

do the proof again with these two values of n

see which r you'd get

[sacred junco]

5 is 1 mod 4 and 5 is 2 mod 4

[normal heart]

??

[sacred junco]

I'm doing this

oh wait it's p not r

[normal heart]

.. yes

do the proof again

with the two different values of n

and see which r you get from the proof

[sacred junco]

Wait the n you gave me are for p's?

[normal heart]

oh yes, sorry for the confusion

[sacred junco]

for p =11
10 = 1(-1)^1
2 = 2(-1)^2
7 = 3(-1)^3
4 = 4(-1)^4
6 = 5(-1)^5
6 = 6(-1)^6
4 = 7(-1)^7
8 = 8(-1)^8
2 = 9(-1)^9
10 = 10(-1)^10
...

for p =13
12 = 1(-1)^1
2 = 2(-1)^2
10 = 3(-1)^3
4 = 4(-1)^4
8 = 5(-1)^5
6 = 6(-1)^6
6 = 7(-1)^7
8 = 8(-1)^8
4 = 9(-1)^9
10 = 10(-1)^10
2 = 11(-1)^11
...

[normal heart]

do more steps until you hit one of the possible values of r

[sacred junco]

Its edited now