elementary-number-theory

[obtuse mason]

thats why you only consider the cases where m ist the product of different primes

[dreamy rain]

but isnt the result that (m-1)!==0(mod m) when m is composite true even when m consists of the same primes?

seems silly not to explain the full thing idk

[nimble cedar]

If that’s a textbook, it wouldn’t surprise me if that extension of the theorem shows up as an exercise for the student to prove

Particularly since they state “it’s not hard to show...” about it

[dreamy rain]

ah right

[dreamy rain]

i really dont understand the point of this ‘additional work’

if n|a that means n is composite anyway

[obtuse mason]

n divides a

either n is composite or it divides a

[dreamy rain]

hm i think im reading this wrong

i dont get how does fermats little theorem implies that n is composite or n|a

ohhhh

the gcd(a,n) must be equal to n? (if n isnt composite)

and if gcd(a,n)=n, then n|a?

when a>n ofc

but in this example it isnt

idk if im making sense

[alpine jasper]

fermats little theorem says that

$p$ prime and $p\nmid a\implies a^{p-1}\equiv1(p)$

so taking the contrapositive of that statement gives

$a^{p-1}\not\equiv1(p) \implies p$ is not prime or $p\mid a$

[sterile pumice]

Publius:

[dreamy rain]

ah i see, thank you

[dreamy rain]

idk if this a silly question, but could there not also be the situation that b_{i}k== 1(mod m), where k is less than m and not relatively prime to m?

[light flicker]

No you can't

if k isn't relatively prime to m, then b_i k isn't relatively prime to m either

but 1 is relatively prime to m

[dreamy rain]

ahhhh

ok thank you

and if b_i k isnt relatively prime to m, that means, there wont be any solutions for k if we write b_i k==(mod m)?

well yea, p sure thats right lol

[dreamy rain]

this is for the same question, i dont get how d cant be c_i? d^2 is 1(mod m) and so is (c_i)^2?

[light flicker]

because c_i d = -1 (mod m)

[dreamy rain]

i am dumb

thank you again

[last grove]

Hello, I am confused to how they received the final result in this proof. Can anyone suggest some pointers?

[craggy solstice]

We will go over all the factors of n in the expansion as all the factors of n are some combination of the prime factors of n and since all the factors of n are all written as a product of distinct primes which are all coprime, no (p_i)^2|(the factor of n) so mu(the factor) is never 0 by definition

They just open up the product and expand

[last grove]

I understand what you mean, and I know how to get to

but I don't know how they used the above result to get to

[last grove]

OH

NEVERMIN

I get it now

[craggy solstice]

Oo how did you get it

I now saw the wiki page and they used some mobius inversion and fourier transform things

[last grove]

ok so earlier in the book, the book shows you another theorem that you need to prove the current one

with that, you can just multiply both sides by n and the totient function

[silk vine]

There's Lagrange's Four-Square Theorem which states that any given natural number n can be written as a sum of 4 squares and similar results for k less than or equal to 4, i.e theorem's that states whether or not a positive integer can be written as a sum of k squares for k less than or equal to 4.

But are there results about whether or not, given a positive integer n and a given positive integer k, can n be written as the sum of k integer squares?

Like, how hard is it to generalize this result?

Of course I mean generalizing this result where n is expressed in a non trivial way for k bigger than 4

since n can always be expressed as a sum of 4 integer squares, then the rest of the terms would be all zero, but that's trivial

[light flicker]

@silk vine Lagrange's four square theorem allows for 0^2 so already, you wouldn't be able to get all numbers, if you restrict to positive squares

However, its true that every integer > 33 can be written as the sum of 5 positive squares

[sleek cove]

anyone have experience with either?

[dreamy rain]

im kinda lost at the point where ive highlighted

where have s and t come from, is s just a number in the rth row?

could someone may be just explain the bottom bit differently to the text

[last grove]

I think s and t are just example integers

[dreamy rain]

hm

[last grove]

oh wait

s and t refer to the row

[eager tendon]

If I divide an integrer by an irrational number the result carry on being irraitonal ?

a/rootsquare(2)

For example

a is an integreer

[dreamy rain]

could u elaborate andrew

[last grove]

im not sure about this... I'm learning this as well right now lol

[dreamy rain]

ah thats fine

yeah im just confused about the whole bottom part

like even past the s and t

[eager tendon]

How do we know irrational numbers cannot be expressed by a fraction ?

[light flicker]

that's literally the definition

[last grove]

@eager tendon

[eager tendon]

Yep I saw that

If I multiply integrers with irraitonals

the resuts are always irrationals numbers rights ?

[last grove]

yeah

ok bri im still trying to understand the page...

[dreamy rain]

oke np

[eager tendon]

Fermat theorem talks about x,z,y pow 3

it also proved that x,z,y pow 4 has no solution ?

Oh the problem talks about n <= 3

Sorry ignore that

[last grove]

but I think the book is assigning a number from [1,2,...n-1] to each row

[light flicker]

what exactly are you confused about? It's just stating that being coprime to n, only depends on the residue mod n

[dreamy rain]

oh lol

ok that explains what s and t are then

so

oooooo

ok all makes sense

thanks

[last grove]

yay nice

what book are you using by the way

[dreamy rain]

this is burtons elementary number theory, the main book im using is silvermans one

but they provided a different explanation to why the phi function is multiplicative

which i do not understand whatsoever

tbh

this proof is more common i think and makes more sense to me lol

[last grove]

lol nice

it's a nice proof

[dreamy rain]

ya

btw just to make sure, the ending is just basically saying that

because the numbers in the rth row are congruent to modulo n to 0,1,2,...n-1 (in some order) and due to the fact that being coprime to n only depends on the residue mod n (where we have stated the residues to be 0,1,2...n-1), the rth row contains exactly phi(n) integers coprime to n?

@light flicker

[light flicker]

rth column, but yes

[dreamy rain]

whoops yea

[dreamy rain]

how come p satisfying p==0,2(mod 4) wouldnt also result in phi(m) not being divisible by 4?

[light flicker]

They cover those cases

[dreamy rain]

hm i dont quite get what u mean

did the text just forget to mention it?

@light flicker

[light flicker]

No they cover those cases

If p is even, it must be 2

[dreamy rain]

ahhhh yeah

[alpine jasper]

i've been stuck on this for sad amount of time now

if there exists $n$ such that $n-n^2\equiv1(p)$, then $p\equiv1(6)$

[sterile pumice]

Publius:

[alpine jasper]

first i write $n-n^2 = g^l$ for some generator $g$ of the group $(\bZ/p\bZ)^\times$, then it must be that $n-n^2=1\implies n^2-n+1=0$... am i even on the right track

[sterile pumice]

Publius:

[alpine jasper]

@winter bear give me your power dad

[winter bear]

hmm

||complete the square||

