elementary-number-theory

[supple acorn]

we are trying to prove that "p satisfies b) => p is prime" is false, correct?

[red yacht]

"b) => p is prime" is what I am trying to prove is false

[supple acorn]

yes

is there a distinction

[red yacht]

unsure

[supple acorn]

b) on its own does not mean anything if you do not specify the value of p

[red yacht]

take p = 6 then what

d in {2,3,6}

[supple acorn]

now we need to show that 6 satisfies b) but 6 is not prime

6 is clearly not prime, we agree there i assume

[red yacht]

ye

is composite

[supple acorn]

to show 6 satisfies b), we need to prove
∀d ∈ N, (d > 1 ∧ d | 6) => d^2 ∤ 6

here i have replaced the instances of p with 6

so now we need to prove
(d > 1 ∧ d | 6) => d^2 ∤ 6
for all d

[red yacht]

2 > 1 , 2 | 6 => 4 does not divide 6

[supple acorn]

we can't just choose one d in particular

[supple acorn]

yea

[red yacht]

3 > 1 , 3 | 6 => 9 does not divide 6

6 > 1 , 6 | 6 => 36 does not divide 6

[supple acorn]

oops i copied it down wrong but

i fixed it

[red yacht]

so p = 6 satisfies b)

[supple acorn]

yea exactly

ok i will admit i need to sleep rn, but, hopefully walking through an example helps

[red yacht]

is like 2pm

wdym sleep

@supple acorn

[supple acorn]

i live in California so it is 10 am for me

[red yacht]

isnt that morning?

[supple acorn]

anyway i did sleep last night but i am constantly drowsy

i think i am just fucked up

[red yacht]

same

[eager silo]

For all d phi(d) => d = specific value
Can you explain pls?

[red yacht]

what?

[eager silo]

nvm

Ignore me

Pretend I never made that message

I'm dumb

Treat it like a ghost ping

[red yacht]

how can I prove euclids lemma?

[lilac bronze]

bezout's identity

[wooden glen]

Googling "Euclid's lemma" should lead you to a lot of proofs to choose from.

[red yacht]

take a prime p such that p | ab
there's two possible cases either p | a or p does not divide a

case p | a then p | ab because p | a <=> a = p.k then ab = p.k.b = p.(kb) = p.q

case p does not divide a then
a does not have a prime p in his prime factorization, and so p and a are coprime, so gcd(a,p) = 1 and thus aX + pY = 1 has a solution (bezouts) @lilac bronze @wooden glen

[wooden glen]

Euclid's lemma is usually a step on the way to proving that prime factorizations are unique, so unless you have a different proof of that, depending on it would be circular.

[lilac bronze]

I think using prime factorisation here is cheating

[red yacht]

what do you recommend

[west glade]

the gcd of a and p would be a divisor of p...

[red yacht]

right, gcd(a,p) | a and gcd(a,p) | p

what can I do with this tho?

[west glade]

p is a prime

[red yacht]

so gcd(a,p) = 1 or gcd(a,p) = p

suppose gcd(a,p) = p then p | a

and the assumption was that p does not divide a so this is not possible

it must be the case that a and p are coprime @west glade

if both a and p are coprime then there exists some x,y in Z such that aX + pY = 1

[west glade]

ok good

you havent used b so far

how could you get b into this equation

[red yacht]

bax + bpy = b

but got stuck

[west glade]

you are given p|ab

ab appears in this equality

you want p|b

[red yacht]

bax + bpy = b
<=> bpy = b (mod p)

<=> 0 = b (mod p)

wait, I actually did it?

<=> p | b

[mortal osprey]

yep, you can also do it without mod p

p | bax (because p | ab)
p | bpy
therefore p | bax + bpy

[unique cypress]

yes this is correct

Notice how the fact that you could use Bezout's identity ensured you can do this

[red yacht]

ye its from the lemma and the coprimality condition

it is guaranteed by bezouts that solutions exists

[unique cypress]

Yeah it's a thing unique to the structure of Z and similar rings

It's not true in general

[ionic latch]

non-euclidean NT 🥸

[red yacht]

care to elaborate

[unique cypress]

Yeah these are called Bezout domains for obvious reasons. Any PID is one

Bezout just says the sum of two principal ideals is also principal

[dreamy sundial]

Anyone got a good intro book recommendation for number theory

I just got a job working for a number theorist don’t tell anyone but I literally don’t know any number theory

[carmine tide]

Have you tried looking in #book-recommendations? For example, here.

[dreamy sundial]

Beautiful thank you

Maybe I won’t get fired

[carmine tide]

[orchid seal]

Is this for elementary children

I do not have permission to talk in advance number theory

[red yacht]

Gcd(cx,y) = gcd(x,y) if gcd(c,y) = 1? how to prove

[unique cypress]

unpack definitions

[abstract ferry]

use bezout identity on gcd(c,y)=1

[red yacht]

ac + by = 1

[abstract ferry]

and reminder gcd(p,q)=gcd(r,s) iff common divisors of p,q divides r,s and similarly for r,s

how will you use it?

[red yacht]

no idea

[unique cypress]

take g = (x,y) and d = (cx,y). Unpack definitions to show g|d and d|g

[red yacht]

so divisibility is antisymmetric

or what

g | d, d|g => d = g

[unique cypress]

yes

of course both g,d here are positive otherwise this is true up to a sign change right

[red yacht]

how

[red yacht]

gcd is always posiruve

[rugged locust]

the gcd of a and b is the terminal cone over the diagram {a,b} in the category of Z under divisibility, easy

[unique cypress]

one way is easy

the other needs a bit more work

[abstract ferry]

mamma mia

[unique cypress]

is it obvious why g|d is the easy direction?

[red yacht]

take d = (x : y) => d | x , d | y => d | cx , d | y => d | (cx : y)

[unique cypress]

good

[red yacht]

d | x => d | cx because
x = d.k => cx = d.k.c => cx = d.(k.c) => d | cx

what about proving (cx: y) | (x : y)

[unique cypress]

for this you need the condition they provided

namely (c,y) = 1

[red yacht]

ac + by = 1

[unique cypress]

right

notice that you already have d | y so if you show d|x then you win

[red yacht]

acx + xby = x

[unique cypress]

mhm

[red yacht]

because d = (cx,y) then d | cx , d | y
acx + xby = x
acx = 0 (mod d) because d | cx
xby = 0 (mod d) because d | y
we get x = 0 (mod d) <=> d | x

so d | (x,y) and d = (cx, y) so (cx, y) | (x,y)

holy typo

[unique cypress]

yeah that's it (minus the typo)

[red yacht]

I see and since divisibility is transitive then gcd(cx,y) = gcd(x,y) if gcd(c,y) = 1

holy typo

not transitive, antisymmetric

I appreciate the help

[red yacht]

if I know gcd(x,y) = 1 how do I show that gcd(x^4, y^3) = 1

[dusty dragon]

hint: repeatedly use the result: if gcd(a, b) = 1 and gcd(a, c) = 1, then gcd(a, bc) = 1

[red yacht]

gcd(x,y) = 1 => gcd(x^3, y^3) = 1
gcd(x^4, y^3) = gcd(cx^3, y^3) with c = x and gcd(c,y^3) = 1

now since gcd(x,y) = 1 => gcd(x,cy) take c = y with gcd(x,c) = 1 then gcd(x,y) = 1 => gcd(x,cy) = 1 with gcd(x,c) = 1 and c = y, now this means gcd(x,y) = 1 => gcd(x,y^2) = 1
since gcd(x,y^2) = 1 then if gcd(c,x) = 1 with c = y we get that gcd(x,y^2) = 1 and gcd(c,x) = 1 with c = y => gcd(x,y^3) = 1

now coming back to gcd(cx^3, y^3) with c = x and knowing that gcd(x,y^3) = gcd(c,y^3) = 1 we get that gcd(x^4, y^3) = gcd(x^3, y^3) = 1

[red yacht]

how do you prove that if gcd(x,y) = 1 then gcd(x^m, y ^n) = 1

[dusty dragon]

gcd(x, y) = 1 => gcd(x, y^n) = 1 by repeatedly applying the rule. Then gcd(x, y^n) = 1 => gcd(x^m, y^n) = 1 by repeatedly applying the rule again

