elementary-number-theory

[sterile pumice]

Ann:

[quick furnace]

so the total count of divisors is 2 * (size of lower group) + 1

which is literally odd by definition

@craggy solstice

[carmine shard]

does anyone know of a proof that states any prime is a sum of other primes and or 1

[silver solar]

Yes, here: any prime p = 1 + 1 + ... + 1 (p times)

[wild zinc]

are they required to be distinct?

if so, there's a simple induction proof using bertrand's postulate

[olive remnant]

For division with remainder theorem (Let a and b be integers with b > 0. Then there exist unique integers q and r such that a=bq+r and 0 \geq r < b), can I just say a=0 q=0 and r=0 is the base case and P(a+1,b) splits off into if r < b - 1, r = r+1 and if r = b-1, then r=0 and b=b+1? (and then do the same for P(a-1,b) and prove uniqueness?)

[craggy solstice]

i dont think all primes can be written as a sum of primes

[sacred junco]

@craggy solstice you can use Bertrand’s postulate for this.

excluding the case for 4,6,11

If we take the primes to be distinct, that is

And you’d have to include 1

This is hard to prove

[wild zinc]

1,3; 1,5; 1,3,7

[crystal pond]

What is the second largest number that cannot be expressed in the form of 13n+31m, where n and m are integers.

I’m not sure how to approach this

[torn escarp]

are you sure this is the question?

Bezout's identity tells you that there's a solution to 13n+31m=1 so once you find that, 13(kn)+31(km)=k

you can make any number

[stoic bear]

I assume positive integers n and m

[torn escarp]

even then, the problem is easier

13, 26 done

can only be a combination of multiples of 13 and 31

oops did that backwards

1, 2

done

[stoic bear]

what

2 largest

[torn escarp]

2 is the second largest number that can't be written of the form 13n+31m with n,m positive

not sure how else you could interpret it

question is just wrong

[stoic bear]

The largest number that cannot be expressed is 359 by McNugget Theorem

[torn escarp]

oh lmao

makes sense, I don't know why I did second smallest

[stoic bear]

Finding the second largest number after that is trivial

[crystal pond]

Ohhh McNugget Theorem

I didn’t know that was a thing haha

[sacred junco]

Show that $\sum_{n \leq x} d\left(n\right) = xlnx + O(x) $ where dn is number of positive divisors of n

[sterile pumice]

Godel:

[sacred junco]

Assuming u know sum 1/n = lnx +O(1)

Abels summation theorem but not sure how

[idle holly]

Oh, I see

hm, I’ll think on this

@sacred junco

O(1)*x=O(x)?

or is this not correct, I am trying to learn it so I can help

[supple furnace]

sum n<x d(n)=sum n<x floor(x/n) by swapping order of summation

[hollow basalt]

$\sum_{n\leq x} d(n)=\sum_{n\leq x}\sum_{m|n} 1=\sum_{m\leq x} \lfloor \dfrac{x}{m}\rfloor=x\sum_{m\leq x} \frac{1}{m}+O(x)$

[idle holly]

@hollow basalt that was a quick proof Gomez, I had a similar idea for multiplying the sum over 1/m by x

that’s why I was asking about O(1)*x=O(x)

[sterile pumice]

gomez:

[idle holly]

put \bigg before \lfloor

and \rfloor

[hollow basalt]

I know how to make delimiters bigger, I just didn't care.

[idle holly]

Ik you do haha

[sacred junco]

wait why is that

[idle holly]

I was just noting

[hollow basalt]

why is what?

[sacred junco]

floor x/m

that sum

[idle holly]

$\sum_{m|n}1=\bigg\lfloor{x/m}\bigg\rfloor$?

Oops forgot the outer sum

[sacred junco]

no thats different

[hollow basalt]

Think about how many times a given m "counts" in the previous sum.

It is precisely the number of multiples of m less than x.

which is the floor of x/m

[sacred junco]

ohh ok I think I see it

it was a question on my exam and I had like 10 mins lef to do it

I tried induction or something lmao

but that was very quick

nice

[hollow basalt]

a much better bound on the error than O(x) can also be achieved with not too much effort.

[sacred junco]

well

it was probably O(x) because the previous question on the exam was to show sum 1/n is lnx + O(1)

[hollow basalt]

Yeah I wasn't suggesting you were remembering your exam question wrong.

[sacred junco]

ye ye gotcha, thanks tho

[hollow basalt]

🐱

[scarlet mountain]

So I've been trying to find the integer solutions to y^3 = x^2 + 4. When I factorise it I get y^3 = (x+2i)(x-2i). If I can prove that gcd[(x+2i),(x-2i)] = 1 then I know there exists integers a,b such that (a+bi)^3 = x + 2i
Following this, I assume y is odd and hence the gcd^2 divides both 16 and y^6 hence is 1, so I get the solution y=5, x = +-11 (solving for a,b from imaginary part and then solving for x) however this also gives me the other solution(s) y = 2, x = +-2 despite me assuming x,y were odd. Is there some obvious thing I'm missing here?

Because when I assume they are even, I get the second equation 2y^3 = x^2 + 1 which I have no idea how to solve due to the pesky 2

[craggy solstice]

catalan

[sacred junco]

@craggy solstice Tijdeman’s. Catalan says x^m - y^n = 1.

that’s a bit advanced though, how do you solve this lol

[broken igloo]

y^3-8=x^2-4?

gcd[(x+2i),(x-2i)] divides 4 and x+2i, and 2x, so the only possibilities are 1, 1+i, 2, 2+2i.
If x is odd, then the gcd can only be 1.
If x is even, the "gcd" is only 2 or 2+2i.

[quick furnace]

first find the exponent of 3 in the prime factorization of 1000!

gotta make it at least a little bit easier

esp given that it's greater than 333

[quick furnace]

no

in the product of all the integers from 1 to 1000

you have

actually you have precisely three hundred and thirty-three numbers which are divisible by 3 and so contribute a factor of 3 to the product.

3, 6, 9, 12, ..., 999

[silver mortar]

no you don't get it

how many multiples of 3 are in 1000!

there are 333: 3, 6, 9, 12, ..., 993, 996, 999

