elementary-number-theory

[graceful pebble]

say you wanted the set of numbers that are a_i mod m_i

CRT helps you solve this. You can either solve explicitly for the set but it's significant strength is the existence of such a set of infinite solutions

@weary eagle lemme know when you come online, we'll go step by step

[heady plinth]

It's surprising that they had to wait this long.

In any case @weary eagle you can watch a youtube video about it and then ask questions about what is unclear, that would make it easier for people to answer.

And if it is that nothing makes sense to you then I think you should start at the beginnings of modular arithmetic.

[weary eagle]

I know that it exists and works for that

I have mastered fermat,wilson,toitent

Just one piece

How to use crt is left

I wanna learn how to use crt

I know what it is

@graceful pebble

(again,mods pinging for doubt)

I know like when like
X mod 5(mod 3)
X mod 7 (mod 4)
We let x= 3x+5=7y+4

Then we do 7x-3y=-1

Ie 3x-7y=1

Wait.... Isn't this the whole concept

But for this we have to plug and chug too much

Which is not good is there any like algorithm or smth for exact soln

[heady plinth]

Yes

There is

[weary eagle]

Can u come #help-6 and explain it

[heady plinth]

A sec

[magic rain]

Here is the second challenge. I think that's a nice problem

[rotund gust]

Please post images (such as PNGs or JPGs) of the question rather than other filetypes such as PDFs which have to be downloaded. Non-image downloads can potentially contain viruses or other security risks.

[unique cypress]

[tall arch]

p2 was a putnam problem i think

or an IMO problem

seomthing along those lines

[magic rain]

Oh, great! The whole exercise is part of the French tournament “Évariste”

[fossil sundial]

I tried chatgpt on problem 2, it can actually solve it

[midnight cloak]

yes chatgpt is good at problems it knows the answer to

[rain wren]

do we have special terms for "set of products of n biprime numbers"?

[carmine tide]

semiprimes?

[rain wren]

that's semiprime
this one is "products of it"

semiprime set\this one =
{16, 24, 40, 60, 64,...}

[carmine tide]

Are you sure that 64 belongs here? Because I'm thinking you meant to say 4-almost primes ... ?

[rain wren]

...uhh, not what i meant

basically if we have a set of semiprimes, choose n numbers from it, can choose members multiple times, multiply the chosen numbers, then you get another set

[ionic latch]

would that be union of the sets of 2n-almost primes

[rain wren]

oh that's the name

[rain wren]

oh right, 729 is also in this set

so 2n-almost primes it is

[rain wren]

also by this page, 64 is a 6-almost primes, right

[tepid vector]

So I have this problem where I need to solve $5x + 1 \equiv 13 (mod 23) $

I don't know how to do that

I know through equivalence classes modulo n that the equation $5x + 1 - 13 = 23k$ but I don't know how many different x's satisfy the equation

[sterile pumice]

Heavy_Hussar

[kindred moss]

if you can compute the inverse of 5 mod 23, you can multiply both sides by that inverse

(we know an inverse exists because 5 and 23 are coprime, and more generally since 23 is prime every nonzero number has an inverse)

[tepid vector]

Alright that should work. Now I need to figure out how to take modulo inverses

[kindred moss]

extended euclidean algorithm works

alternatively you can try guessing a power of 5 such that 5^n is congruent to 1, and then 5^(n-1) will be the inverse

for any nonzero number x mod prime p, you can always write the inverse of x as x^(p-2), and then reduce

(this is essentially fermat's little theorem)

[tepid vector]

What does the reduction look like here using Fermat's Little Theorem?

5^(21) is what I get but I don't know what reduction for that looks like

I'm not doing this for an assignment (I'm doing this for fun) but I'm very lost here

I know the extened euclidian algorithm better so I'll use that

[wooden glen]

5^21 · 5 = 5^22 == 1 (mod 23) due to Fermat's little theorem.
So 5^21 is multiplicative inverse to 5 modulo 23.
You may be more familiar with using Fermat to evaluate modular powers, but it won't help you with 2^21 here because the exponent is already smaller than the totient.
Instead you could use exponentiation by squaring: compute 5^2, 5^4, 5^8, 5^16 by squaring modulo 23, and then 5^21 = 5·5^4·5^16. That's 6 modular multiplications -- not super quick for pencil and paper, but better than the 20 you would need to raise to the 21th power naively.

You can also just wing it: Multiplying your initial 5 by 5 gives 25 == 2, and multiplying 2 by 12 gives 24 == 1. So the inverse of 5 is 5·12 = 60 == 14 == -9.

[tepid vector]

Yeah I got that from the extended euclidian algorithm approach

Now I need to translate that into the equivalency directly

[tepid vector]

Which I also don't know how to do >.>

[kindred moss]

now that you know 14 is the inverse of 5, you can multiply both sides of your congruence by 14

this gets rid of the coefficient of x, and you can solve for x

and because you're multiplying by an invertible number, your new congruence is equivalent to the old one, so you don't add any extraneous solutions or lose any solutions

[tepid vector]

But wouldn't 60 or -9 also work if they're equivalent?

They're all equivalent I guess

[wooden glen]

-9 or 14 or 60 all work, it's just a matter of making the arithmetic simpler by choosing the smaller one.

[tepid vector]

I guess 14 is the easiest number to deal with then

Also how does one find the other modular multiplicative inverses? I only got -9 from the Euclidian Algorithm approach

[wooden glen]

You can get the others by adding different multiples of 23 to the one you found.

[kindred moss]

when doing anything mod n, you can think of 0 to n-1 as being the "only numbers"; any two integers that are n apart will have the same properties mod n when adding or multiplying, so you don't have to distinguish between e.g. 0 and 23

multiplicative inverses are defined by how they behave when multiplying, so this property is preserved for all numbers 23 away mod 23

[twin tide]

1+1=3

[wooden glen]

Ah, Z/1Z.

[patent acorn]

working mod 23, all of those are just different ways to write the same number, so they all work for the same reason that multiplying by "7*2" would also work

[iron spade]

Hi, I'm really struggling with this problem, looking for just a small hint/push in the right direction

Not sure how to proceed at the moment

ah wait i think i just got it

[wooden glen]

"the length of the path through any one circle is always known" seems to be a pretty fat hint...

[iron spade]

im not good enough at this to understand why thats a big hint i guess

[wooden glen]

The path being described consists of two radii in each circle, so it's really just asking us to sum all of the diameters.

However, the sum of the diameters of the circles that touch the red ones is at least 1.

And the sum of the diameters of the next "layer" of circles is again at least 1.

And (if I interpret the figure right) there keep being new layers of circles whose diameters add up to at least 1 in each layer.

[iron spade]

ah okay that makes sense

thanks

[wooden glen]

(It actually seems to take a bit of finesse to even convince oneself that the description does define a "path" in the sense of the continuous image of a real interval. I think it does -- but it will not be a continuous injective image of an interval).

[iron spade]

what does "continuous injective image of an interval" mean?

i may be in over my head here

[wooden glen]

It is common to define a "path" in the plane to mean a continuous function f: [0,1] -> R².
I'm saying that that definition does seem to be possible for the description in the problem, but f cannot be injective.

[iron spade]

Like the path is continuous but it overlaps itself?

[wooden glen]