[red yacht]

are you using induction?

[dusty dragon]

you basically have gcd(x, y) = 1 and gcd(x, y) = 1 so using this with b = y and c = y, you get gcd(x, y^2) = 1 and then you can use induction over n and then induction over m

[minor musk]

If m,n be any two distinct odd primes then \ $\left(\frac{m}{n}\right) \left(\frac{n}{m}\right) \equiv (-1)^\frac{(m-1)(n-1)}{4}$

And NOT BY LATTICE RECTANGLE way

[sterile pumice]

TᖇᗩᑎᔕᑭᗩᖇEᑎT ᔕᕼᗩᗪOᗯ

[minor musk]

<@&286206848099549185>

[tacit current]

Well have you tried posting it?

in a help channel I mean?

its not good practise to ping helpers HERE

#❓how-to-get-help

if you're new.

[minor musk]

I usually post in the specific channel related to my course

[minor musk]

Ok

[pastel robin]

what's the reason i got summoned here

[tacit current]

Someone decided to ping helpers.

[ionic latch]

Isn't this from the definition of the legendre symbol

[wooden glen]

No, that is quadratic reciprocity. It takes significantly more than the definition of the symbol to prove it.

[ionic latch]

oh that's what I meant probably

I remember proving the (-1)^p-1/2 result from back in ENT and thought that that was it 😂

[supple tide]

theorizes

[midnight cloak]

theorizes with greater intensity, as to outshine Cat Enthusiast's theorizing

[sterile pumice]

Renato

[red yacht]

how do I prove this?

related: https://math.stackexchange.com/questions/12065/the-product-of-n-consecutive-integers-is-divisible-by-n-factorial

[tall arch]

Consider v2(2n choose n) = v2((2n)!) - 2*v2(n!) and use legendre to simply v_p(n!)

[red yacht]

wtf does that mean

did you saw the link I sent

[tall arch]

v_2(x) for x in Z+ is the largest positive integer k such that 2^k | x

[red yacht]

@tall arch

[tall arch]

im answering for 6ii)

not the first one

[red yacht]

can you help with i)

I am not even in II)

[tall arch]

what help would you like that's like

not alr in the math stack exchange post

@red yacht

[red yacht]

help please

[tall arch]

the answer is alr in the stack exchange post

[red yacht]

care to elaborate

[tall arch]

wdym

there's not much to elaborate

what would you like in an expalnation that is not already in the link that you just sent

cuz the link you just sent contains the answer to 6i

[red yacht]

how

[tall arch]

https://math.stackexchange.com/questions/12065/the-product-of-n-consecutive-integers-is-divisible-by-n-factorial

this is the answer

question 6i that you asked

is in that math stack exchange thread

the exact same questino

[red yacht]

how?

[tall arch]

what do you mean how

this is the question asked in the link that you sent: "The product of n consecutive integers is divisible by n factorial"

this is identical

to the question that you are trying to solve

just read through the link that you sent

adn you will have your answer

unless you just want hints for the problem?

[red yacht]

can u help with 6i) or not

[tall arch]

i can try sure

one way is to use binomial coefficients to show that result

or you can do induction

using k! | [x(x+1)....(x+k-1)] to show that k! | [(x+1)(x+2)...(x+k)]

with base case k!|(1x2x...xk)

[red yacht]

what

[tall arch]

do you know what induction is?

[red yacht]

what about it

[tall arch]

you. can try to use induction

to solve the problem

[red yacht]

it is not mentioned to use induction in the mse post

[tall arch]

there's multiple methods to solve a problem

[red yacht]

whats the easiest

[tall arch]

probably binomial coefficients

the solution is in the mse post

[red yacht]

can u explain

[tall arch]

you have that (n choose k) is a positive integer for all n≥k right?

[red yacht]

how

[tall arch]

do you understand what a binomial is

and what the choose function is?

what is means to choose k objects out of n objects (where order doesn't matter)

[red yacht]

yes

[tall arch]

if you know that, you know that n choose k must always be a posotive integer

since there are an integer number of ways to choose k objects from n objects

[red yacht]

cant it be 0

[tall arch]

only for like (0 choose 0)

it can be 0

otherwise its a postive integer

acc no

0 choose 0 is euqla to 1

it can never be 0

[red yacht]

what do I do now then?

[tall arch]

you have that (n choose k) = n!/(k!*(n-k)!) = n(n-1)...(n-k+1)/k! which must be an integer

thus, the product of the k consecutive integers n, n-1, ..., n-k+1 is divisible by k!

[red yacht]

you have that (n choose k) = n!/(k!*(n-k)!) = n(n-1)...(n-k+1)/k!
how?

[red yacht]

simplest way is using induction and using that the product of i from 1 to n is equal to n!

then prove 1 divides 1!

then assume p(n) holds

and then we get the product from 1 to n+1 of i

[tall arch]

why are you asking here if the mse has all the asnwers

[red yacht]

I am saying the answer in mse isnt the simplest to understand

I have a simpler proof, if you know that n! = product of 1 to n of i

[sterile pumice]

Renato

[red yacht]

if we take this for granted the proof is very simple actually @tall arch

[tall arch]

what?

[tall arch]

sure i guess but binomial proof is also easy if u know binomial coeffs

[red yacht]

care to elaborate?

[red yacht]

If you use the definition that $n!$ is equal to the product from 1 to $n$ of $i$, then prove the base case—that is, prove that $1$ divides $1!$. Next, assume $P(n)$ and demonstrate that $P(n+1)$ holds, meaning that the product from 1 to $n+1$ of $i$ divides $(n+1)!$.

The product from 1 to $(n+1)$ of $i$ is equal to $(n+1)$ multiplied by the product from 1 to $n$ of $i$, and $(n+1)! = n! \times (n+1)$. Then, use the property that if $x \mid y$, then $xc \mid yc$, because $x \mid y \implies y = xk$, and if you multiply by $c$ on both sides, $cy = cxk \implies cy = k(xc)$, and therefore $xc \mid yc$. Thus, $P(n) \implies P(n+1)$.

[sterile pumice]

Renato

[tall arch]

this only proves that hte pfroduct of the first k numbers is divisible by k!

you have to prove this for any set of consectuive integers

not just the FIRST k integers from 1,2,..., k

[red yacht]

wdym?

no

the question says, PROVE THAT THE PRODUCT of n CONSECUTIVE NATURAL NUMBERS IS DIVISIBLE BY n!

[tall arch]

yeah

ur proof only shows that the product of 1,2, .., n is disible by n!

it doesn't say anytiung sbout products such as k, k+1, ..k+n-1 for k≠1

[red yacht]

say for example

2 , 3, ..., n + 1 is the n consectuive numbers, but we want to prove this is divisible by n!

dont we run into a contradiction because the product 2 . 3 ... n + 1 is larger than n!?

@tall arch

[wooden glen]

You're confusing "is divisible by" with "divides" I think.

[red yacht]

care to elaborate?

[wooden glen]

35 is divisible by 7.

[upbeat salmon]

Why would the product being larger than n! contradict it being divisible by n!

[wooden glen]

7 divides 35.

[red yacht]

I dont understand your point @tall arch

[tall arch]

can somewhere read over @red yacht proof to make sure im not going crazy

but like

[carmine tide]

https://tenor.com/view/panda-roll-back-roll-cute-animals-gif-5302560

[tall arch]

ur only proving that n! | 1x2x3...xn

not that the product of any n consectuive integers is divisible by n!

empahssis on ANY

[wooden glen]

I think you're not going crazy -- it looks like it just proves that n! divides n!, by induction on n.

[tall arch]

yeah

[wooden glen]

Perhaps emphasize it as "every" since "any" might be a bit confusing in English (consider e.g. "is any even number a prime?" to which one could answer either "yes, namely 2" or "no, because 4 is not prime", depending on how one parses the sentence).

[tall arch]

i guess so yeah

[red yacht]

can someone help

[wooden glen]

Vivdax made an honest attempt.

[red yacht]

did he

[tall arch]

ts js ragebait 💔 💔

[red yacht]

I mean I get that my proof sucks but you couldve help me more aswell

[tall arch]

i tried explaining

that ur proof only showed a very specific subcase of the general proof

[red yacht]

I mean I get that my proof sucks

what I dont understand is how you prove the general case

[tall arch]

i showed one way with binomial coefficients

[red yacht]

how?

[tall arch]

(n choose k) = n!/(k! * (n-k)!) = (1x2x3...xn)/(1x2x...xk * 1x2x...x(n-k)) = (n-k+1) x (n-k+2) x ... x n / (1x2x3x...xn) = (n-k+1)(n-k+2)...(n)/k!

(n-k+1), (n-k+2), ..., (n-1), (n) are k consectuive nubmers

and they are divisible by k!

ssince binomial coeffs are always integers

[red yacht]

how did the third equality happen

@tall arch

[tall arch]

its because (1x2x3...xn) = (1x2x3x...x(n-k) x (n-k+1) x(n-k+2) x ... x (n-1) xn)

[magic isle]

could anyone explain the calculation here?

I want to find 3-ary expansion of 24/17.

If it wasn't a fraction, i would just do repeated long division, for example $14=43+2=13^2+1*3+2$ so $14_{10}=112_{3}$

[sterile pumice]

Former Rank 7 LLORT AJNIN

[red yacht]

how

[tall arch]

by like basic multiplication properties?

i genuinely don't know what else to say

[red yacht]

this is what I have

[unique cypress]

What's the problem you're trying to solve?

[red yacht]

.

[unique cypress]

Which part?

ii)

