elementary-number-theory

[mossy sun]

so we've established the prime number theorem in the form psi(x) = x + o(x)

💯

[silk breach]

Pretty cool.

[mossy sun]

hell yea

shows the power of that tauberian theorem

you can use the same method to prove Dirichlet's PNT

[silk breach]

So, essentially PNT can be implied by $$\psi (x) = x+o(x)$$?

[mossy sun]

it's equivalent.

want a proof of that?

[silk breach]

I see.

Maybe...

[mossy sun]

it's not too bad

[silk breach]

Sure.

[mossy sun]

first we need a definition

=tex \theta(x) = \sum_{p \leq x} \log(p)

[mossy sun]

=tex 0 < \psi(x)-\theta(x)

[mossy sun]

the terms not in the difference psi(x)-theta(x) are generated by primes whose squares are <= x

that is

=tex 0 < \psi(x) - \theta(x) \leq \sum_{p \leq \sqrt{x}} \log(p) * \lfloor \frac{\log(x)}{\log(p)} - 1 \rfloor

[mossy sun]

=tex \leq \pi(\sqrt{x})\log(x)

[silk breach]

Dirichlet convolution?

[mossy sun]

nah multiplication

[vast vessel]

(\left,\right apply to \lfloor,\rfloor)

[mossy sun]

I know

[silk breach]

o.

[vast vessel]

:P

Hm

[mossy sun]

using pi(x) = O(x/log(x)), which is again easy, we get

=tex 0 < \psi(x)-\theta(x) = O(\sqrt{x})

[mossy sun]

so psi(x)/x goes to one iff theta(x)/x goes to one

that's the first step

next step is easier

=tex \theta(x) = \sum_{p \leq x} \log(p)

[mossy sun]

use Abel's, as always

=tex = \log(x)\pi(x) - \int_2^x \frac{\pi(t)}{t}dt

[mossy sun]

use pi(t) = O(t/log(t)), and then that the integral of 1/log(t) from 2 to x is O(x/log(x))

=tex = \log(x)\pi(x) + O(x/\log(x))

[stoic basin]

Support the bot on Patreon: https://www.patreon.com/dxsmiley

[mossy sun]

divide by x.

=tex \frac{\theta(x)}{x} = \pi(x) \frac{\log(x)}{x} + O(1/\log(x))

[mossy sun]

so theta(x)/x goes to one iff pi(x)log(x)/x goes to one.

thus PNT <=> psi(x)/x goes to one.

[silk breach]

$$\theta (x)/x \to 1$$?

[mossy sun]

mhm.

also \to

[mossy sun]

yep.

kinda cool result.

[vast vessel]

Cuz $$\psi(x)=x+o(x)?$$

[mossy sun]

yeap.

=tex \psi(x) = \theta(x) + O(\sqrt(x))

[mossy sun]

so

=tex \theta(x) = x + o(x)

[vast vessel]

Nice

[mossy sun]

here's somethin for you to try @silk breach @vast vessel

let A(x) be the number of naturals n <= x with an even number of prime factors (with multiplicity), B(x) for odd

[vast vessel]

Oh dear

[mossy sun]

prove that for any C>0, r<1/2, I can find a real x with

=tex \left|A(x)-B(x)\right| > C x^r

[vast vessel]

😰 ugh but I wanna git gud at ANT eventually

[mossy sun]

read apostol ya dummy

[silk breach]

http://plouffe.fr/simon/math/IntrodAnalyticNTApostol.pdf

What is meant by "with multiplicity?"

[mossy sun]

ie, 2*2*3 has three prime factors, not two

[vast vessel]

@mossy sun :P

[mossy sun]

oh, and @silk breach @vast vessel if you wanna get good at ANT, abel's theorem is a godsend

learn it, use it whenever possible, it's amazing and i love it

[vast vessel]

Kek

[mossy sun]

oh, and you can use the fact that the zeta function has a zero with real part 1/2.

[silk breach]

ok.

[vast vessel]

Rip

[silk breach]

I'm headed to bed now, but I will get into this tomorrow.

[mossy sun]

👍

[sacred junco]

Ant = algebraic number theory 👀

[vast vessel]

Analytic number theory 👀

[wild zinc]

Arithmetic number theory 👀

[noble jay]

I don't need quantity

These problems are too basic

Where can i find legit number theory problems

Or Theory of numbers. If there's any difference between the two

[steel steppe]

https://www.screencast.com/t/NA8iuCed

@noble jay

[noble jay]

This is good

[sacred junco]

Whats e ?

[steel steppe]

exp

[sacred junco]

Or tau ?

Okay wasnt sure

[steel steppe]

$$e(x) = e^{2 \pi i x} $$

[stoic basin]

Support the bot on Patreon: https://www.patreon.com/dxsmiley

[sacred junco]

Yeahseems eight

Tau is some discrete fourier stuff ?

[steel steppe]

tau is gauss sum

[sacred junco]

Mhm

Its ~ discrete fourier

[silk breach]

Yeah, that looks more like a DFT.

[sacred junco]

I dont want to do the computation but the idea seems clear to me ^^

[vast vessel]

tau is 2π

[fossil sapphire]

Not according to w|a

[sacred junco]

=wolf tau

[stoic basin]

Assumptions
Assuming "tau" is a mathematical constant. Use as 🇦 a particle or 🇧 a character or 🇨 a word or 🇩 a given name or 🇪 referring to a mathematical definition instead

Query made by @sacred junco
Data sourced from Wolfram|Alpha: http://www.wolframalpha.com/input/?i=tau
Do more with Wolfram|Alpha Pro: http://www.wolframalpha.com/pro/
🐺 Try out the new =pup command! It's much more concise.

[fossil sapphire]

Prove all even natural numbers greater than 2 are the sum of at most 2 primes

How do you do this?

[half fable]