[alpine jasper]

ok let me try that

yeah i still don't know

so i get

$\left(n-\frac12\right)^2=-\frac34$

[sterile pumice]

Publius:

[alpine jasper]

but no idea where to go from that

i know there can't exist such n tho

so if it's solvable then $n^2-n+1\neq 0$...?

[sterile pumice]

Publius:

[winter bear]

well -3 is a Quad res right

use that

[alpine jasper]

hmm

let me think about that

ok so
$\left(\frac{-3}{p}\right)=\left(\frac{1}{p}\right)\left(\frac{3}{p}\right)$

[sterile pumice]

Publius:

[alpine jasper]

i suppose it's straight forward from there

tyty

[winter bear]

np

[eager tendon]

Could someonle explain me why n > 0 and p a prime

Then root square(n) > p

[obtuse mason]

there has to be more to it

4 > 0 and 7 is prime

but sqrt(4) = 2 < 7 no?

[eager tendon]

To know if a positive integrer N is prime. You can check if N is divided for any prime P such that P >) sqrt(n)

I think it was wrong

What I wrote above

[obtuse mason]

i mean if you can divide N with any prime it aint prime

you don't have to do anything anymore after that

[eager tendon]

But you dont know that about N

You just know N value

[obtuse mason]

okay and what do you do with it?

[eager tendon]

You have to proff

N is prime

[brittle patrol]

What you're saying is "If n is not divisible by any prime smaller or equal to square root of n, then n is prime"

Which is the same as showing that "If $n$ is composite, then it's divisible by some prime $\le \sqrt{n}$"

[sterile pumice]

Gonzo17:

[brittle patrol]

But the latter is easier to show

Take any composite n, recall what it means for an integer to be composite

And from there you should be fine

[eager tendon]

But why that is true

[brittle patrol]

why what is true?

The fact that it's enough to prove this

If $n$ is composite, then it's divisible by some prime $\le \sqrt{n}$

[sterile pumice]

Gonzo17:

[brittle patrol]

?

Or just that fact?

[eager tendon]

Why that fact is true

[last grove]

if it is only divisible by primes that are bigger than sqrt(n), then if you multiply together all the primes that divide n, you will get something larger than n

I hope that helps

[obtuse mason]

i think the best way to go about it, would be just to make a couple examples for yourself

to convince yourself of the fact

[devout bridge]

If there are both infinitely many rational and irrational number, on the interval [0,1], if a random number was chosen what would the probability be that it was rational?

[obtuse mason]

0?

[devout bridge]

if it was zero then is the probability a random number is irrational 1?

[obtuse mason]

yes

[devout bridge]

why?

[obtuse mason]

because there are just so many irrational numbers

the irrational numbers between 0 and 1 are uncountable

so no bijection between $\mbb{N}$ and $[0, 1] \subset\mbb{R}$

[sterile pumice]

deekaan:

[devout bridge]

doesnt make sense how that means the probability is 0 for it to be rationakl

im looking for a proof not an intuition btw

[obtuse mason]

oof best bet would be something like stackexchange

I'm not gonna write one up

I dont like those kinds of proofs

[nimble cedar]

$ \frac{m( \bQ_{[0,1]})}{m([0,1])}$

q.e.d.

[sterile pumice]

Malix:

[obtuse mason]

rofl

[devout bridge]

@nimble cedar I dont know what

$m( \bQ_{[0,1]})$

[sterile pumice]

Shipreck:

[devout bridge]

is

[nimble cedar]

The measure of the rational numbers in the closed interval from 0 to 1

[devout bridge]

I know that I dont know what it evaluates at

[nimble cedar]

0

[devout bridge]

fr?

[nimble cedar]

Yes

[devout bridge]

thats what im trying to find a proof of tho

bit circular no?

[nimble cedar]

https://math.stackexchange.com/questions/508217/showing-that-rationals-have-lebesgue-measure-zero

[devout bridge]

thanks pal

[nimble cedar]

👍

Googley Googley Alakazam

(Teasing)

[last grove]

hey all, I'm having trouble with a part of a proof

somehow, they calculated that g(1)=1

how do they know that?

[light flicker]

multiplicative functions must always have that g(1) = 1

since 1 is coprime to everything

[last grove]

how do we know that g is multiplicative? in the proof, they start with the assumption that f is not multiplicative

[light flicker]

read the theorem

[last grove]

it says g is multiplcative on the top line.. but in the proof, they only assume that f is not multiplcative

I think I'm not understanding how proofs work

lol

[nimble cedar]

It’s a proof by contrapositive

[light flicker]

They're assuming g is multiplicative

[last grove]

sorry if this seems like a dumb question... but which line implies that?

[nimble cedar]

If g and f*g are multiplicative...

The Negation of (p and q ) is (not p or not q)

They tell us they will show not q

So p will still be true

In case the symbols I switched to are confusing, the theorem says: if (p and q), then r.

They assume not r, and need to prove not (p and q), which only requires one of p or q to be false

They chose for q to be the part they showed would be false

[last grove]

so if q is false, then p has to be necessarily true

[nimble cedar]

No, we are allowed to choose it to be true

So we do

[light flicker]

Theorems are implications, you assume things to be true, and see the consequences of those assumptions

This theorem assumes that g and f * g are multiplicative and concludes that f is also multiplicative

[nimble cedar]

Also, just because f is not multiplicative, doesn’t mean g isn’t multiplicative. So we shouldn’t assume that

[last grove]

ok Malix I understand that part now...
but what are the initial assumptions of the proof? The proof says that ** "We shall assume that f is not multiplicative and deduce that f * g is also not multiplicative." ** .

Is the top part ** "If both g and f * g are multiplicative, then f is also multiplicative." ** also an assumption?

WAIT

I GET IT NOW

the two assumptions are actually the same and not contradictory

they assume A -> B which is also implicitly assuming !B -> !A

or am I wrong

[light flicker]

uh no?

If A is that g is multiplicative and B is that f is multiplicative

Then they're assuming A and not B (and that f * g is multiplicative) and coming to a contradiction

[last grove]

oh, I set A = "g and f * g are multiplicative" and B = "f is multiplicative"

[light flicker]

okay sure, then they're assuming A and not B

[last grove]

so that works

[light flicker]

uh

They're not assuming A-> B or any implication

[last grove]

ok

thanks

!!

[eager tendon]

$a \equiv b \quad mod(n) \rightarrow |a| \equiv |b| \quad mod(n)$

This is not true right ?

[sterile pumice]

AfterJack:

[light flicker]

No it's not

[upbeat wren]

yes but not in the other direction.

lol nvm. woke up on the dumb side of the bed,

[sacred junco]

Show that the equation $x^2-y^2=n$ has only a finite number of integer solutions for each value of $n>0$.