[red yacht]

i

@unique cypress

[unique cypress]

yes i was writing out the problem

[red yacht]

care to elaborate

[unique cypress]

okay here's what I'm thinking

can you rewrite "the product of n consecutive natural numbers" in terms of factorials?

[red yacht]

no

[unique cypress]

well the factorial n! starts from 1 and ends with n right? Here we have k(k+1)...(k+n-1)
This almost looks like a factorial but it's missing the beginning

[red yacht]

how?

[unique cypress]

okay let's take (k+n-1)!. This is not our product obviously but what do you need to divide by to get what we want?

[red yacht]

n!

[unique cypress]

not quite

[red yacht]

who tf knows

k + 1 , k + 2 , k + 3 , k + 4 , k + 5 , k + 6 . . . , k + n - 1

[unique cypress]

notice that (k+n-1)! is 1x2x3x...(k-1)x**(k)(k+1)...(k+n-1)**

[red yacht]

what

[unique cypress]

just by definition lol

[red yacht]

why are you grabbing k + n - 1

why not k + n

why not k

why not n

why not n - 1

why not k + n + 1

[unique cypress]

okay from k to k+n-1, how many integers are there?

[red yacht]

k + n - 1 + k + 1

(k + n - 1) - (k) + 1

n integers

@unique cypress

[unique cypress]

right

that's exactly what we want

[red yacht]

what is k

[unique cypress]

k is any natural number

[red yacht]

what is n

[unique cypress]

"n consecutive natural numbers" means k,k+1,k+2,...,k+n-1

[unique cypress]

also a natural number

[red yacht]

from here how do I start the proof

[unique cypress]

okay you want the product right so you take these ans multiply them

the end goal is to show n! | this product

[red yacht]

how do I do that

[unique cypress]

.

[red yacht]

how did you figured this has n consecutive terms

[unique cypress]

??

[red yacht]

from k to k + n - 1

(k + n - 1) - (k) + 1

[unique cypress]

I didn't. You did

[unique cypress]

Here

anyways what I'm trying to get into here is trying to somehow get the binomial coefficient

force both n! and the product to appear

[red yacht]

so k - 1! but multiplied with n conductive terms

[unique cypress]

yes that's what you need to divide by correct

[red yacht]

how

[unique cypress]

?

look in the formula

We want to get rid of 1x2x3...x(k-1)

well this is just (k-1)!

[red yacht]

yes

[unique cypress]

awesome so our product = (k+n-1)!/(k-1)!

so far so good?

[red yacht]

thats prod k + i with i in 0 and betweenn - 1

[unique cypress]

0 to n-1 correct

[red yacht]

what then

[unique cypress]

well we want n! to appear right

[red yacht]

what do I do

[unique cypress]

we are saying it is divisible by this product

how about we add it to the denominator?

[red yacht]

how

[unique cypress]

well cuz this will make it so that n! is divisible by the product

but we are not done yet

because we don't know if (k+n-1)!/(n! (k-1)!) is an integer

But I claim we do

why?

[red yacht]

because Binomial k + n - 1 , n is int

[unique cypress]

yes exactly

So really this question just comes directly from looking at Binomial(k+n-1,n) and we know it's an integer so we're done

[red yacht]

how

[unique cypress]

wdym how

[red yacht]

can we proof everything in detail

because i got lost a little bit

[unique cypress]

go over the details yourself

start with Binomial(k+n-1,n) then reason your way out why this implies n! is divisible by the product

[red yacht]

why the Binomial

this seems out of the blue

@unique cypress

[unique cypress]

I agree it seems out of the blue

[red yacht]

from k + n - 1 you are chopsing n

[unique cypress]

But that's kinda the point

[red yacht]

i appreciate it

ty for the help

@unique cypress

[unique cypress]

You're welcome

[red yacht]

i finally get it

[tall arch]

(m+1), (m+2), ..., (m+n) are n consecutive integers. Their product is divisible by n!, since if you divide the product of these numbers by n!, you get (n+m choose n) which must be an integer. Since the product divided by n! is an integer, by definition, the product is divisible by n!

[wide snow]

That works if you've proved (probably by induction) the formula for n choose k, but otherwise that's going to be circular in a lot of treatments