haha yes

[fossil sapphire]

Pls halp

What's the answer

[sacred junco]

All natural numbers n, proceed with no use of n

[frail gorge]

everyone saw that

[mossy sun]

you mean at least

well

hurgh

bad wording

[fossil sapphire]

No I mean at most

[half fable]

@fossil sapphire are you serious with the question?

[fossil sapphire]

No

[half fable]

ok lol

[fossil sapphire]

Though if you can prove it I'll be happy to see the proof

[half fable]

sure let me call up my boy wildberger

[fossil sapphire]

Nah just do proof by exhaustion

Easy enough

[sacred junco]

Find three positive integers a, b, c that satisfies the equation: a/(b + c) + b/(a + c) + c/(a + b) = 4

I have no idea how to do this

Could anyone please help me?

[fossil sapphire]

Iirc try a few values that might work

Then work out the others

[sacred junco]

Hmm

I'll try

Good luck

Do I really have to test numbers?

Isn't there an algebric approach?

[wild zinc]

there is an algebraic approach

[sacred junco]

Thanks :D

@Chalcedon ❄#8294 what grade are you in to try this?

[wild zinc]

@sacred junco I sent the page that explains the solution

[sacred junco]

Where ?

@wild zinc

[wild zinc]

dms

[sacred junco]

To chalcedon you mean ?

[wild zinc]

ye

[sacred junco]

Ah why not here ?

[wild zinc]

because they asked me to share the algebraic method in dms

[sacred junco]

Is it with any N or tricks to do N=4 ?

[wild zinc]

n=4

[sacred junco]

@sacred junco I'm 12 years old and am in grade 7 - I didn't expect it to be that complicated D:

[swift shard]

You're in grade 7 and solving that mess?

[sacred junco]

Nope, this is way too complicated for me ;D

[mossy sun]

lol its an elliptic curve, ofc its complicated :P

[granite sun]

I know what an ellipse is

I know what a curve is

what is an elliptic curve?

Just a curve that can be represented as the arc of an ellipse?

[mossy sun]

i think its a curve of degree 3 but I don't have any experience so i may be wrong

[granite sun]

degree 3?

[half fable]

@granite sun not an arc of an ellipse

totally different thing

[granite sun]

oh

[proper cypress]

isn't that some equation where you have y^2 = x^3 or something

[granite sun]

y=x^(3/2)?

that's not degree 3...

[half fable]

not the same thing

[granite sun]

that's degree 3/2...

[half fable]

y^2 = x^3 is not a function

[granite sun]

But you can make it one by taking both sides to the power of 1/2, no?

[proper cypress]

thats why i said eqation

[granite sun]

(aka. root both sides)

[mossy sun]

doesn't need tp be a function

its a collection of points

a curve.

[granite sun]

sorry I'm outside of my element in number theory, probably doing something stupid there

whoa

symmetry

I hope I'm not interrupting a conversation

[half fable]

your avatar looks kind of like the king in musicians of bremen

the russian movie

[proper cypress]

see the first one isnt a function ^^

[granite sun]

ye

[half fable]

the curve is the image of 2 functions

[mossy sun]

thats a singular curve iirc

[half fable]

not the image

but the graph

[mossy sun]

try y^2 = x^3 + 3x + 10

[sacred junco]

An elliptic curve is a non singular cubic curve with a rational point if you want

[granite sun]

ohmygodwhatisthat

[sacred junco]

Or a complete curve of genus one with a rational point

[proper cypress]

Why do ppl think 2 being the only even prime is something special, i mean 3 is the only prime divisible by 3 too and so is 5 etc.

[half fable]

parity is very important in number theory

from what I've seen

arguably more important than divisibility by other numbers

or more useful idk

[proper cypress]

kay, you know its important if it has an own name

[sacred junco]

Work more and youll see how p=2 is a special caqe

Case*

Mostly its the fact that there isnt enough space in F_2

So usual formulas that involve p-1 for other primes break with 2

Also for an example you dont have bijection between bilinear forms and quadratics in char 2 cause no polar form formula cause cant divide by 2

Makes it much more complicated

[mossy sun]

and then there's the parity problem in sieve theory

but iirc that involves 2 less directly

[somber rampart]

The 2-adics behave weirdly as well

[mossy sun]

memes in #chill pleaz

[proper cypress]

i dont even get that meme, is it supposed to make fun of the goldbach conjecture?

[half fable]

I guess it's making fun of weak/strong distinction

[proper cypress]

ah

[half fable]

could anyone provide hints on how you'd prove that

x^p + 1 == 0 mod p^k implies (x+1)^p == 0 mod p^k

[fossil sapphire]

p prime?

[half fable]

yes

[fossil sapphire]

try expanding the RHS and see what happens to the terms

[mossy sun]

^

[half fable]

I already did

[mossy sun]

do it for a few test values of p if you're confused

like, say, p=5

[half fable]

do you know how to prove it?

[mossy sun]

mhm

what does (x+1)^5 equal?

[half fable]

x^5 + 1 plus some more terms

[sacred junco]

Is k arbitrary

[half fable]

all of which are divisible by 5 because 5 is a prime

[sacred junco]

Because I'm not sure that's true for all k

[half fable]

yes k is arbitrary integer

of course it's obvious when k=1

i'm having trouble when k>1

@mossy sun more hints pls?

[sacred junco]

Well what if you pick a massive value for k, so that mod p^k doesn't do anything

Then I don't think that identity is true

[half fable]

could you give me an example?

i checked a lot of cases with python

[mossy sun]

@half fable write all the terms

[half fable]

it seems to always hold

[mossy sun]

do it and trust me

[sacred junco]

p = 5, pick k = 1000000000000000000000

[mossy sun]

what is (x+1)^5

[sacred junco]

then x^5 + 1 is (x +1)^5?