More precisely, the circle centers for x-coordinates just below ½ converge to (½,0) and so to the ones with x-coordinate just above ½. So the path being described must have a part where it goes straight up from (½,0) to the center of the largest white circle, and then straight down to (½,0) again.

[iron spade]

Yea that makes sense

like in here as you pack infinitely more circles in

[wooden glen]

Yes.

[ionic latch]

theoretically that occurs at every circle no

[wooden glen]

Right.

[ionic latch]

at first I thought the length would be |N| but that makes it feel like |R|

[iron spade]

that was helpful, thanks. ive found this class to be really challenging lol, i may be under equipped to do a lot of these problems

[wooden glen]

There are only countably many circles.

The x-coordinate of the path function will look something like the Cantor function (but not exactly that), and the y-coordinate will be a fractal mess of triangular spikes.

[sharp shadow]

where is this from?

looks like a fun problem

[iron spade]

my number theory class in hs

those problems were already due, and i didn’t have time to solve that one so i was just curious as to what the approach might be

[loud maple]

I fail to see the "number theory" in the problem.

Maybe that's just me being stupid, but could someone explain what the connection is?

[wooden glen]

I don't think it really looks like number theory either. Perhaps miscategorized due to some language barrier.

[whole delta]

so where would such a question go to

[wooden glen]

#real-complex-analysis might be our best match.