My attempt:
First note that $x^2-y^2=(x+y)(x-y)=n$, so $x+y=a$ and $x-y=b$ are factors of n, of which there are finitely many. But $x=\frac{a+b}{2}$ and $y=\frac{a-b}{2}$, so there are finitely many corresponding integer solutions $x$ and $y$.

[sterile pumice]

zd:

[sacred junco]

Something feels a bit off here and I don't know what. Any tips would help
I think I need to show all of the solutions are of this form, and that will complete it right?

[light flicker]

Yes that would complete it

[dreamy rain]

i dont really understand the significance of gcd(a, m-a)=1? this as a fact is true, but did they mean to say gcd(m, m-a)=1? that seems more important here idk

[nimble cedar]

They want gcd(a,m-a) =1 to justify the simplification of the fractions they do in that next line

[upbeat wren]

Trick: Pick any positive whole number with no zeroes as digits. Rearrange the digits as you like but form a different number. Take the positive difference between the two numbers and add 1. Find the sum of the digits. Find the sum of the digits for this sum. Continue finding sums of digits until you have one digit left. You will get 1. I think! 🙂

[nimble cedar]

Trick: Pick any positive whole number with no zeroes as digits. Rearrange the digits as you like but form a different number.
@upbeat wren
This requires the number to be greater than 9 and not have all the same digits (ie not 11 or 33 or 222)

Also, 121-112=9

[last grove]

can someone show me how this is derived?

[alpine jasper]

What's lambda? And mu is the Mobius function?

[last grove]

yeah

lambda is the liouville function

[upbeat wren]

@nimble cedar Thank you.

[eager tendon]

Why mcm can not be > 0

Is that a convention ?

[torn escarp]

@last grove completely multiplicative functions distribute over dirichlet convolution

so if you look at $(u \star \mu)(n) = \delta(n)$ (here u(n)=1 and delta(n) = 1 if n=1, 0 otherwise) and multiply both sides by $\lambda(n)$ you get

[sterile pumice]

Merosity:

[torn escarp]

$(\lambda \star \mu \lambda)(n) = \delta(n)$

[sterile pumice]

Merosity:

[torn escarp]

make sure it's clear why u went away on the left side and lambda went away on the right side

also probably you should derive that fact about completely multiplicative functions distributing yourself too, it should be fairly straight forward by looking directly at the convolution, but if you run into any trouble just ping me

[light flicker]

@eager tendon what do you mean by mcm?

[eager tendon]

Minimum Commun Multiple

[light flicker]

Uh, the mcm is always > 0

Is that what you mean?

[torn escarp]

when are $m^2+4$ and $m^4+4$ simultaneously perfect squares mod p?

[sterile pumice]

Merosity:

[torn escarp]

lol when m != 0

[torn escarp]

irrelevant to me, made a mistake earlier that makes this not matter

[simple hearth]

Well, the answer is basically never, if m is an integer, because m^2 is a square so m^2+4 almost never is because squares are far apart.

Oh, mod p, I can't read.

[torn escarp]

For $n > 1$ is there always a prime $p > 2$ such that $n^2 = - 1 \mod p$?

[sterile pumice]

Merosity:

[torn escarp]

any ideas or rough sketches of attack are helpful, I don't really know what I might look into to begin

[simple hearth]

Factory n^2+1

err

factor n^2+1

(too much Satisfactory I guess)

(I can say more, but that is likely enough)

[torn escarp]

I don't think that does it for me, because I can write (n+i)(n-i) = 0 mod p

assuming p = 1 mod 4 let's say

[simple hearth]

Well n^2 = - 1 mod p is exactly saying p divides n^2+1.

[torn escarp]

but I don't think this shows that n+i or n-i is 0

[simple hearth]

so if I want to know which primes have this property for say, n=7, I'd calculate 7^2+1 = 2*5^2

[torn escarp]

right but I'm working the other way around

I'm saying we start with n

[simple hearth]

and so 5 is the only prime greater than 2 with this property

I know, but this is sufficient to get you the answer

so n has this property if and only if n^2+1 has an odd prime factor

[torn escarp]

ah that sounds better one sec

yeah that makes perfect sense haha

thanks

[simple hearth]

so now you just have to worry about whether n^2+1 is ever a power of 2

[torn escarp]

I see and that can't be because n^2 = 1+2+2^2+...+2^k can't be a perfect square when n=1+2m since n^2 = 1 + 4t

[simple hearth]

perfect

[torn escarp]

thanks 👍

[past mauve]

do you vguys know this one

https://prnt.sc/sqepps

[torn escarp]

wrong channel, go to one of the questions channels further down. But here's a quick suggestion, work backwards start from (x+a)^2 and expand this to match the terms with your trinomial

[sacred junco]

@past mauve c has to be a perfect square number

[sleek cove]

why does stopple have so much stuff about sigma(n) and s(n)? is it like super important for later material?

[simple hearth]

sigma(n) is a classical object that was of interest as far back as the ancient Greeks, so it is the kind of thing number theorists like to use as examples to show how powerful an idea is

it also winds up being important in the context of modular forms

I'm not sure I know what you mean by s(n)

[sleek cove]

s(n) is just sigma(n) - n

[simple hearth]

ahh, yeah, so directly digging at perfect/abundant numbers

[sleek cove]

like, its definitely interesting, with perfect numbers and amicable pairs and such, but I don't see the need to to pages of problems on these topics

[simple hearth]

There are only so many multiplicative functions to choose from is I suspect what is going on.

[sleek cove]

wdym

[simple hearth]

oh, just that it is a concrete approachable multiplicative function and there are not that many of those.

(I do not have the book in front of me, so I can only guess from the table of contents what the author is doing with them a bunch, but they show up a lot in most analytic number theory books, along with phi(n) and d(n) and friends because those are the nice examples)

[sleek cove]

like literally all of chap 2 coveres these functions as well as Tau

[simple hearth]

admittedly the other day when I was going to make an analytic number theory video one of the first things I put in the script was proving that sigma(n)/n is pi^2/6 on average

[sleek cove]

so its realated to zeta?

[simple hearth]

Yes, multiplicative arithemtic functions have a nice relationship with the zeta function, in terms of an Euler Product.

(ahhh, tau(n) is what I called d(n))

[sleek cove]

the sigma function does look similar to eulers prduct

like very similar

[simple hearth]