[mossy sun]

x^5+1 plus what?

[somber rampart]

x^p +1 == 0 mod p^k is a strong condition there snore

binomial theorem people

[fossil sapphire]

@sacred junco that wouldn't have the first hold if "mod does nothing"

[sacred junco]

oh lol I didn't see "== 0"

I'm blind

[half fable]

well pascal's for 5 is 1,5,10,10,5,1

so x^5 + 5x^4 +10x^3 + 10x^2 + 5x + 1

[mossy sun]

right

or

[somber rampart]

5x^4 +10x^3 + 10x^2 + 5x + 5k for some k :)))

[mossy sun]

(x+1)^5 = x^5+1+5(x^4+2x^3+2x^2+x)

[half fable]

yes

I already noticed that yesterday

[mossy sun]

mod 5, any multiple of 5 disappears

[half fable]

correct

[mossy sun]

you are left with x^5+1

okay so

[half fable]

mod 5 yes

[mossy sun]

you just have to show that the binomial coefficients you use are all div by p.

[somber rampart]

Write it out with binomial theorem

[half fable]

i already know they're divisible

it's obvious

the case k=1 is obvious

as i said before

i want to prove it for k>1

[mossy sun]

what is k

[half fable]

look at my messages above

any positive integer

"could anyone provide hints on how you'd prove that
x^p + 1 == 0 mod p^k implies (x+1)^p == 0 mod p^k"

[somber rampart]

it's the same method

[half fable]

how come

@somber rampart care to elaborate?

[somber rampart]

I believe you can do it by induction

[half fable]

on k?

[somber rampart]

yeah

[half fable]

well base case is true

i dont see how I'd do the induction step

do you have any reason to think that induction would work or was it just a guess?

[somber rampart]

x^p + 1 == 0 mod p^k implies x^p + 1 == 0 mod p^(k-1)

[half fable]

yes

[somber rampart]

seems like a nice intro to an inductive proof

[half fable]

but we need to raise the power not decrease it

i actually don't know if it's true but I checked it with python for primes up to 13 and powers k<13 and no exeptions were found

and A LOT of x's were found that satisfy both equations

hundreds

[somber rampart]

I've seen the implication before

it is true

[half fable]

oh

[somber rampart]

induction on k is probably your best next step imo

haven't worked it out myself though

give it a shot with binomial theorem

[half fable]

could you too give it a shot?

in case I don't succeed, which is very likely

i have reasons to believe that induction wouldn't work

because we're proving an implication, not an equality

