elementary-number-theory

[proven cypress]

@unkempt void

[gaunt marlin]

Guys, I'm very noob at Number Theory, I'm trying to integrate Mathematics (especially NT and Combi) and Computational Task together, I wanna research on those topics, especially I'm fascinated to solve problems from https://www.projecteuler.net
But I don’t know how can I approach, I wanna start from project euler. I need complete roadmap since I'm absolute beginner. Besides, I want solid foundation of NT as well as Combi and Its implementation on CS as well as solving problems.

[mint stone]

I don’t see any reason not to start. You can sort the problems by difficulty (which is nice, since Project Euler allows that), pick the ones you find interesting, and try solving them. And if you get really stuck, there are explanations available online for many of them.

[gaunt marlin]

My actual problem is, I don't see explanation or editorial, I think my approach is right but ultimately its wrong, in some cases, my logic goes wrong. So you are saying I need to seek editorial when I'll get stuck. And that's how I can do better, right?

[mint stone]

Yep, try searching for an editorial on the problem. Those with low to medium complexity can often be found somewhere on the internet. Alternatively, you can check other platforms like Codeforces (CF), which hosts a lot of number theory problems as well. CF is much more popular, so you're more likely to find explanations there. That said, some of the highest-difficulty problems still have no solutions available online.

If the problem is just too hard and you have no clue where to even begin, it's actually a great opportunity to indulge in slow-paced mathematical reflection — say, early in the morning, when you're not fully awake yet. You can let your mind wander through different approaches, hoping that some mathematical deity will descend and bless you with a solution. In any case, the real joy comes from the process itself, and solving the problem in the end will feel like a well-earned reward. But of course, this is more for the math aesthetes — a rare breed, as always 🙂

[main fractal]

the set of remainders you get when taking multiples of x modulo m is the same as the set of multiples of gcd(x, m) modulo m - why?

[rugged locust]

that does not sound true - for instance if x is coprime to gcd(x,m) then the set of multiples of gcd(x,m) is just 1.
but as long as x itself is not equal to 1 mod m then its set of multiples mod m has to contain more than just 1

[main fractal]

This probably doesn't apply to all cases then or maybe I said it wrong. I'll try to explain it with more of a visual I guess. I thought that if you have x, 2x, 3x, 4x, 5x, etc. and then take all of those modulo m, that the set becomes multiples of gcd(x, m). This definitely seems to work for coprime numbers because all the numbers start getting listed and loops forever. For example x = 6 and m = 7 would be 6, 5, 4, 3, 2, 1, 0, 6, 5, 4, 3, 2, 1, 0, etc. If you then switch m to 8 where gcd(6, 8) = 2 you end up with 6, 4, 2, 0, 6, 4, 2, 0, etc. I am really new to number theory so I could be completely wrong though

[rugged locust]

oh, you meant sums of x

[rugged locust]

it's because coprime numbers mod m are invertible

namely, if x is coprime to m, then there exists another number y such that xy = 1 mod m

[main fractal]

Thanks

[rugged locust]

just a quick sketch for the proof of your statement.
For any number x, let x = x'g, where g is the gcd of x and m.
Then x' is coprime to m.
Thus let y be an integer such that x'y = 1 mod m, such that xy = x'gy = g mod m.
So the set of multiples of x contains the set of multiples of g.

On the other hand, x'g = x, so the set of multiples of g contains the set of multiples of x.

[orchid escarp]

Hi all!

If d divides a and d divides b, does that mean it divides any integer combination of a and b? Like, can I just go on adding and multiplying a and b forever and d will still divide the result? For example: d divides a * whatever + b * whatever - a * somethingelse + b * anotherthing - b * onemorething. Even if all those "whatever" things are different?

If that's true, what's the general theorem that says this? Because Bézout only talks about ax + by, not stuff like ax + bx - bj + ak + am - br etc. Is there a more general theorem than Bézout for this?

[wooden glen]

ax + bx - bj + ak + am - br = a(x+k+m) + b(x-j-r)

[patent acorn]

...i don't see how bezout is relevant here at all?

this just follows from the facts that:

1. if d divides a and d divides b, then d divides a + b
2. if d divides a, then d divides a * b

which are both pretty immediate from the definition of divides:

1. if a = kd and b = jd, then a + b = (k+j)d
2. if a = kd, then ab = (bk)d

[orchid escarp]

but... i d|a and d|b, d = ax + bx + br + bj - ak + asomething.

I dont know how to say in english.. "linear interger combination" I think

but bezout say just ax + by, not a lot of sums with others integers, not just x and y

[patent acorn]

(where all the variables here are integers)

[patent acorn]

...i'm not clear on what direction you're asking for a result in

or no, not "direction", i'm not clear on the quantifiers

you're talking about two completely unrelated results that have very little to do with each other beyond being about divisibility

or actually it's not quantifiers

you're just being generally really unclear

[orchid escarp]

Yeah, I get that if d divides a and d divides b, then it divides a + b, a − b, and any multiple like ka or kb.

But what I'm trying to understand is: if I start adding and subtracting a and b with lots of different integer coefficients, like:
d | ax + by − bj + ak + am − br + ...

Isn't that still something that d divides? Like, all of these terms are still just combinations of a and b, right?

So my real question is:
Is there a name for the set of all these combinations? Like, is this the "ideal generated by a and b"?
I was thinking Bézout's identity covers it, but Bézout just gives one equation, like ax + by = d, not the whole set of expressions like that.

So is there a theorem that says:
"all combinations like ax + by + ak + bj − b*r + ..." are still divisible by d if d divides both a and b"?

[patent acorn]

yes, this

you just apply these facts multiple times

although also, as tropo pointed out, the numbers of the form ax + by - bj + ak + am - br + ... can in fact all be written as ax + by, by just collecting together all of the terms with a in them and all of the terms with b in them

[orchid escarp]

is that what people call the ideal generated by a and b?

[patent acorn]

also bezout's identity is still completely irrelevant

[wooden glen]

It is indeed the ideal generated by a and b.

But note that you already got that ideal as { ax+by | a in Z, b in Z }.

You don't get any new numbers by your "− bj + ak + am − br" calculation that you couldn't already make just as ax+by for appropriate x and y.

[orchid escarp]

Thank you! I'm back to work now — I'll digest your answers later.

[orchid escarp]

cool, I get it now: a(3 + 5 - 2) + b(4 - 1 + 10) = a(6) + b(13). thanks for the answers

[maiden solar]

has anyone seen something like this before? i cant find it on the OEIS

[white prairie]

Can i get a hint on second case? I tried analyzing the solution from the notes i got but it doesnt make much sense to me and internet didnt help much either 🙃

[stuck shore]

looks interesting. you should submit it to oeis if you can't find it there

[supple quarry]

Can I reasonably assume you're familiar with the Riemann Hypothesis?

[atomic harbor]

hes bernhard riemann himself

[cunning goblet]

@deep fable

so

[deep fable]

Thanks, one sec

[dreamy wraith]

a^x | b^y , det(A) greater or equal to zero => a^w | b^z

A= [x y]
[w z]
Matrix

What’s the proof of this ?

[ocean flame]

I suppose that x, y, w, and z are non-negative integers. What about a and b?

[zinc pewter]

I'm trying to understan if my proof of the following lemma is correct: "if p is a prime and p|ab, then p|a or p|b". My attempt is as followed, If $p|ab$, then either $ a = pq$ or $b = pq_2 $, or both cases. Case 1: $p|a = p|pq$, valid. Case 2: $p| b$, valid. Case 3: $p \nmid a$, then $a = pq_2+r$ for some nonzero integer r. p|ab = p|(pq+r)b. b has to be a multiple of p, $b = pq_2$, so that $p|ab = p|(pq+r)pq_2 $otherwise we have a contradiction.

dont know the latex keyword for not divisible is : /

∤

[brittle prairie]

“if p|ab then either a = pq or b = pq_2” needs justification

[sterile pumice]

Pen

[zinc pewter]

ah okay

Hmm

[brittle prairie]

(this is the wrong line of reasoning)

sorry i wasnt clear

do you know Bezout’s Lemma

[zinc pewter]

It is the case since $p|ab =p|(pq+r) $ where the rest is 0 using the division algorithm

[zinc pewter]

I do not

Looked it up and yes, I know of it

as a matter of fact, my book uses it without mentioning the name

[zinc pewter]

Could you explain why this thinking is wrong? I tried showing that if p|ab, then either a = pq or b = pq_2 must be true using contradiction