(one thing a lot of people do is to write $\sigma_k(n)$ for the sum over the divisors $d$ of $n$ of $d^k$

[sterile pumice]

zetamath:

[simple hearth]

and then $\tau(n)=\sigma_0(n)$

[sterile pumice]

zetamath:

[sleek cove]

hmm

[simple hearth]

Yeah, Euler's proof using that product formula to show that every even if perfect number comes from a Mersenne prime is very similar to the idea of the product formula for zeta. I don't think I'd noticed taht before!

One thing I wish would show up somewhere is a more holistic treatment of generating functions.

[sleek cove]

Is there a formula/pattern to finding these values?

[simple hearth]

you will want to use your formula for tau(n)

[sleek cove]

that if n=p^k, T(n)=k+1, and if (m,n) = 1, then Tau is multiplicative?

[simple hearth]

yes

so, if, e.g., I wanted the smallest number with 101 divisors

what would that number be?

[sleek cove]

I have no idea

im trying to work out a formula

[simple hearth]

well, 101 is prime

how can I get a prime number of divisors?

(out a multiplicative function)

[sleek cove]

you can get a prime num of divisors by raising itto itself minus 1?

so 101^100? but thats like massive idk

[simple hearth]

what about 2^100?

[sleek cove]

well yeah

but thats far from minimal, no?

[simple hearth]

I claim that is minimal

[sleek cove]

uh

wait nvm

[simple hearth]

got it?

[sleek cove]

yeah

but that only works for prime number of divisors

[simple hearth]

correct, so when you go on to say, find the smallest number with 8 divisors, you ahve to look at ways you could factor 8

8, 42, and 22*2

err 2 * 2 * 2

[sleek cove]

yea

[simple hearth]

so, 2^8, 2^4 * 3^2, and 2* 3 *5 all have 8 divisors

[sleek cove]

yes

wait no

[simple hearth]

oh sorry

I screwed taht up 😛

2^7

and 2^3 * 3

and 2 * 3 * 5

[sleek cove]

ok yea

but you still have to calculate the minimum of those three values

[simple hearth]

yes

so what you have is really more an algorithm than a formula

[sleek cove]

but say I had like D(360) or something

that would take a while

I see

[simple hearth]

oh yeah, you definitely do not want to compute D(100!)

[sleek cove]

mmhm

[sacred junco]

cool problem: show 55, 5050, 500500, 50005000, ... are triangular numbers. (so for all k>=0 numbers with 2k+2 digits such that first one is 5, k zeroes after it then again one 5 and rest are zeros, are triangular)

[deft verge]

||
"The formula for calculating the nth triangular number is: T = (n)(n + 1) / 2"
and the formula for getting the nth of your fancy numbers is (10^n)*(10^n + 1) / 2
sorry, I know nothing of how to formalize this
||

[sacred junco]

that's enough, no need to formalize any more

Try this one then: same thing but for sequence 45, 4950, 499500, 49995000,...

[deft verge]

||oh, bc T(n) = ((n + 1))((n + 1) - 1) / 2||
wow that's pretty funny

[sacred junco]

uhhh can you elaborate? How does that say anything?

at least I did it other way I guess

[deft verge]

yeah that was brief
I mean that your second sequence is much like your first sequence but you have (thing)(thing - 1)/2

[sacred junco]

it's also true for the sequence 21, 2211, 222111, 22221111,... 222111 is 666th triangular number btw

[wispy moon]

How do I find primitive roots of a large prime number such as 197?

[wild zinc]

I'm not sure of a good method to find a primitive root

but once you've found one primitive root g, the others are g^k, where k is coprime to 196

[wispy moon]

Thank you, how would you go about finding one root?

[torn escarp]

brute force

start with 2, and start raising it to powers and see if it gets to 1 prematurely or not

[wispy moon]

would that be the only way or would you be potentially able to use discrete logs to solve this?

[torn escarp]

in doing so you'll get a list of other numbers that are powers of 2 which you would then skip

what algorithm do you have for computing discrete logs?

[winter bear]

also say the order of 2 is (p-1)/n, you can then restrict to looking for nth roots of 2

hmm on second thought i dont think this will make the algorithim more efficient

[wild zinc]

hmm

I think we can use multiplicity of legendre symbol

bc euler's criterion says the primitive roots are those with (g / p) = -1

so you check 2

check 3

don't need to check 4

check 5

don't need to check 6

(bc if both 2 and 3 have (g / p) = 1 then so does 4, 6 etc.)

[wispy moon]

Would you still require brute force to check 2,3,5 etc

[wild zinc]

hmm, 2 you can check nicely

using one of the supplements to quadratic reciprocity

[wispy moon]

The question I got is a diffie-hellman one - Give an example of how Alice and Bob can exchange keys, using the prime p = 193 and a primitive element g (you need to determine a primitive element g yourself)

[wild zinc]

bc you have (2 / p) = 1 if p = +/-1 mod 8, and (2 / p) = -1 otherwise

I think this is the result at least

p = 193 is 1 mod 8 so 2 is not a primitive root

p = 197 is 5 mod 8 so 2 is a primitive root

actually I'm not sure all this euler criterion logic is correct

[winter bear]

this isnt right btw

[wild zinc]

yeah mb

[winter bear]

not all non-QRs are generators

[wild zinc]

if (g / p) = 1 you can guarantee it isn't

[winter bear]

(sizing reasons, phi(p-1) generators but (p-1)/2 NQRS$

yeah

[wild zinc]

so if your p is 193 I guess this at least tells you not to check 2 :^)

"brute force" here is checking when the power is some divisor d of p-1 btw

so it may not be too bad to do

[winter bear]

factoring p-1 itself might not be algorthimically effecient

im not sure

[wild zinc]

yeah probably not

but for 193 or 197 it's not too bad

[winter bear]

yeah. my thought is two fold, one is where we do not factor p-1 and then slowly eliminate the subgroup generated by each of 2,3 etc

and then another is where we do and then test all numbers (still eliminating but less so) against the divisors

[wispy moon]

would this method work?

[wild zinc]

yeah that works just fine

[winter bear]

yeah should be fine

factorization is NP iirc

so might not be the most effecient way?

i mean this problem is NP too probably so lol

oh theres some interesting literature on this

so it seems we do need to factor for deterministic algorithims

[wispy moon]

In the example above why is 2^152 and 2^40 not also tested?

[winter bear]

you dont need to, you already know 2 is not a generator

[wispy moon]

ah right i understand now

[winter bear]

turns out generalized RH implies that if $g$ is a generator mod $p$, then there is some $g\leq O(\log^6 (p))$, so some algorithim test it against that hoping to get lucky

(but yeah ur prolly not looking for this, the factoring trick is prolly whats intended rip NP)

[sterile pumice]

JohnDoeSmith:

[wispy moon]

alright I think I've got it

thanks for the help people

[sleek cove]

so I looked this up, and it seems to be 1500 not 300, but how do they pick the exponent?

[wild zinc]

might be an old bound

proving it is almost certainly not easy

[sleek cove]

well yeah, but like, why not 1499 or 1501?

[simple hearth]

almost assuredly the proof, if you look at it, looks like "any counterexample must have the following properties..." where the list of properties is so restrictive that you can enumerate all the numbers with those properties less than some huge bound (e.g 10^1500)

and then you just do a computer search of all of those numbers

Like here is a list (from wikipedia) of theorems we know about odd perfect numbers

[sleek cove]

hmm

these bounds are interesting

[simple hearth]

Do you know any group theory?

[sleek cove]

like 3 weeks of intro group theory lol

so no

[simple hearth]

So there was this many decade long search to find all the finite simple groups. It doesn't matter what those are. But it proceeded a lot like this, where people kept proving that if there was one that we didn't know about, it had to have this ridiculous list of properties.

and so people became convinced that there wasn't one

and eventually they narrowed it down to that if there was such a thing, it had to be a group with order 808,017,424,794,512,875,886,459,904,961,710,757,005,754,368,000,000,000

and that number is just so absurd, it couldn't possibly exist, right?

and then someone found it.

[sleek cove]

tf

[simple hearth]

The Monster Group, as it has become known

[sleek cove]

by guess? surely a computer cant check that

[simple hearth]

They found it as the automorphism group of a particular lattice, if I recall correctly

So this whole "cascading list of restrictions" is not an uncommon thing to see in math. Sometimes it leads to eventually getting to "there aren't any" and sometimes it leads to finding that this one thing dodged all the restrictions

[sleek cove]

yeah I get that

its just that like, these seem kind of odd lol

[simple hearth]

yeah, probably every piece of one of these is a paper.

[sleek cove]

yeah, it just seems kind of weird/arbitrary at a glance from my perspective as a rising soph in undergrad lol

[simple hearth]

Elementary number theory is incredibly weird/arbitrary. I really recommend reading the paper "The Law of Small Numbers", by Guy. it's short, and readily available online. Basically, I think the right view is that the deep theory dictates the behavior of large integers, but there are a lot of "small" integers where strange accidents happen.

like, for example, n!+1 shouldn't be a square, but it just so happens it is a bunch of times for small n

[sleek cove]

how do people write out the aterisk for convolution

like is a 5 pointed star acceptable lol

[simple hearth]

haha well, anything you write by hand is pretty mcuh only for you, so you do you

I draw three intesecting line segments

[sleek cove]

mu(n) = 0 iff n is not square free, right

[simple hearth]

right

[sleek cove]

I'm not following what dq is from

take n=30 = 2 x 3 x 5

d = 1, 2, 3, 5, 6, 10, 15, 30,

let q = 5

how can dq divide 2 or 3 or 6

[light flicker]

what is u here?

[sleek cove]

sorry u(n) = 1 for all n

mu is mobius

[light flicker]

dq is a divisor of n, not a divisor of d

[simple hearth]

so what they're saying is that they are pairing each divisor of 6 with that divisor times 5

so 6 gets paired with 30, 3 gets paired with 15, 2 gets paired with 10, 1 gets paired with 5

That's all of the divisors of 30

but each pair contains an elements whose mu's are opposites

[sleek cove]

ahh

each prime will cancel with its multiplication with q

thanks

[simple hearth]

yeah, mu is multiplicative, so mu(xq)=mu(x)mu(q) = -mu(x) as long as (x,q)=1

so mu(x)+mu(qx)=0

[sleek cove]

[steady nest]

multiplicative inverse(redirected from other channel) @light flicker

[light flicker]

What do you mean by that

x and y are multiplicative inverses?

[steady nest]

yeah i believe

[light flicker]

can you define multiplicative inverses for me

[steady nest]

aren't they just reciprocals

$ X and \frac{1}{X} $

[sterile pumice]

suck2015:

[light flicker]

but why does that mean that x = y (mod p)

[steady nest]

ok scratch that

that just means x and y have the same remainder

[light flicker]

when dividing by p yes

a better way to say it is that if you take the number x - y

then this will be divisible by p

[steady nest]

yeah

because x-y = 0 mod p

[light flicker]

right

and so now you can check this for p-1 and -1

[steady nest]

?

p = 0 (mod p)

[light flicker]

yes

[steady nest]

what does that mean?

p = pk , k being an integer?

oh

then k just equals 1

🤦‍♂️

thanks Zoph

[last grove]

hey all, I'm confused to how they turned the derivative into f(n) - f(n-1)

or do the curly brackets {} represent something important?

[sacred junco]

well, $\int_{a}^{b} f'(x) dx = f(b) -f(a)$

[sterile pumice]

Godel:

[sacred junco]

you can take (n-1) out the integral since it's just a constant

[last grove]

oh

thanks a lot

xD how did I not notice that

[lucid girder]

Please help me to finding Cp(V) and Cs(V)

[fervent crest]

Doesn't feel very number theory to me

Probably post it in question channels or in physics server

[lucid girder]

Actually findind the equations

Cp(V) equation and Cs(V) equation

[fervent crest]

I'm saying this isn't the place to ask

But look up separable differential equation

[lucid girder]

oh thank u

[vast dove]

Are we still talking about Wilson's theorem?

[simple hearth]

I love Wilson's Theorem

I put a question on one of my cryptography exams about whether it would be an effective primality test

[wild zinc]

O(n) primality test, pretty good

[simple hearth]

haha if you even forget and do the digits thing backwards you could call it O(log(n))

[last grove]

Wilson's theorem is pretty cool

in fact, anything involving consecutive numbers in number theory is pretty cool

[last grove]

hey, how did they combine 5) and 6) to prove the theorem?