and RHS is much weaker than LHS ( there are many cases where RHS holds but LHS doesn't )

so in induction proof we would need to use the implication to a weaker condition with a lower exponent

which is pretty useless imo, because 1. we get a weak condition 2. the power k is lower than we need, which makes it even weaker

idk but this is just intuition, I might be very wrong

i'll state the problem again

"could anyone provide hints on how you'd prove that
x^p + 1 == 0 mod p^k implies (x+1)^p == 0 mod p^k"

[somber rampart]

Yeah, that line of reasoning makes sense

[noble jay]

looks like Fermat

lemme think about this

[mossy sun]

=tex (x+1)^p = x^p + 1 + \sum_{1 \leq n < p} \binom{p}{n} x^n

[mossy sun]

by the binomial theorem

now write \binom{p}{n} = p! / (n! * (p-n)!)

it is, first of all, an integer

second, the number of factors of p in the numerator is exactly one, and from the denominator, none, since n and p-n are both less than p

therefore it's divisible by p, \binom{p}{n} = p a_n for some sequence a_n of integers

=tex (x+1)^p = x^p + 1 + p \sum_{1 \leq n < p} a_n x^n

[somber rampart]

yeah but we need it for k

that's base case

[mossy sun]

OH shit

[half fable]

base case is obvious

[mossy sun]

oh my god I've been missing that

this entire time

[half fable]

we already talked about it griff

[mossy sun]

I'm sorry lol.

[half fable]

and i explained it to you :DDDD

and you come again

np

[mossy sun]

I was on my phone and didn't know what you were talking about /.\

[half fable]

just amusing

[mossy sun]

but uhhh

here's a nice fact you could use

[half fable]

@somber rampart do you maybe know where you've seen it before?

[mossy sun]

x is not divisible by p

that much is definitely true

[half fable]

it's not

i agree

[mossy sun]

that'll help

[half fable]

i don't think it will

but thanks anyway 😉

[mossy sun]

:\

it's good because now you know it's in a residue system mod p

that's a nice thing to use sometimes

[somber rampart]

griff is so used to ANT they can't do divisibility proofs anymore

[mossy sun]

lol shush

[half fable]

what does a stand for here

analytic or algebraic

[mossy sun]

analytic in my case.

[noble jay]

i got an idea but i'm sure if it's correct

[half fable]

it's a bad acronym

[mossy sun]

it is lol

[half fable]

@noble jay please share your idea

[somber rampart]

ANALNT

[half fable]

correct

[mossy sun]

well AnaLytic = AL so ALNT

[noble jay]

oh wait nvm k is arbitrary

[half fable]

😦

sorry if you consider this spam, but

"could anyone provide hints on how you'd prove that
x^p + 1 == 0 mod p^k implies (x+1)^p == 0 mod p^k"

[mossy sun]

I like writing it as uh

[wild zinc]

have you tried hensel lifting?

[mossy sun]

x^p = -1 mod p^k implies (x+1)^p = 0 mod p^k

hensel might work maybe

[half fable]

@wild zinc never heard of such a thing

[mossy sun]

it does seem like a roots equation

type deal

[half fable]

i dont even know quadratic reciprocity

[mossy sun]

it's a way of moving solutions from p^j to p^(j+1)

[half fable]

i assumed it could be proved by elementary means

[mossy sun]

okay so let's say

x^p + 1 = 0 mod p^k for some k

and you have the solution X for x^p + 1 = 0 mod p^(k-1)

we know x = X mod p^(k-1)

so x = X + r p^(k-1)

plug that boy into the equation and solve, hensel lefting is basically doing that iirc

[half fable]

that seems elementary

and like it shouldn't deserve a name

[mossy sun]

and this time we know (X+1)^p = 0 mod p^(k-1)

it's ridiculously helpful

[somber rampart]

induction :D

[mossy sun]

mhm!

that may be the way to go

induction on the shoulders of hensel

[somber rampart]

when your intuition is right but you have no idea how to implement it

I know basically no number theory

[half fable]

me too 😛

[mossy sun]

ooh hold on

one sec

[half fable]

[mossy sun]

it boils down to (X+1)^p = 0 mod p^k?? but that doesn't feel right hrm

shouldn't be right

unless X=-1

[half fable]

no it is right

for A lot of cases

hundreds of cases

when x!=-1

[mossy sun]

are there any cases where that's false?

oh

[half fable]

no

i checked using python

and strikingwolf says he saw this theorem before

[mossy sun]

so the solutions are just -1?

[half fable]

and claims that it's true

no

different

[somber rampart]

it is very familiar

[mossy sun]

😶

[half fable]

is there any way to search an equation online?

up to some equivalence

to maybe find if someone did this before

google is very bad at searching equations

[mossy sun]

right I think the only solutions are uh

x = n(p^(k-1) - 1)

• r p^k for any r

that'd make sense

[half fable]

how come

[mossy sun]

hold on i'll write it out

x^p + 1 = 0 mod p^k for some k
and you have the solution X for x^p + 1 = 0 mod p^(k-1)
we know x = X mod p^(k-1)
so x = X + r p^(k-1)

[half fable]

and yeah you're right

using python

mod 3^k

[mossy sun]

I tried mod 7^k and 13^k

if we expand (X+r p^(k-1) + 1)^p

[mossy sun]

we get (X+1)^p + (bunch of stuff divisible by p^k easily)

if (X+1)^p = 0 mod p^k then we're good

obv X=-1 satisfies this

this isn't a proof it must be true

[half fable]

ah yes

i see it

[mossy sun]

just why it works

[half fable]

proof that if the theorem holds, solutions are of this form

nice

ok imma go sleep now

please ping me if you get any ideas on how to prove it

that would be really helpful

good night ;+

[sacred junco]

@half fable try proving by induction thzt the solutions to X^p+1 mod p^k are of the form -1+ap^(k-1), a in {0,...,p-1}

[half fable]

@sacred junco did you succeed

Or is it just a suggestion

[sacred junco]

it should work

[sacred junco]

Did you make it work?

[half fable]

No

[fossil sapphire]

Is this that question from yesterday?

The (n+1)^k mod p thing?

[sacred junco]

So if a is a solution mod p^k its a solutin mod p^k-1 and by induction it tells you thzt a=-1 + ap^(k-1) +bp^(k-2)

Now just use newtons binomial theorem twice and it should give that if b is not zero than a^p is not -1

Oh there are two different a’s

Rename first a by x

(-1+ap^(k-1) +bp^(k-2))^p = (-1+ap^(k-1))^p +bp^(k-1)(-1+ap^(k-1))^(p-1) mod p^k

=-1 -bp^(k-1) mod p^k

@half fable

[sacred junco]

Anyone have any idea about this question? @everyone

[fossil sapphire]

The a|b symbol means that a divides b

[sacred junco]

What does w|x mean? I have no idea where to start with this.

Ah, gotcha.

[fossil sapphire]

So there is a factor of a in b

[sacred junco]

Does it say anything about whether it divides it cleanly or not? Will there be a remainder?

Okay. Gotcha. So b contains a factor of a.

Divides means no remainder otherwise it would be an empty statement

What if w = 24 and x = 13. Will w|x = 1 ? Will it floor the result?

What happens to the remainder?

[fossil sapphire]

It's a statement not a calculation

So a|b just gives a true or false

[sacred junco]

Ah okay. So it is just stating that w is divided by x.

Okay, so it returns a boolean. I like that idea.

[fossil sapphire]

If there is a factor of a in b then it returns true, if there is not it returns false

[sacred junco]

w|x == (true || false)

Gotcha. So if w is 24, and x is 12. then w|x will return true

Since 12 is a factor of 24.

[fossil sapphire]

More or less yes

[sacred junco]

Okay.

So this statement is saying that w will be a factor of (ax + by + cz)

?

Did I interpret that correctly?

[fossil sapphire]

Yes

[sacred junco]

How do I prove this? @fossil sapphire

[fossil sapphire]

Show each term has a factor of w in it

[sacred junco]

Hm. Ok. Let me try and work that out and I will post it on here.

Its the other way around w|x means w is a factor of x

If w=24 and x=12 its false

[jovial ether]

what level is this type of question usually taught in school? first year college?

[fossil sapphire]

I got this sort of stuff in GCSEs

Not exactly that symbol but same level

[sacred junco]

2nd year

[noble jay]

is this true for all a b and c in N
if q_1 is the quotient of a/b and q_2 is the quotient of q_1 / c
does it imply that q_2 is the quotient of a / bc?

wait no a is in Z

yeah is this true or no

[fossil sapphire]

Wdym quotient?

[noble jay]

like a=b*q_1 + r

[fossil sapphire]

r=0?

[noble jay]

not sure

if it was 0 then i probably wouldn't need all this

like i'm trying to prove it but i'm getting something irrational

[fossil sapphire]

Would it be true if c|r?

[noble jay]

which t

r*

there's 3 remainders

i assumed that none of them are 0

[fossil sapphire]

If q_1 is the quotient of a/b st a=q*b+r

[noble jay]

i'll rewrite it one sec

a in Z, b and c in N*
| a = bq_1 + r_1 (0<r_1< b)
|q_1 = cq_2 + r2 (0<r_2< c)
implies
| a = bc* q_2 + r3 (0<r_3< bc)
my question is is this implication true or false

[sacred junco]

Good discussion @noble jay @fossil sapphire

[half fable]

"So if a is a solution mod p^k its a solutin mod p^k-1 and by induction it tells you thzt a=-1 + ap^(k-1) +bp^(k-2)
Now just use newtons binomial theorem twice and it should give that if b is not zero than a^p is not -1
Oh there are two different a’s
Rename first a by x
(-1+ap^(k-1) +bp^(k-2))^p = (-1+ap^(k-1))^p +bp^(k-1)(-1+ap^(k-1))^(p-1) mod p^k
=-1 -bp^(k-1) mod p^k"

rename first a by x but you never use x

[sacred junco]

first a=x

then i compute x^p

[half fable]

"Now just use newtons binomial theorem twice and it should give that if b is not zero"

not zero mod what?

nevermind

damn the lack of latex makes this hard to read :9

[sacred junco]

yeah

tex it 😛

[half fable]

yeah that proof seems to work

thanks

we get that b is divisible by p

[sacred junco]

Good

Btw hensels lemma has more to it than what youve been told and dserves a name 😛

Its an existence abd unicity result to lift solutions to polynomials in z/p^nz to p adics

One of the main tools for the basic study of p adics

And it doesnt apply here

[half fable]

that sounds complicated

[sacred junco]

Thats why we have those solutions to x^p+1

You can see that they dont ‘go down’

The only solution that you are left when going down is -1

So its the only solution you can lift and that holds for all k

So its also a way to have the intution that the solutions will have that form if they exist

[half fable]

i see

[cursive thicket]

I thought Hensel's lemma had a name, "Hensel's lemma"

@sacred junco

[sacred junco]

Yes ?

[cursive thicket]

I'm not sure what you meant there

you're just saying Hensel's lemma tells you everything pete said plus extra, right?

@sacred junco

wondering if I'm missing something here

[ember crystal]

Do u have a name

[cursive thicket]

oh Pete said it didn't deserve a name

[ember crystal]

Or r u just an artificial nameless being

[cursive thicket]

roood

[ember crystal]

K

:(

[half fable]

most likely i misunderstood the lemma :D

[cursive thicket]

@ember crystal how do you feel about Hensel's lemma

[ember crystal]

It's a waste of time uwu

[solid plover]

Lmao

[sacred junco]

I said the lemma is not what have been told to pete. Thing is a lots of things are called Hensel lemma, in its stronger form it does really deserve a name

And it gives you existence and unicity of roots in the p adics from ones in z/pz or stuff like that

There are different version

Point was its a fundamental result in study if p adics that well deserves a name

[hollow basalt]

Q/ Find all triangles with consecutive integer side lengths and integer area.

[outer brook]

3 4 5 triangle

that's all I know

[fossil sapphire]

Which conjecture is it that states 8 and 9 are the only consecutive powers?

Nvm it was actually proven

=pup Mihăilescu's theorem

[stoic basin]

Wolfram|Alpha didn't send a result back.
Maybe your query was malformed?

[fossil sapphire]

=pup catalan's conjecture

[stoic basin]

Query made by @fossil sapphire
Data sourced from Wolfram|Alpha: http://www.wolframalpha.com/input/?i=catalan's+conjecture
Do more with Wolfram|Alpha Pro: http://www.wolframalpha.com/pro/

[wild zinc]

== sqrt (7056)

[stoic basin]

84

[wild zinc]

is the area of 13,14,15 triangle

[hollow basalt]

😃

[vast vessel]

@hollow basalt Any pythagorean triple works

no idea on any other cases

[wild zinc]

not consecutive

[hollow basalt]

yeah

other than 3,4,5 ofc.

[vast vessel]

oh

ships

Well

I got it down to solving a² = 3b²+1

[wild zinc]

ya#

redacted's equation

[vast vessel]

oh

I was trying to solve it but nvm

reasons why I'm bad at this

[sacred junco]

So its the units in Z[sqrt3] 🤔

[zealous goblet]

Truncated Approximations of √3

or just solve the difference equation and obtain the closed form

[sacred junco]

Quick maths

And i know what a prime number is -_-

[vast vessel]

https://www.mangareader.net/suugaku-girl/1

@sacred junco Within this manga, you shall find an explanation of what it means to be prime

as well as a semi-proof of the infinitude of the primes

[sacred junco]

Thanks!

[vast vessel]

:)

[mossy sun]

@hearty timber here's something that will help with that problem

[hearty timber]

oh they already gave me the solution pretty much

[mossy sun]

letting f(n) be the sum of remainders of n mod q for q<=n

[hearty timber]

but yours might be more colorful go on

[mossy sun]

=tex f(366) - f(365) = 2*365+1-\sum_{q \geq 1} q\left(\left \lfloor \frac{366}{q} \right \rfloor - \left \lfloor \frac{365}{q} \right \rfloor \right)

[mossy sun]

that difference of floors behaves very nicely when it's just a difference of one

specifically it's only nonzero if q is a divisor of 366

thus

[hearty timber]

oh you still have to sum over all divisors of 366 manually

any way to avoid that?

[mossy sun]

hold on

=tex 2*365+1 - 366 d(366) + \sum_{q \mid 366} q \lfloor 365/q \rfloor

[mossy sun]

d(n) being number of divisors of n

I thinkkkkkkk

hold on

that floor(366/q) - floor(365/q) is 1 if q divides 366

[hearty timber]

[mossy sun]

yeah

=tex f(366) - f(365) = 2*365+1 - \sum_{q \mid 366} q

[hearty timber]

yeah

[mossy sun]

that's nice at least

365 - sum of proper divisors of 366

[hearty timber]

ye it looks like the other way

I don't think you can avoid calculating sum of divisors

[mossy sun]

yeah.

it's not many at least

366 = 2*3*61

[tacit solar]

Does this work for any consecutive numbers?

[mossy sun]

mhm

[tacit solar]

That's very neat. I like it.

[mossy sun]

so sum of divisors of 366 is (1+2)*(1+3)*(1+61) = 3*4*62 = 744

== 2*365+1 - 744

[stoic basin]

-13

[mossy sun]

QED

[hearty timber]

ah that's a good way to calculate sum of divisors

[mossy sun]

multiplicativity is always nice

[tacit solar]

Very cool indeed.

[wild zinc]

question 1 from this year's BMO1 :^)

[fossil sapphire]

what was it

[wild zinc]

pretty much that

one minute, I'll get the phrasing it had on the paper

wait nvm I misread what the earlier question was :^)