each multiple is equal to 3*something else

so you have 3*1, 3*2, 3*3, ..., 3*332, 3*333

you can factor out the 3s

so just like how 3*6*9*12 = 3*3*3*3 * 1*2*3*4 = 3^4 * ...

3*6*9*12*...*999 = 3*3*3*...*3 * 1*2*3*...

= 3^333 * ...

so 1000! is a multiple of 3^333

np

[stuck lintel]

@gentle elk u here?

[gentle elk]

Yes

[stuck lintel]

okay so

[gentle elk]

Yeah pls

[stuck lintel]

are you fluent with basic modular arithmetic?

[gentle elk]

Not

[stuck lintel]

okay do you know what euclids algorithm is?

[gentle elk]

Not really.

But it would be awsome to know how to do the problem.

[stuck lintel]

there's a lot of prerequisites if you wanna know how to do it without a calculator lol

[gentle elk]

Lol I need to know on the calc though because I need to be able to do it in 30 secs

[stuck lintel]

okay so basically the short version is that via the euclidean algorithm, we know that every integer x has an inverse in mod m if gcd(x,m)=1. so using that, we can find x by finding x^-1

we can also use euler's theorem, $x^{\phi{(m)}}\equiv \pmod{m}$ if gcd(x,m) =1 to reduce the power down by a lot

[sterile pumice]

Plum:

[stuck lintel]

if youre using a calculator then you can just use euler totient to get 7^384 = 7^-16, then use a calculator for 7^16 and take the inverse

[gentle elk]

How did you knwo it’s was -16

How did you determine that

[stuck lintel]

phi(1000) = 400

[gentle elk]

Liek for 5502 how will you determine it

[stuck lintel]

well we only care about the mod so we use the same phi value

[gentle elk]

So 400-5502 ?

[stuck lintel]

5502 = -98 mod 400

[gentle elk]

How do you k@ow that though ?

[jade latch]

to find the first 3 digits just take log_10(n) and then divide by 10^(log_10(n)) and look at the first 3 digits on the calculator

[gentle elk]

I need the last thre Fitbit

Digits *

[jade latch]

log_10(n) basically finds the number of digits

last 3 just use crt

mod 8 and mod 125

[stuck lintel]

he/she doesnt know crt

[gentle elk]

Idk what taht means

Yeah

[jade latch]

chinese remainder theorem

just google it

[gentle elk]

So I would take 5502 mod 8 and 5502 mod 125

[jade latch]

if u want youll find out that the last 3 digits cycle every 100 🤣

[gentle elk]

And crt it?

[jade latch]

whats 5502

[gentle elk]

7^5502 is the question

Liek what are the last three digits of it

[jade latch]

no not like that

[stuck lintel]

lol honestly if you have a calculator just use fast exponentiation

[stuck lintel]

just find 384 in binary and calculate 7^(2^k) for every 1 in position k

[gentle elk]

That happens

Wait could you just explain me the mod one

[stuck lintel]

okay so

[jade latch]

just google crt

[stuck lintel]

he doesnt have the background knowledge to understand the theorem

[gentle elk]

Yeah

[jade latch]

oh

[gentle elk]

If you did that problem on a paper I could Kanye recreate the same thing for other questions

Maybe *

[stuck lintel]

interesting autocorrects

okay ill just latex it

[gentle elk]

What does that mean ?

Latex ?

[stuck lintel]

$$\varphi{(1000)}=400 \to 7^{400} \equiv 1 \pmod{1000}$$ $$7^{384} \equiv 7^{-16} \pmod{1000}$$ $$7^{16} \equiv (-1)^{16} \equiv 1 \pmod{8}$$ $$7^{16} \equiv (7^4)^{4} \equiv 26^4 \equiv 101 \pmod{125}$$ Using CRT, $$7^{16} \equiv 601 \pmod{1000}.$$ Using euclidean algorithm, $$7^{-16} \equiv 401 \pmod{1000}.$$ Therefore, $$7^{384} \equiv 401 \pmod{1000}.$$

[sterile pumice]

Plum:

[gentle elk]

How did you get 7^-16 is 401

[light flicker]

Idk why you guys are trying to do this, he obviously doesn't understand any of what you're doing

Just tell him to go read some book

[gentle elk]

Wait I understand all@of it

Except one thing

How did you do 7^-16 =401

[light flicker]

No you don't understand any of it

[gentle elk]

Ok sorry

[light flicker]

You don't know what CRT means or what euclidean algorithm is

[gentle elk]

Yes but what I do get is take the number look at the last two digits do 100-that number

Then do 7^_the number you get mod 1000

And your awnser is there

[light flicker]

Yeah but you don't understand any of the other stuff

And that's the stuff you need to understand to be able to do this

[gentle elk]

Ok 👌

[light flicker]

So you should just go read a book

Maybe the aops number theory book

To try to learn this stuff to be able to do these types of problems

[jade latch]

@light flicker where is ur pfp from

[gentle elk]

Dude I just need a way to do this question that all

[jade latch]

oops this is prob the wrong channel for that

[light flicker]

Tower of God

[jade latch]

oh

thought so

[stuck lintel]

BRUH

I KNEW IT

[light flicker]

Have you read it?

[jade latch]

yeah

im caught up

[stuck lintel]

smh

[light flicker]

Including the fastpass chapters or

[jade latch]

nah

i dont fastpass

[light flicker]

They're fifty cents each

[jade latch]

lmao

[light flicker]

It's a 2 dollar a month subscription lmao

[jade latch]

eh it doesnt make much of a difference

[light flicker]

Yeah I just couldn't help myself

[jade latch]

thank god rachel is gone

idk where she is but i dont care

as long as i dont have to see her again

[light flicker]

Someone asked me if this was Rachel yesterday lmao

[jade latch]

rachel is blonde smh

[light flicker]

Yeah that's what I said

Okay anyways

@gentle elk This isn't going to be the problem on the test

You're not going to get better at competition math if you just memorize processes to do certain types of problems

The problem you're going to get on the test is going to be altered and so you have to actually understand these ideas if you want to be able to do problems

[jade latch]

aops books r a good start

[stuck lintel]

10 days before amc no-less