I am thinking that they did something with this

[light flicker]

"integration by parts"

[last grove]

yeah...

but how did they subsitute it back?

[alpine jasper]

you can first write

$4503x\equiv4(1803)$

and since you said gcd = 3, and $3\nmid4$, the first eq has no solution

[sterile pumice]

Publius:

[alpine jasper]

uh yes, moreover, there are exactly gcd(4503,1803) = 3 solutions

you can use euclidean algo and perform back sub

do uhh,
4503 = 3 * 3606 + 897
3606 = ...
...

once you get to the bottom, you can solve for 3 (aka the gcd you just found)

i don't have time to go in to details but that's the idea, try a small example if you're confused

@sweet jay

you can sort of guess and check when the (mod n) has a small n, but in this case idk if there's an easier way

[alpine jasper]

not sure why your solution didn't work, maybe a silly mistake?

in any case, you can generate more solutions once you found a solution

do you know how?

if $x_0$ is a solution, then $x_0 + \frac{1803}{(4503,1803)}$ is another, keep adding and you'll get more

[sterile pumice]

Publius:

[alpine jasper]

once you added for a total of $\frac{1803}{(4503,1803)}$ times, you've obtained all incongruent solutions, in this case, 2 times

[sterile pumice]

Publius:

[alpine jasper]

np

[winter crow]

we have to find such x and y right ?

@alpine jasper

[alpine jasper]

wdym?

technically, finding x only will suffice, but usually you get y for free via back sub

[winter crow]