but it was similar

http://puu.sh/zJFDE/08076929c3.png

[fossil sapphire]

oo interesting

well my first instinct is crt

[wild zinc]

ya

well

december 2017

the naming convention for years for BMO is a bit weird, and varies between BMO1 and BMO2, but I think it was called BMO1 2017 on the paper

and then the next round was called BMO2 2018 on the paper

[woeful solar]

helppp

[sacred junco]

A

[woeful solar]

why

[sacred junco]

because I said so

[woeful solar]

uhh okay

[sacred junco]

it is A right?

ok look

$$1 + 2 + \dots + n = \frac{n(n + 1)}{2}$$

[sacred junco]

So we have $$p = n + 1$$

[sacred junco]

The only one of those where p is prime is A), n = 108, p = 109

the others aren't prime

[woeful solar]

oh it cannot be n because it will divide one of the summands

so is (n+1)?

[sacred junco]

...

Kawaii-snore - Today at 12:51 PM
So we have $$p = n + 1$$

[woeful solar]

ya idk why its n+1

[sacred junco]

Because n + 1 is going to be odd

[woeful solar]

but what if n+1 is divisible by 2

[sacred junco]

idk

but that doesn't happen

1 + 2 + ... + 108 = 5886

That's divisible by 109, which is prime

And 108 + 109 = 217