(I agree that's the way it should be done in principle)

[red yacht]

we can prove (n k) = n! / (n-k)! x k! using strong induction and assuming (n+1 k) = (n k-1) + (n k) , but is there any way without it

[wide snow]

I was thinking about how 5 divides any product of five consecutive numbers, because one of them must be a multiple of 5

So that kind of reasoning in a structured way - problem is when you have, say, 5 and 10 as part of n!, you need to be a bit more careful that you're not overcounting factors

Morally, that's why n! divides any product of n consecutive numbers. I think writing the proof might be a little annoying

[red yacht]

how

[wide snow]

Any five consecutive numbers have all possible remainders when you divide by 5

Remainders are multiplicative

Since one of them is zero, their product is 0

Modular arithmetic to the rescue :D

[red yacht]

ah I see
the remainders under mod 5 are 0 1 2 3 4
if you have x or x + 1, or x + 2, x + 3, x + 4 one of them are guaranteed to be 0 under mod 5

[red yacht]

yes

[red yacht]

yes

[red yacht]

care to elaborate

[wide snow]

If n = a (mod 5) and m = b (mod 5), then nm = ab (mod 5)

[red yacht]

yes

ah I see that's what you meant

[red yacht]

however we also need to one of them be 0 under mod 4

same for 0 mod 3, 0 mod 2, 0 mod 1

[red yacht]

care to elaborate

[wide snow]

Do that reasoning for all k <= n

[red yacht]

the problem is that there's definitely going to be some factors that are divisible by other factors

[wide snow]

Mmhm!

[red yacht]

how? can you help me with the induction

[wide snow]

It's a little annoying - I'd go prime by prime

For every prime p and every e≥1, if p^e | n!, then p^e | the product of n consecutive numbers​

That way you avoid weird factor overlaps

[red yacht]

why prime

[tall arch]

Because primes are “building blocks” of the positive integers

[red yacht]

so the product of consecutive integers have a prime factorization

it is sufficient to show that forall x >= 1 that p^x | n! then p^x the product of n consecutive integers

[modest coral]

how would you solve t^15 + 1 = 0 (mod 5) ?

[wide snow]

The mod is small enough that brute force seems feasible

Also whenever you see an exponent bigger than p, you should hit it with Fermat’s Little Theorem

[modest coral]

thanks

[tall arch]

t=0 (mod 5) fails, so t^4 = 1 (mod 5) for all t s..t 5 doesn't divide into t. Thus, t^15 + 1 = 1/t + 1, so 1/t + 1= 0 (mod 5) --> 1/t = -1 --> t = -1 = 4(mod 5)

note that most of the above operations could be done without issues since we are working in the multiplicative ring Z*, which consists of the set of all positive itnegers less than x that are relatively prime to x

[wide snow]

Can also just shrink to t^3 = 1 4 via FLT, which is far easier to solve by inspection

[wide snow]

Not just a ring, a field! Since 5 is prime

[red yacht]

t^3 = 4, no?

maybe thats what you meant(?

[wide snow]

t^5 = t, so t^15 = (t^5)^3 = t^3

[red yacht]

yes thats little fermat

[wide snow]

OH yes 4

I lost track of where the = was

[red yacht]

yeah after t^3 = 4 (mod 5) the best we can do is check the 4 remainders of t (mod 5)

either that or do t^3 + 1 = 0 (mod 5) and then notice t = -1 is a root and divide this polynomial by (t + 1)

you get a quadratic polynomial, then use the quadratic formula and see if the determinant is greater or equal to 0, if its not then theres no more solutions, either that or do a table with the posibles remainders under mod 5

[tall arch]

you could rewrite t^3 as 1/t (mod 5) since t^4 = 1 (mod 5)

[red yacht]

care to elaborate?

[tall arch]

t^4 = 1 (mod 5) by fermat's little theorem

divide both sides by t

t^4/t = 1/t (mod 5) --> t^3 = 1/t (mod 5), so if t^3 = 4 (mod 5) and t^3 = 1/t (mod 5) then 1/t = 4 (mod 5)

[red yacht]

how do you know 1/t in Z

[tall arch]

its in the ring Z/5Z

[modest coral]

1/t is the multiplicative inverse mod 5

[tall arch]

yeah

probably should've defined that

t^(-1)

[modest coral]

the number that you can multiply by t such that the product is congruent to 1 mod 5

[red yacht]

the inverse exists if and only if t and 5 are coprime

[modest coral]

yeah

[red yacht]

how did you guys proved that t and 5 are coprime?

[modest coral]

check that t = 0 is not a solution to t^15 + 1 = 0 (mod 5)

[red yacht]

how does that prove anything

if 5 | t then 5 | t^15

[kindred moss]

5 is congruent to 0 mod 5

modulo 5, there are 5 equivalence classes, and we can think of modular arithmetic as arithmetic between these equivalence classes. the only class that doesn't have an inverse is the class that represents 0

[red yacht]

sure

[red yacht]

this is fancy way of saying there's just 4 possible remainders under mod 5. However the classes are sets, pairwise disjoint sets strictly speaking, how do you plan on doing arithmetic on sets? or you mean doing arithmetic with the representatives of each equivalence class?

again, representative of an equivalence class is just a fancy word for an element from the equivalence class, two representatives of same equivalence class are congruent under a equivalence relation

congruent no, more like. equivalent under a equivalence relation would be more accurately said

[red yacht]

the only class that doesnt have an inverse is the one of remainders 0 under mod 5, because then we dont have coprimality if 5 divides each representative from the equivalence class

where is this Mambo-Jambo of equivalence classes coming from?

[tall arch]

Snowflake mentioned equivalence classes because u were confused at how showing a claim for t=0 applies to all multiples of 5

[red yacht]

how do you know the inverse of t under mod 5 exist

did you managed to prove that t and 5 are coprime

[red yacht]

we just stablished that the inverse doesn't exist in the case that t = 0 (mod 5) and it does exist in any other case

[kindred moss]

the point is that each element within an equivalence class behaves the same under the arithmetic operations. you can verify this, and this is why we can identify each class of numbers as 1 object. you should really think of modular arithmetic as arithmetic on a finite set, where each element in this set is one of the equivalence classes of integers

the inverse does not exist for all numbers congruent to 0 mod 5

and it does exist for all numbers not congruent to 0 mod 5

the idea is that the set S of multiples of 5 is a two-sided ideal of the integers. the details of this aren't too important, but we can describe cosets of S as k+S, where k+S = {k + s : s in S}, basically shifting every element in S by k.

we can then define arithmetic between cosets as (k+S) + (h+S) = (k + h)+S. This is well-defined because S is a two-sided ideal

similarly (k*S) * (h*S) = (k*h)S

[red yacht]

aren't we derailing? you lost me with the ideals and cosets machinery, we didn't covered ring theory in depth

this course is shared between various majors and specifically we covered equivalence classes and quotient sets and basic notions of some cyclic groups and basic notion of rings, but that's about it

[kindred moss]

we're just obtaining a quotient set that respects the same arithmetic relationships as the original set

[red yacht]

the quotient set is made out of sets (the pairwise disjoint equivalence classes)

the original set is not made out of sets

[red yacht]

I still don't understand the correlation between our problem at hand XD

[kindred moss]

the union of the elements in each quotient set forms the original set

okay i dont think you're understanding so it's fine

the point is that if a number is 0 mod 5 then it has no inverse, and if a number is not 0 mod 5 then it has an inverse

[red yacht]

the union of the equivalence classes form the quotient set

[kindred moss]

we don't need to check individual numbers because all numbers that are 0 mod 5 will have the same properties mod 5

[red yacht]

yeah

[kindred moss]

you only have to check 0,1,2,3,4 mod 5 because of this, and that's what they meant when they said 0 doesn't have an inverse mod 5 and everything else does

you can basically pretend 0,1,2,3,4 are the only numbers

we know t is not 0 because 0^15 = 0 which isnt -1 = 4 mod 5

so we know any solution t must have an inverse

[red yacht]

this is what axe is saying but

i guess that must be it

if 5 | t then t ^15 + 1 ≠ 0 (mod 5)

[red yacht]

yeah I guess that is a good way to put it

sorry for wasting everyones time

[mild pond]

hello i became interested in how the sum of two coprime numbers will not have any prime factors in common with summands. Ex: 30+7=37
2x3x5+7=37
The same can be said of the difference of two coprime numbers. My understanding of this situation goes like this:
Since the two numbers are coprime, I am not able to factor out a common prime factor from both numbers. That would mean the sum or difference of those coprime numbers will not be divisible by any of the prime factors from the two coprime numbers. Since 30=2x3x5 and 7=7 and those two numbers share no common prime factor, their sum cannot be divisible by 2,3,5 or 7.

That would mean if the prime factors of the two coprime numbers encompass 2 to the nth prime (densely, without a skipped prime number), the difference (or sum) of those two coprime numbers will have prime factors that are not {2,3,5,...nth prime}
Examples:
3^2 - 2^2 = 2 + 3 = 5
(2 x 5)-3 = 7
(5 x 11) - (2 x 3 x 7) = 13
(2 x 7 x 13) - (3 x 5 x 11) = 17

My question is can we somehow combine the finite set of prime numbers (sum or difference, probs difference) so that we can get the next immediate prime number? The combinations above are not the only ones, but I tried to use primes with the power of 1 since I find it cool.

Also as I was doing the computations, I realized that if the difference between the two coprime numbers happens to be less than the square of the largest prime factor, L, that number, P, must be prime.
ex: (2x5x7x11) - (3x13*17)=107<17^2 Which means 107 is prime. In this case, L=17, P=107.
This comes from the fact that to check if a number is prime or not, we can check if mod[P, for n<sqrt(P))]=0. If the mod is zero that means P is not prime. However, we know that P is not divisible by any prime numbers up to the largest prime since that is how we contructed P to be . So that means mod[P, for n<sqrt(P))]=/=0 and that P is prime since P<L^2

I have tried to get the next prime number 19 but I have not found the combination yet. I exhausted all the "power of 1" prime combination

Another question is: If we have a finite set of consecutive prime numbers starting with 2, {2,3,5,7,11,... and so on} can we partition those numbers so that the difference of product of the partitions is always 1?
Ex:
3-2=1
2x3-5=1
3x5-2x7=1
and so on

I think this is also neat in that we can interpret the meaning of 1 to be:
1=product(all the primes raised to the power of zero)

[quasi granite]

you might find this helpful: https://en.wikipedia.org/wiki/Coprime_integers#Generating_all_coprime_pairs

[hearty hornet]