[jade latch]

yeah well

im assuming hes younger than us lol

[gentle elk]

@light flicker that’s the thing I know that it won’t be. Tecas is not the smart when I comes down to this stuff. But I still see your post

Point*

Yeah I am 15

[jade latch]

oh

still younger than me

😢

[gentle elk]

😢😢

[stuck lintel]

wow im old

[light flicker]

The point is also that most tests won't allow calculators and so you shouldn't rely on calculators when one won't help, like in this question

[gentle elk]

Lol ok

[jade latch]

u need a calculator to find the first 3 digits tho

[light flicker]

Yeah true

[gentle elk]

It ussaly asks us to find the tens place for the question

[jade latch]

but for the last 3 u dont really need to, its just a bit of computation

[stuck lintel]

or learn fast exponentiation

[light flicker]

If they give you the approximation for log_3(10) or whatever the question is then you don't need a calculator either

[jade latch]

well

[gentle elk]

Like is says, 7^5502 what is the digit in the tens place

[jade latch]

thats just mod 100

[gentle elk]

That’s the problem

[jade latch]

lol

[light flicker]

And that's why we're trying to tell you to learn this stuff

[jade latch]

well 7^8 = 1(mod 100)

and 8 is small enough where u can just test a bunch of small values and find a pattern

[gentle elk]

Dude I think we have two difrent mod definitions

[jade latch]

a = b (mod n) -> a = b + kn for an integer k

[gentle elk]

When you say mod 100 I think of a number dicddd by 100 and the reminder of it is the awnser

[jade latch]

yes

[light flicker]

They're the same

[jade latch]

^

[light flicker]

7^8 is 5764801

[jade latch]

yeah

[gentle elk]

Ok then what from there ?

[jade latch]

then 7^(5496) = 1 (mod 100) cuz 8 divides 5496

so the last two digits is just the last two digits of 7^6

which is 49

[gentle elk]

Ok

Made no sense to me but I will get it soon

[light flicker]

I mean you won't

Unless you read a book on number theory

There are a lot of things going on in what he said

[gentle elk]

yeah

[stuck lintel]

how do you prove that if m and n are coprime, then m^2+n^2 and mn are coprime?

[jade latch]

m^2+n^2+2mn

m+n and mn are coprime

done

[stuck lintel]

what how

[jade latch]

or m^2+n^2-2mn both work

euclidean algorithm gcd(m^2+n^2,mn) = gcd(m^2+n^2-2mn,mn) = gcd((m-n)^2,mn))

and gcd(m-n,n)=gcd(m-n,n) = 1

[stuck lintel]

oh ty

[pine marsh]

if you're using the euclidean algorithm to solve for x and y in ax + by = c, where c is the GCD of a and b, do you always do a/b first (to get the remainder and such)? because I have a problem where b > a so if I do a/b I get basically 0 and b as the remainder. Should I just flip them and do b/a?

[sacred junco]

ax+by=c has no solutions in the integers.

[sacred junco]

@pine marsh yes

@sacred junco what?

@sacred junco for some reason I thought we were restricting to Z+

well Z+ \cup 0 are naturals not integers

but yeah, there is a solution in integers and obviously isn't in positive naturals

[spiral lantern]

Hey guys.

I don't understand the implication of then n+1 is an element of B
I understand it like this: B is a subset of N, 1 is element of B, members of set [1,2...n] are elements of B.
Why does that imply that n+1 is also element of B?

[inner crest]

we aren't supposing 1,2,...,n are elements of B. we are supposing that: if 1,2,...,n are elements of B, then n+1 is an element of B

[spiral lantern]

So, its a hypothesis.

[inner crest]

uh what do you mean? We are supposing that the if...then... statement is true

(while also supposing $B\subseteq\mathbb N$ and $1\in B)$

@spiral lantern

[sterile pumice]

EpicGuy4227:

[inner crest]

The whole sentence has the form "Suppose...; then $B=\mathbb N$"

[sterile pumice]

EpicGuy4227:

[spiral lantern]

right

I am having difficulties understanding the "...then n+1 is also in B" part. Why is it true and where does it follow from? Is that simply a part of the assumption (Suppose that...)?

[sacred junco]

what they're trying to say is

1. B is a subset of N

2. 1 is in B

3. whenever an element x is in B, x + 1 will also be in B

if these three conditions are satisfied then B = N

because of condition 1 we know that the set doesn't contain any other type of numbers other than natural numbers

condition 2 says that 1 is in B

so use condition 3 on x = 1

1 is in B -> 2 is in B

now take x=2

2 is in B -> 3 is in B

and you can do this forever

and you'll end up getting all natural numbers in B

so B = N

condition 2 is called the base case

[spiral lantern]

right

thanks!

[sacred junco]

3 is called the inductive step

👍

[tawny meadow]

is there some typo here? i don't understand where $m+b\geq 0$ came from

[sterile pumice]

fields!:

[tawny meadow]

if $b$ is a lower bound of $S,$ then $m\geq b$ for all $m\in S$

[sterile pumice]

fields!:

[quick furnace]

should definitely be m-b and not m+b

er

wait

lemme make sure i'm not screwing something up big time

yeah they should've considered -b + S and not b+S

if S = {-10, -9, -8} and b = -11 then their construction fails

[tawny meadow]

belated ty

[tawny meadow]

for the case that $S$ has an upper bound, from where does it follow that $M$ has a least element? is it due to the well ordering principle? how?

[sterile pumice]

fields!:

[tawny meadow]

<@&286206848099549185>

[civic marsh]

yup, wop states that a discrete countable set has a least element. you can substitute it with induction in many proofs

[quick furnace]

define "discrete"?

[winter bear]

basically i reduced the problem to showing:

$J(\chi \rho,\rho)^3 = \left(J(\chi,\rho)^3\right)^*$, where $\chi$ is a character of order 3 and $\rho$ order 2. i tried doing some stuff like expanding the sum, but i didnt really get anwhere.

[sacred junco]

whats J ?

I wont be able to help but just curious

[winter bear]

its a jacobi sum

[sacred junco]

It's trivial

whats the original problem?

[winter bear]

its to show

[light flicker]