[woeful solar]

hmm

ya it still doesnt convince me that p = n+1

but i kinda understand where ur going

hm

[sacred junco]

oooohhh

[woeful solar]

what if uhhh (n+1) is divisible by 6

[sacred junco]

so that's how you do it

sotto ur a genius

yeah I got A but idk how

but I get it now

[woeful solar]

why must it be n+1

[sacred junco]

let p = (n + 1) / 6

[woeful solar]

OH

[sacred junco]

then p would divide (n + 1) / 6

[woeful solar]

OMG

[sacred junco]

which can't happen lafaom

[woeful solar]

okay

thanks

[hearty timber]

well it's kind of a simple manipulation

try to use modular arithmetic

a solution is https://math.stackexchange.com/questions/174175/proof-of-the-divisibility-rule-of-17

but you won't get much hint from it

just a direct method

[robust shale]

i'll try

It does not work

oh

wait

Let me try one more minute

It does work, but it is quite triky

wait

I'm an idiot

it does not work

and now i can proof it

54-4*5=34, which is multiple of 17, but 54 isn't

[sacred junco]

is this channel new

[hearty timber]

no

[outer brook]

Someone should teach me how the amount of digits in an exponentiated expression can be determined by taking the log of the base times the exponent

ofc rounded up to a whole integer

[sturdy dirge]

$$1 + \floor{log_{10}(a)}$$

[somber rampart]

Digits of a?

[viscid narwhal]

What does a geometric interpretation that show how the ordinary iteration method behaves when g'(x) < -1.

How*

[noble jay]

i don't think this is the place to ask that

[viscid narwhal]

It isn't? mb

[sacred junco]

would someone mind giving some direction (not solving):

it is under the section with sigma functions; but im having trouble seeing how they relate

[unkempt hedge]

How do you solve something like 32^128 (mod 25)

@sacred junco Not sure how you would use sigma function but if you let p = prime number and a = any integer then a^p == a (mod p) (it is called fermats little therom)

[sacred junco]

yeah ive been trying that direction but im just confused as to why this is in the sigma function section

[unkempt hedge]

[sacred junco]

my prof likes to do this for bonus' like there's some hidden gem we've missed

he'll accept it for solving it any other way but needless to say im excited to see when he posts the solution to this one

[unkempt hedge]

How would you solve something like 32^128 (mod 25).

[half fable]

@unkempt hedge euler's theorem?

32 == 7 is coprime to 25

[unkempt hedge]

@half fable ok, but if they are not co-prime?

[half fable]

then idk something else

computer could help

[unkempt hedge]

how would you solve something like 31^128 (mod 25)?

[half fable]

31 == 6 is still coprime with 25

[unkempt hedge]

wait, then I have the wrong understanding of what coprime is

does that mean 6 does not divide 25?

and therefore it is not coprime?

[half fable]

coprime means no common factors

[unkempt hedge]

oh, ok...

[sacred junco]

Try reducing to b=1 should work

Its the same kind of shit shinshen asked a while ago

[half fable]

?

what did i ask

[sacred junco]

A while ago

I dont remember exactly but it was about roots of unity in Z/p^kZ

[noble jay]

@xanaxmonk#4162 do you still need help with that?

rip

tfw someone asks a number theory question but you're too late

[sacred junco]

hello

[noble jay]

@sacred junco so you have

$$a^p-b^p=(a-b)\Big(\sum_{i=0}^{p-1}a^{p-1-i}b^i\Big)$$

and you've already proven that p divides a-b
so all you have to do know is prove that p divides that sum right? so you can multiply one by the other