It looks like you are trying to create something like a next prime / prime generator algorithm, based on the premise that two coprime numbers will have no prime factors in common with its summands. (I acknowledge you are editing the long post).
In other words, if gcd(a, b) = 1 and a + b = c, you claim that gcd(a, c) = 1 and gcd(b, c) = 1 (this takes a little thought but is correct).
You then are trying to get essentially "new" primes out of this function continuously.
I think if you appeal to something basic like Goldbach's conjecture, this is pretty doable. You prove some small cases, then just basically "add some primes" to get to the next one. But this conjecture itself is very hard, so I'm not sure the process you are describing is easy to deduce / possible to deduce for this reason.

oop lemme edit

[hearty hornet]

You'd need to specify what's going on with the sets here for me to understand exactly what you mean. For instance, are we allowed to repeat primes as powers? Are you forced to use every prime to get another set?

[mild pond]

Yes. Repeating primes as powers are allowed, but the prime numbers used to generate the two co prime numbers lets say A and B must be so that all prime numbers up to the largest prime be used. And that A and B do not share a common prime number (since that cannot generate a prime)

So if we have a finite set of consecutive primes starting with 2, P={2,3,5,...,L}, then A is a subset of P with repetitions allowed. Ex A={2,2,3,...}. Then B is a subet of P with prime numbers not contained in set A, with repetitions allowed. Now the number A=product of the elements in A and number B=product of the elements in B

[mild pond]

So if L is the nth prime number, can we have sets A and B so that we can get:
product(A)-product(B)= (n+1)th prime number
or
product(A)-product(B)=1

It would be interesting because that would mean the primes are dispersed in a way that allows consecutive primes to be partitioned into two groups and where the difference of the product of each group gives the next biggest prime or 1

[slate juniper]

The fact that

\begin{align*}D(m) \cross D(n) &\to D(mn) \
(x, y) &\mapsto xy
\end{align*}

is a bijection when $(m, n) = 1$ is such a nice and useful fact

[sterile pumice]

Neamesis

[slate juniper]

Where D(n) is the set of divisors of n

[red yacht]

is this correct?

[sterile pumice]

Renato

[red yacht]

the problem is that idk how to conclude

I didnt even used the conditions for a or b

oh wait

[carmine tide]

[red yacht]

yes

[red yacht]

is it possible to know beforehand if after diving a polynomial by another polynomial if the resultant polynomial will be in Z[X]

because if the resultant polynomial is in Q[X] then I cant use stuff like gauss lemma (rrt)

[wooden glen]

The most important case where you can be sure the results are in Z[X] is if both inputs are and the divisor is monic.

[red yacht]

care to elaborate?

[wooden glen]

In that case there's no reason for any of the intermediate coefficients produced during long division to be non-integers.

[tall arch]

Can’t you still use rrt by scaling all the coefficients by some factor k such that all the rational coefficients become integers?

[red yacht]

In the case of the greatest common divisor between two polynomials, let arg1 and arg2 be the arguments of the gcd where both are polynomials. It is possible to perform long division of arg1 by arg2, which then leaves you with $arg1 = arg2 \cdot Q(x) + r$, and then you can compute $\operatorname{gcd}(arg1, arg2) = \operatorname{gcd}(arg1 \bmod arg2, arg2) = \operatorname{gcd}(r, arg2)$, where $r$ is the remainder of the long division of arg1 by arg2.

[sterile pumice]

Renato

[supple tide]

can someone please explain to me why $$1^{\infty} = 1$$

[sterile pumice]

Cat Enthusiast

[carmine tide]

,w limit of (1+1/x)^x as x approaches infinity

[sterile pumice]

Results provided by WolframAlpha

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

Requested by civil_service_pigeon

[carmine tide]

[supple tide]

nuh uh

1/x -> 0 which yields 1^x and 1^infinity = 1

[tacit current]

I mean, $1^\infty$ is usually seen as an indeterminate form, not something that can be equated to one.

[sterile pumice]

Annie Maqionde

[supple tide]

one to the power of anything is 1 tho

[sweet orchid]

you're right that 1^(anything) is 1 provided that the 1 in the base is a constant 1. if that's what you're asking, then yeah, 1 multiplied by itself a shitfuck number of times is still 1. but if the base is NOT 1, merely a value approaching 1 as x grows, then it's a whole other story.

[supple tide]

the base is 1 in 1^infinity

[ionic latch]

Normally I take "anything" in such a context to mean a number, which infinity is not (hence the denomination as an indeterminate form)

[sweet orchid]

read the second sentence

[supple tide]

i dont get it

[sweet orchid]

if that is what you're asking, then yeah, 1 multiplied by itself a shitfuck number of times (as is the definition of exponentiation) is always gonna be 1.

though more accurately we don't write 1^inf = 1

we write $\lim_{x \to \infty} 1^x = 1$

[sterile pumice]

Hanako(x, y); ∂(fox)/∂x

[sweet orchid]

woops typo

[ionic latch]

Yes, since infinity itself isn't a number 💃

[sweet orchid]

we do not talk about the extended reals

[ionic latch]

that doesn't count