now we add too $\frac{1803}{(4503,1803)}

but what to add

[alpine jasper]

(a, b) denotes the gcd of a and b

if that's what confuses you

oh shit wops

i said something wrong

[winter crow]

okey

[sleek cove]

whata lambda here

for the distribution of perfect numbers

[simple hearth]

that's a gamma, and I'm guessing it's Euler's constant

https://en.wikipedia.org/wiki/Euler–Mascheroni_constant

[sleek cove]

lmao yeah, its too early for me

hmm ok

[simple hearth]

it shows up a lot in analytic number theory

[sleek cove]

Im confused ab the << notation

couldn't you switch f(x) and h(x) and the relation would still hold?

[light flicker]

yes

[simple hearth]

What book is this? I feel like I just saw taht paragraph in some Analytic Number Theory book

[sleek cove]

so the relation is kind of useless if the functions are of the same degree at least for polynomials

[simple hearth]

I wouldn't call it useless, it just is much weaker than <

but the functions in analytic number theory have a lot of noise in them

and so if you want to compare, e.g., pi(x) and sqrt(x) or something like that, you're going to need more flexible relationships

[sleek cove]

gotcha

[simple hearth]

also, having relationships like this helps you a great deal in proofs by making you not have to carry around inequalities evrywhere

[sleek cove]

hmm

I'm confused, why is finding a constant C necessary here, or anywhere rather

[simple hearth]

how can it be wrong?

[winter crow]

because 320 is too high

value to find

[simple hearth]

I don't think it's that bad

[winter crow]

i cant solve

can you help me

[simple hearth]

Hint: 320 = 2^6 * 5

[winter crow]

i have already know that man

[simple hearth]

Hint 2: phi is a multiplicative function

[winter crow]

ım stuck in the end

this hint not help me

because ı know that

@simple hearth

[simple hearth]

so if phi(n)=320, what primes could divide n?

[winter crow]

1 2 4 5 8 10 16 21 32 40 64 80 160 and 320 divisors of 320

if we add +1 each one

and choose prime

we obtain that 2 3 5 11 17 and 41

right ? @simple hearth

[simple hearth]

That sounds very reasonable to me.

and that's not a very long list

[winter crow]

what primes could divide n? answer of this question

2 3 5 11 17 and 41 these

or what ?

[simple hearth]

Yes, so now what powers of those primes could divide n?

[winter crow]

n=2^a 3^b 5^c 11^d 17^e 41^f ??

[simple hearth]

yup, so now you just have to find all the a b c d e f that work

it's like a little soduku

[winter crow]

how can I do that

[simple hearth]

for example, can f=2?

[winter crow]

absolutely not

noww if 41In then 41.m=n right ?

so phi(n)= phi(41) phi(m)

and then phi(n)=40 phi(m)

since phi(n)=320 then we have to find phi(m)=8

m values

[simple hearth]

Exactly, now you've got it

[winter crow]

then convert n values to product 41

but i have question

are we apply all of this values ?

what about 2 ?

if we apply we concluded same thing

as a question

phi(m)=320

[simple hearth]

yes, phi(2)=1, and so if m is odd, phi(2m) = phi(m)

[winter crow]

now when we solve for 3

we obtain phi(m)=160

this is again too hight

am ı use process from the beginning ?

to find

[simple hearth]

isn't phi(11*17)=160?

[winter crow]

oww You are right

[last grove]

hey, does anyone know where the 1 comes from?

[simple hearth]

its' the n=1 term of the series

note the strict inequality in the second formula

wait, now I'm confused and think maybe it should be a -1

oh, no, it's a +1

[last grove]

I think you have the right idea...

[simple hearth]

because what they're really doing is aplying the formul for 1/2+1/3+...

and then tacking a +1 on both sides

[winter crow]

i cant reach 800

this is solution for n

i check that calculator

but i cant reach

[last grove]

thanks bro zetamath

I get it now

[sleek cove]

are we supposed to use a calculator for this lol

[simple hearth]

I think very little is lost in using a calculator at the analytic number theory level 😛

[last grove]

you're gonna need a big calculator 😳

[simple hearth]

I almost always have a sage window open

[sleek cove]

I dont see how to do this by hand lol

finding big O

wait

[simple hearth]

oh, H_1000 is just the 1000th partial sum of the harmonic series?

you can do that with Euler Maclauren

[sleek cove]

uh idk what that is

[simple hearth]

https://en.wikipedia.org/wiki/Euler–Maclaurin_formula

It is a tool sepcifically for answering this question

but I'm guessing they used it in the proof of the result you gave

so you can just use that result prboably (-:

oh, never mind, they just used the bound on the error in a lefthand Riemann Sum

[sleek cove]

yes

[simple hearth]

but if you dig in the proof, instead of saying that the error is O(1/n), the error is literally <1/n

[sleek cove]

yes

[simple hearth]

which means you get 3 decimal places for free

[sleek cove]

oh

yeah I didnt realizd

so I just need ln plus gamma

much more managble lol

[simple hearth]

yeah, that should do it (-:

but fun fact, when Euler was studying 1+1/4+1/9+1/16+... he calculated the sum to 17 decimal places by hand

[last grove]

bruh

[sleek cove]

isnt that like 10^3 terms

[simple hearth]

(for comparison, if you literally calculated the sum of the first 10 trillion terms, you would only get 10 decimal places)

[sleek cove]

oh nvm lmao

[simple hearth]

anyway, in two weeks my video on this should be up.

It's been my current project.

[last grove]

nice :))

send us the link when you're finished

[simple hearth]

Will do, I posted the link to part 1 of my intro to analytic number theory here

but it is a good topic to transition because the method Euler used to show that zeta(2)=pi^2/6 is exactly the same method that Riemann used to show the zeroes of the zeta function dictate the distribution of the primes

[last grove]

Euler's proof is pretty insane

[simple hearth]

a "coyote time" proof

there are a lot of those in math

[last grove]

you mean a proof created in the midst of being high?? xD I guess people are more creative when "high"

[simple hearth]

when Wile E Coyote runs of the edge of a cliff chasing the roadrunner he doesn't fall until he looks down

[deft verge]

I still don't understand why his ski + refrigerator solution didn't work

[simple hearth]

(the proof of the Weil conjectures is, to my eye, the most impressive of these.)

"oh, if we had a cohomology theory for these wholly non-geometric objects then the result would be a trivial consequence of the Lefshetz trace formula. Of course."

[last grove]

hmmm... how did they get this result?

did they plug it into the Eulers ummation formula

[simple hearth]

they drew the graph of the sum (as rectangles) on top of the curve

[fervent crest]

It's abel summation formula

@last grove

[winter crow]

can ı ask another question @simple hearth ?

[simple hearth]

so the area of the rectangles is the sum and the area under the graph is the the integral of 1/x which is log(x)