[sacred junco]

ohh

[sacred junco]

hold on give me a moment to process, im quite slow

[noble jay]

alright

[sacred junco]

i thought binomial expansion was for sth of the form (x+y)^n

wouldn't this be a general geometric series?

though im confused on how to write this in terms of

wait hold on

[noble jay]

i don't reallly know the name

[sacred junco]

its a different formula than the newton's binomial one

[noble jay]

lets just call it factorization

[sacred junco]

I dont think it has a name

ah

thank you for the nudge in the right direction

[noble jay]

anyway we've already proven that p/a-b
so if we prove that p/sum
that means p divides sum times a-b

to prove that you would just need to play a bit with powers of a and b

in mod p

no problem

[sacred junco]

yeah im working on it right now

thanks a lot you've been a great help!

[noble jay]

👍

[unkempt hedge]

Ok, I am stuck. Which theorems do I Need to know to solve this (I do not want the answer) I have tried to use Euler's theorem, Fermats little theorem and combined with the Chinese remainder theorem, but I don't see any connections.

[distant creek]

You solve it by hand

[unkempt hedge]

@distant creek Are you saing that I already have all I need to solve it, or are you asking if I am solving it by hand?

[distant creek]

2018¡=2018^2017^2016^2015^2014...^1

[unkempt hedge]

yes, "2018^2017^2016^...^2^1 mod(100) = ?"

[pine fiber]

That is hilarious for that question

[unkempt hedge]

@pine fiber What should I do then?

[noble jay]

@unkempt hedge go to pm i'll give you a hint

[vast vessel]

Related: http://googology.wikia.com/wiki/Exponential_factorial

But not really 👀

=tex 2018^n\equiv8^n\equiv8^{n\bmod4}\pmod{10}

[exotic oxide]

OH

nvm I only know how to get the units digit

hmm

[hearty timber]

do it mod 100

[noble jay]

are you guys still discussing that 2018¡ problem?

[unkempt hedge]

lol

[worthy sable]

Could anyone help me with this problem?

[sturdy dirge]

$$\left{\begin{matrix}u(2u+2z-1) = n & \text{if k = 2u}\(2u+1)(u+z) = n & \text{if k = 2u + 1}\end{matrix}\right.$$

[sturdy dirge]

Factorize n and start counting.

[noble jay]

good thing no one can find deleted messages

[sacred junco]

So you think

Bijection works in english btw

[noble jay]

any ideas how i can prove that there is no prime number that is equal to the sum of 15 other primes to the 4th power

so like (p_1)^4 + (p_2)^4 + .. .. .. .. . + (p_15)^4 is prime

i don't know if there is or not but thats what i'm trying to figure out

[outer brook]

Wow I have no clue how to prove I would like to see a proof though

[noble jay]

how the heck would you know if theres infinitely many primes
everything i found so far doesn't get me to any conclusion

if only number theory was as common as calculus or something

@outer brook i got it

it doesnt exist

assuming p>5

but you can easily get a contradiction if p = 2 or p=3

or p=5

[somber rampart]

@noble jay Assume there are a finite number of primes

p_1 through p_n

Create a new number

=tex Q = 1 + \prod_{i=1}^{n} p_i

[noble jay]

i did -1 instead

[somber rampart]

doesn't work

not as well anyway

[noble jay]

and i proved it using mod

[somber rampart]

I'm talking about proving infinite primes

[noble jay]

oh right

[somber rampart]

Q is not divisible by any p_i

[noble jay]

yeah i've seen that proof before

[somber rampart]

and Q > p_i for every i

How does that not get you to any conclusion?

[noble jay]

i wasn't asked to prove that there are infinitely many though

[somber rampart]

how the heck would you know if theres infinitely many primes
everything i found so far doesn't get me to any conclusion
?

[noble jay]

oh

[somber rampart]

confuse

[noble jay]

what i meant by that is how the heck would you know (my question), if there are infinitely many primes

[somber rampart]

ahhhh

[noble jay]

i still don't know how to prove my question for all p
it only works for p>5

that way i can use fermat

[wild zinc]

look mod 3 as well

might give something useful

it's too early for me to work out if that's all you need or not :^)

[noble jay]

@wild zinc i did thats why i assumed that p>5 so i could use fermats theorem

[wild zinc]

mod 3 gives unless p_i = 3 for some i

mod 5 gives unless p_i = 5 for some i

[noble jay]

but p_i is prime

oh

right

i feel dumb

[wild zinc]

mod 2 gives an even number of p_i equal 2

mod 3 and 5 should actually give similar results (multiple of 3/5 of p_i equal 3/5)

[noble jay]

yes thats what i used

15 divides p_i means its not prime

[wild zinc]

yeah

you can probably do something mod 8

using euler's theorem

but I'm not sure that gets you much

[noble jay]

i don't think the first method doesn't apply for p=<5 because we're talking about the sum of 15 distinct prime numbers and if 2,3 or 5 are in the list they won't have the same modulo as the other primes but i think there's a way to treat them on their own

maybe by using mod 8 like you said

[wild zinc]

oh if they're distinct that should be fine

we know 2 can't appear from taht

and that 3 and 5 must

[noble jay]

why not?

[wild zinc]

if 2 appears then we have that it's 0 + (14 1s) mod 2, or 0 mod 2

so not prime

[noble jay]

right

[noble jay]

i'm always the last one to post here for some reason

[shrewd marsh]

Not anymore

[noble jay]

rip

[vast vessel]

👀

[solar fox]

@noble jay

[noble jay]

@solar fox

[shrewd marsh]

🚪

[brave shell]

👋

[noble jay]

let n be a positive 6 digit number. we exchange the 3 first and 3 last digits of the number
so for example 125614 becomes 614125
find n so that the result after the exchange is 6n+21

[celest plinth]

look at wat

[noble jay]