(I actuall don't really know how exponents work in stereographic projection)

[tacit current]

anything that is a number. 'infinity' is not a number; consider it to be a symbol.

[red yacht]

what does this have to do with ent

[ionic latch]

Exponentiation is very important to ent, probably

[midnight cloak]

It's not $\lim_{x \to \infty} 1^x$, it's $\lim_{x \to \infty} (\lim_{a \to 1^+} a)^x$

[midnight cloak]

If you want some intuition

Your base isn't constant

[midnight cloak]

This isn't correct as written, but the idea is the base approaches 1 and is not simply a constant 1

[kindred moss]

$\lim_{x \to \infty} f(x)^{g(x)}$ where $\lim_{x \to \infty} f(x) = 1$ and $\lim_{x \to \infty} g(x) = \infty$

[sterile pumice]

snowflake

[tawny rose]

https://tenor.com/view/bro-just-typing-shit-bro-just-typing-shit-gif-18336060238854257551

[red yacht]

again how is this related to ent

[supple tide]

whats ent

[kind marten]

elementary number theory

[slow birch]

Guys, what do you think of this problem set on Elementary Number Theory?

Almost all of these are standard results (like P16 on Zeckendorf)

P14 is troll (trivialized by AM-GM)

[tall arch]

p8 is just ||factoring using 3rd roots of unity|| i think, the problems look cool overall

[slow birch]

Yeah

[tall arch]

p11 looks similar to an old imo question

[sharp shadow]

Have you designed this?

[slow birch]

Its more of a group effort.
I designed Problems 1-8, Problems 11-13, and Problems 16.
I got other problems from suggestions of my friends

This was for our school math club.
The topic was Elementary Number Theory.

[heady plinth]

Is this like a take home thing? Cause first part of problem 12 would be brutal on a test, unless there are much simpler proofs than Euler's

[quasi granite]

dammit. was about to use FLT

for $x, y, z=1$ the base case holds for $n=3$ and $n=4$

[sterile pumice]

Gary

[quasi granite]

indeed, the identity $x^n+y^n=z^n$ has no solutions for all $x,y,z\in\mathbb{Z}^+$

[sterile pumice]

Gary

[quasi granite]

$x^n+y^n>z^n$ for all $x,y,z\in\mathbb{Z}^+$

[sterile pumice]

Gary

[quasi granite]

how would one prove it though without having had any knowledge of NT

[wide snow]

I mean that’s not true as quantified

Often these smaller Fermat cases proceed by factorization (possibly in another ring) or modular arithmetic

I don’t recall exactly how

[quasi granite]

i've had a very basic intro to rings. are we speaking of the ring like $\mathbb{Z}$

[sterile pumice]

Gary

[wide snow]

Yeah sometimes it’s helpful to pass to like Z[i] to factor certain expressions

Like x^4 + y^4 = (x+y)(x-y)(x^2+iy^2)

Or Z[sqrt(n)]

[sterile pumice]

Gary

Gary

[rugged locust]

thats just C

if y is allowed to be whatever complex number you want

if you want a+bi, set y = ix + -i (a+bi) so x + iy = a+bi

[quasi granite]

Complex numbers satisfy all of the axioms of a ring apparently:

Addition axioms:
Closure: (a+bi) + (c+di) is still a complex number
Associativity: (z₁ + z₂) + z₃ = z₁ + (z₂ + z₃)
Identity: 0 + 0i is the additive identity
Inverses: every z has an additive inverse −z
Commutativity: z₁ + z₂ = z₂ + z₁ (as you just noted)

Multiplication axioms:
Closure: (a+bi)(c+di) is still a complex number
Associativity: (z₁z₂)z₃ = z₁(z₂z₃)
Identity: 1 + 0i is the multiplicative identity

Distributivity:
z₁(z₂ + z₃) = z₁z₂ + z₁z₃

Since multiplication is also commutative and every nonzero element has a multiplicative inverse, ℂ is a field

this is going far deeper than i had expected for one question

[ionic latch]

Yes, because all fields are rings

You should look into abstract algebra if you are interested in how these structures build upon each other

[heady plinth]

There is an elementary proof by Euler for n = 3, n = 4 isnt that hard to do, you can prove the stronger result that x^4 + y^4 = z^2 has no solutions, by infinite descent, both proofs I know use that

Both proofs i know are by infinite descent i mean

[rain wren]

for problem 16 can we answer like this

{0,1} subset F
{1} subset Z+
trivial case 0+1=1
and 1+1=2 case where first 1 is 2nd term of fibonacci deries and second 1 is the 3rd term, thus legit
thus f in F\{0} implies f in Z+ therefore F\{0} subset Z+
proofing that there's a positive integer that cant be made of 2 fibonacci numbers of different term
4 not in F
thus any f in F\{0}
test for 12 -> 12 can't be made with fibonacci series
therefore disproven

unless you allow negative fibonacci world

[slow birch]

You use $Z[\omega]$ (the Eisenstein integers) for n = 3 case.
You use Method of Infinite Descent for n = 4 case.

It becomes simple that way.

[sterile pumice]

LemmaLover

[heady plinth]

Well I dont see how it can be arrived at in a test unless you have seen anything similar before

[heady plinth]

What did you even prove

[slow birch]

12 = 8 + 3 + 1

It is representable as a sum of distinct fibonacci numbers

(This is Zeckendorf theorem)

[slow birch]

It's more of a problem set that you are supposed to solve in a week.
Not like timed on a test

[heady plinth]

Fibonacci numbers form a complete sequence

You can wiki the criteria for a complete sequence

But its pretty straight forward, if a sequence contains 1 and obeys a bertrand postulate like inequality then it is complete

[heady plinth]

I see

Its pretty good in my opinion

Lot to learn from it

[slow birch]

I am surprised that nobody is talking about Problem 7. I feel this is harder than the rest. Same for Problem 9.
ALso, obviously Problem 13 and 15 are the hardest imo.

[heady plinth]

9

It seems the most interesting to me

How do you go about proving it?

I have seen something similar before, rayleigh smth smth

[slow birch]

Let me take my time to write a brief strategy

[heady plinth]

Sure, thanks

[slow birch]

Usually in problems like these, an inequality helps for preliminary investigations.
You need to show $2^k \leq n \sqrt{2} < 2^k + 1$ has an integer solution for all $k.$
That way, its floor would be $2^k.$

Now, like, dividing the inequality by $\sqrt{2},$ we have:
$$ \frac{2^k}{\sqrt{2}} \leq n < \frac{2^k + 1}{\sqrt{2}}$$

We are searching for integer values of $n$ in this range. What is the length of this range? Well, its $\frac{1}{\sqrt{2}}.$

So, if there is an integer in this range, only one would exist.

If there exists an integer here, then it must be $\left\lceil \frac{2^k}{\sqrt{2}} \right\rceil.$ If you let this be some $\tau,$ then:
$ n = \tau + \delta.$
Here, $\delta \in (0,1).$

Now, we proceed like so. Obviously, this is a brief sketch. This problem was not made by me. So, I am unsure. But, my experience dictates this approach.

[rain wren]

you can use 3 numbers?!

i thought we can only use 2

[sterile pumice]

LemmaLover

[slow birch]

I mean the question did not prohibit it

[rain wren]

eh...

[rain wren]

that sum of two fibonacci numbers can't reach all positive integers

which, isn't what the question asked turns out

[heady plinth]

Yeah, the theorem talks about representation by arbitrarily many Fibonacci numbers

[rain wren]

cos formerly i thought we can only use 2

[heady plinth]

A more interesting and somewhat more natural seeming (although it would be in principle the same thing) question would be: Prove that you can represent all naturals as a sum of distinct primes and/or 1

Using a number only once (obviously if you use 1 as many times as you want its trivial)

[heady plinth]

Looks good, but I suspect it won't be enough

[rain wren]

generalized goldbach conjecture

but instead of P starting point we have Pu{1}

[heady plinth]

Thats something different but it does seem like a cool theorem

[rain wren]

and endpoint is Z+ instead of 2Z+

[heady plinth]

Yeah, because only 1 can represent 1

I have never thought about it if we remove 1, can the primes represent Z -{1} alone

[rain wren]

suppose dummy set Y then P subset of Y

dummy set Y later should be the same as N so that it can be proven

[heady plinth]

Are you like

Grothendieck or something

[rain wren]

btw anyways set N should be the same as Z+ or Z+\{0}

[heady plinth]

This language confuses me so much

You need an extra fact

Do you know of Bertrand's Postulate

[rain wren]

i dont

[heady plinth]

Its a cool theorem, Erdos found his own proof when he was 19

[rain wren]

idk i just thought that for this thing

the "can we represent positive integers bigger than 1 with sum of distinct primes"

[heady plinth]

Either im not used to this language

[rain wren]

replying to this too btw

[rain wren]

this one, trivial cases:
prime numbers can be represented as sum of 1 prime number, which is itself

[heady plinth]

Fair enough

[rain wren]

now next step is to proof that there (are numbers)/(is a number) that can't be made out of sum of distinct primes

[heady plinth]

How about 4 😋

[rain wren]

yes

6 too

but not 10

3+7

[heady plinth]

They are small cases

Is there any such number greater than 10

[rain wren]

or, hear me out, an odd number that isnt sum of primes

[rain wren]

greater than 8 btw

which, doesnt do much

[heady plinth]

Is there one?

Im horrendouly bad at calculations

[rain wren]

perhaps we should make sets of pos integers that isn't sum of primes first,

4 and 6 are already inside

[rain wren]

call this A maybe?

[heady plinth]

Why make sets

Wanna bet

Im guessing

All of the numbers beyond a certain limit can be represented as a sum of distinct primes

[rain wren]

cos i think there's a bunch of pos. integers that can't be made with adding different primes, other than 4 and 6

anyways:
p not in A
p+2 not in A, p>=3

[heady plinth]

There is no integer which cannot be made with multiplying primes

[rain wren]

*adding

my bad

[heady plinth]

Actually

You want to see how I proved it when I came across it?

Or do you want to save it for yourself

[rain wren]

eh, show me ig

[heady plinth]

Sure!

First we need bertrands postulate

It says for any n>1 there is a prime between n and 2n

What we are going to use is that there is a prime between n and n/2 (this will be a rough sketch)

So the main idea is you give me any number

Say N

There exists a prime between N and N/2 by bertrands postulate (lets assume N isnt prime because in that case we are already done)

call that prime A, now N - A < N/2 as A > N/2

So there exists a different prime between N - A and (N - A)/2

Call that B, and repeat the procedure of subtracting the greatest prime less than the number

You will eventually reach the smallest prime that can be subtracted

Which can be, in the worst case, 2

[rain wren]

so if N=12 then
primes between 12 and 7 -> 7 and 11
12-7=5
primes between 5 and 2.5 -> just 3

like this?

[heady plinth]

Yep

The essence of the proof lies in the fact that you will ALWAYS be able to find a prime in these intervals

Which is guaranteed by Bertrand's postulate

Lets try something huge

927290191791001000189100

I asked Claude, ofc I'm not going to do it myself

927,290,191,791,001,000,189,100 = 927,290,191,791,001,000,189,091 + 7 + 2

How disappointing

[rain wren]

umm, how could we get from bertrand's postulate to any pos. integer (except 1, 4, and 6) can be made with summing different primes?

cos we know that prime a is/are between n/2 and n,

[heady plinth]

I don't know

Let me think

We'd have to change our procedure

Then it wont be as clean as it is now

[rain wren]

and btw this is where i somehow connect to goldbach conjecture, which states p1+p2 "can" access all evens (assumed right but no proof)

and for distinct p case, remove 4 and 6

[heady plinth]

Because if there is a number n and a prime is just 1 less than n, we cant subtract the greatest prime as we do in the procedure since then we'll get 1 in the representation

[rain wren]

let's say 156

cos 157 is prime

[heady plinth]

Opposite

159

[rain wren]

oh wait, prime is 1 less

[heady plinth]

159 is one greater than a prime

[rain wren]

should take 158

[heady plinth]

Lmfao

I cant believe i got

Addition wrong

Crazy

Anyways yeah we take 158

According to the procedure you just subtract the greatest prime

158 - 157 = 1

[rain wren]

158-157=1

[heady plinth]

Thus 158 = 157 + 1

[rain wren]

can be rewritten as 158 = smth + prime?

156+2?

then we break the 156 but can't use 2 somehow?

[heady plinth]

Clever, but the you have to guarantee that the prime will not appear in the representation of that something

Which is not easy to do

[heady plinth]

Thats the way yeah but how can you guarantee that you wont have to use 2

Perhaps looking at the number of ways in which a number may be represented as a sum of primes will help

If we can prove that we can represent a number (sufficiently large) in multiple ways using different primes we are done

But that sounds much harder

Im thinking of induction

[rain wren]

wait, i suddenly remembered the mcnuggets problem that numberphile suggests

that given boxes of 3, 9, and 20 (or i forgot) you can make any number of mcnuggets

[heady plinth]

Interesting name

[rain wren]

this but with prime numbers

[heady plinth]

Let me have a look at it

[rain wren]

oh nvm, this one allows reusal of numbers

which our problem doesn't

[heady plinth]

I see

Oh!

I see it now

It was simple

We do the same thing we did till now but use induction

Take any n

No, first see that it works for small values except 4 and 6

Lets assume it works upto N

(also suppose N is not 1 greater than a prime)

Then subtract the greatest prime from N, say A, then we have N - A, now notice that N - A can already be represented as a sum of distinct primes because of our supposition

And also note that N - A < A since A > N/2, so any prime in the representation of N - A is different from A

Therefore N can also be represented as a sum of distinct primes

Now we have to worry about N when N is one greater than a prime and when N - A = 4 or 6

Im tired, hit me up if you are interested to talk further

[rain wren]

hmm, try 325

then 325-317=8.
8 can be sum of distinct primes (3+5) so does 325

[rain wren]

i think we can reverse-craft N by using 4+A or 6+A instead

but yeah let's continue it one day

[rain wren]

to next readers: our topic was about this question with constraints:
m_i can only 0 or 1
p_i is the i-th prime number

wait
i think for
N=A+6
we can change it to
N=(A-2)+8
usable if A-2 is prime too
now worry for A-2 composite...

[heady plinth]

Hello

Back

[heady plinth]

Frustrating

Hecke, let me find a way to prove that there exist atleast two primes between n and n/2

Then the proof of this fact follows easily

[heady plinth]

I can't believe it, I'm still trying to get this, insane

[heady plinth]

So far I got that this doesn't help either

[heady plinth]

https://math.stackexchange.com/questions/1382663/prove-that-every-integer-n-geq-7-can-be-expressed-as-a-sum-of-distinct-primes

We were almost there

[rain wren]

which is the exact stopping point for the thread starter

p+4 and p+6 case

[heady plinth]

Yep

p + 1, I didn't think much about, since all three cases looked same to me and I was focusing mainly on 4 and 6

I must say it was much harder than I thought, though had we hit upon making the hypothesis stronger we would have gotten it

Regardless, its a somewhat beautiful theorem

Much more so than Zeckendorff's

What is surprising is that this was proven very recently it seems

I can't believe Gauss didn't notice it, maybe its not theoretically important enough

He didn't have Bertrand's Postulate but he did have the Prime number theorem, from which deducing Bertrand's is trivial

[magic rain]

I had an idea and wanted to know if it might interest you: I could post weekly elementary number theory challenges every Monday. Each problem would require a proof, and I would publish a full solution every Sunday

[ionic latch]

They do something similar with integrals in the calculus channel, sounds like it could be fun

[heady plinth]

How about

We do it like, an inquiry based approach to building number theory from the ground up

Motivated by history

[magic rain]

Perhaps, but it needs to be well thought out and will require a lot of work

[heady plinth]

True

Let me check if I can find a good book

[heady plinth]

Can't find anything, Genetic introduction to algebraic number theory by Harold M Edwards was what I had in mind but thats not exactly elementary number theory

https://pi.math.cornell.edu/~web401/steve.gauss17gon.pdf

But I still think something which is actually related to important results would be good

I doubt if that would work

[magic rain]

Maybe I have something, but it’s easier to solve than I thought. I should also mention that the original problem isn’t mine ,but I adapted it.

[quasi granite]

No. My most advanced maths course at uni got as far as that. Defs of fields, groups, rings.

[tall arch]

mobius inversion is so peak

dirichlet convolutions are also cool

[slow birch]

I second this.

Dirichlet convolutions are COOL

[slow birch]

Mobius Inversion is what saved the Arithmetic Functions chapter for me.

It was so fun afterwards.

[heady plinth]

Cool

I noticed now, cool username.

[heady plinth]

For a server with 200k people this place is real quiet.

[magic rain]

true

Perhaps we can change that

[heady plinth]

How? Weekly/daily problems is a good start.

[sterile pumice]

Renato

[red yacht]

how do I prove the hint?

[ionic latch]

For the first part of the hint, I think you can prove it both directly or by contrapositive, both ways rely on prime factorization (based on my scratchwork) [and the fact that every number has a prime divisor]

Or are you asking about the second part of the hint

[red yacht]

how to prove the first part of the hint directly

got stuck

p | a => a = pk
a = 3 (mod 4)
=> pk = 3 (mod 4)
=> pk - 3 = 0 (mod 4)
=> 4 | (pk - 3)
=> ???

[ionic latch]

=> pk = 3 (mod 4)
either p == 3 (mod 4) or p == something else mod 4
||show that p == 2 and p == 4 cases are contradictions||

||else p == 1 (mod 4)||
||so k == 3 (mod 4)||

But this is the original situation
If you're familiar with descent or have the well-ordering principle, that completes the proof

[red yacht]

i have the well ordered principle

[ionic latch]

Then you can use the fact that k < a to conclude 👌

this has become a contradiction proof

but that was because my direct scratchwork was incorrect

[red yacht]

well ordering principle is any non empty susbset contains a first element

[ionic latch]

Yes

Let a under the given conditions be the smallest natural such that a has a prime divisor with p == 3 mod 4

[red yacht]

pk = 3 (mod 4)
then what?

[ionic latch]

It essentially follows the way of the proof that every number has a prime divisor

just proving that 3 is prime mod 4

[red yacht]

coprime

[ionic latch]

since we are working mod 4, we only need to consider p in the equivalence classes 0,1,2,3

show what happens in each case

[red yacht]

so much casework is getting me confused

[red yacht]

p = 0 (mod 4) is literally impossible

[ionic latch]

right

[red yacht]

otherwise p is not prime

[ionic latch]

and how about p == 2

[red yacht]

unsure

ohhh

no, nothing

[ionic latch]

does 2k == 3 (mod 4) have a solution

[midnight cloak]

i dont know ask AI

[red yacht]

if k = 3 (mod 4) yes

[midnight cloak]

uh

i think the answer is no

[ionic latch]

if k == 3, then 2k = 6 == 2
Does 2 == 3 (mod 4) 🤔

[midnight cloak]

2k - 3 = 4m
2k - 4m = 3
2(k - 2m) = 3

lhs is always even

and last i checked 3 is not even

[ionic latch]

that is correct

[red yacht]

wait

[midnight cloak]

altanis is now a &number theorist

[ionic latch]

(This comes from the theorem that ax == b (mod m) has a solution iff (a:m) divides b)

[red yacht]

2 doesnt have a inverse under mod 4

[ionic latch]

Which is a consequence of bezout

[ionic latch]

correct

[red yacht]

ye

[ionic latch]

So p == 0 and p == 2 are impossible

If p == 3, we have our witness, so we just need to make sure we have a prime divisor in the case when p == 1 (do you see how I reached this conclusion)

[minor zealot]

n|0 is true right

[red yacht]

the idea is that 2k = 3 (mod 4) <=> k = 3 (mod 4)
but since 2 doesnt have an inverse under mod 4 is literally impossible

[midnight cloak]

hm?

division by zero is undefined

[ionic latch]

0|n is true

[heady plinth]

Wdym n|0 is true

[ionic latch]

No, the idea is that 2k = 3 (mod 4) is a contradiction, so that case is impossible

[minor zealot]

Wait sorry

[heady plinth]

0|n makes no sense? Or is that a joke?

[minor zealot]

Mix up

Idk

Which way is it

[heady plinth]

I mean you are right

[minor zealot]

All numbers divide 0 right

[heady plinth]

Yep

[minor zealot]

but 0 divided nothing

[heady plinth]

Yeah

[ionic latch]

oh I switched it sorry

[minor zealot]

I get confused too

[ionic latch]

i hate divides notation

[red yacht]

how do you prove it

[ionic latch]

[red yacht]

2k = 3 (mod 4)
2k + 4q = 3
4k + 8q = 6
4k + 8q = 0 (mod 4)
6 = 2 (mod 4)
0 ≠ 2 (mod 4)

[ionic latch]

sure

One could simply say 2k + 4q = 3 DNE by bezout as (2:4) = 2 does not divide 3

but yes, that works as well

[red yacht]

wait but did i used bezouts correctly?

[ionic latch]

I don't see where bezout was applied at all in your work

That's just algebra

[red yacht]

in the first step

2k = 3 (mod 4) <=> exists some q in Z such that 2k + 4q = 3

[ionic latch]

That is not bezout, that is the definition of congruence

(modular arithmetic)

[red yacht]

i see

[red yacht]

this is bezout then

[ionic latch]

Yes

A corollary to bezout says that all integer linear combinations of a and b can be written as n*(a:b)

[red yacht]

wdym

[red yacht]

yeah

[ionic latch]

What part is confusing

[red yacht]

witness and conclusion

[ionic latch]

We are intending to show that a has a prime divisor q with q == 3 (mod 4)

If p == 3 (mod 4) then we are done

p == 2 and p == 0 are impossible

The only thing left to show is that a has a prime divisor q with q == 3 (mod 4) in the case that p == 1 (mod 4)

[red yacht]

how do i do that

[ionic latch]

That is what the well ordering principle is for

[red yacht]

every non empty set has a first element

every non empty set of positive integers

[ionic latch]

oh this reduces back to factorization 😔 I was trying to avoid it

welp

Turns out WOP isn't needed then

If p == 1,
Then k == 3 (mod 4)

But k is a positive integer, so it has prime divisors

As we showed, the prime divisors of k can only be == 1 or == 3 (mod 4)
But if all of them are == 1 (mod 4), then k == 1 (mod 4)

Therefore, k must have a divisor q with q == 3 (mod 4)

See if you can follow that step by step

Probably the broad overview of what we have done will help here

1. We showed that for any positive integer congruent to 3 mod 4, its prime divisors can only be congruent to 1 or 3 mod 4
2. a == 3 (mod 4), so by (1), if p | a, then p == 1 or p == 3 (mod 4)
3. Since p | a, we can write a = pk for some positive integer k. Then if p == 1 (mod 4), k == 3 (mod 4)
4. k is a positive integer congruent to 3 mod 4, so all prime divisors of k are congruent to 1 or 3 (mod 4)
5. If all prime divisors of k are congruent to 1, we have a contradiction, because then k == 1 (mod 4)
6. Therefore, k must have at least one prime divisor q such that q == 3 (mod 4)
7. By extension, since k | a, q == 3 (mod 4) is a prime divisor of a

[red yacht]

the casework intensifies

[red yacht]

yeah and after 7 how do i get to 8)