you should just pull up Ireland Rosen and read for yourself

[winter bear]

$g(\chi \rho)^6 = \rho(-1) p \bar{(\chi(2) J(\chi,\rho))}^4$

thats it fuck bars lmao

im using *

[sterile pumice]

JohnDoeSmith:

[winter bear]

better lmao

but yeah, any hints zoph?

[sacred junco]

You will probably find something similiar in Problems in Algebraic NT by Murty,Esmonde

full with solutions

[light flicker]

this isn't algebraic NT

[sacred junco]

it has jacobi sum problems

I wasnt giving a random book, why would I do that

[light flicker]

Idk you talk out of your ass a lot

@winter bear Let me get home in maybe an hour and I'll think about it

[winter bear]

aight

[sacred junco]

true

@winter bear check the book mate its really nice

[light flicker]

the book has nothing similar to this problem

[sacred junco]

looked very similiar so jsut recommended sorry my bad but still it might help

sorry again

[winter bear]

actually im stupid

i was trying to expand sums and shit, but actually just converting to gauss sums makes it easy

nvm lol

(also there was a factor of rho(-1) ontop of the conjugation thing btw,if you end up trying to prove it)

[sacred junco]

where can i start with find all positive integers n for which both n and n^2+2 are prime ?

heres what i tried

since both n and n^2+2 need to be prime n has to be of form 2k+1

then i substituted that into n^2+2

(2k+1)^2+2=4k^2+4k+3

now im looking at this expression and i know that i somehow have to show that 4k^2+4k+3 cant ever be a prime but i cant guess how

*cant ever be a prime unless k=1 or k=0

i also tried about thinking in terms of prime factorization, but couldnt get far with that either

[light flicker]

k = 4 gives 83 which is prime

[sacred junco]

oh yeah but in that case you have n^2+2 prime and n composite

@light flicker do you know how to go about it?

[light flicker]

Hm, I can only think of one solution

using quadratic residue ideas

[sacred junco]

i havent learned of quadratic residues in my class yet

[light flicker]

you've learned about fermat's last theorem?

[sacred junco]

i do know about it but not in class

this is like 2nd week in the elementary number theory class

the only thing weve learned is gcd prime factorization and some other basic stuff

[light flicker]

you've learned about mod right

[sacred junco]

yup

[light flicker]

think about p^2+ 2 (mod 3)

[sacred junco]

is there something about perfect squares that helps?

[light flicker]

no

[sacred junco]

alright ill chew on it

[light flicker]

well

yeah go ahead

[sacred junco]

right now i dont see anything else than p^2+2 (mod 3) being anything else other than 0,1,2

if its 0 then p^2+2 is not prime

if its 2 its not prime either

if its 1 it can be a prime

so i can write p^2+2 = 3k+1

so @light flicker i've realized that p^2+2 is prime only when p^2+2 (mod 3) is 1 or 2. setting up equations for both scenarios is p^2+2=3k+1 and p^2+2=3k+2 and further simplifying those 2 equations i get p^2+1=3k and p^2=3k

so what im thinking of now is to claim that

[light flicker]

Can p^2 + 2 ever be 1?

[sacred junco]

nope

i said (mod 3)

if you're referring to that

[light flicker]

Can it ever be 1 mod 3?

[sacred junco]

its 1 mod 3 if p^2 mod 3 is 2

i guess im not seeing why p^2 mod 3 cant be 2

[light flicker]

Just check all the possibilities

There are only 3 of them