i still haven't solved it

and i'm close

[celest plinth]

oh ok

[noble jay]

thank you

[celest plinth]

there

[noble jay]

👍

[celest plinth]

i deleted it then edited a post from a month ago and put it there

[noble jay]

mhm

it's too messy to understand so dw

i'll figure it out and post my own solution

[celest plinth]

ok~

ya i kinda just wrote it as i went

so it's def not organized lol

[noble jay]

lel

[brave shell]

c) it's too short

I don't know that much on encryption, I've only ever skimmed on it in CS at GCSE level

But that's pretty obvious. Aren't they supposed to be at least 32 bits?

[wild zinc]

if you want it to be secure it should be at least 1024 bits

preferably 2048

[brave shell]

oh haha

That makes sense

[sacred junco]

I've done (a) and (b)

(a) is C= 9 and (b) 27 (and checking again it's 4).

Yeah, I need help with (c) @brave shell

[brave shell]

Well it's way too short

It can be cracked in milliseconds

And with his public key that short, it means his private key is short too

(is what i mean by that getting cracked)

[sacred junco]

I see, so it'd be easier for him to attack or hacked whatever.

to get*

[brave shell]

It would be harder not to get hacked with a key that short

[sacred junco]

that doesn't make sense?

do you mean decrypted?

[sacred junco]

This is a set-theory topic.
A relation is formally a set of pairs

Yep. Let's move the discussion in pure-math

(no set-theory room :/)

[noble jay]

tfw someone finally posts in NT channel but its not a NT question

[sacred junco]

ahahaha RIP

and it's set theory, which has no tag :/

[proper cypress]

there are more than enough open nt questions : ^)

[sacred junco]

Goldbach plz

easy

EZ

every even number is sum of two primes

EZ

[somber rampart]

Big oof

[noble jay]

@sacred junco congrats on the honorable role

[sacred junco]

@noble jay eheh thanks 😊

[cyan pawn]

Congrats @sacred junco you deserve it!

[sacred junco]

@cyan pawn Aww thanks 😊

[pine fiber]

I'm trying to learn number-theory by myself, but I don't know where to start

[fossil sapphire]

Congruences is probably a good idea

[sacred junco]

@pine fiber look for a nice introductory book

https://www.quora.com/What-is-the-best-textbook-for-self-learning-number-theory

[unkempt hedge]

Prove: if c divides ab and gcd(c, a) = d then c divides db
I have been trying forever, and it probably has an easy solution

[fossil sapphire]

Let a=a'*d

Does that help?

@unkempt hedge

[unkempt hedge]

what does ' mean

does it mean a divisor of a ?

[fossil sapphire]

It's just "related to a but not actually a" in this case

You can use any letter

[unkempt hedge]

ok

[fossil sapphire]

Let a=ed if you prefer

[unkempt hedge]

I have been using that method. But it does not look to go anywhere.

cause you come to something like cq=ab , dp=c and dz=a

[fossil sapphire]

What is gcd (c,e)?

[unkempt hedge]

@fossil sapphire I am not sure

[fossil sapphire]

Well if gcd (a,c)=d, what is gcd (a/d,c)?

[unkempt hedge]

c?

[fossil sapphire]

Try putting some numbers in if you prefer

Say a=10, c=6

[unkempt hedge]

wait it is 1?

[fossil sapphire]

Yes

[unkempt hedge]

cause d is the gcd which mean they don't have any common denominators anymore once you divide

[fossil sapphire]

Common factors but yes

[unkempt hedge]

true

[fossil sapphire]

So if c divides ab what is gcd (c,b)?

[unkempt hedge]

@fossil sapphire I want to say b, but I don't know if "c divides a" or a combination of "a" and "b".

[fossil sapphire]

gcd (c,ab)=c and (gcd (c,a)=d and gcd (c,a/d)=d/d=1).

What is gcd (c,ab/a)?

Try to spot a pattern with the bit in parenthesis

[unkempt hedge]

gcd(c,ab) = c => gcd(c,ab/a) = c/a ?

[fossil sapphire]

Well technically c/a*e (where e is a random integer)

But yes essentially

So what is gcd (c,db)?

[unkempt hedge]

why?

the random integer that is?

[fossil sapphire]

Well gcd (24,4)=4

But gcd (24/4,4)=2=/=4/4

[unkempt hedge]

ok, but why did you do it in your example then?

[fossil sapphire]

So you're guaranteed to have that factor but there may be another factor

?

[unkempt hedge]

well you said gcd(c,a) = d and gcd(c, a /d) = d/d = 1 but should it not be gcd (c/d, a/d) = d/d = 1

[fossil sapphire]

Oh I think I assumed d=/=c

Which I probably shouldn't have done in retrospect

The logic still applies

So if we go back to the original question,

What is gcd (db,c)?

[unkempt hedge]

c, but I don't know why

cause we are trying to prove that c divides db which means c is a multiple of db

[fossil sapphire]

No it means c is a factor of db

[unkempt hedge]

Is that not the same multiple and factor

[fossil sapphire]

No

[unkempt hedge]

regardless, the meaning was factor

[fossil sapphire]

Complete opposites

[unkempt hedge]

lol

[fossil sapphire]

Well you can think of c as have two "sets" of factors

Ie the factors it has in common with a

And the factors it has in common with b

Now, there is some overlap so it ends up being more like a Venn diagram

[unkempt hedge]

How do you know that there is overlap, or not

[fossil sapphire]

It doesn't matter

Since d contains all the common factors with a

Including those in the overlap

Ýes?

[unkempt hedge]

Ok, but if c = 4 and a = 4 and b = 3, then if d divides a saying that d = 4 or d = 2 and if d = 2 then c does not divide ab

oh

Now I see

It has to be 4

because the gcd(c,a) = d

@fossil sapphire Am I correct?