[ionic latch]

what 8 👀

[ionic latch]

Ah you mean part 2 of the hint?

[red yacht]

no, i mean

q | a but how do i get that p | a

[ionic latch]

where do you see a | q

ah

q == 3 (mod 4)

[magic rain]

I think I've done this before; I used the quadratic residues with 9 and also the divisors of 2^n-1 when n is not equal to 2^m

[ionic latch]

q is a prime divisor of a that is congruent to 3 mod 4

therefore there exists a prime divisor congruent to 3 mod 4

Which was to be proven

[red yacht]

i see

[ionic latch]

I was thinking of quad residues but don't remember enough to apply them

[magic rain]

The goal was to find all positive integers n such that 2^n - 1 I a² + 9 (for some a)

I'll try to prove it again

[slow birch]

All powers of 2

$n = 2^k, k = 0, 1, \dots$

[sterile pumice]

LemmaLover

[ionic latch]

Looks like one of the problems @mystic spoke would bring

[kindred aurora]

$\text{Find the number of non-negative integer triplet(s) } (a,b,c) \text{such that } a^2b+b^2c+c^2a=3(abc)!$

[sterile pumice]

ItzAM

[kindred aurora]

Uff finally

[kindred aurora]

Is it 4? Guys help me to justify it

[red yacht]