so the thing in the limit is the sum of all these triangulish regions

and say, the second one is : 1/2 - \int_2^3 1/t dt

and you can do a little bit of trickery to turn that into what is written above

[This is just proving the Abel summation formula in this case, though]

@winter crow You can ask, there are probably plenty of folks around who might answer!

[winter crow]

but for the second question

ı cant use euler formula

[simple hearth]

I bet they want you to use the Chinese Remainder Theorem

[winter crow]

both of questions or just 2 ?

Is my solution wrong for a ?

[last grove]

dang, @fervent crest , I never knew that existed. Thanks a lot sir

[fervent crest]

Also read what zetamath said above ^

[simple hearth]

the number of times I've said to myself "oh crap, I just reproved the abel summation formula in this special case" is high

[sacred junco]

i can tell you the last digit but not the last 2 digits

[last grove]

thanks zetmath man

im gonna learn that asap

[simple hearth]

FWIW, I find the abel summation formula highly unintuitive, so even when I prove something that would have fallen out of it, it is often insightful

[winter crow]

@sacred junco why 17^2=289 then the last two digit 89

[sacred junco]

bc the last two digits are 89

[winter crow]

yes as I said

then whats the problem here

[sacred junco]

bruh idek what u were asking

[winter crow]

ı was asking part b

[sacred junco]

ok

[deft verge]

the repeating pattern for the second digit is 0,1,6,5,2,9,8,3,4,7,

[sacred junco]

ye

[last grove]

what is the high-level idea for proving this

using abel's summation formula?

sorry if I'm asking too much 😫

lol you guys didn't mean the euler summation formula.. did you??

[sacred junco]

Abels should work

Looks like typical problem for Abels summation theorem

[simple hearth]

did you see how to derrive it from my picture earlier, andrew?

[last grove]

it was a helpful point

I was able to visualize it better

I used Euler's summation formula to prove it though... I'll upload a picture of my process later

it would be interesting to know how to use Abel's formula to tackle this though

[simple hearth]

So what do you get if you apply the Abel summation formula to the sum from 1 to x of 1/n?

[last grove]

so I will let phi(n) = 1/n

and a\subn = 1 always

(if I do it the other way around, then the derivative of phi will be zero and the integral disappears)

wait no

it doesn't make sense that way

[sleek cove]

I'm stuck at this step trying to prove this

am I missing smth obv or

[simple hearth]

I think the traditional way here is to use the next term in Euler MacLauren

[sleek cove]

I still dont know what that is lol, I haven't learned that

idk how to deal with the n^C

[simple hearth]

I think given that you're doing this kind of thing, it is worth learning the formula.

I can link you to a couple of articles I found useful when learning it

or alternatively you can watch the really excellent mathologer video about it

[sleek cove]

alright then, I'll check out his vid, I like his stuff

if I still dont get it I'll lyk

[simple hearth]

I'll note, btw, this is a form of Stirling's Formula

but Stirling's Formula gives yo uthe actual constant, which you can't get out of EM