(also fermats little theorem, but you don't need that here)

[sacred junco]

oh i see it with fermats little theorem

when you say 3 possibilities, what possibilities do you mean?

[light flicker]

The value of n^2 (mod 3) depends only on the value of n (mod 3)

[sacred junco]

oh

and

n needs to be prime

so it needs to be odd

[light flicker]

I.e, if you pick 1,4,7,10,... The square will always be 1 mod 3

[sacred junco]

its 2 only when n is even, right?

[light flicker]

Uh what no

[sacred junco]

ok fail

[light flicker]

Check all three possibilities

0 squared is 0, 1 squared is 1 and 2 squared is 1

[sacred junco]

thanks, i get it now

[light flicker]

Do you see how to finish the problem

[trim kraken]

That one was a fun one :D

[still granite]

if n is 3 mod 8, and k is a positive integer at least 4, prove that n^(2^(k-3)) - 2^(k-1) - 1 is divisible by 2^k

can i have a hint

i tried some weird induction/mod stuff
but i haven't gotten anywhere after a while

[light flicker]

@supple furnace

[still granite]

<@&286206848099549185>

[torn escarp]

use the lifting the exponent lemma on $n^{2^{k-3}}-1$

[sterile pumice]

Merosity:

[torn escarp]

||it turns out to be exactly divisible by 2^{k-1} so combined with 2^{k-1} it's divisible by 2^k||

lol

sorry didn't realize you wanted just a hint

I'm sure there are other ways to do this too, just the first way that came to me.

for p=2 and n even, v_2(x^n - y^n) = v_2(x-y) + v_2(n) + v_2(x+y)-1

stop deleting your messages lol

also you need p| x-y but not x and y individually, don't forget that either

[light flicker]

I should learn LTE rip

did you hear about how I proved a case of LTE in a paper I'm writing up but never realized that it was LTE until someone talked about it here

[torn escarp]

yeah I remember that the other day

or maybe month or more now haha

also the ultrametric inequality makes simplifying it quicker too @still granite if you've heard of that

@light flicker I heard you did your presentation on it the other day right?

[light flicker]

poster yeah

[torn escarp]

I think I downloaded it and was going to read and ask questions about it but I forgot

you said a while back you actually talked with silverman and he like said a bunch of stuff really fast about it or

I'm kinda interested in knowing what your thing is about I kinda want to get up to speed on that sounds interesting

[light flicker]

Well what happened is we were stuck and asked Silverman for help and he basically solved our problem

I could send you the draft of the paper we're writing, I don't think it's super complicated stuff

[torn escarp]

ok sure sounds good, I guess dm it to me or something

also as far as the LTE goes, I found it easier to remember cause there's a more general similar p-adic theorem about strictly differentiable functions, there's always some open ball centered at a, given f'(a) != 0 where

$|f(x)-f(y)| = |f'(a)||x-y|$

[sterile pumice]

Merosity:

[torn escarp]

LTE is f(x)=x^n and a is a unit

[alpine jasper]

@all functions are Lipschitz

[strong tiger]

how do i find deriv respect to t when (h-r)/r = h/5

[light flicker]

Wrong channel

[strong tiger]

how did i get in here lmao

[sacred junco]

was just looking at this now

https://math.stackexchange.com/questions/1009511/primes-dividing-11-111-1111

am i misunderstanding this question or why does my argument seem to be so simple

if integers are of the form 11, 111, 1111, ...

then every 3rd integer their digits sum up to a multiple of 3

111 is divisible by 3 because digits sum to 3

111,111 will also be divisible by 3 because digits sum to 6

so doesnt this question become trivial to answer?

[light flicker]

You've only done the case for the prime 3

what about all the other primes

[sacred junco]

oh i misread it

then its pretty not trivial haha

[spare tangle]

What does this question asking us to do?
Show that any product of any set of numbers of the form 6n+1 is again of the same form

[light flicker]

Do you understand what it means for a number to be of the form 6n+1?

[spare tangle]

Yes

I think so?

refers to the set of numbers with the elements 1, 7, 13, 19... right?

[light flicker]

Yea

Then what exactly don't you understand here

[spare tangle]

So we're trying to prove that a number of the form (6n+1) x another number of the form (6n+1) = (6n+1)?

[light flicker]

Technically this statement says more than that

[spare tangle]

I don't understand what it is actually asking us to do in this case

[sacred junco]

yep once you edited its ok

[light flicker]

No Godel

[spare tangle]

so you just expand and factorise it?

[sacred junco]

why not?

[spare tangle]

That seems too trivial

[sacred junco]

wait i might be wrtong

[light flicker]

It says the product of any number of things of the form (6n+1) is also of that form

Which

Follows from what you said

But

[sacred junco]

just need to show for 2

[spare tangle]

i.e. L = a multiple of n?

is thst what you mean?

[light flicker]

Sure but it's still not what the question is asking

Uh what

[spare tangle]

he said (6j + 1)(6k+1)=(6l+1)

right?

[sacred junco]

no actually the statement says sth more

[spare tangle]

Hmm

[sacred junco]

ANY number of numbers of that form are of that form

[spare tangle]

so the product of all the numbers in the set

or you mean

k(6n+1)

[sacred junco]

no matter how many numbers of the form 6k+1 you multiply, you will still get one of the form 6k+1

[spare tangle]

Hmm how does it say that

ahh

[sacred junco]

Show that any product of any set of numbers

[spare tangle]

I see it now

[sacred junco]

ANY product

[spare tangle]

Okay nvm I don't see it

[sacred junco]

"Show that any product of any set of numbers of the form 6n+1 is again of the same form" - What does 'any product' mean

[spare tangle]

So

[sacred junco]

Any product, meaning, for example (7*13*13*13*13) still is of the form 6k+1 for some k

[spare tangle]

(6n+1)(6n+1)...(6n+1)=(6n+1)

[sacred junco]

no, those 'n' may not be the same

[spare tangle]

where none of those n's are equal

[sacred junco]

whip why are you saying yep

where clearly its not right

and then you say Eh no HEre

[spare tangle]

where none of those n's are equal

[sacred junco]

no , they MAY be equal

[spare tangle]

Oh

[sterile pumice]

WhipStreak23:

[torn escarp]

this seems like some major over thinking here lol

[spare tangle]

But I thought we don't have repeated elements in a set

[sacred junco]

you can

[spare tangle]

Wait, really?

[sacred junco]

yes, because it says any product of ANY SET OF NUMBERS, so, first set might be {7,13} , second {13,19}, then 13 will appear twice in the product

[light flicker]

n_n lmao

[sacred junco]

lol

how can you multiply sets

Show that any product of any set of numbers of the form 6n+1 is again of the same form

read this

before typing `10000 lines

[spare tangle]

Guys relax

[sacred junco]

no he clearly didnt understand it

that the numbers can repeat

[spare tangle]

Should I show you the entire question

it might help

[sacred junco]

@spare tangle have you learned about induction?

[torn escarp]

@spare tangle just work through the algebra of expanding this (6j + 1)(6k+1)=(6l+1) thing you typed earlier

[spare tangle]

yeah

So it should just be proved by induction?

how does that account for repeated elements though

nvm repeated elements would also be of the same form

[torn escarp]

technically, but I don't think it's worth really doing more than just mentioning it

[sacred junco]

think about the induction step here.

[spare tangle]

Yea

[sacred junco]

@torn escarp well, but only then the product of two elements what you wanted him to do makes sense

[torn escarp]

I'm aware

[sacred junco]

which is obvious to you, but not for him

[torn escarp]

I'm also aware of that

[spare tangle]

so just show that the product of two elements is of that form

[sacred junco]

so why did you say not weorth to do anything more than mentioning it

[torn escarp]

this is spinning wheels violently not getting anywhere lole

[spare tangle]

and then I can just mention that by induction this is true for any number of elements?

[torn escarp]

yeah

[sacred junco]

you should show the case for 2 elements and how knowing about n implies it works for n+1

[torn escarp]

it's obvious, probably this guy has been multiplying numbers his whole life, to multiply 10 numbers together you pick two next to each other, multiply them to make a single number and now you have 9 numbers

rinse and repeat

call this "induction" sure, it's belaboring something that's obvious to most children imo

[spare tangle]

I mean it makes sense but seems rather trivial

[torn escarp]

yeah just go forward with (6j + 1)(6k+1)=(6l+1) and showing l is indeed an integer

that's really the only step that's "hard" lol

[sacred junco]

if you understand it then dont type it out

[spare tangle]

idk the girl next to me mentioned a proof by contradiction

something about (6n+1)(6n+2)(6n+3)

does that trigger any useful ideas?

[light flicker]

No

Do induction

[sleek cove]

bezouts identity only holds for 2 integers, right?

nvm

[light flicker]

It can be generalized

[sleek cove]

yee

[spare tangle]

bezouts identity = h,k lemma?

Do induction
@light flicker ok boss

[spare tangle]

Hey, I'm struggling to express 1 as a linear combination of 50 and 41

[light flicker]

Bezouts identity

[spare tangle]

I know, but I'm not quite getting it

I've gone through a couple of sheets of paper now xD

[light flicker]

You're using the euclidean algorithm?

[spare tangle]

Yeah

repeatedly applying the division theorem

and then just going backwards from the last step

[light flicker]

Maybe let me see your work

[spare tangle]

nvm

idk where I was messing up

but it took me like 4 tries to actually get it?

[torn escarp]

seems about normal, just be careful

you can also sometimes get shortcuts by using negative numbers but I don't think it'll be too helpful here, like for instance where you did the step 41=9*4+5 you could have done it as 41=9*5-4

might save you like, only a single step in this particular problem cause the numbers are so small doesn't matter

[spare tangle]

Btw, I still didn't understand how to do this question

4i

Proof by induction would only prove that the product of n * succ (n) takes the form 6n+1

[light flicker]

You're not understanding how we're inducting

[spare tangle]

Kindly do explain then

[light flicker]

just read what mero sad

[spare tangle]

So you mean you're using the result of this induction to prove that cumulatively all products would take that form?

Sort of like, recursively form every number as a product of n and succ (n)

[torn escarp]

don't "succ(n)" anything

[spare tangle]

why not

[torn escarp]

you're overcomplicating something that's very easy

you have some kind of fundamental misunderstanding I guess, I don't know

explain in just simple english what it means for a number to be of the form 6n+1

[spare tangle]

that it's one more than a multiple of 6?

[torn escarp]

ok good

now what do you have to prove?

[spare tangle]

That the product of any numbers of that form is of that form

[torn escarp]

so what would you do to convince someone of that

[spare tangle]

well, after seeing what you've said

I'd convince them that if the product of an element in the set and the next element is of that form

then it would hold true for all elements in the set since you can form them all in terms of products of the original element and the successor being referred to

[torn escarp]

sure

[spare tangle]

Is that sarcasm?

[torn escarp]

no, just not sure what to say

[spare tangle]

I mean, is there a fallacy in that logic?

[torn escarp]

if you are convinced then I guess I'm convinced

what doubts do you have?

part of knowing why something is true is knowing what isn't true

I can't really tell if you're just saying this but you don't believe it yourself or not

if there's something about it you don't believe, then say it

I'm not psychic

like apparently you're here with some sort of doubt but

every step along the way you seem to be just producing and agreeing to

so why are you here?

@spare tangle

this isn't rhetorical I'm trying to help you refine your question

[spare tangle]

sorry on the tube no signal

Well, I guess I don't fully agree with all of my statements or rather I don't fully understand them

Particularly the inductive bit which means that it would hold true for all elements in the se

set*

[stray helm]

hey there

[spare tangle]

Hi

[stray helm]

can i get a tldr?

[spare tangle]

of all of this?

[torn escarp]

just say no

[stray helm]

of what you need help with

[torn escarp]

I guess alternatively let's pretend you have to prove that the product of N integers is an integer

[spare tangle]

I'm doubting the inductive logic in proving that the product of any elements in the set of integers given by (6n+1) is of the form (6n+1)

That's the tldr

[stray helm]

what's the product of two such numbers?

[torn escarp]

@stray helm you ready to help instead of me?

[spare tangle]

I mean suppose you have the second element times the fifth element

[stray helm]

thanks for the tldr!

[torn escarp]

good luck have fun

[stray helm]

@torn escarpsure ill take over

[spare tangle]

Thanks a lot @torn escarp

[stray helm]

so erm

berry boi

[spare tangle]

yo

[stray helm]

i want you to think of the solution alright, i will only guide you to it

[sacred junco]

yo I can take voer I love induction

[stray helm]

first of all, why do you think induction works here?

@sacred junco lmfao but na i can manage

thanks

[spare tangle]

Well you can definitely prove that the product of an element and its successor is of that form

so you can prove that the entire product of the elements of the set take that form

[stray helm]

but it's not just about the product and it's successor is it?

[spare tangle]

Yes

and that's kinda the bit I'm getting confused with

[stray helm]

it can be erm, 6(1)+1 and 6(3)+1 too yeah

[spare tangle]

cant each element be written in terms of the successor of the first element

[stray helm]

like how

[spare tangle]

so in terms of the products

the product of the first element and its successor take the form 6n+1, the product of the second element and its successor also take that form

so if you get to the point where you kinda have a cumulative product?

so this proves that the product of each element in the set and another element in the set must be of the form 6n+1?

No?

[sacred junco]

How do you define 'first,second element' and a successor in this problem?

[spare tangle]

Since you can construct elements in the set using the form of the product

Well, because the question started out with primes

We had already defined n > 0

[stray helm]

do you mean to say that [6(1)+1] [6(2)+1] is of the form 6n+1?

[spare tangle]

yeah

6(15)+1

[stray helm]

and then [6(2)+1][6(3)+1]

is that the way you wish to induct?

[spare tangle]

Yes

[stray helm]

it's a good idea, but do you think it hits all such products?

[spare tangle]

it doesn't

[stray helm]

nope it doesn't

[spare tangle]

but my question is if all the products are rewritten in terms of the original

[stray helm]

wdym by the original

[spare tangle]

of the first element

and the second

the product of the first two elements*

[stray helm]

what would be the original of
[6(1)+1][6(3)+1]?

[spare tangle]

at some point all elements can be rewritten as a product of succ in the set, right?

I mean that when deaing with super large numbers

Like, theoretically

all elements can then be written as a product of some n and succ(n), right?

[stray helm]

why do you think that?

[spare tangle]

idk

[sacred junco]

The thing is, in your problem, there isn't a 'minimal' element

[spare tangle]

gut feeling

[stray helm]

do you have an idea for a proof?

[sacred junco]

Unless you define it in a different way, 7 isnt it

[stray helm]

nope

[spare tangle]

I mean I just think that when you have large enough numbers you can define them as the product of two successive? elements in the set

I don't know if it's true

nor can I prove it

[stray helm]

multiplication is a rather quick operation

gets to huge numbers very fast

[spare tangle]

Idk how to prove it then

[stray helm]

so na, i don't think your conjecture is true

[spare tangle]

And even if it was, that wouldnt cover all the possibilities

[stray helm]

erm a counterexample could be

[f(1).f(3).f(5)] [f(7).f(9).f(11)]

where f(n)=6n+1

see these are in their "smallest" state

because f(1).f(2)=f(15) right

[spare tangle]

yeah

[stray helm]

so, let's forget about your idea alright

[spare tangle]

Yeah

[stray helm]

it was a dead end

now

two numbers in the set {6n+1}, how wouls they look like?

[spare tangle]

"how" would they look like?

6(n)+1, n € Z+

[stray helm]

euro symbol

nice

[sacred junco]

lmfao

[spare tangle]

I'm on my pgone

[sacred junco]

new meta

[spare tangle]

CUT ME SOME SLACK

[stray helm]

it's cool

verry cool

[sacred junco]

no its nice

[spare tangle]

it's almost the same

:(

[stray helm]

it's beautiful

[spare tangle]

ahahahah

[stray helm]

okay so

by "how" they look like, erm ye you were right

but we need a product of two(2) such numbers

how would the product look like

[spare tangle]

(6n+1)(6m+1) n!=m

and n,m € Z+

[stray helm]

SWEET MOTHER OF MOON you got it

[sacred junco]

n can be m

so not quite

[stray helm]

why n!@=m?

yeah

[spare tangle]

That's in the trivial case

[sacred junco]

no

[spare tangle]

No

No?*

[stray helm]

no

[sacred junco]

thats a case you will be missing if you dont include it

[spare tangle]

I included it

I just considered it trivial

[sacred junco]

no

[spare tangle]

and didn't think it requires further proof

[stray helm]

[6(7463377)+1][6(7463377)+1] aint trivial my boi

[sacred junco]

I mean sure if you proved that then its fine

[spare tangle]

Well

I didn't prove it

[stray helm]

itt does require proof ma guy

[spare tangle]

in hindsight

idk why I thought it's trivial

[stray helm]

it's fine

[sacred junco]

I mean its the easier version of the base case you will have to show so I guess its fine

[stray helm]

happens to the best of us

now

MULTIPLY

[spare tangle]

right, done

You know the funny thing is, in my head I was thinking that form all along, but I said m = n+1

[stray helm]

yep

you were close

[spare tangle]

Right, so you multiply

But what do you do with that expression?

[stray helm]

what do you get?

[spare tangle]

(6n+1)(6m+1)=36mn+6m+6n+1

[stray helm]

AAAH BEAUTIFUL

do you see that?

[spare tangle]

See what?

[stray helm]

it's of the form 6( )+1

[spare tangle]

How?

[stray helm]

you tell me

[spare tangle]

oh

[stray helm]

[spare tangle]

Dude

it's sad that I

WROTE ALL OF THAT

And then let

m=n+1

because

I was so fixated on induction

😂 😂 😂 😂

[stray helm]

KEKE

[spare tangle]

(earlier)

[stray helm]

happens

[spare tangle]

so

[stray helm]

induction can be a hoe sometimes

[spare tangle]

do we have to show the trivial stuff

[stray helm]

you shouldn't let her control you

[spare tangle]

like mn € Z

and stuff

[stray helm]

ehhhhhh?

[sacred junco]

you take that back wolf I love induction

[stray helm]

m=n?

[spare tangle]

huh

No I meant

[torn escarp]

back up I don't believe he knows

(6n+1)(6m+1)=36mn+6m+6n+1

[stray helm]

@sacred junco i just love her too much, and i suffered

[spare tangle]

that the brackets

[torn escarp]

write it explicitly

[spare tangle]

are integers

the entire bracket

[torn escarp]

factor it out

(6n+1)(6m+1) = 6k+1

what's k?

[spare tangle]

6mn+m+n

[stray helm]

which is.....

[torn escarp]

why did I ask you to solve for k?

[spare tangle]

No I meant

Do I have to explicitly state

that's an integer

which belongs in the set

[stray helm]

yep

yeppppppp

[spare tangle]

Yeah

That's what I meant

[stray helm]

HJJIIIIJNNNNN IRRATIONAL

[spare tangle]

by saying do I have to show that the brackets belong to Z

[stray helm]

actually yeah, but it's trivial right

m.n is in Z

hence 6.m.n in Z

hence 6.m.n+m in Z

[spare tangle]

Yeah

[stray helm]

hence 6mn+m+n ik Z

yeahhhh

[spare tangle]

ik?

[stray helm]

hm?

[spare tangle]

what's ik

[torn escarp]

a typo

[stray helm]

*in

[spare tangle]

ah

Thanks a lot btw

NOW FOR GAUSSIAN PRIMES AND OTHER SHIT THAT I DON'T UNDERSTAND

😂 😂

I didn't anticipate this homework would take this long

[stray helm]

🤙 🐺 🤙

[spare tangle]

I guess I'm just a noon

noob*

yes, I'm a noon

[stray helm]

yes u noonberry

[sacred junco]

🤙 🐺 🤙

I love this

[stray helm]

[spare tangle]

Thanks a lot though

Honestly

[sacred junco]

Solving my first diophantine equation

Need to show that 5x^2+2=y^2 has no integer solutions

This is what I've done

I take mod 5 of both sides and show that they are not equal

5x^2+2 mod 5 -> 2

y^2 mod 5 -> {0,1,4}

since there is no overlap, the equation cant be solved

does this work?

[light flicker]

Yes

[sacred junco]

yeey!

[spare tangle]

Hey, I'm wondering how I'd prove the division theorem for Z[i]

i.e. part (ii)

[light flicker]

have you tried using the hint

[spare tangle]

I'm not sure what to make of it

so, suppose we have the s = a +bi and t = A + Bi

We can find s/t, in terms of a,A,b,B but I'm not sure where to go from there

[light flicker]

It's not a coincidence that they use the letter q there in the hint

as well as having the letter q be one of the things you need to exists

[spare tangle]

yeah but how would you show that there's a remainder?

[light flicker]

s - tq

= r

[spare tangle]

Hmm... that makes sense and all but

how would you show that t is decreasing

[light flicker]

what

why do you need t to be decreasing

[spare tangle]

if applied multiple times?

[light flicker]

uh

still not seeing where in the problem it asks you to show anything like this

[spare tangle]

also don't you have to show that the quotient is less than s?

[light flicker]

where in the problem does it tell you to do anything like that

[spare tangle]

I mean if s = tq + r

[light flicker]

also, it makes no sense to compare complex numbers

[spare tangle]

i.e. division theorem

you'd have to show that the quotient is less than s, no?

[light flicker]

Again, the problem doesn't tell you to do any of this

[spare tangle]

So what exactly is it asking then 😅

[light flicker]

you can read

[native zenith]

I cant understand this article. Why is it necessary https://brilliant.org/wiki/bezouts-identity/https://brilliant.org/wiki/bezouts-identity/

why is it a necessary condition.

did i do this wrong, how do you post a new question

This article is not brilliant, its full of logical gaps.

This is one of the reasons i hate number theory.

It like people write stuff and never look back (like they are in a hurry), and typos abound.

[light flicker]

Okay well first to answer your question

gcd(a,b) divides both a and b

[native zenith]

right, by definition

[light flicker]

so maybe think about gcd(a,b) and ax+by

[native zenith]

Im not sure what they mean by 'this condition', and what equation.

[light flicker]

They're trying to show that all integers of the form kd can be written as ax + by

I.e., ax+by=kd

What they're noting in the thing you've highlighted is the converse statement

That if ax+by= c, then c = kd for some integer k

[native zenith]

and d here means gcd(a,b)

[light flicker]

yes

[native zenith]

" all integers of the form kd can be written as ax + by" that means there exist integer solutions x,y such tat ax + by = kd

[light flicker]

yes

[native zenith]

ok and where is the converse here

the author doesnt say where the converse begins

[light flicker]

they don't

They just say "we already know"

[native zenith]

what does that mean?

[light flicker]

it was proven earlier usually

[native zenith]

i know what that means but

im lost

[light flicker]

what exactly are you lost about

[native zenith]

for someone learning this the first time, idk

i dont get it, it makes no sense.

what is the necessary condition?

this paragraph is trying to prove the convers?

[light flicker]

"That if ax+by= c, then c = kd for some integer k" like I said earlier

This is the necessary condition

[native zenith]

so they never proved bezouts identity

they just assumed its true

[light flicker]

I mean yes, but not where you're highlighting

[native zenith]

anyways. thanks for your help

[light flicker]

Maybe a piece of advice

It's pretty clear you're not really familiar with proofs or higher math at all

So you should familiarize yourself more with that before trying to read these things

Yes there are a lot of logical gaps here, but they are logical gaps that you could fill in if you understood what they were saying

And that's why people leave logical gaps, so the reader can check that they're understanding what's happening in the proof

[native zenith]

but it doesnt make sense, because bezouts identity says ax+by = d has a solution, not ax+by=kd has a solution

if we start from bezout's identity on the page

https://brilliant.org/wiki/bezouts-identity/

you dont have to insult me by saying i dont understand higher math proofs. i am familiar with proofs

[light flicker]

Sure

[native zenith]

this is bezouts identity

[light flicker]

And they they take bezouts identity and multiply it by k

[native zenith]

then you would get kax + kby = kd, not ax + by = kd

[light flicker]

Which is indeed what they get

But (ak) is an integer

So is (bk)

[native zenith]

no they didnt multiply by k, they just said its a necessary condition

i mean i guess it was obvious to them?

[light flicker]

They write d=ax' + by' for bezout's identity

[light flicker]

then the next line is

[native zenith]

what they are actually proving is , one sec

[light flicker]

kd = (ak)x' + (bk)y'

this is multiplication by k

[native zenith]

that was a proof for the converse

this is the statement they are proving

" ax+by=z has an integer solution x,y,z if and only if z is a multiple of d=gcd(a,b)."

its an iff statement

[light flicker]

Correct

Which is why they talk about necessary and sufficient conditions

[native zenith]

so the necessary statement would be, "if z is a multiple of gcd(a,b) , then ax + by = z has an integer solution", do you agree

by the way, brilliant.org is supposed to be for math beginners

[light flicker]

No that is the sufficient condition

[native zenith]

right

so the necessary statement would be ' if ax + by = z has a solution, then z is a multiple of gcd(a,b) '

[light flicker]

Yes

[native zenith]

for integers x ,y,z

well i dont see how 'we already know that'

since thats not bezouts identity

wait, let me think

no i dont see how we already know that

the only thing given was bezouts identity

[light flicker]

going back to what I said at the very beginning

gcd(a,b) divides a and b

[native zenith]

yes

[light flicker]

so what about ax + by

[native zenith]

it divides ax + by

[light flicker]

what divides ax + by

[native zenith]

gcd(a,b)

[light flicker]

and so you're done

if ax + by = z has a solution, then z is a multiple of gcd(a,b)

[native zenith]

huh?

[light flicker]

gcd(a,b) divides ax + by like you said

[native zenith]

that doesnt prove that if ax + by = z has a solution, then z is a multiple of gcd(a,b)

[light flicker]

gcd(a,b) divides ax + by yes?

[native zenith]

you proved that gcd(a,b) divides ax + by

yes

[light flicker]

so gcd(a,b) divides z

since z = ax + by

[stuck lintel]

if it divides the left side then it divides the right side lol

[native zenith]

and this is true because ax / gcd(a,b) + by /gcd(a,b) is an integer

ah

[north pagoda]

its true because ax+by and z are literally the same number

[native zenith]

ok wait

right by substitution

[light flicker]

idk you guys handle this I have a party to be at

[native zenith]

so if gcd(a,b) divides z , then z is a multiple of gcd(a,b)

[north pagoda]

yes

thats the definition of "divides"

[stuck lintel]

lol have fun zoph

[native zenith]

this is not obvious at all. how can someone in high school know this

brilliant.org is targeted towards high school students

this article is written by an indian professor who is sloppy af

[north pagoda]

this is... the standard definition

idk what to say