k = 3 (mod 4) yes. But why do you say that his prime divisors are only congruent to 1 or 3 mod 4

[ionic latch]

Ah I forgot to write "by (1)"

It is because of (1)

We showed that having a prime divisor congruent to 0 or 2 is a contradiction if your original number is congruent to 3 👌

so 1 or 3 are the only options left

basically k is a mimic of a

So we can apply any results we proved about a

(and descent yields the contradiction)

You could theoretically just say the same things directly about a, but then you'd have to write the stuff you proved about the divisors in a separate lemma

Which tbh would be more clean than writing this all in a single proof

[hushed steeple]

guys did u know 1+1 is a bigger 1

[ionic latch]

Yes actually LosAngeles proved it in #proofs-and-logic not too long ago

[hushed steeple]

how do uall know abt math

[kindred aurora]

Is it correct?

[red yacht]

k is in Z, a is in N

[red yacht]

we cant though

[magic rain]

Eventually I think I've found a simpler proof

[ionic latch]

It's simple to show that k > 0 though

[red yacht]

what if k <= 0?

[ionic latch]

Then kp <= 0, which is impossible

If a > 0 and p >0 then a/p >0

[red yacht]

but p is never said that p is in N, is just a prime

[ionic latch]

You allow primes to be negative?

[red yacht]

no wait, I just read the problem statement it mention the prime p is positive

I think?

[ionic latch]

Well I guess agnostic of that the other way to show k > 0 is

if k < 0, then k == 3 (mod 4) -> -k == -3 = 1 (mod 4)
But if k < 0, then p < 0
So (-k)(-p) = a == 3 (mod 4)
-p == 3 (mod 4)
-p is a prime divisor of a congruent to 3 mod 4

and k = 0 is impossible, because then a = 0

[red yacht]

-3 = 1 (mod 4)

[ionic latch]

Oops that's what I wrote the first time

and then accidentally replaced additive inverse with multiplicative

fixed

although the standard definition of primes is to only admit members of N

if for some reason you allow negative, wehave (unfortunately) one more case, but thankfully it is only a few steps

[weary eagle]

Can someone explain me chinese remainder theorum

[ionic latch]

If no one comes in like 7 hours I should be free and can

But someone else will probably come by in that time and help you

[graceful pebble]

what's your current understanding?

[unique cypress]

You can do things like Z/6Z \cong Z/2 x Z/3 with CRT

[red yacht]

is not that complicated, is a algorithm you have to follow, if you have an exercise about crt we can maybe guide you step by step

[weary eagle]

You have to multiply the modulo to get M that's it and it is used for remainders and equation like x mod 3 (mod 5)
X mod 2 (mod 3) here m=15

[dire stratus]

$R/(\bigcap_{i=1}^n I_n) \cong \prod_{i=1}^n R/I_n$ if $I_i + I_j = R$ for any $1 \leq i, j \leq n$

[sterile pumice]

lexi

[graceful pebble]

sorry i forgot! has anyone explained or shall I ?

[weary eagle]

Nope no one has yet

@graceful pebble

(pinged him to explain not randomly mods)

[graceful pebble]

okay I'll try what I can

so usually it's used to solve congruences in multiple moduli