(that's just context, it doesn't mean you shouldn't figure out the exercise, of course)

[sleek cove]

um not going to lie, this is fairly intimidating lmao, and by fairly I actually mean very

[simple hearth]

it looks intimidating, but it is not as bad as it looks. Basically, the place your log(n!) approximation is coming from is from approximating \sum log(n) with \int log(x) dx

[static sparrow]

I've got some weird stuff but it should work
https://cdn.discordapp.com/attachments/488104216678760469/717792123524481184/94730921676115968.png

[simple hearth]

and what this formula gives you is an approximation for what that error is

[sleek cove]

hmm

yeah I remember the sum being interchangeable with the integral

I'll try that if I can't get grasp the euler maclauren method, thanks Tuong

[static sparrow]

👍

[simple hearth]

I think the result you want follows from EM with p=1.

[sleek cove]

this vid?

[simple hearth]

Yes

[sleek cove]

ok

wait, so what is the function that I am replacing with the sum on the left

log(n) or log(n!)

[simple hearth]

log(n)

because log(n!)=log(1)+log(2)+...+log(n)

[sleek cove]

oh duh

[simple hearth]

I'm sorry, I maybe should have made sure we were on the same page about that earlier!

[sleek cove]

wait

but the derivative is never constant

so why would p be 1

[simple hearth]

I think I really want p = 2 in your formal, that is through the first derivative. This is only an approximation, afterall

[sleek cove]

oh right

am I summing from 1 to n or 2 to n

[simple hearth]

log(1)=0 so it shouldn't matter much

since you're looking for an asymptotic bound anyway, that only shifts stuff by a constant

[sleek cove]

so do you think I should evaluate p=1 or 2

[simple hearth]

p=1 first, see what you get, and then do p=2

you should not need more than that.

[sleek cove]

p=1, not sure what to do with this exactly

I know that the error, or big O will decrease with larger p values

but I don't see how this will allow me to arrive at the original claim

[simple hearth]

so rewrite this as log(n!) = ...

and then use log properties to collect stuff

noting, e.g., that n= log(e^n)

actually, I think this is more terms than you need, because n log(n) - n + log(n) is already log(n*(n/e)^n)

[sleek cove]

no

wait

that doesn't help

wait

yeah i dont get how that helps

I was already at that step before trying this

but you have n^C

[simple hearth]

So what I get just from the integral is that log(n!) = log(n (n/e)^n) +A(n) +C

where |A(n)| is at most as big as log(n)

and C is a just a constant

so you could write that as

log(n!) = log(n (n/e)^n) + O(log(n)

which certainly implies your result

(the EM makes that error term much more precise)

(I'm sorry, I think I gave you a bigger hammer than was needed for this problem)

[sleek cove]

yeah that makes sense

however, the proof is supposed to just rely on just the theorem

https://cdn.discordapp.com/attachments/418981682117345288/717782461328654346/image0.jpg

which I still cant figure out

[simple hearth]

Well the theorem just gives you log(n!) = log((n/e)^n) + O(log(n)), so that would say there is a constant C such that for large enough n, we have log(n!) \le log((n/e)^n) + C*log(n)= log((n/e)^n) + log(n^C)

so, there is definitely an N such that if n>N then (n/e)^n > n^C

so then for n>N we have log(n!) \le 2 * log((n/e)^n) ... Something went awry here?

[sleek cove]

what does \le and \ ge mean

less and greater?

[simple hearth]

$\le$ and $\ge$

[sterile pumice]

zetamath:

[simple hearth]

sorry , I can actually compile the latex

this is easy if yo uuse the fact that you prove, in the proof of the 'Know" that the error isn't just less than C*log(n), it is less than log(n)

I don't think the fact, as stated, with no other context, is sufficient fro the desired result, however

[sleek cove]

This is the hint from the answer section, which did not help me

[simple hearth]

I would want to start exactly with the line written there

and then use e's to get rid of the logs

[sleek cove]

I did, and arrived at smth similar, you still have n^C

[simple hearth]

where did you get a C from?

[sleek cove]

oh wait

hold on

bruh

I feel so dumb

like actually

I spent too much time thinking about C, and the definitionsof << and O

[simple hearth]

haaha it happens to the best of us

but yeah, to elaborate just slightly, this gives you that it's at most of order n * (n/e)^n

but if you go one more term down the EM thing, you learn that front term can be repalced with an n^(1/2)

[simple hearth]

Perfect

[sleek cove]

yeah that makes sense

[simple hearth]

so the "implied constant C" is the e

[sleek cove]

yup

[simple hearth]

well sorry for contributing to confusion there, but hopefully it makes sense now

[sleek cove]

I was trying to like, make my way backwards through the definitions involving O and << from the original theorem, instead of actually thinking about what was going on

no, thank you lol

plus the euler maclaurin expansion will definitely be helpful in the future

[simple hearth]

oh yeah, it is in the intro chapter of most analytic number theory books because you use it all the time

though it is suuuuuper finicky and weird

[sleek cove]

the first time it's mentioned in this book is 219/400, im only at 53 ish lol

[simple hearth]

just as an example of how finicky it is, you choose this number p of terms you want to use, and even for fairly small p it is often very accurate

but then in most cases, for large p, the sum actually diverges

let me get that in a more human file format

[sleek cove]

how would that happen though

[sleek cove]

like wouldnt that require and increasing derivative

[simple hearth]

so, one of the things Euler used this for was to approximate zeta(2)

and he used 10 terms of the EM approximation, and got 17 digits of accuracy

so what you're looking at is a graph of the number of digits of accuracy you get out of EM for that series based on the number of terms you use

so you very rapidly get 17 digits of accuracy

and then it hangs at exactly 17 digits of acuracy for a bunch of terms

and then the bottom falls out and it explodes

(so negative 20 digits of accuracy means the 20 digits before the decimal place are incorrect, btw)

[sleek cove]

how does that happen lol

[simple hearth]

roughly speaking,what's happening is that taking a bunch of derivatives gives you giant factorials

e.g. the hundreth derivative of x^100 is 100!

[sleek cove]

yes

[simple hearth]

and so at each new term, you're chopping off the error from the lower order terms

but you're magnifying the error of the higher order terms

and so at first, you're winning

but eventually you lose the battle

(and lose it fairly catastrophically as the illustration shows)

[sleek cove]

and so at each new term, you're chopping off the error from the lower order terms
@simple hearth what does this mean

[simple hearth]

I'm off for now, but I can elaborate later

[sleek cove]

okie cool, lmk

thanks

[sleek cove]

oof I thought this book was done with Tau, literally a whole ass chapter on it

[simple hearth]

tau is the number of divisors?

[sleek cove]

ye

[simple hearth]

I like d(n) so much better, but it does get ugly when you do mobius inversion ahd have d(d) floating around everywhere

[sleek cove]

where can I find a proof of this, the one for k=3 was gross, but I can't find one googling that has this form

[fervent crest]

What's tau(n)?

[sleek cove]

sorry, divisor function

[simple hearth]

its on page 101 of Koninck and Luca's Analytic Number Theory book

their form of it is d(n) = n^ O(1/log(log(n)))

(obligatory joke about what sound a drowning analytic number theorist makes)

[sleek cove]

ok sweet thanks

[simple hearth]

https://en.wikipedia.org/wiki/File:Riemann_Explicit_Formula.gif

If you have not seen this, I think this is really awesome. It shows how Riemann's formula for psi(x) in terms of the zeroes of the zeta function fits it near perfectly

[sleek cove]

thats the floor of log x?

sum of

oh nvm I found it

thats wierd

[last grove]

it's really cool

there's a formula that uses the zeros of the zeta function to create this curve that fits the prime counting function really nicely (I think)

@simple hearth I think it's this one

and the more zeroes you include, the more accurate it gets (to a point)

[simple hearth]

It actually converges to it perfectly even

[torn escarp]

interesting, I wonder if anyone's thought about this sort of Gibbs phenomena at the discontinuities or derived any kind of information from them

https://prnt.sc/stfuus

seems like something someone way smarter than me would have already looked into already and found some kind of bound of some sort, just curious if you know anything about that so I don't consider wasting any time on this lol

[simple hearth]

I don't know anything about it, but I'm very far from an expert on this

[sleek cove]

the reason he lets n=N!, is so the first inequality holds?

and thus H_n becomes larger than log (N)

[simple hearth]

yeah, N! is divisible by every integer from 1 to N

that's all that is being used here

[sleek cove]

yup making sure

[simple hearth]

I would just have phrased this as $\lim_{n\to \infty} \frac{\sigma(n!)}{n!} = \infty$.

[sterile pumice]

zetamath:

[sleek cove]

wait fr

I feel like it should be 0

[simple hearth]

well, it can't be 0 because n! is a divisor of n! so the ratio is always at least 1

[sleek cove]

wait

oh yeah i was thinking n

wait

even then

oh yeah

i was summing divisors of n, not n!

my bad

[simple hearth]

but $\frac{\sigma(n!)}{n!} \ge 1 + 1/2 + 1/3 + ... + 1/n$ and the latter, in the limit, is the harmonic series, which famously diverges

[sterile pumice]

zetamath:

[simple hearth]

it's not a different argument than the one given in the text you quoted, but I think it puts the emphasis on the right part

[sleek cove]

$\lim_{n\to \infty} \frac{\sigma(n)}{n!} = \infty$.

[sterile pumice]

Sideurk:

[sleek cove]

I was doing this

which didnt make sense lol

[simple hearth]

haha yes that definitely isn't true

[sleek cove]

yeah I see that yours is equivalent

so you get s(n) > n(C-1) which implies this, right

[simple hearth]

what is s?

[sleek cove]

sigma(n)-n

[simple hearth]

yeah, sure.

[worldly tree]

HI, for euler totient. How do i figure out all numbers n such that phi(n) = 16 ?

I try, maybe just 1?

@winter bear

17

[winter bear]

well i mean what did you try theortically not computationally

like what ideas do you have

[sleek cove]

its like a puzzle kinda like sudoku

[worldly tree]

I think it is one less than prime

So just 1

[winter bear]

well is that necessarily true?

how do you get phi for a general number

[worldly tree]

ph(n) = p-1 ?

[winter bear]

thats for primes

[sleek cove]

for n=p

[worldly tree]

Oh

Maybe

[sleek cove]

factor n into prime powers then work backwards

[worldly tree]

(p_1^k -p_1^(k-1)) .... (p_r^k - p_r^(k-1)) = 16

[winter bear]

bad () but yeah

[worldly tree]

Oh I edit