Proofs are hard : (

[wooden glen]

You seem to start by assuming the thing you're supposed to prove.

(Ah, Ark already pointed that out).

[zinc pewter]

I meant that those are the possible cases without contradicting p|ab

[wooden glen]

But that is what you're supposed to prove!

[zinc pewter]

Yes! The first two cases is when p|a or p|b, because it follows then that p|ab. The third case is when p|a, showing that p|b must be case

Or maybe I need to step back a bit and read what I wrote, I am clearly in the wrong

My own ignorance is my greatest weakness

[wooden glen]

You start by saying "if p|ab then either p|a or p|b or both p|a and p|b" -- but that doesn't actually differ from the lemma you're supposed to prove because "X or Y" is logically the same as "X or Y or both X and Y".
So once you say that, you're saying "we already know that what I'm supposed to prove is true", and the whole rest of your paragraph is superfluous.

[dreamy wraith]

Yep a and b are also non negative integers

a,b,x,y,z,w ∈ W

[zinc pewter]

One of my weaknesses that I have identified is the begining of a proof and what assumptions are allowed to make. You are correct and I need to work more on this

Thanks for the feedback ❤️

[ocean flame]

So, without a statement a | b, it seems that it is not always true. Are there any additional statements?

[dreamy wraith]

No there are not additional statements, we use it to check if questions like this are true

a^4 | b^ 5 => a^6 | b^ 8

In true or false questions

From the determinant this should be true

[ocean flame]

Interesting. I think, the formula of the determinant for 2 by 2 matrix and the Fundamental Theorem of Arithmetic can help

[wooden glen]

Assuming a, b, x, y, w, z are all nonnegative integers: For each prime p, let f(p,a) be the the exponent of p in the prime factorization of a.
a^x | b^y then says that x·f(p,a) <= y·f(p,b) for all p.
We want to know how w·f(p,a) compares to z·f(p,b). Multiply the known inequality by w/x, and we get
w·f(p,a) <= wy/x·f(p,b)
which gives us the desired w·f(p,a) <= z·f(p,n) if wy/x <= z which is if wy <= xz, which is if 0 <= xz-wy.

[dreamy wraith]

Thanks! Can we extend this to negative integers as well ?

a, b ∈ Z

[wooden glen]

Probably not without a lot of sign-fiddling.

Oh, a and b should work, yes -- divisibility doesn't care about signs, after all.

[dreamy wraith]

Got it thanks! I gotta do more work on fundamental theorem of arithmetic it seems

Another proof i was struggling was done with fundamental theorem of arithmetic

This one particularly
a^n | b^n => a | b

[wooden glen]

With the same machinery as above, a^n | b^n tells us f(p,a)·n <= f(p,b)·n for all p, which immediately gives us f(p,a) <= f(p,b) for all p, so a | b.

[dreamy wraith]

Appreciate It! What book do you recommend for elementary number theory ?

[wooden glen]

Unfortunately I don't have any book recommendations.

[regal summit]

Friendly intro to number theory by Silverman isnt too bad

Silverman is also a big name in number theory so its a good start

[unkempt void]

I liked Ireland and Rosen's book

[dreamy wraith]

I’ve heard his name from his calculus book

[unique cypress]

Ireland and Rosen

Apostol

[long lion]

here's the proof you've tried to do:

"Suppose for a contradiction otherwise. By the division algorithm, write $a=q_1p+r_1, b=q_2p+r_2$ for some $1 \leq r_i < p$ then we obtain $p \mid r_1r_2$, contradiction

[sterile pumice]

LY

[long lion]

the problem is the last line: why is that a contradiction

[wraith pebble]

Hello mathcord! Is the following statement true? i've been using it in a lot of problems relating divisibility but I haven't seen this stated as a lemma/theorem in any of my books.

[sterile pumice]

lord_breadcrumb

[verbal axle]

if a | (b + c) then an = b + c for some n

now if a | b then am = b and so an = am + c -> (n - m)a = c

so a | c

and the same proof the other way works to show a | c => a | b

[wraith pebble]

cool! thx

[junior swallow]

Does this proof work for $\implies$ (here $(a, b)$ is the gcd of $a$ and $b$)? Suppose that $(a, b) \nmid c$. Then there are $q, r \in \mathbb{Z}$ with $r < (a, b)$ and $c = (a, b)q + r$. Then $ax + by - (a, b)q = r$, and since $(a, b)$ divides the left hand side, $(a, b)$ divides $r$. This contradicts the fact that $r < (a, b)$.

[sterile pumice]

okeyokay

[rugged locust]

you're overthinking it

suppose it has a solution x_0,y_0

[west glade]

your proof literally uses that (a,b) divides the lhs of some equation

immediately apply it to ax+by=c

[rugged locust]

then ax_0 + by_0 = d [ax_0/d + b y_0/d] = c, where d := (x_0,y_0), so d divides c

[junior swallow]

ohh yeah right

thanks

[junior swallow]

thanks bud

[junior swallow]

Could I have a hint for <= please?

[trail sleet]

what if x = 0

[junior swallow]

Nvm I got it

[junior swallow]

Yeah I considered that but ended up hitting a dead end

[trail sleet]

oh hm

[junior swallow]

We have ax' + by' = d for some d in Z, where d = (a, b). Then d | c, so that (ax' + by')k = c for some k in Z. Consequently ax'k + by'k = c, so we may take x = x'k, y = y'k

[trail sleet]

oh wait

(a,b) refers to gcd(a,b)?

[junior swallow]

yeah

[verbal axle]

I also hated that shit till I realized that its the ideal generated by {a, b}

[trail sleet]

ah i thought it was saying a|c and b|c lol
yeah idt its true in that case

[dreamy wraith]

Why we don’t consider Willan’s formula for primes ?

[trail sleet]

Because computing the nth term of that sequence takes more work than just searching through the list of numbers until the next prime
Or something like that

[compact swift]

is there an elementary proof of like given a prime p divide the discrimiant of an integer polynomial coefficient f(x) then f(x) == g(x)h(x)^k (mod p) k > 1

[sacred junco]

What does a||b mean

[still flare]

Hard to say without context, but it could mean:

1. a is parallel to b
2. this is a typo and they meant to write a | b, meaning an = b for some integer n.

[sacred junco]

But I've seen twice it in number theoretical context

[rugged locust]

mind showing the context, then?

[rugged vigil]

!original

[rotund gust]

Please show the original problem, exactly as it was stated to you, with the entire original context. A picture or screenshot is best. If the original problem is not in English, then post it anyway! The additional context might still be helpful. Do your best to provide a translation.

[shell heath]

maybe it denotes proper divisor? just guessing...

oh wait, on googling... it means exact divisibility, so 3^k | n but 3^(k+1) does not.

https://math.stackexchange.com/questions/1491116/what-does-double-vertical-lines-mean-in-number-theory

[long lion]

i think generally in NT, p^k || stuff means v_p(stuff) = k

[unique cypress]

Yes that's what I'd assume too

[junior swallow]

Am I stupid? As to the second assertion, (2, 4) = 2, and 2 | 8, 4 | 8, and 2 * 4 = 8 | 8

[rugged locust]

You’re just asked to give a counter example

Of course there’s going to be cases where (u,v) is not 1 and it still works, as you have demonstrated

[junior swallow]

Bro my brain does not work when it comes to number theory holy shit

[unique cypress]

replace noggin

[rugged locust]

Have you tried turning it off and on again

[junior swallow]

Can I have a hint on showing that if (u, v) = 1 then (u + v, u - v) = 1 or 2? If it's 1 then we're done, so we can suppose it's not 1 and show that the gcd is 2

So far I know that (u + v)a + (u - v)b = d for some d > 1

we also have ux + vy = 1

thus u(a + b) + v(a - b) = d = uxd + vyd, and I'm stuck

[rugged locust]

you know more than that actually, d has to divide every possible integer combination of u+v and u-v

[junior swallow]

Ah

d | 2u = u + v + u - v

uhhhhh

if d =1 then we are done so suppose it's not 1

d | 2u and d | 2v, if d > 2 then d | u and d | v, contradicting (u, v) = 1

?

[rugged locust]

good enough

[junior swallow]

hold up i feel like this explicitly uses euclid's lemma

/requires d to be prime

We're basically saying if d | 2u and d does not divide 2 then it divides u right

[rugged locust]

not really

let p be a prime factor of d, think about what happens next

this is a common trick when you want to prove things about divisibility of numbers

instead of looking at a number itself, which may or may not be prime, try looking at what happens to an arbitrary prime divisor of that number

and if you can prove something about that prime divisor, usually that's as good as proving something about the original number

[junior swallow]

Hmmm... let 2 \neq p be a prime divisor of d. then p | 2u and p | 2v, so that p | u and p | v (here we really use Euclid's lemma). Since p > 2, this contradicts (u, v) = 1

[rugged locust]

you don't need to assume p is not 2

since p divides 2u and 2v, and (u,v) = 1, you immediately get that p has to be 2

so either d is 1, or it has a prime divisor, which can only be 2

there's a final step that I haven't mentioned yet

can you see what it is?

[junior swallow]

I mean I would guess involving showing that the exponent of 2 in d is equal to 1

[junior swallow]

I guess this would involve showing that there's only one 2 in the product as well

[rugged locust]

it's a really straightforward proof

WLOG let d be 4

[junior swallow]

Well I guess if d = 2^n where n > 1, then 2^{n - 1}k = u and 2^{n - 1}j = v for some k and j in Z. then 2 | u and 2 | v, contradiction

[junior swallow]

Am I going crazy? By the Proposition, we have $\sigma(n) = (2^{m + 1} - 1) \cdot \left(\frac{(2^{m + 1} - 1)^2 - 1}{(2^{m + 1} - 1) - 1}\right)$. Substituting $x = 2^{m + 1} - 1$ gives $x \cdot \frac{x^2 - 1}{x - 1} = x(x + 1) = (2^{m + 1} - 1)2^m$, aka what we started with

[sterile pumice]

okeyokay

[rugged locust]

the first part of your expression doesn't look right

let's label the prime 2^m+1-1 as p

then as a = 1, the term in the expansion is (p^2-1)/(p-1) = p+1

[junior swallow]

Is this for the second term in the expansion for \sigma(n)?

the first term is 2^{m + 1} - 1 because we take p_1 = 2

[rugged locust]

oh wait hold on I think I misread your thing

[junior swallow]

all good

[rugged locust]

everything is right, but you substitied in x wrong at the end

x(x+1) = (2^{m+1}-1) (2^{m+1}-1 + 1) = (2^{m+1}-1) 2^{m+1}

so there's the missing factor of 2

[junior swallow]

ahhhh

thanks!

[waxen pumice]

hellloooo

okay, so

marvel, and be in awe!

[wooden glen]

What are we seeing there?

[junior swallow]

Could I have a hint for this question please

[rugged locust]

do you know v_p notation?

[junior swallow]

Nope

Wait are you referring to ord_p

[rugged locust]

I think so

anyways, just write a out as a prime factorization

then look at each prime dividing a

[junior swallow]

👍

[slender current]

Yeah what it looks cool

[junior swallow]

I'm probably not understanding this correctly but why is this true? for instance, if a_1 = 3 and a_2 = 1, we have \epsilon_1 = 3 and \epsilon_2 = 1

also it appears as if this is my channel now

I guess my question is how is \mu defined if the integer is not a product of distinct primes - is it a homomorphism or something

wait no for it to be a homomorphism it has to be defined for products containing multiple primes

never mind I'm dumb

not square free

can somebody explain the displayed equality though?

is it like 1 place to choose a 1, 2 places to choose 1, etc.

[wooden glen]

Yeah, that's the first equals sign. The second equals sign is the binomial theorem in reverse.

[junior swallow]

got it, thanks

[dreamy wraith]

Can someone explain the intuition of this

7|14m-21n+143x => 7|3x

[spice plank]

assuming that m, n, and x are integers

7 | (14m-21n+143x) means that (14m-21n+143x)/7 is an integer

(14m-21n+143x)/7 = 2m - 3n + 20x + 3x/7

but since 2m, 3n, and 20x are integers, 3x/7 must also be an integer

[dreamy wraith]

Thanks

[unkempt void]

14m -21n + 143x = 7(2m - 3n + 20x) + 3x

[uncut arrow]

I have this diophantine equation I've been trying to solve, with relatively little luck. Domain for n is non-negative integers.
I'm aware of the small, trivial solutions at n = 0 and n = 5 (I think those were them at least), but my question is whether or not there are others.
To that end, my goal is to either prove that there are no solutions for n > 5, or find one.

I'm not very experienced in number theory, and any diophantine equations beyond linear ones are generally beyond me, so I'm just not sure what to try.
Any related theorems or connections would be really helpful, I tried googling stuff but got nothing besides AI overview straight up lying.

Also, I got this equation through a convoluted series of events involving some parts of math I'm more familiar with (discrete calculus, graph theory, Pascal's triangle, combinatorics), so if this ends up being completely intractable I can always try to backtrack there.

[west glade]

with induction you can easily show that eg cn^4<=24*2^n for n big enough

[wooden glen]

As soon as n>=6, 2^n grows by a larger factor than the quartic polynomial for each step of n, since (7/6)^4 < 2.

[west glade]

at that point its a bit of a question of how much you want to optimize the constant c

[wooden glen]

Wait, is it 2^n or 2^m on the right hand side?
0 and 5 are not actually solutions if it's 2^n.

[uncut arrow]

It's 2^m

So you can't just reason that the exponential grows too fast

[west glade]

ok the next obvious thing: can you factor that quartic?

[uncut arrow]

No

(at least not over the reals)

(to the best of my knowledge)

[junior swallow]

Let a, b be two integers. Is lcm(a, b) = d, where (d) = (a) (b), the product of the principal ideals generated by a and b in Z?

[unkempt void]

(a)(b) = (ab)

[junior swallow]

ah so no then

maybe it's their sum?

[unkempt void]

Intersection

[junior swallow]

alas

I guess that makes sense since elements of (a) n (b) are multiples of a and b lol

oopsies!

[junior swallow]

I'm quite terrible at number theory.. can I have a hint for 20a please

[rain glacier]

look at prime factorization of a and b

[unique cypress]

Tip: when lost, always prime factorize

[uncut arrow]

Still working on this if anyone has any ideas or suggestions of what to try

[hearty hornet]

Are you looking for hints or an answer? I seem to remember a 3b1b video about this problem (Or something related)

[uncut arrow]

Anything. An outright answer isn't really what I'm looking for, but if there's explanation for where it comes from then totally

I've pretty much given up trying to solve it this way on my own

[surreal crescent]

i dont think so

[surreal crescent]

where did u get this problem from

[hearty hornet]

It's a sum of binomial coefficients

[surreal crescent]

wdym

[hearty hornet]

edited\

$$ (n - 4)^4 + 14 (n - 4)^3 + 83 (n - 4)^2 + 262 (n - 4) + 384 = \sum_{k=0}^4 \binom{n}{k} $$

https://www.youtube.com/watch?v=YtkIWDE36qU

@uncut arrow This seems related, you can confirm the values in the sequence are just shifted. Where did the problem come to you from?

[surreal crescent]

?

[hearty hornet]

yeah it's a rising factorial not falling

I'll edit rq

That should work, it's only nonnegative though

[sterile pumice]

Yumdub

[hearty hornet]

Sorry for the haphazard edits, it's correct now.

[surreal crescent]

oh wow yeah

but does that help?

[hearty hornet]

It's a helpful hint which seems to be the request. I'm unsure if it's a full solution but it does give a lot of insight into where the problem could have come from

It doesn't look like you can immediately determine if it's a power of two or not from this

but binomial coeffs sum to be powers of two across the rows. Hence the small solutions, the video mentions the Moser Circle Problem

[surreal crescent]

but its just a portion of a row

[hearty hornet]

it's not a portion of a row if n < 5

probably would need the OP to weigh in next

[uncut arrow]

Yeah, aware of those connections, but didn't find anything super useful there sadly
Is it more worth trying to find some combi or graph theory approach instead do you think? (vs continuing to explore the diophantine equation I originally posted)

[uncut arrow]

I got it from a friend, who probably got it from here if I had to guess.
(He's a 3b1b fan)

[hearty hornet]

Yeah, I think the video might end with a conjecture for this or something. I'm not sure I remember

[uncut arrow]

If Grant isn't sure of an answer I'm not sure if I have much hope

[hearty hornet]

It doesn't seem exceptionally difficult, but it's a number theory problem ofc so it could look that way and be crazy hard lol

[uncut arrow]

Yeah lol

[hearty hornet]

This may have a combinatorial answer, I wouldn't turn it into algebra

not sure what else to do though, I was thinking using the coefficients next, as in their divisibility properties

[uncut arrow]

He poses the "is there another power of 2" question at about 15:00 in that video and says he's not sure of the answer

[hearty hornet]

Glad I could save you the headache lol, a friend definitely did this to me a couple years back too

Why I knew the problem immediately.

[uncut arrow]

Oh I was going to ask lol

How did you see this

[uncut arrow]

I wouldn't have noticed this probably, though I could have figured it out probably by thinking about the pascals triangle connection more

Someone in the comments brute forced it to 10,000,000 lol, and they found nothing

[hearty hornet]

Anyone who writes 24 under a polynomial like that is usually looking at something like n choose 4, since 4! = 24. From there I just checked the values a bit with a physical calculator. I was somewhat convinced when I saw 384 = 2^4 * 4! , so then I tried to do the second coefficient (the sum of the values in the product, by Viete's equations) and make it work out

I also have seen this before, so I had a feeling it was that circle problem from 3b1b lol

[hearty hornet]

Pascal's triangle wasn't my first thought, although that is a way to define Binomial Coefficients, but the factorial definition is the true definition.

[surreal crescent]

No, this probably pretty likely has a very bashy mod solution at least

[hearty hornet]

My limited experience is that's kind of like the "turn it into a big algebraic diophantine equation" thing where it's often just as difficult that way

[astral quiver]

Tinyguess.com

Maths game

[unique cypress]

Memes go to #chill

Number theory has applications

[wise karma]

1. Sorry, I'm new (deleted and replaced now) 2) some, but it gets greatly exaggerated by some lecturers and in popular science

[unkempt void]

Number theory is the application

[unique cypress]

sotrue

[hearty hornet]

Where is it most appropriate to ask a mathematics question relating to undergraduate number theory? Should I use #help for an answer requiring a reference / proof or ask the question here?

I had a question related to a small generalization of Fermat Factorization (difference of squares method)

[warm meadow]

here because it's the university category

or in help channels

[hearty hornet]

Well first off, the difference of squares method is the following:
If you have N = x^2 - y^2, then N = (x - y)(x+y), so you can factor N. If N is odd, it can always be written this way, and so you can do Fermat Factorization by starting with a rounded value of x = sqrt(N), and then solve that equation backwards to find a perfect square integer y^2

It's known that Fermat Factorization is fast if p = x - y and q = x + y (these both exist if N is odd). That's because it basically increments x for the smallest y value, since you start with
round( sqrt(N) )^2 - N,
and then square root to search for y (or test it's a square I guess).

You can generalize Fermat Factorization to a "ratio hint" for how far apart the factors are. The assumption is that r = 1 in the basic Fermat Factorization. To demonstrate this, r = 4 (q = 4p, or round about there) can be done as follows:

$$ N = (x - y)(x+y) = p*q \approx 4p^2 $$
so now
$$ sqrt(N) / 2 \approx p $$

[sterile pumice]

Yumdub

[hearty hornet]

My question is firstly, and I may table the rest pending response, how far off can that "ratio hint" truly be from the real ratio? Surely if the factors p and q have r = 4, then using normal Fermat Factorization (r = 1) would take a long time, as the test is slow. But if I chose an r = 3.9? I know the answer of closeness also depends on N, so I'm curious how to get a function f(N, r) that can succeed in a single hit.

[thorn relic]

are all sufficiently large integer the sum of 4 positive squares?

[wooden glen]

No. https://oeis.org/A000534

In particular, odd powers of 2 are not.

[thorn relic]

presumably as one require the squares to be larger and larger, the number of squares needed to make sufficiently large integers goes to infinity right?

That is, If $G(n,2)$ denotes the minimum number of square greater than $n$ needed to represent all sufficiently large integer, then $\lim_{n\to \infty} G(n,2)=\infty$?

[sterile pumice]

qwertytrewq

[kindred moss]

https://math.stackexchange.com/questions/1410157/integers-which-are-the-sum-of-non-zero-squares

every integer >= 34 is a sum of 5 positive squares :0

[thorn relic]

i think circle method shows that such number always exists no matter what bound you have (every sufficiently large integer can be the sum of some fixed number of squares greater than 10 for example)

[kindred moss]

thats cool :0 but that must only work for specific bounds? since we already see it fails for 4 squares

or is that referring to nonnegative squares

[wooden glen]

I don't think so. Without loss of generality, assume n is a square. Then every residue class modulo n is a sum of 4 square residues, so for each residue class we can pick a representative that's the sum of four squares >= n. Now, for a sufficiently large number, you can subtract one of those representatives and have a multiple of n left -- and that is the sum of at most 4 squares each a multiple of n.
So 8 squares will always suffice.

[thorn relic]

the statement is "for every n,there exists some number m for which every sufficiently large integer is the sum of m squares greater than n"

[kindred moss]

oh so you're letting the number of squares vary on the bound, that makes more sense

[thorn relic]

right! thanks. thats perfect, this argument should generalize to show that $\lim_{n\to \infty}G(n,k)\leq 2G(k)$

[sterile pumice]

qwertytrewq

[thorn relic]

actually might be G(n,k)<=2G(1,k) cuz 0 might mess up the argument

[wooden glen]

In the square case, note that the exceptions in A000534 get farther and farther apart. So if you just have two possible representatives for each residue class modulo n ready that you can make with exactly 4 squares, then eventually it will be certain that you can pick one of the two representatives to subtract and end at something that is not one of the forbidden multiples of n.

(But I don't know how well that generalizes to higher powers).

[thorn relic]

for each n, and kth power, you mod out by n^k, and carry out the same argument. Ofc, this is given that one knows G(1,k) is finite, so you can really pick powers greater than 1. And this is the result mentioned in the first couple paragraph of https://ford126.web.illinois.edu/wwwpapers/warpoly.pdf

I think the bound that your argument provides is really 10 rather than 8 unless i misunderstood

because every large integer is the sum of 5 positive sqaures

which i think you need them to be positive in the end because u want multiples of n in the end (otherwise it might still be 0)

[wooden glen]

I think I can make it 8.
For every residue r, 0 <= r < n, first write r = a²+b²+c²+d² with a,b,c,d>=0. Then if, say, a² is smaller than n (including if a=0), replace it with (a+n)², which does make the square large enough without changing the residue class. Similarly for b, c, d.
This itself gets us down to 9 squares for sufficiently large targets, you agree?

[thorn relic]

right that gives 9

[wooden glen]

Now you have for each r a selection of a²+b²+c²+d² == r (mod n) with each of a², b², c², d² >= n. But then we also have a²+b²+c²+(d+n)² == r (mod n), so there are at least two different choices of how to reach a multiple of n when we see residue r.

[thorn relic]

right and ig you argue that counterexamples that is not the sum of 4 squares must be sparse eventually everywhere?

[wooden glen]

Yes, because we have the entire list of counterexamples in A000534.

In fact scratch all the above modulo business! (no, that is still necessary, sorry)

[thorn relic]

right! i didn't check carefully, much nicer than I expected

that's cool, it makes a interesting question to ask what the sup of G(n,k) over n is.

[waxen pumice]

man, I think it's super cool how the square root of perfect squares will always be in the middle if you were to list out all the divisors of the perfect square in ascending order

just blows my mind

[wooden glen]

In fact if we let n=p² where p is a prime of the form 4k+1, then every residue class modulo n can be made as the sum of two squares, rather than four.

[thorn relic]

genius

[lavish estuary]

I have no clue if this should belong to pre algebra or this channel but oh well

[rugged locust]

hint: ||ABCABC = 1000ABC + ABC = ABC(1001)||

[wooden glen]

Also hint: ||1001=7·11·13||

[lavish estuary]

how do u all even think about that D:

ok maybe its because i didnt actually learn number theory in its own

This was a question from my uni entrance exam

Thats why i was a lil confused on where to send it-

Thank u so much-

[wooden glen]

Hmm, recognizing that ABCABC=1001·ABC is fair game for an entrance exam, but memorizing the prime factorization of 1001 is more of a parlor trick that feels more like competition math or recreational math.

[rugged locust]

by the way, there's a really fast way to figure out what the remaining 2 primes are

[wooden glen]

Perhaps the problem is given in a context where there's ample time to factor 1001 by trial division?

[lavish estuary]

Yee one of them is 2

Thats like the only prime number i could find lol

[wooden glen]

It's the only way for the sum of two distinct primes to be odd. (Or the sum of five distinct primes to be even).

[lavish estuary]

then i tried to divide 98 by 4 so that ik it would have numbers closer to 98/4 in order to get the big number

[lavish estuary]

But yeah uh that didnt go so well-

[lavish estuary]

I think there is like 3 mins given on average for each question

<but like some questions are easier than others so maybe 4 mins-ish for the harder ones?

Tysm!

[junior swallow]

Here, do we assume that a > 0? Otherwise, -2 = (-1)^3 - 1 is prime

[kindred moss]

yeah, i dont really see negative numbers referred to as prime very often

[junior swallow]

Could I have a hint for showing that n is prime?

I'm assuming that it has a proper divisor and looking at 2^n - 1 = 2^{n - 1} + 2^{n - 2} + 2^{n - 3} + ... + 1

[kindred moss]

i would instead do a substitution tbh, if n = xy for x, y > 1, then 2^(xy) - 1 = (2^x)^y - 1. a similar argument for why a must be 2 will reveal why this must be composite

your argument would work too, you just have to organize the terms a bit to show it

[limpid atlas]

presumably n>1 as well I assume, other wise you can set a to be any prime + 1 and n = 1

[junior swallow]

Ah that's smart lol

[junior swallow]

How can I see that 4k^2 + 4k is a multiple of 8 for k >= 0

[kindred moss]

Tru factoring it

[junior swallow]

I just wrote 4k(k + 1)

Hm

Nvm

Uhh

[kindred moss]

that gets us a lot of the way already right

[junior swallow]

Yeah, I mean either k or k + 1 will be even, so we can pull out a 2

[kindred moss]

yaa that’s it

[junior swallow]

nice thx

[junior swallow]

Can somebody please explain where this highlighted equality came from?

Nvm it comes from Taylor Series ig

I don't recall learning this expansion in real analysis or calculus hm

[kindred moss]

It’s easy to see if you take an derivative and then an integral

[unique cypress]

If you don't like this you can use Euler summation

[thorny ermine]

Hey folks!!!!!!!!!

Fucking got D grade in every maths subject. Someone wants to challenge me in advanced mathematics? Beluga🦆

[junior swallow]

Sorry, would you mind elaborating more please?

[kindred moss]

ya

$-\log{(1- x)} = \int_0^x \frac{d}{dx’} [-\log{(1- x’)}]dx’$

[sterile pumice]

snowflake

[kindred moss]

basically just taking a derivative and then undoing it with an integral (the lower bound is there to give us the right constant)

if you compute that derivative, you get a nice rational with a nice power series expansion

And then you can just integrate that power series

And you’ll get the series expansion of log

[junior swallow]

Hmm okay I see

Lowkey I kind of forgot about power series and am too lazy to review these things lol

[kindred moss]

valid, the series here is just a geometric series which is nice

And then the integral gives us those m coefs

[junior swallow]

Yeah the rest of the proof I can remember from ra

Am I dumb or does this only count polynomials of degree one less than f?

Also where do we use that we're summing over positive primes in the proof? I'm assuming it's where they say 1 + 1/2 + 1/3 + \dots + 1/n < \lambda(n)

Which follows from unique factorization

[kindred moss]

I believe 0 is in the field

So the coefs can be 0

[junior swallow]

Wdym

I mean why aren't we counting polynomials of the form a_0 x^{m - 1} + a_1 x^{m - 2} + \dots + a_{m - 1} as well

and polynomials of lower degree

[kindred moss]

like if a0 = 0 then x^m isn’t really there

So you already have an m-1 degree poly at most

You can represent any lower degree poly by zeroing out the top terms

[junior swallow]

Oh I see that makes sense

Thnaks

[kindred moss]

I don’t really understand what the inverse prime elements are here though someone else will probably have to help with that

[junior swallow]

Like the p_i^{-1}?

I think it just means 1/p_i

[kindred moss]

Right but here the primes are like… irreducible polynomials right

[junior swallow]

Are you referring to this?

[kindred moss]

like there it’s integers, whereas the generalization is to polynomials

Unless you’re asking about the integer setting

[junior swallow]

I think they only write p_i^{-1} when they're talking about integers yeah

[kindred moss]

No yeah like that first one is def using integers

I thought you were asking how the polynomial setting connects to that

Which I don’t really know

[junior swallow]

Oh well it's a theorem on the next page lol

[kindred moss]

oo

[kindred moss]

I think the primes just gave us that lambda expression, and then the log gave us the prime reciprocal form, if that’s what you’re asking?

[analog crystal]

Is there anyone knowledgeable on Primes?

[rugged locust]

just ask your question and they will come

[kindred fulcrum]

!da2a

[rotund gust]

No need to ask “Can I ask…?” or “Does anyone know about…?”—it’s faster for everyone if you just ask your question! See https://dontasktoask.com/

[kindred fulcrum]

I can try to help

[junior swallow]

Why are we allowed to compute this? Don't we have the possibility that a/b - y is not in Z[w], while \lambda is a function only defined on Z[w]?

[rugged locust]

what is omega? is this the eisenstein integers

[junior swallow]

w = (-1 - \sqrt{-3})/2

[rugged locust]

so it is

[rugged locust]

first of all is it clear why r,s are rationals

[junior swallow]

Yeah

[analog crystal]

What I may ask is more closer to number theory with Primes.

We have 3 numbers, A B C

Each being Primes and Additive Primes. Their Linear concatenation being Prime ( ABC ), Reverse Concatenation being Prime ( CBA ) and a concentric structure ABCBA is a Prime.

How common are these?

[rugged locust]

in this case, you can actually just treat gamma as the norm function

essentially what the proof is doing is applying the norm function on C, restricting it to Z[w], and showing that the restriction gives a well-defined Euclidean norm

and hence Z[w] is a ED

[kindred fulcrum]

probably very rare, other then A,B,C being prime the other properties are pretty random

[rugged locust]

by the way, although it may be tempting to conclude from this that "most" extensions of Z are euclidean domains using this method, turns out that this actually fails for almost every case you can find, except for a few specific handful of situations.

in particular, a really interesting result is that there is actually only finitely many Eucliean Domains of the form Q(sqrt(d)), where d is some integers

and we fully know what that list looks like, you can find it here
https://en.wikipedia.org/wiki/Euclidean_domain#Norm-Euclidean_fields

[neat rock]

I think we can also assume the lambda function defined for Q[w] in a similar way. In the proposition 1.4.1 the author has done this only.

[kindred fulcrum]

its the absolute value of the field norm I think

[tidal anchor]

can someone help with this question? Find all the integers x, y, z so that 4 ^ x + 4^y + 4 ^ z is a square.

[analog crystal]

But to level it up.

Let's pick a specific base, such as Base-N, N being greater than 10.

So far we have such Symmetric Prime structure, and I decided to consider these numbers A B C to be in Base-N and convert them to Base-10, giving X Y Z. I notice they are not individually Primes, but:

XYZ is a Prime
ZYX is a Prime
XYZYX is a Prime
XYZZYX is a Prime
ZYXXYZ is a Prime

Now how rare would this be to have happened by a random chance?

[analog crystal]

The A B C feature and Base-N to Base-10 later giving the X Y Z feature.

I am intending to know how I can compute the rarity of this.

[kindred fulcrum]

I don't think it will be easy to find any relation between the fact that these are primes and these properties.... What we can do is try to "guess" what it should be by choosing $1 \leq X,Y, Z \leq M$ uniformly. Then the property XYZ is a prime means that it shouldn't be divisible by 3 (or other small primes). Maybe we can make a very strong assumption that is $XYZ \bmod 3$ is close to be uniform on ${0, 1, 2}$ and then we get a probability of at least 1/3 that our properties are not satisfied.

[sterile pumice]

ExpertSqueeSQUEE

[kindred fulcrum]

I am thinking about this. If you more people to see this you should post in the math help channel.

[tidal anchor]

thx

the section is occupied tho

[kindred fulcrum]

#help-11 for example is not occupied

[kindred fulcrum]

I managed to reduce it to two variables...
If WLOG $x\leq y \leq z$ then
$$4^x + 4^y + 4^z = 4^{x}(1+4^{y-x}+4^{z-x})$$
Since $1+4^{y-x}+4^{z-x}$ is odd, the left side is a square if and only if both $4^{x}$ and $1+4^{y-x}+4^{z-x}$ are squares.
Also $4^{x}$ is a square if and only if x is even.

[sterile pumice]

ExpertSqueeSQUEE

[kindred moss]

i have no context but isn't that only odd if x < y and x < z, or if they're all equal

oh but that's easy to check as edge cases

[kindred moss]

wait isn't 4^x a square no matter what x is

bc 4^x = 2^(2x)

[patent acorn]

yes, it's (2^x)^2

[kindred fulcrum]

oh yeah xD mb

multitasking moment

[kindred moss]

z - x + 1 = 2y - 2x, unless there's some other weird way for the sum to be a square
z = 2y - x - 1, that's a pretty easy set of solutions

assuming x < y < z

[kindred moss]

$1 + 4^a + 4^b = k^2$ where $0 < a < b$, so
$4^a + 4^b = (k+1)(k-1)\$

clearly $k$ is odd, so let $k = 2n + 1$, and then
$4^a + 4^b = 4n(n+1)$

[sterile pumice]

snowflake

[kindred moss]

does this mean anything

[kindred fulcrum]

right side is divisable by 4^a

[kindred moss]

right

[kindred fulcrum]

and one of n, n+1 must be odd

[kindred moss]

its a little annoying again bc a could be 1 but ill just separate that out for now

[kindred fulcrum]

so $4^{a-1} \mid n$ or $4^{a-1} \mid n + 1$

[sterile pumice]

ExpertSqueeSQUEE

[kindred moss]

oh and if a = 1 then 4^(b-1) + 1 = n(n+1), impossible since odd = even

okay perfect

$4^{(a-1)}(1 + 4^{(b-a)}) = n(n+1)$

[sterile pumice]

snowflake

[kindred moss]

i feel like n has to be the one that's a multiple of 4

no idk

n just being a power of 4 is an easy solution again

o yeah why was i doing mod 4

😭

[kindred fulcrum]

mod 3 maybe works

[kindred moss]

is modulo 3 convenient, the LHS is 2 mod 3

yess

[kindred fulcrum]

n = 3k+1

man I love doing number theory instead of doing hw in cpp 🙂

[kindred moss]

this feels like going in circles i have a headache

what even is n again

[kindred fulcrum]

k = 2n+1
n = 3m+1
k = 6m + 3

[kindred moss]

hmm

oh yeah we're just imposing more and more structure on the square

that's good

[kindred fulcrum]

I think n = 4^(a-1) is a must

if $4^{a-1} \mid n$ then $n = 4^{a - 1}m$. The equation $4^a + 4^b = 4n(n+1)$ becomes
$$1 + 4^{(b-a)} = m(4^{a-1}m + 1)$$ which modulo $4^{\min(b-a,a-1)}$ yields $m=1$ modulo this power of 4.

[sterile pumice]

ExpertSqueeSQUEE

[junior swallow]

Can somebody please explain these highlighted sentences?

By unique factorization, isn't s unique?

It makes sense that f_S(x) <= 2^t

Assuming that all subsets of S are in the form y(n)

But the highlighted sentence still doesn't make sense

[kindred fulcrum]

s is a product of unique primes from S

so 2^t options for every subset of S

[hearty hornet]

It is unique, but n is a variable. So over the range of possible primes, one bounds the subsets as just picking one element in or out (that's a factor of two, which you seem to understand).
I think because there are only \sqrt(x) options for m, m^2 also has only \sqrt(x) options, and the product means that you are simple taking the product of the number of each

Maybe the proof could have said "there are \sqrt(x) choices for m^2 less than or equal to x"

[junior swallow]

Thank you

[junior swallow]

Thanks this is helpful

[junior swallow]

What is the purpose of counting these multiples? Is it that they're all the potential divisors of m which don't exceed x?

[kindred fulcrum]

yes

[wanton gorge]

Hi. What books or materials do you recommend me in order to start with number theory? Is there any subject that I need to know before starting with number theory?

[quaint gate]

if you're comfortable with hs math youre good to go

[junior swallow]

Where did this 2 come from?

[rugged locust]

2n choose n = (2n)!/(n!)(2n-n)!

[junior swallow]

Oh wait I'm trolling

Thanks

[junior swallow]

Also, why is tp = floor(log 2n/ log p)? For instance, we have 3^3 <= 2 x 15, but floor(ln 15/ ln 3) = 2 \neq 3

[unique cypress]

comes from the inequality

[junior swallow]

Would you mind elaborating please?

I understand that we can isolate t_p via logs but idg why we can just take the floro

[unique cypress]

are you asking why floor instead of ceil?

you're taking floors because you want an integer

[rugged locust]

as opposed to taking ceil, which famously returns non integers

[unique cypress]

[hoary shell]

tp <= log2n/logp. You want the smallest such tp so you take floor

[hoary shell]

Is this a joke? lmao

[rugged locust]

whats a joke

[hoary shell]

ceil giving you non integers

Can't tell if you're memeing

[rugged locust]

:3

[hoary shell]

This is implying that you take the floor because the ceil gives you a non integer

[unique cypress]

[forest portal]

hello, new here. I'm working on arithmetical/multiplicative functions such as the famous Möbius function and its inversion formula.

I need some clear explanation on indexes exchange on double sums

it appears anywhere

it's not necessarily a number theory question as it's common in other fields too

[wooden glen]

Can you show an example of a situation that confuses you? As long as it's elementary number theory, all the sums will probably be finite so you can rearrange them freely.

[forest portal]

let me write it

is it possible to type in latex?

[long lion]

yeah just type latex and there's a bot which displays it

[forest portal]

$$\sum_{d\mid n}\mu\left(\frac nd\right)\sum_{d'\mid d}g(d')=\sum_{d'\mid d \mid n}g(d')\mu\left(\frac nd\right)=\sum_{d'\mid n}g(d')\sum_{m\mid \frac n{d'}}\mu(m)$$

[sterile pumice]

schrysafis

[forest portal]

I want to know how and why this works

I understand that on the first sum we can use that since m,d are independent to the index d' of the outer sum so we can put it in then we get a double sum with two index conditions

[rugged locust]

fix a d' such that d' divides n.
Then d' divides d divides n <=> d/d' divides n/d'

[forest portal]

so you can freely make new conditions like this in finite sums?

for indexes

[rugged locust]

no

once again this only works because d and d' are independent

[forest portal]

ah

alright

https://math.stackexchange.com/questions/875509/prove-sum-k-1n-muk-left-frac-nk-right-1

can you explain the first answer to this problem?

it's similar

I get confused when he enters new index i

when we write dk=i it's a different way of saying d|i?

[rugged locust]

no, not d|i

it's saying that (k,d) where k<=n and d<=n/k is the same as (k,d) where kd <= n

[forest portal]

<= what does this mean?

[neat rock]

less than or equal to

[forest portal]

alright got it

[forest portal]

but how do we evaulate each term of the sum? how do 1 and 0's come up?

[rugged locust]

the 1's and 0's filter for the double counting

because otherwise the kd<=n will count the first sum twice

because if kd <=n then two things are possible: either k<=n and d < n/k, which is what we want, or d <= n and k <= n/d, which we don't want

the 1's and 0's get rid of the second case by making it go to 0

[forest portal]

need to think of it

[forest portal]

wait why will the latter case not hold?

[rugged locust]

because 1 only happens when d <= n/k (the first case)

[forest portal]

oh got it

[forest portal]

Order Test $\ ,a,$ has order $,n\iff a^n \equiv 1,$ but $,\color{#0a0}{a^{n/q} \not\equiv 1},$ for every prime $,q\mid n$

Proof $,\ (\Leftarrow),\ $ Let $,a,$ have $,\color{#c00}{{\rm order}\ k}.,$ Then $,k\mid n,$ (proof). $ $ If $:k < n,$ then $,k,$ is proper divisor of $,n,$ therefore $,k,$ arises by deleting at least one prime $,q,$ from the prime factorization of $,n,,$ hence $,k\mid n/q,,$ say $, kj = n/q,\ $ so $\ \color{#0a0}{a^{\large n/q}} \equiv (\color{#c00}{a^{\large k}})^{\large j}\equiv \color{#c00}1^{\large j}\equiv\color{#0a0}1,$ contra $\rm\color{#0a0}{hypothesis}$. So $,k=n.$ $\ (\Rightarrow)\ $ Clear.

[sterile pumice]

schrysafis
Compile Error! Click the reaction for more information.
(You may edit your message to recompile.)

[forest portal]

can anyone explain in the proof: i) modulo what are we working on, ii) why if k is a proper divisor of n then k|n/q?

the part with the prime factorization is unclear since if n=q then k|n/q implies k=1 which contradicts the hypothesis

then q must be a proper divisor of n

[delicate vortex]

i) modulo any integer. ii) if k is a proper divisor, then n/k is divisible by at least one prime q dividing n, so k divides n/q

[forest portal]

i see

the rest of it is okay

''if k is a proper divisor, then n/k is divisible by at least one prime q dividing n'' wait can you prove this quick to be sure?

nvm got it

it's just a little divisiblity exercise

and prime number theorem

[drifting mango]

is the intro to NT math-115 by UCB a good point to start for getting from 0 to like decent level in NT?

[junior swallow]

Can somebody help me see how the above implies this highlighted inequality?

Does it follow from the fact that all primes dividing (2n n) must divide 2n?

[neat rock]

not necessarily divide 2n but they should be less than 2n

becuase if p > 2n then by the inequality just above proposition 2.4.4 you see that ord_p (2n,n) = 0

[broken sluice]

im gna start number theory this yr is there anything i need to know

[kindred fulcrum]

To have fun

[broken sluice]

oh ok ty

[junior swallow]

Ah right, thanks!

[junior swallow]

Can somebody please help me see why we can bound the blue circled term by the yellow highlighted term?

[primal pewter]

each term is ≤log(2n) ||use [x]<=x|| and there are at most sqrt(2n) terms

[junior swallow]

Is there any other way to see this other than an annoying proof by cases

Bc if not than I CBA lol

[neat rock]

which cases are you referring to?

[rugged locust]

holy shit PRIME LOCALIZATION 🔥 🔥 🗣️ 🗣️ 🗣️

it's just two cases, it's a pretty straightforward check

[junior swallow]

Not tryna do allat I’m negl

[rugged locust]

honestly you don't even need to check

just notice that every other prime other than p is a unit

and p itself is not

then the fact just follows from factoriaztion in Z

[unique cypress]

Prime localization MENTIONED?!

[wooden glen]

"Z_p", though ...

[warm meadow]

I've asked it before (here if not on other channels), but is the following true?

The $n$th digit (from the right i.e. the first or the lowest place value) of a power of two $2^k$ is equal to the $n$th digit of $2$ raised to the following power
\[ \bigl((k-n) \bmod (4\times5^{n-1})\bigr)+n. \]

[sterile pumice]

glass

[wooden glen]

That sounds right. Note that 4×5^(n-1) is the totient of 10^n, and subtracting/adding n before/after the modulo makes sure don't choose a power that is smaller than n, which might give the wrong residue modulo 2^n.

... wait, that explanation of the adding/subtracting n sounds crazy. Does it even work?

For n=4, k=3 the claim wants us to find digit 4 of 2^503, but 2^503 ends in ...20715008 with doesn't have 0 as digit 4 from the right as it should.

It should work as long as k >= n, though.

[warm meadow]

I see. I didn't know what totient is. But now I know

thankyou

[warm meadow]

btw here's the first time I asked it. Some replies can give insight now that I'm looking back at it.

-# also interesting to see my mistakes

and the original question was to actually calculate a power of 2

using this method

[warm meadow]

\[
2^k = \sum_{n=1}^\infty\left\lfloor\frac{\exp\!\biggl((\ln 2) \cdot \Bigl(\bigl((k-n) \bmod \phi(10^n)\bigr)+n\Bigr)\biggr) \bmod 10^n}{10^{n-1}}\right\rfloor \cdot 10^{n-1}
\]

[sterile pumice]

glass

[warm meadow]

-# wrote 2^x as exp(xln2)

\[
2^k=\sum_{n=1}^\infty\left\lfloor\frac{2^\varphi\bmod10^n}{10^{n-1}}\right\rfloor\times10^{n-1}
\]
where $\varphi=((k-n)\bmod\phi(10^n))+n$

[sterile pumice]

glass

[warm meadow]

and as Troposphere said, k >= n

maybe there's a way to set the upper limit to a finite number

oh maybe u can set the upper limit to k

like the number of digits should not exceed the exponent

[warm meadow]

-# the algorithm works

[warm meadow]

4x5^(n-1) as totient of 10^n seems to be false

but it seems to be but divided by 2^(n-1) ?

[wooden glen]

Yeah, oops
But it is the totient of 5^n, which is what we really need here.
By the CRT we just want to find a number that is 2^k modulo both 5^n and 2^n, and the latter is always 0 if we assume k>=n.

[warm latch]

guys is this set theory

[quaint gate]

no?

[coral merlin]

-# maybe he saw the word theory and thought it's set theory

[spiral radish]

Prove that if p and p^2 + 8 are prime numbers, then p^3+8p+2 is also a prime number

[little wigeon]

i think its a bit of a trick question haha

[little wigeon]

are you familiar with modular arithmetic ?

[spiral radish]

Yes

[little wigeon]

are you familiar with the result that for primes p > 3, p equiv +/- 1 mod 6

[spiral radish]

Nopee..

[west glade]

you dont explicitly need that here

one way to go about this could be: check for which small primes p this holds. maybe you can spot a pattern

[spiral radish]

Ok thxxxxx

[little wigeon]

whats the alternative?

[west glade]

||mod 3, not mod 6||

[spiral radish]

No pattern spotted

[little wigeon]

oh right ok

[west glade]

that was 2 minutes of checking. try a bit more

for which primes p did it hold

[little wigeon]

thought you were going to pull some rabbit out of a hat

[spiral radish]

For those unpair

p>=3

But even after hours of trying out i cannot prove it

Thats why I’m asking for help

[west glade]

the key insight I wanted to get is that curiously the only small prime that you check for which it works is p=3

for all other primes p^2+8 is seemingly never prime

I wonder why

[spiral radish]

OH

[spiral radish]

I still don’t know how to prove this

[west glade]

3 seems to be special. the word modulo has also been mentioned

[spiral radish]

Ok ill think

[hoary shell]

It's a trick problem

Spoiler: ||Prove that it is never prime for p not equal to 3||

[unkempt void]

Woah Acman...

[little wigeon]

hihi !

hows it going

[unkempt void]

Gooood thanks yeah hru?

[little wigeon]

im well !!

[fervent night]

Hello guys
This is a very beautiful arithmetic problem
I found two proofs of it
Text me if you have solved the problem
i just translated the problem in english

[placid stratus]

can someone verify that state of the art probabilistic prediction of nth prime is < 1s and error ~ sqrt(nth) / 25?

[placid stratus]

also can someone verify (or refer me to a table) for the de bruijin count of 5 smooth numbers less than or equal to 2^49, i'm calculating it as 6164

[lapis dew]

very nice problem! i assume one of your proofs uses prime factorisation of squares but i dont know what the other could be, care to enlighten me?

[fervent night]

Yes of course

This is it in french because i study maths in french

[lapis dew]

oh coool i am bilingual i speak both french and english

[fervent night]

Oh nice

[lapis dew]

hmmm i kind of understand it, no offense but your handwriting isnt the best (but honestly i cant complain mine's worse)

I have a nice number theory problem for you though

[fervent night]

Hahaha i know
My teachers always noticed it .

Okay i will try.

[lapis dew]

don't worry its not too bad

Let a^3 + b^3 = 2^c

Prove that a=b

i managed to solve it myself

it was an australian math olympiad (AMO problem in 2016)

[fervent night]

A b and c are natural numbers ? Or real numbers ?

[lapis dew]

sorry positive integers

yes natural numbers

[fervent night]

Okay

[lapis dew]

but you can include 0

[fervent night]

Ok

[fervent night]

A real headache. Hahahaha

I found the solution just for odd numbers

Even numbers not yet

[steady glen]

Holà peeps,
I'm looking for online resources/books to start learning number theory :0
Any recommendations?

[lapis dew]

this is the key

you need to find an extension that links all odd solutions to even ones

[fervent night]

You want the basics of arithmetics ?

[steady glen]

yess

[fervent night]

I have courses in french

[fervent night]

Mmm okay i will see what i can do

[lapis dew]

okay you have done the hard part already

[fervent night]

Really ?

I think even numbers is the hardest part

[lapis dew]

yes showing that the only odd solution is when they are both one and equal

[lapis dew]

hmmm its hard to see but once youll see it will look simple

[fervent night]

I know i didnt write a good essay

Is the idea good ?

[lapis dew]

that looks good

i did a slight modification to this i think but this works

well done!

[fervent night]

Nice brother 👌

[lapis dew]

👌

[fervent night]

I have a problem if you want

[lapis dew]

want another slightly different one

lol mind reading

[fervent night]

Hhhhhhh

[lapis dew]

sure! want a mini math duel?

ill give you a problem you give me one

[fervent night]

My problem is about an exercise with many questions.
And i have to translate it to english

Oh

[lapis dew]

oh i see

[fervent night]

You say you understand french

[lapis dew]

yes

you probably dont have to translate

although i dont know the math language in french

ill see what i can do

i can speak fluently

[lapis dew]

hey guys so umm... please dont laugh but i have been working on the collatz conjecture

i have found some interesting structure

[placid stratus]

what is it

[lapis dew]

when encoding the structure of reverse accelerated odd steps i have been able to represent multiplication as nested sums

[placid stratus]

what is an "accelerated" odd step and what is the idea of a nested sum since summation is commutative

[junior swallow]

Could I have a hint on this problem? This is what I have so far: By induction on $n$. If $n = 0$ or $n = 1$, this is true. Suppose that the formula holds for $n - 1$. Then
\begin{align*}
\text{ord}_p(n!) &= \text{ord}_p (n \cdot (n - 1)!) \
&= \text{ord}_p(n) + \text{ord}_p((n - 1)!) \
&= \text{ord}_p(n) + [(n - 1)/p] + [(n - 1)/p^2] + [(n - 1)/p^3] + \dots
\end{align*}
Now, $\text{ord}_p(n -1 ) = \alpha = \text{ord}_p(n)$, so that $\dots$

[sterile pumice]

okeyokay

[rugged locust]

oh, you don't need induction for this

first question, how many numbers are divisible by p at least once, that are <= n?

[sly sand]

anyone hear know basic algebra to plot points and make lines I am kind of Dum

[junior swallow]

[n/p] numbers right

[rugged locust]

how many numbers are divisible by p^k, that are <= n?

[junior swallow]

uhh is it just [n/p^k] also?

[rugged locust]

now here's the big claim: v_p(n!) is just sum of all of them

{# of numbers divisible by p at least once} + {# of numbers divisible by p at least twice} + ... = {total amount of times p shows up in the product of n!}

[junior swallow]

Hmm okay thanks for the hint, it kind of makes sense but I'm trying to see why it's true (even intuitively)

Try in #prealg-and-algebra

[sly sand]

k

[junior swallow]

Can somebody please help me see why this is true? If $x_0 + jm'$, $x_0 + km'$ are two solutions where $0 \leq j < k < d$ and $x_0 + km' \equiv x_0 + jm' ; (m)$, then $m \mid (k - j) m'$. I don't see the contradiction.

Nvm, (k - j) < d, so m'(k -j) < m'd = m, so can't be divisible by m

[sterile pumice]

okeyokay

[rugged locust]

you can think about the block diagram

[junior swallow]

block diagram?

[rugged locust]

well young diagram but thats the fancy word for it

hold on

[rugged locust]

here I asked gpt to make the tikz code to visualise what I'm thinking

[sterile pumice]

HChan

[rugged locust]

v_p(n!) is the total number of boxes present

you are adding up the rows

[limber verge]

if f(n)= reminder when n^n is divided by 7 ,then find the min value of T (positive integer) where f(n+T)=f(n)

[kindred fulcrum]

There are two cycles in the base and in the exponent.

I mean the base has a cycle of 7

And due to Fermat there is a cycle of 6 in the exponent

So T=42 is a cycle

The question is if its minimal

[limber verge]

now i feel even more sad cause i got the right* answer but wrote the wrong one

[modest coral]

For all n, or for any n?

[kindred fulcrum]

All

[modest coral]

Yeah I believe 42 is minimal

(5+T)^(5+T) = 3 (mod 7), implies T is 0 or 5 mod 7.
(2+T)^(2+T) = 4 (mod 7) implies T is not 5 mod 7.

Then n^n n^T = n^n (mod 7), so 3^T = 1 (mod 7), so T = 0 (mod 6)

[hearty hornet]

A follow up question:

If f_m(n) = (n^n % m), where we take a % b to mean "remainder of a upon division by b,"
then is it true that for T = λ(n) * m,
f_m(n) = f_m(n + T),
where λ(n) is the Carmichael function?

[kindred fulcrum]

Yes

Its pretty much the proof

[hearty hornet]

Yeah, but this doesn't prove it's the minimal T, right? Just that that T works

for some m

also I guess my letters are wrong too?

like λ(m) * m is right

Is lcm(m, λ(m)) = T for any composite m?

[wanton gorge]

Hello! I read somewhere in a message that there’s something that helps you write formal proofs or something like that. I’m not sure if it’s an AI or something like that; right now I can’t seem to find the name.

[kindred fulcrum]

Lean

[wanton gorge]

Thanks

Guys, I know it is not april but I think I found a proof about Collatz Conjecture

But I don't know how to right it so I won't do it 🙂

[kindred fulcrum]

not to put you down but it probably doesn't prove collatz

[wanton gorge]

Don't tell me that 😢

[hearty hornet]

For all composite m, let f_m(n) be the function that maps n to (n^n % m). Let T > 0 be its period.
Is T = lcm(m, λ(m))? Can someone confirm or deny this result?

here T is dependent on m, so T_m if you will

[lapis dew]

would you be down to send it to me? I have been working on the problem and have many ideas and have seen many attempted proofs

[unkempt mason]

i dont think hes serious

[lapis dew]

yeah you're probably right

[wanton gorge]

Yes, it was a joke. Sorry to disappoint you, although I imagine you’re used to this kind of humor. I know that nobody really finds it funny.

But seriously, I’m genuinely interested in this problem and I have a question about it. I was reading somewhere and saw that several users mentioned a connection between the Collatz Conjecture and prime factorization. Could that be true? In what way are these two topics related?

[lapis dew]

if you could prove that the collatz function maniputates numbers in a way such that they can reach any prime factorisation then you would have proven that it hits all positive integers (because from the fundamental theorem of arithmetic, every positive integer has a unique prime factorisation)

[west glade]

if you knew how the prime factorization changes when you go from one number to the next one, then you could control how it changes when you do the 3n+1 step. and depending on how well you can do that you could maybe show that eventually the prime factorization has the form 2^k in which case you would be done

[limber verge]

collatz conjecture just seems so simple and elementary and yet it is still baffling mathematicians

[sacred junco]

skill issue

[limber verge]

prove it

i mean ik u saving it as ur first paper to publish but it wouldnt hurt to leak it a lil

[unique cypress]

Why is ENT brainrotted with Collatz

[unkempt mason]

Whats wrong with an entire field focusing on Collatz?

[unique cypress]

What field?

[unkempt mason]

oh wait you meant the channel?

[unique cypress]

yes

[unkempt mason]

oh then still i think its fine for a group to be focused on one problem

[unique cypress]

[kindred moss]

i will be geeked if they find an odd perfect number or a collatz loop in my lifetime

[wanton gorge]

Interesting. I was thinking about something related to the fundamental theorem of arithmetic but I couldn't get any further

[wanton gorge]

Very interesting

[wanton gorge]

Have you ever read the Enis Olgac paper about it?

[wanton gorge]

About Collatz Conjecture I mean

[kindred moss]

it seems sketchy that it has no citations

[wanton gorge]

But what do you think about his arguments?

[kindred moss]

umm i didnt read too closely but i also think its sketchy that the paper is like 3 pages long 😔

article

oh

thats annoying

okay this looks sketchy as hell now

uhh was this the paper you were referring to 😭

is there a way to embed link hmm

okay yay

[kindred moss]

this is the important part and this proof doesn't really make sense

[wanton gorge]

Yeah yeah that's it

[wanton gorge]

I guess you are referring to the proof by contradiction

That doesn't make any sense to me either

I found it very strange

But I think that inverting the tree is the way to go. I was playing with the Conjecture and I come up with the same idea before reading this paper

Funny thing happen when I was talking with GPT and asking him if someone has taken this approach before. I asked him for historical references y he come up with this

I was like: WTF, someone proof the Conjecture????
I he then he answers: My apologies for the earlier confusion. After a more careful review, I can confirm that the Collatz Conjecture remains unsolved.

Do not scare me like that dude 🤣

[loud maple]

GPT hallucinates a lot and is unreliable even when "just" asking it for references.

[half vortex]

Anyone here from nz?

[lapis dew]

yes also true, but the issue with the prime factorisation method is that when you meddle with both the additive and multiplicative construction of integers things get extremely convoluted (+1 messes up all the structure)

[hushed sable]

Can anyone help with a guiding hand in my number theory homework? I'm very tired and just need a starting point (the help channels say they're for pre-uni questions)

[rugged locust]

just ask the questions

[wanton gorge]

Yeah, but at least it's getting better if we compared it with a few years ago.

I'm sure GPT saw something like: "here we are gonna prove de Conjecture" or "we have proven the Conjecture" and assumed that XD

[halcyon spruce]

Is the marked area (with blue pen) of the proof even necessary? The theorem just asks to prove the uniqueness of q and r.

[kindred fulcrum]

its asks to prove existence and uniqueness

[halcyon spruce]

😅 ​True. I missed the existence part, sorry. Thanks for pointing it out.

[slim viper]

So for the extended eulcidean algorithm, there is a trick if a and b are coprime:

and it's this algorithm

but I dont understand why Pn=a and Qn=b

how could I go about proving this

I get the idea is kind of like this:

If we have:

a=q1b+r2
b=q2r2+r3
r2=q3r3+r4
...
r_(n-2)=r_(n-1)q_(n-1)+1
r_(n-1)=q_n

Then we can substitue the r_i up the chain to recover a

but it's like backwards from how the algoriothm proceeds

[wanton gorge]

Sorry to bother you, could you check this paper out? The thing is that it's in spanish and you have to translate it 😬

Anyway, I'm going to leave it in case you could check it out

https://www.safecreative.org/creators/work/27081

[lapis dew]

okay I'll have a look

[nocturne vortex]

could I have some help proving this? I see that I can apply the division algorithm first, and my thought is that either r is already less than half of b so that works, or r is greater than half of b so you can multiply q by (b+1) then use a negative remainder, but I'm not sure how to show it formally

[modest coral]

i would break it into two parts, showing existence and showing uniqueness

it's as you said, we have a=bq+r with 0 <= r < b by the division algorithm
if r <= b/2 we have shown existence. otherwise
a = b(q+1) + (r-b) and b/2 < r < b, which implies -b/2 < r-b <= b/2
this shows existence, using q+1 and r-b

you can multiply q by (b+1) then use a negative remainder
oh this was a bit off, you mixed up the q and b. other than that it makes sense

anyway, what remains is to prove uniqueness

[wanton gorge]

Oh thank you

If I have a positive integer n and I know the congruence of n modulo 5, is there any way to determine the congruence of (n/5) modulo 5?

[nocturne vortex]

Thank you!

[kindred fulcrum]

n/5 is not an integer unless n is divisable by 5. Then if you write n=5m, the question of what is
m mod 5
is the same as asking what is
n mod 25
and there are 5 perfectly valid answers (0,5,10,15,20)

[wanton gorge]

But isn’t there any way to narrow down that set of valid answers?

[kindred fulcrum]

Not unless you know more about n

[broken phoenix]

How do I find the last $2$ digits of $2023^{2022^{2021}}$ or any number and any number of digits for that matter?

I figured using mod (number of digits) (in this case $mod 100$ for last 2 digits)

But I don't know how to develop further

[sterile pumice]

danilojonic

[broken phoenix]

2023 = 23 mod 100

So the problem becomes $23^{2022^{2021}}$ mod 100

[sterile pumice]

danilojonic

[broken phoenix]

I've heard of Euler's totient function but I can't see why and how it's useful here

[kindred fulcrum]

Eulers theorem tells us that
for $\gcd(a,n)=1$ we have $a^{\phi(n)} \equiv 1 \bmod n$

[sterile pumice]

ExpertSqueeSQUEE

[kindred fulcrum]

So to find $23^{2022^{2021}} \bmod 100$ we need to find
$2022^{2021} \mod \phi(100)$

[sterile pumice]

ExpertSqueeSQUEE

[kindred fulcrum]

.

[broken phoenix]

Okay, but what do I do from here?

What is mod phi(100)

[kindred fulcrum]

phi(100)=40

[broken phoenix]

I don't understand how you got this

[kindred fulcrum]

There is a formula

phi(n) is the number of 1<=a<=n co-prime to n

You can use this and the prime factorization of n to get a nice formula

[broken phoenix]

Yeah I know that

So there are 40 coprimes to 100?

But how do I calculate that efficiently

[kindred fulcrum]

$\phi(n)=n \cdot \prod_{p \mid n} (1-\frac{1}{p})$

[sterile pumice]

ExpertSqueeSQUEE

[broken phoenix]

Ohh this is kinda familiar yeah

[kindred fulcrum]

The proof of this is usually using the Chinese Reminder Theorem

It reduces to showing the formula for prime powers

And there its easy

[broken phoenix]

What's p?

Can you show me how you used it in mod 100 example?

[kindred fulcrum]

100 = 2^2 * 5^2

[broken phoenix]

But crt relies on multiple coprime modulos

[kindred fulcrum]

So we multiply by
(1-1/2) * (1-1/5)

[kindred fulcrum]

The different primes dividing n

[broken phoenix]

Okay so 25 and 4 couldn't work because they're not primes even though they're coprime

[broken phoenix]

I don't have any intuition for this, could you explain CRT, little fermat and Wilson's theorem?

I never did any number theory so it's very weird for me to understand these

Like I can learn formulas by heart but I want a logical explanation why they work the way they work

[kindred fulcrum]

You know some group theory right?

[broken phoenix]

Yes but give me some topic to see if I know

I know groups, subgroups, homo-iso morphisms, cyclic...

[kindred fulcrum]

Some theorems from elementary NT are simply group theory results

Z/nZ is the integers modulo n, which is a cyclic group of order n

likewise there is a group (Z/nZ)* (the operation here is multiplication and not addition like in the last example)

Euler's theorem tells the order of (Z/nZ)* is phi(n)

[broken phoenix]

We write that group as $\mathbb{Z}_n = \left{0, 1, 2, ..., n-1\right}$ I guess it's the same thing just with different notation

[sterile pumice]

danilojonic

[kindred fulcrum]

Yes

If you learn some ring theory you will understand where my notatiom comes from

[broken phoenix]

alright that makes sense

[kindred fulcrum]

And fermat is the special case where n is prime

[broken phoenix]

is eulers theorem and function related to order of element in a group? Because I keep mixing them up

[kindred fulcrum]

Eulers function is the order of (Z/nZ)*

Which depending how you orginally define eulers function, is by definition or by eulers theorem

[kindred fulcrum]

Wilson is sort of unrelated to group theory but there are some grouo theoretic proofs

[broken phoenix]

I understand diophantine's equations and euclid's algorithm tho

[kindred fulcrum]

CRT is the assertion where if $$n=p_{1}^{k_1}p_{2}^{k_2}...p_{m}^{k_m}$$ the prime factorization of n then
$$\bZ / n \bZ \cong \bZ / p_{1}^{k_1} \bZ \times \bZ / p_{2}^{k_2} \bZ \times ... \times \bZ / p_{m}^{k_m} \bZ$$

[sterile pumice]

ExpertSqueeSQUEE

[kindred fulcrum]

Usually most proof give an explicit isomorphism

[kindred fulcrum]

Good for you

Anyway.. if you want to study all of this, you can google these things and read some about it online

Or you can pick up a number theory book and read it alongside learning Grouo Theory

[broken phoenix]

Not really atm I need it for my abstract algebra course, I don't quite understand why they included it in such limited way, it's only done for like 1-2 classes so I couldn't pick up much.

[junior swallow]

Can I have a hint to show that if gcd(a, b) = 1 and if d | ab then d | a or d | b

I know I can reduce it to Euclid's lemma somehow but I'm having trouble

[rugged locust]

if you can prove it for every prime divsor of d

then you have proved it for d

[junior swallow]

But what if some prime divisors divide a and some divide b ig

[rugged locust]

oh, wait, true

do you know anything else about d?

otherwise the statement just isn't true

[junior swallow]

No lol

It was just what came to mind when I saw this but wrong ig

I mean I guess it would be nice if every divisor of ab is of the form d_1 d_2 where gcd(d_1, d_2) = 1 and d_1 | a, d_2 | b

[kindred moss]

this kind of reminds me of how you can write the sum of divisors of a number by adding the powers of each prime factor and multiplying the sums together

if it was d instead of f(d) then that would be the exact answer right

and bc f is multiplicative and ur only ever multiplying powers of distinct primes together in the expansion...

all that's left to show is that every factor does appear in that expansion which i think just follows by a bijective argument/FTA

the final step there is to show that for

g(a * b)

if a and b are relatively prime then the "product of sums of prime factor powers" form for ab is just the product of the form for a * the form for b

which is easy to see in this form

[sweet lichen]

Anyone know resources to study number theory from basics to advanced? Like any Coursera course would be helpful

[kindred fulcrum]

It depends on what you consider advanced.... If you are looking for something on coursera there is probably a search functin there. If not there are some books you can read. If I rememeber Art of Problem Solving have a book on number theory. For more options you can go to #book-recommendations

[hushed sable]

can someone help me with this? I am stuck and I understand I will "factor out" a -1 k times and then the rest is wilsons theorem, but I am literally just confused because the left term has p-k terms and the right term has k-1 terms which are both less than the number I need if that makes sense

[broken phoenix]

how do I learn how to think with these tasks?

Examples:
Determine residue when dividing 11^33^55 with 41
Find last 2 digits of number 2023^2022^2021
Determine residue when dividing 13^19^2023 with 29
Determine residue when dividing 13!*7! + 2207^2647 with 2584

They mostly seem like the same type of tasks but I just don't know how to think through them since this is kind of strange and new to me, can anybody help me?

[hushed sable]

It is probably super easy

[hushed sable]

Use mod 100 and then Euler's Totient Theorem to reduce each exponent mod phi

[broken phoenix]

that's for the 2nd example right?

[hushed sable]

For the last two digits one, sry kinda tired

Yeah the others are just the same but different starting mod

[broken phoenix]

can you tell me like entire process? Why do the totient function and what after it?

[hushed sable]

It just makes the number smaller, take phi of phi of 41, then you can reduce 55 by that

not by that, like mod

gimme a sec to see what it is

[rugged locust]

hint, ||k == -1(p-k) mod p||

[hushed sable]

Right so phi(41) is 40 obvs because it's prime, then phi(40) is 16

So find 55(mod 16), then that can just be replaced

[kindred fulcrum]

you beat me

I was typing

[rugged locust]

fastest keyboard in the west

[hushed sable]

I'm so tired lol this is obvious after seeing it

@broken phoenix so then you have 11^33^7 and you take 33^7 mod 40 (bc phi of 41 is 40) and you work down the chain

Then use whatever other tricks you have on the remaining big numbers

[hushed sable]

Is this a theorem or proposition i'm supposed to know and recall, or are you guys just super smart and have done a million of these

[broken phoenix]

how do you find number of coprimes fast way? Like for 40 how did you know it was 16 or I need to count them manually?

[hushed sable]

There's a formula

[rugged locust]

it's barely a lemma, lol

I haven't done that many NT questions but there are patterns you pick up on

[broken phoenix]

n(1-1/p1)(1-1/p2)...?? where p1 and p2 are factors of n?

[hushed sable]

Yeah that's one of them, there's a few

@rugged locust Yeah I didn't mean that it's that serious but you get what I mean, I've been staring at this thing. Maybe it's the stress of it being homework and being sleep deprived

[rugged locust]

sometimes you just miss the obvious

happens to me

[broken phoenix]

okay so for 40, $5\cdot 8 = 5\cdot 2^3$ which then means $40\cdot(1 - \frac{1}{5})\cdot(1-\frac{1}{2})$ right? Do we ignore the powers (of 2 for example)?

[hushed sable]

@rugged locust So then I can multiply by k keeping in mind the congruence relation and then I can actually factor out the -1^k is the plan?

[sterile pumice]

danilojonic

[hushed sable]

Yeah basically, but you should be able to run the number and see what happens

You can think of it as subtracting from a running total by fractions of that total

40-8=32-16=16

ignore my abuse of notation guys

[broken phoenix]

so no need for CRT or Wilson or whatever?

just euler times and times again until idk

[hushed sable]

I mean you def don't need wilson, but sometimes you can use CRT on these once you get the numbers as small as they go

[kindred fulcrum]

you don't multiply by k, .... you just turn (k-1)!(p-k)! into (p-1)! up to (-1)^(k-1). each term in (k-1)! goes to p - itself

[hushed sable]

No need to get frustrated with me dog I'm multitasking and haven't looked at it yet

[kindred fulcrum]

I am not mad

[hushed sable]

The ellipse comes off mad but maybe cultural diff, no worries

[kindred fulcrum]

"I can be sad or bad or even rad! But never ever mad!" - Esquie

I was waiting for a chance to say this xd

[hushed sable]

@broken phoenix also keep in mind there are conditions of coprimality for Euler's, so sometimes you CRT to get coprimality

I am failing so hard, how do I turn (k-1)!(p-k)! into (p-1)! anything, are you saying I DON'T multiply anything new into the equation?

@kindred fulcrum

[rugged locust]

are you still stuck?