It does feel a bit weird to direct a question from a high-school course to a channel in the advanced category, but on the other hand #real-complex-analysis is a bit dubiously placed -- I had real analysis in my first year of university for example.
(And it's an unusually tricky question for the high school level).

[loud maple]

Right

[iron spade]

that’s just where i got it from lol

there have been a lot of problems like that with tangent circle packing involved in the problem sets and i’m generally not very good at them

[loud maple]

Oh I didn't mean to question why you were posting it here, I was just confused about why a number theory class would discuss such problems.

[iron spade]

ah okay

here are some other questions that go with that diagram, are these more number theory related?

[wooden glen]

That's more of a number theory flavor.

[winter moon]

these are ford circles right ?

[wooden glen]

17 is a very number-theoretic topic; 16 falls into a somewhat neglected area at the intersection between number theory and geometry.

[winter moon]

if so im pretty sure at some point in time you would have covered and hence know the exact radius of each circle and their centres, from there it should be quite easy to calculate

they are connected to something called Farey sequences, so maybe you can dig around there too

[wooden glen]

Interesting. So it does make sense, even though the problem in isolation doesn't look like it has much to do with number theory.

[winter moon]

i cant lie i wouldnt be able to tell that this is a number theory question if i hadnt already knew about them lol

[loud maple]

Ah
Interesting

[iron spade]

no idea, the class is all like exploratory so we never learn the real names of things

[winter moon]

yeah no worries, but heres a wiki page if you care enough
https://en.wikipedia.org/wiki/Ford_circle

i have (poorly) written some stuff on this too, I can dm you a file if you would like

[iron spade]

sure i’ll take a look

[rain wren]

no non-computative solutions for this one?

[rain wren]

they fused geometry and NT ☠️

[heady plinth]

Can you dm it to me too?

[heady plinth]

if you are into it then I think Topology of Numbers by Hatcher may be worth a look https://www.google.com/url?sa=t&source=web&rct=j&opi=89978449&url=https://pi.math.cornell.edu/~hatcher/TN/TNbook.pdf&ved=2ahUKEwi8jcvRtb2UAxVBR2wGHV5EHgwQFnoECBwQAQ&usg=AOvVaw00yB33LDhhiP-0vVhUj2R6

(not pirated, available for free on author's website)

[heady plinth]

what do you mean by non computative?

[rain wren]

non-computative solution

solution that doesnt require computations, or actually bruteforcing all the possibilities

[heady plinth]

I mean

So you want to find all n such that the n-th primorial + 1 is not prime?

[rain wren]

not all, but, just proving its existence

[heady plinth]

hmmm, let me think

i think it might be hard

because showing that an infinity of such primes exist is an open problem

[rain wren]

should say "is there a proof for this that doesnt require any computation"

[heady plinth]

your question is pretty related to that

oh btw

I think one might

use PNT

bounds on primes in general

and show if all such numbers are primes then we run into problems with the bounds

i dont think you can get a "clean" which talks about the "structure" of numbers of such form because that would be close to solving an open problem. dont take my word though im not experienced

hmm, i cant think of anything more than a heuristic argument, nice question though

@rain wren you might want to look into the bounds for primes maybe that will help, you can find them in Hardy and Wright or Number Theory a Masterclass by Granville, I think Granville has a chapter on formulae to represent primes I think he might have discussed it there

[rain wren]

oh, will this actually belong to #advanced-number-theory though

[heady plinth]

I think its fine here

[rain wren]

eh true

[heady plinth]

aren't you that guy

we talked about that theorem that all naturals except 1, 4, 6 are a sum of distinct primes

i remember the pfp, nice to see you working on primes again

[rain wren]

yes

[heady plinth]

cool

small server for one with 300k people

@rain wren lol i was having tea and i came back to say this

i think i got it

we know that all primes are either of form 6k + 1 or 6k - 1

(im probably going to make a fool of myself but anyways)

[rain wren]

wait, is this the 1,4,6 one?

[heady plinth]

no your question about primorials

so

when you reduce mod 6

your primorial + 1 is a product of -1's and 1's

• 1

where am i going wrong though

this would imply it can never be prime

ah i was missing the 2

regardless

let me phrase it well

in one go

@rain wren So lets call the primorial P, now looking at P + 1 after reducing modulo 6 we have 2(S) + 1 where S is a product of -1's and 1's

now S can either be 1 or -1

in the first case P + 1 is congruent to 3 mod 6 and hence composite

in the second case it maybe prime

[rain wren]

wait, 1st case P+1 is 2+1=3, which is prime

same goes P(2)+1=6+1=7

[heady plinth]

no by first case i meant

when S = 1

second case is S = -1

[rain wren]

oh wait, i thought 1st case means 1st primorial

my bad

[heady plinth]

Yeah so the whole problem is reduced to showing that S will be 1 infinitely often

we know that will happen infinitely often

because note that there are infinitely many primes of form 6k + 1 and also infinity of form 6k - 1, now by looking at n-th primorial say its not congruent to 1 mod 6, go to (n+1)th primorial say even it isn't congruent to 1 mod 6, keep going to the next primorial and eventually we should hit a prime of form 6k - 1 making the primorial congruent to 1 mod 6

[iron spade]

thanks

i’ll check it out

[heady plinth]

im so sorry, i meant to say 6k + 1, let me edit

nah lol im right

I think you should convince yourself of the last fact about it being congruent to 1 mod 6 infinitely often

I probably butchered the explanation

but its a really simple fact

[rain wren]

by the fact that primorials themselves are always multiple of 6?

(except 2)

[heady plinth]

No

im sorry i messed up the explanation a little

i mixed up S and P

my bad

I'll go again

So far it is clear that P + 1 will be equally to 2S + 1 obviously, now S is a product of consecutive odd primes

Now to show that P + 1 is composite infinitely often we will show 2S + 1 is congruent to 3 mod 6 infinitely often, which implues P + 1 is congruent to 3 mod 6 infinitely often and consequently P + 1 is of form 6k - 3 and thus a multiple of 3.

[rain wren]

2S ≡3 (mod 6) (wrong)

[heady plinth]

it cant be

[rain wren]

rh wait

[heady plinth]

Thats impossible

[rain wren]

S ≡ 3 (mod 6)

[heady plinth]

No

It can only be 1 or - 1 cant be 3

I think we should get on the same page about what P and S are

[heady plinth]

here

P is the nth primorial and S is the primorial without 2, only odd primes in S

[rain wren]

so it was
P+1=2S+1
therefore
P=2S

known that
P+1≡1 (mod 6)
thus, because P=2S
2S+1≡1 (mod 6)

[heady plinth]

Yeah

but we don't need that

Oh Fuck

I forgot 3

3 isnt of form 6k ± 1

shit

let me see if the proof still works

[rain wren]

perhaps should we use P=6S

[heady plinth]

yeah

[rain wren]

since 6k±1 primes only begin at 5

[heady plinth]

Then we have P + 1 = 6S + 1

yeah it still works

same story again

[rain wren]

wait, i think can assume it's in form of
6S+1= AB
which, gives prime for A=1

[heady plinth]

I don't see that going very far

[rain wren]

so 2 choices
A,B≡1
or
A,B≡-1

which, indicates composite 6S+1 if
A≡-1 and
B≡-1

now we should prove existence of A and B such that A and B ≡-1

[heady plinth]

Welp

sucks my proof doesn't work

the 6 in the 6S makes reducing mod 6 irrelevant

So we cant exploit the structure of S which we know is a product of 1s and -1s that was the key thing

let me read what you wrote closely

Hmm

i don't see any steps beyond what you said

[heady plinth]

but notice that it works if you remove 3 from the primorial

[rain wren]

so if we ask for nonprime P/3+1 we can use that?

[heady plinth]

yes

[rain wren]

for P>=30 actually

cos P/3 will be
2/3, 2, 10, 70, ....

[heady plinth]

yeah

but lets leave that aside i don't see that helping us with the general case

[rain wren]

eh, true

[heady plinth]

Is there another number like 6

[rain wren]

30

[heady plinth]

i mean 6 has a the property that all primes are 6K ± 1

[rain wren]

unfortunately primes in form of 30k+n will be
30k±1, 30k±7, 30k±11, 30k±13

which, is impractical

[heady plinth]

yeah

[rain wren]

basically primorial±coprime

[heady plinth]

there is 8 with 8k ± 1, and 8k + 3, 8k +5

[rain wren]

8k+3 and 8k+5 can be unified as 8k±3

[heady plinth]

yeahh

then we have ti worry about

what will S be?

smallest such prime is 8×0 + 3 = 3

So we have 2S + 1 = P + 1

this time fr!

[rain wren]

wait, P without 3 or normal P?

[heady plinth]

Normal

we are done with P/3

[heady plinth]

then we have S congruent to ± 3^k

[rain wren]

mod 6 or 8?

[heady plinth]

8

[rain wren]

wait
(all mod 8)
S(1)=3, 3≡3
S(2)=15, 15≡-1
S(3)=105, 105≡1
S(4)=1155, 1155≡3

i think it tends to be ±1 though? wronh

[heady plinth]

let me think

what are we trying to

do

[rain wren]

composite P+1

[heady plinth]

last time what i wanted was to show that 2S + 1 is of a particular form infinitely often and that form is always composite

[rain wren]

wait, i think instead of proving their existence without computation, maybe i should just ask to find smallest composite P+1 in the given range of numbers

[heady plinth]

elaborate

[rain wren]

the question? hmmm

maybe like this

smallest composite primorial(n)+1 that is over 1 million.

nvm it seems bruteforceable

[heady plinth]

i think heuristic arguments would help with that

but the best you will get is

[rain wren]

smallest composite primorial(n)+1 that is 100 digits long

[heady plinth]

"it is extremely likely that P + 1 is composite as P grows to infinity"

thats not a good answer

i just asked Claude to pursue the Prime number theorem lane and it brought in some weird Borel Cantelli lemma and something i have no idea of

its proof seems bullshit

so i think reduction modulo different numbers is our best bet

if we try reducing to 4

we do have S being -1 or 1 but we then run into the problem that

2S + 1 will be -1 or 3 mod 4 which we can't guarantee will be composite

But i think it is clear form that why P + 1 will be composite infinitely often because for it to be always prime it should hit at ONLY THE PRIMES of form 4k ± 1 and AVOID ALL COMPOSITES OF THAT FORM

Thats really really unlikely

maybe if we can show that primes of form 4k ± 1 are rarely P + 1 we are done

but that sounds hard too

anyways I'll ask a friend, I'll text you later @rain wren

[whole delta]

!noai

[rotund gust]

Please do not trust ChatGPT or similar AI tools for mathematical tasks, as they often generate output which "sounds correct" but has numerous factual or logical errors. Use of these AI tools to answer other people's help questions is strictly against server rules (see #rules).

[heady plinth]

Didnt know, sorry, it was just so it could give references, i wasnt expecting it to give me a proof, i expected that it would spit out garbage, which it did.

Anyways wont repeat that

[heady plinth]

I cant believe I wrote a thing as stupid as that.

[heady plinth]

@rain wren "As of 2025, it is not known whether there are infinitely many primorial primes, and it is also not known whether infinitely many numbers of the form p_n# ± 1 are composite."
https://en.wikipedia.org/wiki/Primorial_prime

It's a goddamn open problem

[rain wren]

well, nothing we can do about it for now i guess

or perhaps it's a literal unsolvable (like ellipse perimeter)

[heady plinth]

Yeah, though your question was a little different, i.e. can we show it will be composite atleast once without computation

[rain wren]

true

[heady plinth]

I don't see if that can be done easily, if that can then I think it would give a clue about how to solve the original one

[heady plinth]

Can I add you?

Speaking of ellipse perimeters

There is an interesting connection to something called the arithmetic geometric mean, worth checking out

Unless you know already

Its absolutely beautiful, my favourite math ever

[magic rain]

🎉

[mint stone]

||It is fairly straightforward to see that 2n must factor into two numbers of opposite parity. Hence, the number of representations of n as a sum of two or more consecutive positive integers equals the number of odd divisors of n, excluding 1. Therefore, the apathetic numbers are precisely the powers of 2, while every prime number is truly striking (and thus there is no largest truly striking number).
If d is an odd divisor of n then the last term of the representation is n/d+(d-1)/2.
The representation has 2n/d terms when d>sqrt(2n), and d terms when d<sqrt(2n).
Hence, for n=1001 we have 7 nontrivial divisors d=7,11,13,77,91,143,1001 which give representations: 140..146, 86..96, 71..83, 26..51, 35..56, 65..78, 500..501.
For the last task we need the smallest number with exactly 1001 odd divisors.
By the divisor function, this number should be 3^12 * 5^10 * 7^6 =610581076259765625 since larger exponents should go with smaller primes.||

[marsh raven]

any numbertheorists wanna help me with my proof over at #help-7｜zen1thxyz

[last whale]

How to do ts guys?

[carmine tide]

Reposted and resolved: #help-7｜zen1thxyz message

[marsh raven]

once again cheers

@carmine tide now to prove fermats little, would it suffice to use same proof, but replace the set with {1,2,...(p-1)}

[iron spade]

pretty cool problem from my homework i thought i'd share here

[carmine tide]

my beloved ||6/pi^2||

[iron spade]

it shows up everywhere lol

pretty easy to see why it comes up here but i thought the presentation was relatively unique

[tall arch]

||Consider the fraction x/y for integers x,y. The probability that x,y do not share a common factor of p for some prime p is 1-(1/p)^2. Taking this product over all primes p, as the number of fractions goes to infinity, the probabilit ythat a fraction is in lowest terms is the product of 1-(1/p)^2 over all primes.

P = prod_{n=1}^{\infty} (1-1/p^2)
1/P = prod_{n=1}^{\infty} 1/(1-(1/p)^2) = prod_{n=1}^{\infty} (1+(1/p)^2+(1/p)^4+...)
Thus, by fundmanetal theorem of arithmetic, 1/P = 1/1^2 + 1/2^2 + 1/3^2 + ... = pi^2/6
Thus, P = 6/pi^2||

[iron spade]

Correct

[tall arch]

cool problem

[iron spade]

yea i thought it was pretty neat

[tall arch]

do u have any other cool problems?

[iron spade]

this one is kind of cool

[tall arch]

i think generally its because 2 mod 3 factors create 1 mod 3 factors

gotta find a way to prove it tho

[iron spade]

yea i had the same idea

i kinda went though a few examples

[tall arch]

mm alr

so consdier like any number n

it has a 1 mod 3 factors that are prime*

and b 2 mod 3 factors that are prime*

0 mod 3 factors don't rlly matter

and u want to find how many factors of n are 1 mod 3 or 2 mod 3

so the product of any collection (possibly empty) of 1 mod 3 factors is 1 mod 3

and if u consider 2 mod 3 factors

an even number of them make 1 mod 3 factors

so 2 mod 3 prime factors contribute at least as many 1 mod 3 factors as 2 mod 3 factors

cuz (b choose 0) + (b choose 2) + ... + (b choose b-1) for b odd is 2^(b-1) ≥ 1/2*2^b
and (b choose 0) + (b choose 2) + ... + (b choose b) for b even is 2^(b-1) ≥ 1/2*2^b

that should be it i think

this applies for any residues x,y (mod n) where x = 1 (mod n) and y^k = 1 (mod n) for some k ≠ 0

[iron spade]

isnt this kind of treating it like it independently decides if each divisor is 1 or 2 mod 3 but the residue would depend on the product across all the primes at once

unless im misunderstanding

cuz of the exponents

[tall arch]

wait can u explain

[tall arch]

you can independlty decice if each divisor is 1 or 2 mod 3 becuase of the multiplciative structure of divisors for a number n i thiknk

[iron spade]

yea but i think assigning each divisor as like a 1 or 2 mod 3 wont work because the exponent of each prime factor changes it differently

like 2^a * 5^b for example

2^0 *5^0 = 1 mod 3 and increasing either of the exponents but not the other makes it 2, and then increasing both makes it 1 again

like basically if u just look at the 2^a factor its not enough to know if it will make it 1 or 2 mod 3 because sometimes the 5^b causes them both to flip

[tall arch]

you assign only the prime factors as 1 or 2 mod 3

and you detremine the residue of the rest of the factors mod 3 using the reamineder mod 3 of hte prime factors

[iron spade]

but doesnt it depend on the exponents of the prime factors

[tall arch]

you count multiplicity of prime factors

so if ur number is 2^4 * 5^3

the prime factors aare 2,2,2,2,5,5,5

[iron spade]

i might be wrong then idk, i need some time to think that over

u are probably right

[ionic latch]

Just wanted to make sure I understood the problem, the factors of 10 are 5,2,1, does that count as two 2 mod 3 factors and one 1 mod 3 factor?

[iron spade]

no, 10 also counts

[ionic latch]

ah

[iron spade]

so it would be two 2 mod 3 and two 1 mod 3

[slate juniper]

So we know that when $d \equiv 2, 3 \pmod{4}$ the ring of integers of $\bQ(\sqrt{d})$ is $\bZ[\sqrt{d}]$ and when $d \equiv 1 \pmod{4},$ it's $\bZ[\frac{1 + \sqrt{d}}{2}]$

[sterile pumice]

Neamesis

[slate juniper]

But

But instead of writing it as $a + b \left( \frac{1 + \sqrt{d}}{2} \right)$ where $a, b$ vary over integers it seems you can also write it as $a + b \sqrt{d}$ where $a, b$ vary over halves of odd integers?

[sterile pumice]

Neamesis

[slate juniper]

I don't see how they're equivalent

[carmine tide]

Expanding an expression from the first form gives
$$x+y \left(\frac{1+\sqrt d}{2} \right)=\left(x+\frac{y}{2} \right)+\frac{y}{2} \sqrt d$$
for integers $x$ and $y$. \

Setting this equal to $a+b\sqrt{d}$ yields $a=x+\frac{y}{2}$ and $b=\frac{y}{2}$. When $y$ is an odd integer, $b$ becomes a half-integer. Since $x$ is a whole integer, $a$ is also a half-integer. This means that $a$, $b$ are always either both integers or both halves of odd integers;

[sterile pumice]

Civil Service Pigeon

[abstract ferry]

Neam learning algebraic number theory

peak

[slate juniper]

Thanks a lot

[slate juniper]

Just a bit

[carmine tide]

[unique cypress]

Something to think about is what is the 2 representing here

[rain wren]

discovered that for a "custom fibonacci"\
$F_{a,b}(n) = f(n+2)a + f(n+1)b$\
with:\
$f(n)$ is the $n$th fibonacci number with 0th term of 0 and 1st term of 1.\
$a,b$ being the 0th and 1st term of this\
"so called" custom fibonacci

like, should be obvious, but my gullible mind wished for other fancy stuffs that dont involve the original fibonacci numbers somehow.

[sterile pumice]

tsuitachi (tuitati)

[errant lake]

hello

[slate juniper]

hm never thought about that

[unique cypress]

It's a fun problem

Compare it with the ring without the 2

[tepid vector]

I have a question regarding this form of modular arithmetic. Given an $a \in \mathbb{Z}_n$, find an element $b \in \mathbb{Z}_n$ such that $a + b \equiv b + a \equiv 0 (\mod n) $

[sterile pumice]

Heavy_Hussar

[tepid vector]

I don't know how to find the other element b in this equivalency problem

The integer b has to be added to a in such a way that it always produces no remainder in relation to n, but I don't know how to do that with addition

I guess a + b must have n as a factor for this to be true

I don't know how to go about proving that though or what b would be in that case

[heady plinth]

How about b = n - a?

Since a \in \mathbb{Z}_n then a < n and then b = n - a \in \mathbb{Z}_n

[tepid vector]

Yeah that one is pretty easy to be honest

It just felt like that was too easy when I was looking at it

[heady plinth]

Happens sometimes, had that happen thrice with me today.

[rain wren]

Are sequences to be discussed here?

[wooden glen]

If you're interested in things like whether the sequences converge, one of #precalculus, #calculus or #real-complex-analysis will be better.

[cunning forge]

Depends

[magic rain]

I think this one is tricky

[iron spade]

i found one pair that works 😅

as for all of them i’m lost

cool problem though i will try a bit more than guess and check bs

[iron spade]

|| a =16 b=2 should work ||

[tall arch]

a and b both have to share the same set of prime factors

[tall arch]

i think ||(3,27) ||works as well

[mossy sun]

owo

[steel steppe]

[sacred junco]

yeasss

too late dex

[celest plinth]

hi

[sacred junco]

[celest plinth]

am i late

[sacred junco]

what is that sum

[celest plinth]

depends on ur index set @sacred junco

[sacred junco]

another channel to mute

[mossy sun]

:'(

[sacred junco]

i won't if griff is here explaining number theory

[mossy sun]

always!

[sacred junco]

[silk breach]

num-theory

[outer brook]

yay new channel

[sacred junco]

[zenith ferry]

is number theory related to math?

[sacred junco]

is maths related to science

[paper notch]

no

[sacred junco]

@sacred junco are numbers related to number theory?

[steel steppe]

😵 this channel became a shitpost channel as soon as it opened

[sacred junco]

Yup

[craggy osprey]

Indeed

If i have a repeating decimal (like 0.333...), i can express it as fraction as $$\frac{\text{the sequence to repeat}}{\text{99999... the number of 9 is the number of digits in that sequence}}$$
$$$$
Prove that this is true for all repeating decimals.

[mossy sun]

is that tru? :0

prove that, for each k>0, there is a highest natural n so that the prime factors of n(n+1) are all at most k

[craggy osprey]

Channel alridy taken griff...

But i think it’s true

Wdym by n(n+1)? Is n a prime factor?!

[mossy sun]

OH there we og

I thought you meant like

.333... = 3/1

[craggy osprey]

No

[mossy sun]

lol okay that makes it way easier

[craggy osprey]

My bad

[craggy osprey]

I hate how mathbot makes its fractions. Anyways

[mossy sun]

let A be that repeating sentence, and n be the length

=tex \frac{A}{10^n-1} = \sum_{k=1}^\infty A*10^{-nk} = 0.[A][A]\ldots

[craggy osprey]

I have soooo much difficulty vizualizing sums...

But it’s a way to prove it,

NEW QUESTION

Prove that there are no such possible sequence 0.9999999..., or disprove it

[mossy sun]

:(

[craggy osprey]

I know right?

[mossy sun]

here's one for you @craggy osprey

=tex \lim_{n \to \infty} \frac{1}{n} \sum_{k=1}^n \left{\frac{n}{k}\right}

[mossy sun]

{x} is the fractional part of x.

[craggy osprey]

I don’t do sums.

[mossy sun]

:(

[craggy osprey]

It’s gay.

[steel steppe]

[mossy sun]

sums are where it's at

okay

here's one that doesn't use one

[craggy osprey]

“~”? “Squarefree”? Reeeeeeee

[mossy sun]

~ means the ratio goes to 1

squarefree means not divisible by a square > 1

[craggy osprey]

If somfin is <= n, and if it increases over time, obviously it ~n, am i right?

[mossy sun]

counterexample: sqrt n

[craggy osprey]

Fu

sqrt n doesn’t increase over time???

[mossy sun]

it does?

[craggy osprey]

=_=

[mossy sun]

=pup Plot[Sqrt[n],{n,1,10}]

[stoic basin]

Query made by @mossy sun
Data sourced from Wolfram|Alpha: http://www.wolframalpha.com/input/?i=Plot[Sqrt[n]%2C{n%2C1%2C10}]
Do more with Wolfram|Alpha Pro: http://www.wolframalpha.com/pro/

[craggy osprey]

let n be constant

Man idfk... i love geometry... but... I don’t know about “~”

[mossy sun]

so for example

n^2+3n ~ n^2

pi(n) ~ n/log(n)

[craggy osprey]

Mmh

[mossy sun]

stuff like that

[craggy osprey]

Ok... and...? Is balance a thing in this? Like:

3~n
27~n^3

Man idk

Id have to do research

But can you answer my question???

QUESTION

NEW QUESTION

Prove that there are no such possible sequence 0.9999999..., or disprove it

[mossy sun]

if f(n) ~ g(n) and F(n) ~ G(n), then f(n)F(n) ~ g(n)G(n)

and 1/f(n) ~ 1/g(n)

what do you mean "possible sequence"

[craggy osprey]

Like

The sequence:

“9”repeating infinitely in the decimals

[mossy sun]

what do you mean "possible"

[craggy osprey]

Like

Is there a number 0.999999...

[mossy sun]

yes

it's 1

any sequence of decimal digits is a number between 0 and 1

it may not be the unique way to write it tho.

[craggy osprey]

But does it exists, or is it just 1?

[mossy sun]

0.999... exists

and it is also equal to one

[craggy osprey]

Oh, ok

[mossy sun]

here's a nice problem

find the infimum of the set of positive real values \theta such that

=tex \sum_{q \leq \sqrt{n}} \left(\left { \frac{n}{q} \right } - \frac{1}{2}\right) = O(n^\theta)

[mossy sun]

where {x} is fractional part

theta=1/2 is obvious

so that gives you a start 👀

[craggy osprey]

Sums are censored

[mossy sun]

what do you Fuckening have against sums

[craggy osprey]

I can’t visualize them geometrically

[mossy sun]

tfw trying to apply geometry to number theory

[craggy osprey]

=_=

Good question

Anyways, i just am awful at it

I never know of to put these into fractions

[mossy sun]

into fractions?

[craggy osprey]

Like what you did there:

[mossy sun]

oh that was just the geometric series

[craggy osprey]

Oh ok

[vast vessel]

Oi, new channel lol

@mossy sun googology/large ordinals channel (that'll probably become #chill-2) when?

[safe sage]

wait this wasn't here before

[vast vessel]

Lol

[sacred junco]

inb4 how do i solve $$3x^2 + 3 = y$$?

[sturdy dirge]

$$\forall x \in \mathbb{Z}, y = 3(x^2+1)$$

[sacred junco]

what if we let x be in the complex numbers

[sturdy dirge]

$$\forall x \in \mathbb{C}, y = 3(x^2+1)$$

[sturdy dirge]

Find $$y \in \mathbb{Z}$$ ?

[sacred junco]

$$\mathbb{Z} \subset \mathbb{R}$$

?

[sacred junco]

yes

[stoic basin]

Rendering failed. Check your code. You can edit your existing message if needed.

[sacred junco]

Oh wait

Lol

Nvm

You need to use \frac{}{}

Yea i misunderstood something

Nvm

I thought Z as C idk why

...

[tacit solar]

Oh hey, we have a number theory channel now! How cool!

[glad nacelle]

Ooh number theory

Ofc it's gonna be algebraic number theory

[mossy sun]

@glad nacelle lol it's all kinds

i have a deep hunger for analytic number theorists here

[glad nacelle]

Lol the funny thing is I've never seen your type of analytic number theory before

Very direct with the asymptotic analysis

[mossy sun]

really? huh

[sacred junco]

Really ??

[glad nacelle]

I had only known about zeta function/complex analysis stuff

[mossy sun]

ohh right

[glad nacelle]

Like I know some asymptotics are there

[mossy sun]

like using poles and shit to directly prove asymptotic

[glad nacelle]

Just by virtue of what you're trying to study

[sacred junco]

You should check Tennenbaums book

[glad nacelle]

But I've never actually seen what it entails

[mossy sun]

yeah it's cool shit. if you haven't read apostols book i recommend it

[glad nacelle]

Intro to Analytic and Probabilistic number theory @sacred junco?

[sacred junco]

But you have to have some algebrzic number theory knowledge

Yes

[mossy sun]

true^

[glad nacelle]

And @mossy sun I know of two books of the sort

[sacred junco]

At some point number fields / algebrzic integers just basics

[glad nacelle]

One is like, modular forms and Dirichlet series

[mossy sun]

right yea he has intro and modular forms

[glad nacelle]

The other is the intro

[mossy sun]

intro is great, I've read some of modular forms

need to go more in depth with it when I'm freer

[glad nacelle]

Eventually I would like to pick some up. Complex next quarter is gonna do a bit I think

I have notes from the last time this prof taught the class

Anyway they had some I think. One second

These aren't particularly good notes, they were basically study notes for her final exam

So they only did the second half of the class (first half was just standard material on complex analysis)

Apparently this professor's approach to things is quite specific to her. I'll probably supplement using Freitag

[mossy sun]

hadamard factorization!

[silk breach]

Hadamard factorization is awesome stuff.

[mossy sun]

I need to learn more about it honestly. I only have barebones knowledge of complex analysis.

just enough to do contour integrals for number theory stuff

[glad nacelle]

So funny thing is, I did have a complex analysis class but it was done in a kind of strange way

[mossy sun]

yeah? how so :O

[glad nacelle]

Like, okay part of it was that it went a bit more slowly than I wanted since we spent time reviewing a few things from real analysis that people should've known cold

Like it took him a week to prove that holomorphic functions are analytic because he reviewed convergence, so that was annoying

But also we just kinda did things more topologically

For example, we phrased the argument principle in terms of winding number

[mossy sun]

ohh right! that's neat

[glad nacelle]

Like I came in the third week of the class

First week I think he reviewed complex numbers and norms, did derivatives and the basic stuff like chain rule, then Cauchy-Riemann. Second was stuff like Cauchy's integral theorem, and then he started talking about branches of the log

[mossy sun]

💙 branch cuts!

[glad nacelle]

I got there and he was still doing the log, then he talked about winding number, FTA, and Cauchy integral formula

[mossy sun]

I love proofs of FTA

[glad nacelle]

Which he stated in terms of winding number.

But yeah then he did holomorphic implies analytic, Liouville, max modulus, argument principle, singularities and meromorphic functions

[mossy sun]

good shit!

[glad nacelle]

After that we did residue theorem, restated a bunch of stuff from earlier in terms of that, tiny tiny bit about differential forms, Laurent series, and infinite series

But that last part was like, 2 weeks only

[mossy sun]

huh, damn

they never spend long enough on series in courses i've taken

[glad nacelle]

And we didn't have many problems on computing things

Like, we had one problem which was like, find the radius of convergence of 13 power series, another which was like, find the residues of a bunch of functions

[mossy sun]

right, I love residue stuff

[silk breach]

Residue theorem is amazing when it comes to contour integration.

[glad nacelle]

But we rarely had to compute integrals at all

Actually I think we maybe had one or two integrals over the whole course, and at least one of them was like

[mossy sun]

only two???

[silk breach]

Really?

[glad nacelle]

A rational function where one residue was easy to compute, and then you note that the sum of residues including infinity was zero

Yeah it was very much not computationally intensive

I can pull up some of the psets, but you'll see that it's all theoretical problems

[mossy sun]

yea lemme see!

[silk breach]

^

[glad nacelle]

But yeah I think it may have to do with the fact that the guy teaching wasn't an analyst

He does algebraic geometry

[mossy sun]

ohhh yeah.

[glad nacelle]

Okay so these were his notes from last year, though he changed them up

This was like, one of the few computational things we had

[silk breach]

Neat.

[glad nacelle]

The problem from the book which had all parts except m was computing some radii of convergence

This was a pset which was more winding number-ish

Our psets had a mix of such problems but I felt more were like the latter

[mossy sun]

I like 0.4 in hw6

it's cute

[glad nacelle]

Oh yeah it's slick

[mossy sun]

dami did you see the contest problems??

[glad nacelle]

I did look at them briefly but never had the chance to work them out

There was one I recognized from my analysis final

It was the Baire category theorem problem

[mossy sun]

ahh right

i've been thinking about one that's similar to number 4

=tex f(x) = \int_0^\infty g(t)\cos(tx)dt

[glad nacelle]

Ugh an integral gotta run away now goodbye

[mossy sun]

where g(t) is a nice function and f(x) converges for x>0 and has a limit as x tends to 0

trying to prove convergence of f(0) 🤔

under whatever growth conditions on g(t)

[glad nacelle]

Hmm, what method did you use to do 4 btw?

[mossy sun]

it's in the solutions pdf but I can copy it in here

are you familiar with tauber's theorem?

[glad nacelle]

Nope, not by that name at least

I may recognize the statement though

[mossy sun]

if a sequence a_n is abel summable and has |n a_n| -> 0, then a_n is summable

more specifically

=tex \lim_{x \to 1^-} \sum_{n \geq 0} a_n x^n \in \mathbb{R}

[mossy sun]

=tex |n a_n| \to 0

[mossy sun]

then a_0+a_1+... exists.

[glad nacelle]

Oh lord this is nothing close to how I did it

[mossy sun]

you have a solution? :O

[glad nacelle]

This was on my homework, of course I did it

My solution was like, 2 lines

[mossy sun]

..wha?

homework for what class?

[glad nacelle]

Or wait hold on I think we're thinking of different problems

You talked about 0.4 in hw6

[mossy sun]

OH

[glad nacelle]

And were like yeah it's cute

[mossy sun]

I thought you meant contest problem 4

[glad nacelle]

OH kek

I thought you were saying that my homework problem 4 was similar to a contest problem

And was like uh

[mossy sun]

lol no.

too simple

ooooh good

that form should help

[glad nacelle]

Consider making it a contest problem actually

[mossy sun]

oh shit

well then we shouldn't discuss it here lol

[glad nacelle]

True, delete what you mentioned

We can discuss it in PM and if it's appropriate then yeah

[mossy sun]

yeah cool

[glad nacelle]

It was probably one of my favorite problems from algebra

[vast vessel]

.>

lol

[noble jay]

Omg my dream came true

A number theory channel

[wild zinc]

conjecture:

2 is prime

no

sqrt(2)^2?

yeah I guess

conjecture 2:

sqrt(2) is prime

[sacred junco]

In what ring ?

t!image math

[unique vault]

📷 | Can I get your opinion on my idea?Thanks, any help is much appreciated.
https://imgur.com/a/dJr7v

[lilac cove]

@unique vault what is this for????? What is your idea????????

[mossy sun]

tfw bot

[lilac cove]

Oh wow I missed that.

[ember crystal]

What about it

[sturdy dirge]

$$x^2(x^2+8) = (y + x)^2$$

[noble jay]

I solved it don't worry

[sturdy dirge]

Four solutions only in $$\mathbb{Z}^2$$ ?

[noble jay]

The question was given that gcd(x,y)=d. Prove that x=d and (y/d +1)^2 = d^2 +8

Then solve in N

[sturdy dirge]

x = 4, y = 6

[noble jay]

Did you just guess a solution?

Cuz thats not a solution

[sturdy dirge]

No, a example gcd(x, y) = 2.

[noble jay]

Oh. Yeah but you just gotta work with d as a parameter to help you solve the equation

[sturdy dirge]

$$x \neq 2$$

[ember crystal]

@noble jay what was ur old discord name?

[noble jay]

Dusty

[ember crystal]

R u sure u didn't have one before that

[noble jay]

Heres a good one

n is in N* btw

I still haven't done it so please don't tell me the solution

[mossy sun]

what's the wedge mean here

is that meant to be GCD

[noble jay]

Yes

[mossy sun]

alright

[noble jay]

Don't you use that notation?

[mossy sun]

nope

either (a, b) or GCD(a, b)

usually second

[noble jay]

Really? (a,b) means like a solution to an equation

Like a diophantine solution

[mossy sun]

yeah I don't use that one too often

[noble jay]

Theres a question i skipped on that one btw because otherwise its too eas

Easy*

[mossy sun]

right okay

so S_n = (n(n+1)/2)^2

so we can just find the GCD of n(n+1)/2 and (n+1)(n+2)/2 and square it

do it by cases with n=2k or n=2k+1

even first

k(2k+1) and (k+1)(2k+1)

GCD is obviously 2k+1=n+1

now if n=2k+1

(2k+1)(k+1) and 2(k+1)^2

GCD is either k+1 or 2(k+1)

you can do that one by cases again

[noble jay]

Yes

You got ot

It

Lemme find you a tough one

[mossy sun]

yea :D

[noble jay]

So p is prime
Prove that if p=1 mod 4
Then {(p-1)/2} ! is a solution to the equation
x^2 + 1 =0 mod p

[mossy sun]

alright, one sec

[blissful venture]

this is gauss' theorem right?

[mossy sun]

here we go

[blissful venture]

maybe, sorry, it's been ages

[mossy sun]

1*2*...*((p-1)/2) is congruent to (p-1)*(p-2)*...*((p-1)/2+1) mod p

which is easy to show, each factor on the right is negative one of the ones on the left, and there are an even number of factors

so (p-1)! = (((p-1)/2)!)^2 mod p

wilson's theorem says that's negative 1, which is what we wanted.

[noble jay]

Omg

[blissful venture]

Nice, and elegant

[noble jay]

Do you have a phd

[mossy sun]

nah.

I'm a college freshman

[noble jay]

I skipped 4 questions and gave you the application. The first 4 are wilsons theorem proof

[mossy sun]

right

[noble jay]

Are you really a college freshamn

Freshman*

[mossy sun]

mhm

[blissful venture]

essential skills for olympiad

[wild zinc]

wilson's theorem proof isn't too bad

[noble jay]

Im in highschool and i dont think i can figure that out that fast

[blissful venture]

Practice makes Perfect! 🍻 :

[noble jay]

A year of 23/24 hours of practice a day probably

[blissful venture]

I spent an hour a day for 2 years, was averagish for my state

I ❤ Number Theory

[noble jay]

I will spend the next 8 hours doing all 106 problems. Good night

[celest plinth]

cya!

[blissful venture]

Niven and Zuckerman's Introduction to the Theory of Numbers is a nice book, starts from the basics and works up pretty fast

[mossy sun]

niven is cool yea.

[blissful venture]

That and Arthur Engel are the only books I keep from my Olympiad prep days

That reminds me, I lent Arthur Engel to Someone 🤔

[mossy sun]

yo hey alright guys strap in

[celest plinth]

👁

[mossy sun]

we're gonna prove that if π(x) log(x)/x tends to any constant C, that constant is one.

[blissful venture]

:seatbelt:

[mossy sun]

I have two proofs but I'll show the one that uses zeta

[silk breach]

Yes!

[mossy sun]

right, so we only use zeta for a real variable x greater than one

[glad nacelle]

Oh I wasn't thinking of that when I said it was too computational, I thought it was more the method of continuation. But anyway I'm interested in hearing this as well so let's go

[mossy sun]

we also define

=tex \mathbb{P}(x) = \sum_{p} \frac{1}{p^x}

[mossy sun]

p being all primes.

[silk breach]

Prime zeta?

[mossy sun]

yep

right, so we start with Euler's product form of zeta

=tex \zeta(x) = \prod_p \frac{1}{1-p^{-x}}

[mossy sun]

take logarithms.

=tex \log \zeta(x) = \sum_p -\log(1-p^{-x})

[blissful venture]

Oh nice

[mossy sun]

use the series for log (which is justified for x>1)

=tex \log \zeta(x) = \sum_{p, m \geq 1} p^{-mx}/m

[mossy sun]

m are just all naturals.

so now we have

=tex \log \zeta(x) = \mathbb{P}(x) + \sum_{p, m \geq 2} p^{-mx}/m \leq \mathbb{P}(x) + \sum_{p, m \geq 2} p^{-mx}

[mossy sun]

we can bound that last dude by the sum for p being all naturals >= 2, m being all naturals >= 2, which telescopes to 1

so:

=tex 0 \leq \log \zeta(x) - \mathbb{P}(x) \leq 1

[noble jay]

x in R+ right?

[mossy sun]

x>1.

right, so now we're gonna digress for a second

to calculate a limit

=tex \lim_{n \to \infty} \frac{1}{\log(n)} \int_e^\infty \frac{dt}{t^{1+1/n}\log(t)}

[mossy sun]

use the substitution u=n/log(t) to get

=tex \lim_{n \to \infty} \frac{1}{\log(n)} \int_0^n \frac{du}{u e^{1/u}}

[mossy sun]

the integral between zero and one converges and can thus be thrown out

=tex \lim_{n \to \infty} \frac{1}{\log(n)} \int_1^n \frac{du}{u e^{1/u}}

[mossy sun]

using e^(1/u) >= 1, there's an easy upper bound of 1 on that limit

then, if we fix a real n>r>1, we can split the integral into two parts, one constant depending on r, the other getting lower-bounded by log(n)e^(-1/r)

since e^(-1/r) tends to one as r tends to infinity, the limit is one.

right, so we are now returning to zeta

we can use that continuation I mentioned to prove

=tex \log \zeta(1+1/n) = \log(n) + O(1)

[mossy sun]

now we use Abel's summation theorem on P(1+1/n):

=tex \mathbb{P}(1+1/n) = (1+1/n) \int_2^\infty \frac{\pi(t)}{t^{2+1/n}}dt

[mossy sun]

now, since P(1+1/n) = log zeta(1+1/n) + O(1) = log(n) + O(1),

=tex \int_2^\infty \frac{\pi(t)}{t^{2+1/n}}dt = \log(n) + O(1)

[mossy sun]

if \pi(t) is asymptotic to C t / log(t), then we can plug that in (with error terms we're gonna ignore) to get

=tex \int_2^\infty \frac{C}{t^{1+1/n}\log(t)}dt \sim \log(n)

[mossy sun]

this is the integral we mentioned before (plus a small error)

the integral on the left is asymptotic to C log(n) as we said

so:

=tex C \log(n) \sim \log(n)

[mossy sun]

it's then clear that C=1.

[silk breach]

Cool

[mossy sun]

there's of course a less analytic way to do things

[glad nacelle]

"Less analytic" :+1:

Jk this was cool

[mossy sun]

lol 💙

here's a sketch of the other way

=tex \Lambda * 1 = \log

[mossy sun]

therefore

=tex \sum_{n \leq x} \Lambda(n) \lfloor x/n \rfloor = x \log(x) + O(x)

then use θ(x) = O(x) which is elementary

[mossy sun]

=tex \sum_{n \leq x} \Lambda(n)/n = \log(x) + O(1)

[mossy sun]

you use abel's on this thing and do a few transformations to get

=tex \int_1^n \frac{\theta(x)-x}{x^2}dx = O(1)

[mossy sun]

the convergence of this integral is equivalent to PNT

but it's obvious if theta(x) tends to something not equal to one it'd diverge to +-infinity

that's all uou

[sacred junco]

I didn't entirely follow. But you always see some of the coolest stuff just lurking around here.

[blissful venture]

I need to look at Abel's Sum

[mossy sun]

it's the best

[blissful venture]

Ok, I think I finally follow the whole thing 😮

🍻

[somber rampart]

this is why I don't analysis

thanks for reminding me griff

[mossy sun]

:( @somber rampart it's not even that bad

[somber rampart]

joke, I just legitimately don't understand what just happened :P

[sacred junco]

@main plume

[vast vessel]

:o I should follow this channel more lol

[celest plinth]

hmm
6*(abcdef)+21 = defabc
then def=6(abc)+k, where k=3,4,5
100≤abc≤165
also
def=6(abc)+k
6(def)+21 = abc+1000k
6(def)=36(abc)+6k
21=994k-35(abc)
3=142k-5(abc)
3+5(abc)=142k
2k ≡ 3 (mod 5), and 3≤k≤5 → k=4
→ 3+5(abc)=142(4)=568
→ 5(abc) = 565
→ abc = 113
→def = 6(113)+4 = 682

thus
n = 113682

[silk breach]

@mossy sun how would I show that the other part of the integral (from your first proof of PNT) is bounded by log(n)e^(-1/r)?

[mossy sun]

okay so here's how we do it

=tex \int_1^r \frac{du}{u e^{1/u}} = C(r)

[silk breach]

Right.

[mossy sun]

=tex \frac{1}{\log(n)} \int_1^n \frac{du}{u e^{1/u}} = \frac{C(r)}{\log(n)} + \frac{1}{\log(n)} \int_r^n \frac{du}{u e^{1/u}}\
\geq \frac{C(r)}{\log(n)} + \frac{1}{\log(n)e^{1/r}} \int_r^n \frac{du}{u}\
= \frac{C(r)-\log(r)/e^{1/r}}{\log(n)} + \frac{1}{e^{1/r}}\

[mossy sun]

now let n -> infinity

=tex \liminf \frac{1}{\log(n)} \int_1^n \frac{du}{u e^{1/u}} \geq e^{-1/r}

[silk breach]

you can pull out the exponential factor in the denominator?

[mossy sun]

it's increasing.

or decreasing

whichever one we need lol

[silk breach]

Ah, I think I see why now. I think...

[mossy sun]

the substitution for the original integral is pretty clever imo

[silk breach]

By the way, that proof for PNT made much more sense than the first one I was introduced to, which was the one with Chebyshev functions.

[mossy sun]

@silk breach it's not a proof of PNT.

it's weaker than PNT

PNT says it converges to one

my thing says if it converges, it's to one

there's a subtle difference but it means all the difference in difficulty

[silk breach]

Ah, I see.

[mossy sun]

I do know a proof of PNT I can explain tho

it's generally deemed the slickest one

[silk breach]

Okay.... I'm interested.

[mossy sun]

alright, let's do this

[somber rampart]

you used PNT to do it though

so your proof is circular...

[mossy sun]

I used the convergence to a constant C, @somber rampart

PNT means C=1

I assumed the main bit of PNT and proved the rest

but

[somber rampart]

?

[mossy sun]

I didn't assume the convergence

just boundedness

and that's the second proof I gave

[somber rampart]

Ah ok

nvm

[mossy sun]

=tex \zeta(s) = \sum_{n \geq 1} \frac{1}{n^s}

[vast vessel]

woot woot more zeta

[mossy sun]

using the euler product, it has no zeros for Re(s)>1

we wanna do the same thing for a different function

[vast vessel]

(also seems like griff should bump this channel to advanced mafs?)

[mossy sun]

I wanna have a number theory channel here

[vast vessel]

k

[mossy sun]

=tex \sum_{n \geq 1} \frac{\Lambda(n)}{n^s} = -\frac{\zeta'(s)}{\zeta(s)}

[mossy sun]

where \Lambda(p^k) = p if k>0, \Lambda(n)=0 otherwise

[silk breach]

Yep.

Von Mongoldt function?

[mossy sun]

mhm

next

=tex \sum_{n \geq 1} \frac{\Lambda(n)-1}{n^s} = -\frac{\zeta'(s)}{\zeta(s)} - \zeta(s)

[mossy sun]

alright, so we're gonna look at the RHS first

particularly we want to prove it's analytic for Re(s)>=1

can I assume zeta has no zeros on Re(s)=1?

it's a standard trick

if we do, it's up to showing the poles at s=1 cancel out, which is a standard trick again for log derivatives.

so, RHS analytic for Re(s)>=1

now, what's the LHS

we use Abel's theorem on it.

=tex \sum_{n \geq 1} \frac{\Lambda(n)-1}{n^s} = \lim_{N \to \infty} (\psi(N)-N)*N^{-s} + s \int_2^N \frac{\psi(x)-\lfloor x\rfloor}{x^{s+1}}dx

[mossy sun]

we restrict for a second to Re(s)>1, so that

=tex \sum_{n \geq 1} \frac{\Lambda(n)-1}{n^s} = s \int_2^\infty \frac{\psi(x)-\lfloor x \rfloor}{x^{s+1}}dx

[silk breach]

What is $$\psi(x)$$?

[mossy sun]

the sum of \Lambda(n) for n <= x.

[silk breach]

Okay.

[mossy sun]

right so now

you remember contest 1 problem 7?

so clearly since this thing is supposed to be analytic for Re(s)>=0 and we have Re(s)>=1, we need to shift it a bit

=tex \sum_{n \geq 1} \frac{\Lambda(n)-1}{n^{s+1}} = s \int_2^\infty \frac{\psi(x)-\lfloor x \rfloor}{x^2} x^{-s}dx

[mossy sun]

this dude extends analytically to Re(s)>=0.

[silk breach]

k.

[mossy sun]

moreover, since psi(x) = O(x), which is easy, we have (psi(x)-floor(x))/x^2 = O(1/x)

and problem 7 applies

and the integral (and with a reverse Abel's, the sum) converges at s=0

=tex \sum_{n \geq 1} \frac{\Lambda(n)-1}{n} = C

[mossy sun]

we can find the value of C exactly if we wish by taking the limit of -zeta'(s)/zeta(s)-zeta(s) as s approaches 1, but we don't need to

=tex \sum_{n \leq x} \frac{\Lambda(n)-1}{n} = C + o(1)

[mossy sun]

=tex \sum_{n \leq x} \frac{\Lambda(n)}{n} = \log(n) + C+\gamma + o(1)

notice that this is a huge strengthening of the result log(n) + O(1) which I derived earlier by easier methods

[mossy sun]

apply Abel's:

=tex \psi(x) = \sum_{n \leq x} \Lambda(n) = x(\log(x)+C_2+o(1)) - \int_2^x (\log(t)+C_2)dt + o(x)

[mossy sun]

=tex = x \log(x) + C_2 x - (x \log(x)-x + C_2 x)+o(x) = x + o(x)