elementary-number-theory

[lunar laurel]

I don't know if that makes sense

[sharp shadow]

But what about all our examples? Class of equivalence is elements that share the same property (for example being even)

You are not replying to the content of anything that we said above :)

Anyway, it’s fine, I guess those examples and explanations just didn’t change anything

[lunar laurel]

True, im sorry, let me check it

[lunar laurel]

I think I've finally got it

like a clear image in my mind of what it is

So, a class is just a group of objects which are related by a equivalence relation?

[lilac bronze]

a bit more than that

you also need that everything outside the class is unrelated to everything inside the class

[lunar laurel]

Yeah, because if its related then it's in the class, right?

[lilac bronze]

mhm

[lunar laurel]

I mean

[lilac bronze]

if you represent equivalence relations as graphs, then equivalence classes correspond to connected components

[lunar laurel]

I see, but I mean, you cannot have something outside the class that has a relation with something inside the class

[lilac bronze]

yes

[lunar laurel]

yeah, because if it has relation with something inside in the class, then, that object must be inside of the class

[scenic vine]

Since $a\equiv \text{ Mod(a,n) } (\text{mod } n)$. If we have $b + \text{Mod}(a,n) \equiv c (\text{mod } n)$, can we rewrite it as $b+a\equiv c(\text{mod } n)$?

[sterile pumice]

Him

[kindred fulcrum]

Yes

[ionic latch]

(as a note, in general if you have $x \equiv y \pmod{n}$ you can replace $x$ with $y$ anywhere: $a + x \equiv a + y \pmod{n}$)

[sterile pumice]

Coolempire93

[scenic vine]

Thx

[scenic vine]

Yeah that makes sense. Thank you

[fossil agate]

Hello, I don't know if this goes in this section, I'm trying to rewrite the Trachtenberg Method for multiplication in hexadecimal, I only have get the times 8 rule: Reading from right to left, if the number is even add the half of the right number next to it, and if is odd additionally add 8. And if result greater than 15 carry 1

But with the C-12 base 10, I discovered a secuence on the product is 0, C, 8, 4.
I.e\
0 * C = 0\
1 * C = C\
2 * C = 18\
3 * C = 24\
4 * C = 30\
5 * C = 3C\
6 * C = 48\
7 * C = 54\
8 * C = 60\
9 * C = 6C\
A * C = 78\
B * C = 84\
C * C = 9D\
D * C = 9C\
E * C = A8\
F * C = B4

[fossil agate]

Any suggestions?

[elder dew]

are there infinitely many n such that (2n choose n) is coprime to 105?

[wide snow]

I believe so but it's not immediately obvious. How would you go about showing that (2n choose n) is coprime to 3?

[unique cypress]

Probably using Kummer's theorem + CRT will do the trick

[loud maple]

Is this not from the Erdős problems website?

[sharp shadow]

Indeed: https://www.erdosproblems.com/376 -- it's Open as of now, nice try @elder dew

Graham offered $1000 for a solution to this problem (as mentioned in [Gu04] and [BeHa98]).

the largest known such n is 24991943715007537, currently

[loud maple]

Seems like the site and problems blew up in popularity since the viral news that AI was used to solve a few of them.

[sharp shadow]

haha, now probably many people bombard AI sites with requests to solve those problems

[loud maple]

Yeah

[coral holly]

Alright so I'm a freshman in college rn and I'm a little desperate when it comes to math so I decided to study some Number Theory in order to do some research with my professor in the summer. Issue is, I can't understand what most of the questions are telling me to do, like I can't envision it. Mainly in this problem:

If I can get some tips for Number Theory that could help me through it that would be great :)

[wide snow]

For a), you need to verify the definition of a group for the set of powers of a. Track down that definition and work through what it requires.

What book is this? If you're a freshman this does not look like what I'd recommend to get into number theory

[coral holly]

It's a book my professor gave me called "Fundamentals of Number Theory" by William J. Veque

Idk if questions should be this hard on page 11 or im just stupid

[wide snow]

You're not stupid, I think the book is maybe assuming that you're a junior

[coral holly]

that would make sense

thanks for the help

[wide snow]

Sure - if it's the book your professor recommended, you can always try to work through it but jump to other books that are less terse along the way

[coral holly]

Wait so would that mean that, for example, for a^2, it would be a*a?

the * being the tiny circle thing

[wide snow]

Mmhm!

[coral holly]

I got that but I didn't thiink it was right bc of letter B

Idk what B is saying at all

[wide snow]

Do the hint first

(Hint to the hint: there are infinitely many positive powers of a, all in the group, and yet the group is finite...)

[coral holly]

that would only be possible if a was 1 right? Or do I have the wrong idea?

It's prob wrong since a is just anything

[wide snow]

Something is going to be one, but there are finite groups that aren't just boring

For instance, {0, 1, 2, 3, 4} where the group multiplication a*b = "the remainder of a + b divided by 5"

(Multiplication in the group is just a word for an operation - even if that operation is something else!)

[coral holly]

I feel dumber every second I don't understand this.

This is actually frustrating af

[wide snow]

Ask for a different book, would be my suggestion then

(I don't think I'd have gotten this via self-study as a freshman, fwiw)

[coral holly]

sigh I really wanted to be able to do this, but I guess you're right.

[wide snow]

This is elementary group theory (on which many treatments of elementary number theory are based), if you want to hunt down other resources or videos or such

But there are also number theory treatments that get right to the primes without digging into additional abstractions - that's what I do when I teach the course, for instance!

[coral holly]

yeah I kind thought I'd be playing with primes which is why I was excited, but I just ended up getting pranked by my professor :/

So like, what would I have to do to get to elementary group theory?

Like is there other aspects of math I need to know?

[loud maple]

Check out Abstract Algebra by Dummit and Foote.

[coral holly]

that's a crazy combination of names but thanks

[unique cypress]

Smart and Hand

[sharp shadow]

It’s not exactly the easiest book if he has difficulty with definition of a subgroup or order…

[loud maple]

I used it along with Artin when first studying algebra. I found it quite good and accessible.

[sharp shadow]

Yeah, I use and like it too, a great book

[sharp shadow]

You can check out Silverman’s “A Friendly Introduction to Number Theory”, it’s the friendliest one. https://www.math.brown.edu/johsilve/frint.html

Or Burton “Elementary Number Theory”

[wide snow]

Hungerford’s undergrad algebra book is quite accessible, from what I recall - and I think it focuses on number theory before abstracting to other structures

[coral holly]

The thing is my professor gave me this book bc I wanted to research with her during the summer. I didn't really know what to research so I just said number theory would be cool, and so she gave me her old book on it.

[kind patrol]

any good resources to learn modulo arithmetic

i really want to understand the concept

i can apply it to algorithms and problems but my understanding of the identities is very superficial

an example of my usecase of the topic (it might be much more than this in the future)

[ionic latch]

I really liked how our book (ENT by rosen) developed it but that's probably to heavy for what you need

I basically just reference my list of theorems from that book whenever I work with modular arithmetic now 😆

[kind patrol]

i just read the part on congruences, i like it

i can cover chapters 5, 6, and 7

[unique cypress]

Yeah I mean profs will just either make you read prerequisites or force you into their research

Unless you know what you're talking about

[midnight cloak]

What prerequisite math do you know already?

The idea of a group and subgroup should (I think?) Come a lot more naturally to you if you have studied linalg and know about vector spaces

If you are still intent on reading that book I can help you through the first exercise by explaining groups and subgroups to you

[coral holly]

pretty much nothing significant, I'm just learning calc 2 and I read a little bit of proofs and logic

[midnight cloak]

Is the textbook private? I can skim it to see if it's not written that well

[coral holly]

Like I said, I'm desperate to get into the complicated stuff, and waiting for the college to teach me it not ideal for me, so I try to force it almost.

[coral holly]

No, I have a file of the whole book

If u want I can send it somehow

[midnight cloak]

Well that's good; it's pretty difficult to shift from the computational stuff you've done your entire life to abstract stuff

Sooner or later you'll need to persevere

[coral holly]

After reading this book, that reality hit me like a truck

[midnight cloak]

Let me skim rq

[coral holly]

are you gonna find it urself or you need me to send it?

[midnight cloak]

Can you send in dms

I don't think I can find it on gogole frown

[coral holly]

idk if I can send a file that big

ill try tho

yeah nah

says its too big

I found the book online so I mean if you try it you should find it

[midnight cloak]

Is your professor requiring you to read the book

[coral holly]

If I want to do research with her during the summer, yeah. But I dont need to do it.

I literally asked her before leaving her office with the book if I need to know any other aspects of math and she told me no.

[midnight cloak]

Lmao

[midnight cloak]

So what precisely is troubling you with this problem?

[unique cypress]

That's a good thing. It's better to start things earlier

[coral holly]

If i'm being honest, I wish I started earlierer, like in high school. Cuz I didn't know math was "abstract" until I first got into college.

[coral holly]

I literally dont understand what it's telling me to do. Like it almost seems like it's in another language

mainly 2b and 2c, I already figured out a.

[midnight cloak]

2b is worded a bit weirdly

[coral holly]

It's not like I hate it though, if anything it made me love math more, but I really wish I had known.

[midnight cloak]

So a finite set has a finite number of elements right

[coral holly]

yup

[midnight cloak]

But the group generated by a is of form {..., a^-2, a^-1, 1, a^1, a^2, ...}

[coral holly]

right

[midnight cloak]

So if all these powers were distinct the set would be infinite

But it's a finite set

So are all the powers distinct?

[coral holly]

It wouldn't be distict since it's finite then right?

[midnight cloak]

No, the problem tells you it's finite

If your group is finite, any subgroup of it must be finite. Including the one generated by any element a

[coral holly]

that makes sense yeah

[midnight cloak]

The only way this set can be finite is if powers aren't distinct

Mathematically how would you say two distinct powers are equal?

if you let j, k be distinct positive numbers (let's just ignore the inverses for now)

[coral holly]

I actually don't know, I feel like the answer is obvious though

I'm actually pissed I cant figure this out

[midnight cloak]

My question might be a little ill-posed

Or like written poorly

Umm lemme think

[coral holly]

wdym how would I say they're equal "mathematically" if they're just equal?

[midnight cloak]

You understand though that the set is finite only if some of those powers are equivalent rigjt

[midnight cloak]

Just like a equality

[coral holly]

Only some? it doesn't have to be all?

[midnight cloak]

Let me give a more concrete example then

Let's say a^5 = a^2

[coral holly]

yeah

[midnight cloak]

Can you rearrange this to get 1 on the right hand side

[coral holly]

if you divide by a^2 on both sides then yeah

[midnight cloak]

Ok so you get?

[coral holly]

a^3

=1

[midnight cloak]

Yes

[coral holly]

wait so if you do that for all the powers they could all end up equalling 1?

[midnight cloak]

No no I'm just giving you a specific example in which a^2 = a^5

[coral holly]

oh ok mb

[midnight cloak]

This is not necessarily true for any subgroup generated by a, I'm just giving it as an example

[midnight cloak]

So now I want you to compute the following

a^0
a^1
...
a^7

All in terms of a if needed

[coral holly]

using a^5 = a^2 right?

[midnight cloak]

Yes

Or, as you showed, a^3 = 1

[coral holly]

a^0 = a^-3
a^1 = a^-2
a^2 = a^-1
a^3 = 1
a^4 = a^1
a^5 = a^2
a^6 = a^3
a^7 = a^4

so then that means for example that a^5 = a^2 = a^-1?

[midnight cloak]

No

Ok here wakt

[coral holly]

UGH

[midnight cloak]

No it's rigjt I think

Not what I intended

[coral holly]

Oh

[midnight cloak]

a^0 = 1
a^1 = a
a^2 = a^2
a^3 = 1

I should've specified that. Now continue onto a^4, ..., a^7

Ok wait sorry I didn't see that you did it alreadg

[midnight cloak]

So if you formed a set with these elements

You'd notice elements would repeat, but recall sets contain unique elements

So the set would look like {a^-3, a^-2, a^-1, a^0, a^1, a^2, a^3}

Since a^4 = a^1, it's already in the set

a^-4 = a^-1 which is also already in the swt

[midnight cloak]

And this is the only way that will happen if the subgroup were finite. One power must be equal to another in this subgroup if it is finite

[coral holly]

Ok I understand it

[midnight cloak]

So

[coral holly]

so since it's kinda like a loop it ends up being finite

[midnight cloak]

Yes exactly. There's a name for this subgroup btw, it's called a cyclic subgroup

[coral holly]

fitting name

[midnight cloak]

When a cyclic subgroup has a finite number of elements, multiplying by a multiple times will cycle you through the group

Ok now you're like basically already there

[midnight cloak]

In this proof, you need to explain that if G is finite, the subgroup generated by a is finite too (since subgroups are contained in the group G).

Then you need to explain why, if the group generated by a is finite, some powers must repeat.

After establishing some powers must repeat, fix two positive integers j, k with j > k such that a^j = a^k. Then rewrite into the form a^n = 1 for some positive n

Then I think you're done

Apologies for the confusing questions and stuff I'm not that good at helping, but I hope you understand how to do 2b now

I gtg so if you have other questions just ask in this Channel

[coral holly]

So the if I do a^j = a^k and I solve it for 1, which would be a^j-k = 1, a^n = a^j-k?

[coral holly]

Yeah no its ok you've helped me so much I appreciate it

[midnight cloak]

Yes

And j - k is a positive integer

[coral holly]

yeah, omg I got it. Thanks a lot again

[grand vortex]

whats the bestplace to learn elemenatry number theoryh

[cunning forge]

uni

[grand vortex]

online

[ionic latch]

With a pdf

Of a book

[quaint gate]

https://www.amazon.com/Number-Theory-Dover-Books-Mathematics/dp/0486682528

[quaint gate]

https://projecteuler.net/archives if you also like programming

[grand vortex]

is reading books that much better than videos

[ionic latch]

Usually I would say read the book, anywhere you need more context watch a video on it

In general the barrier to publication for a book is higher than a video, which (ideally) correlates with quality

Also generally videos usually are made to learn topics, not to learn subjects

If you find a series you'd need to make sure it also comes with exercises

and not just boohoo ones made to make the viewers feel good and like the video, real exercises so you learn

Meanwhile there are already well-touted books that have been published, reviewed, revised, passed through multiple editions

[sharp jolt]

tbh the best place to learn anything is taking a uni course if the prof is up to mark. my number theory prof is former Yale University assistant prof, 3 times silver medalist in IMO. he never follows a single number theory textbook. instead he has set out his own goals in the course:
classifying integers which are sum of two squares, then four squares and finally three squares. this is probably not the standard way to study NT but the course has been so original and mind blowing so far that he brought so many areas of mathematics together to prove many number theoretical facts and develop tools for our goals, although most of his work is algebraic. kinda feel blessed taking the course ngl. i've taken a NT course in my former uni as well but it was a standard course following David M Burton. the current NT course i am taking is a new exposure to the field in a very original way. i find it much more better to interact in class as well, online videos never clicked for me, but as they say to each their own. still I'd say having an actual expert in the field guide is the best way, and that is by taking a course. i am just talking about the best way, not the best way which can be compatible for everyone perhaps because many may be just learning NT on a whim and not professionally as a graduate student or just to do programming. again i am just talking about my experience with NT, might be different for everyone.

[unique cypress]

Pick up a book on abstract algebra

[upper igloo]

There are some things you just won’t find videos on

[upper igloo]

Chapter 3 of “A Primer of Abstract Mathematics” by Robert Ash gives an interesting introduction.

[grand vortex]

how do yall feel abt underwood dudly number theory

[lime lotus]

you could also try michael penn and his course playlists (he has his main channel and a 2nd channel called MathMajor and he has a number theory playlist as well)
books are definitely more in depth but i personally think its best to have both

[compact swift]

i had readed this way way back but honestly i find it a pretty good introduction to i suppose elemetary nt.

pretty basic, easy to follow for me. So i think anyone could follow it if they took the time

[spiral tendon]

you need sufficient background in the subject to appreciate these kind of approaches.

else you just get more confused.
With some good background, a great teacher always helps.

[hoary karma]

analytic number theory?

[sharp jolt]

little bit ig he brought calculas, algebra, graphs, combinatorics together, even measure theory. this is just an elementary course, we have separate courses for algebraic and analytic. but since he's an algebra guy, he does his things algebraically mostly.

altho he likes to make the course as hard as possible, but it's still by book the first course in number theory at our uni

[hoary karma]

What topics are being covered now

[sharp jolt]

we shall classify all numbers that can be expressed as three squares now, we'll start with quadratic reciprocity to that end and then we'll learn quadratic forms over Z and dirichlet's thm on primes in arithmetic progression to classify them

[sharp spruce]

Howdy, I'd really appreciate some help in something (it's late so I can't get my professor's help now):
We're building up in class for proving the existence of a primitive root in multiplicative groups mod p.

Now, the prof introduced a lemma:

let q be any prime factor of p-1, and suppose q^e divides p-1

Then there exists an equivilence class/element a in Z/pZ* where a has order exactly q^e

I'm confused because the proof the professor provides (copied from my notes) is this:

consider b (equivalence class) an element in the set {b | b ^{q^e} = 1} and {b | b ^{q^{e-1}} = 1}

Then the 1st set is the set of roots x for x^{q^e} -1 and q^e divides p-1 so the set has q^e elements (this much I understand)

Similarly the 2st set has q^{e-1} elements (this much I understand, too) which is fewer elements

So there exists an element a in the 1st set i.e. the order is one of 1, q, q^2, ... q^{e-1}, q^e

but a is not in the second set i.e the order is NOT one of 1, q, ... q^{e-1}. So the order of a is exactly q^e

MY question: It feels a bit artificial the way we defined b to be in both of the sets. Where did this come from? Because I don't quite get the initial definition, my understanding of how we arrived to the conclusion is a bit shaky even though I understand why the elementary pieces along the way work.

I appreciate any help 🙂

[kindred fulcrum]

b looks like just a name in the set-builder notation, and is not used outside of that.

so the argument is: One set has more elements than the other, so there is an element in one set which is not in the other set, which is exactly what you want.

[sharp spruce]

Fair thanks! I get it 🙂

[hoary karma]

Looks like apostal content

[sharp jolt]

might take a look

[hoary karma]

apostal is good for before going to analytic number theory, so might be possible

[broken phoenix]

Clumsy repost

[whole goblet]

write 1002 = -995, 1003 = -994, etc, and factor out the -1s and voila you have 995!

[broken phoenix]

How did you get it though?

Is it just (1002-1997)...

And how do you count them?

So you count 1997-1002 or 1996-1001, I don't know where the count starts for how many elements we've transformed.

And we're going to -1 so 1996 is the end

So it's either 1996-1001 or 1996-1002 elements

Asking that because of sign (-1)^k

[whole goblet]

yeah you start at 1002 and end at 1996, so 1996 - 1001 = 995, is the number of (-1)s at the end

[eager silo]

There are multiple places that I can ask this, but I guess I'll ask it here
Is there a way to find a formula for what I'm deciding to call the "sub-subfactorial", which is the amount of permutations of {0, ...., n-1} (addition here is modulo n, so n-1 + 1 = 0) such that no number gets sent to itself or itself + 1

[ionic latch]

@buoyant mason

[eager silo]

The main thing I'd want is a recursive formula like n! = n * (n-1)! or !n = (n-1) * (!(n-1) + !(n-2))

[patent acorn]

for n >= 4, it's defined by the recurrence a(n) = n * a(n-1) + (n * a(n-2) - 4 * (-1)^n)/(n-2), according to the OEIS

i have no idea why

but i checked up to n=10 and it does seem to work

[ionic latch]

checking the OEIS as if it would ever be wrong is crazy work

[eager silo]

You dareth challenge our sequential gods!

[eager silo]

has anyone went beyond +1, and in general, what work is there on these weird permutation counting functions

[west glade]

I have seen variations of this questions in a book on combinatorics. maybe stanley, enumerative combinatorics? not sure

[west glade]

yes, see section 2.3

in fact, example 2.3.3 is your question

[limber holly]

So

Yeah

Number theory!

Actually its my favourite in maths

after geometry

Does anyone here do AoPS?

[warped tendon]

i did it when i was younger

[limber holly]

is it good?

[cunning forge]

whats that

[limber holly]

its a website

[rugged pasture]

Find all $m,n$ and $k$ integers such that $\newline\newline n-k|m+k\newline n+k|m-k$

[sterile pumice]

Vanellope von Schmugz

[rugged pasture]

@opal marsh @ionic latch @patent depot Noticed this pattern when watching a video and decide to formulate it as a problem. I haven't completely solved it yet but got some progress. I'm rusty in number theory. Deriving some lemmas again

[rugged pasture]

I like Alcumus and the books

[ionic latch]

Interesting

[rugged pasture]

by the time you spent typing, I thought you were about to send the solution lol

[rugged pasture]

no spoilers haha

[ionic latch]

Haha not the solution, just working through some constraints, like m >||= n + 2k||

[rugged pasture]

saw that one, did nothing with it

[rugged pasture]

I'm trying to demonstrate the lemma ||a|bc, (a,b)=1=>a|c|| again, but I'm not sure whether I'll be able to use it. Maybe I'll weaken the original problem so I can use to see if I get to some final answer

[minor musk]

Using Wilson theorem Prove \ $(i)1^2 3^2 5^2...(p-2)^2 \equiv (-1)^{\frac{(p+1)}{2}} (mod p)$ \ $(ii)2^24^26^2...(p-1)^2 \equiv (-1)^{\frac{(p-1)}{2}} (mod p)$

[sterile pumice]

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

[carmine tide]

In the future, please show what you've done so far when asking for help along with any other relevant context - it gives us more to work with and saves time from explaining things unnecessarily. \ \

Assume $p$ is an odd prime. \

\begin{subparts}
\subpart Note that
\begin{align*}
p-1 & \equiv -1 \pmod{p} \
p-3 & \equiv -3 \pmod{p} \
\vdots \
2 & \equiv -(p-2) \pmod{p}
\end{align*}

\subpart This is false for $p=3$.

\end{subparts}

[sterile pumice]

Civil Service Pigeon

[minor musk]

I tried this

[minor musk]

No idea how to proceed after this

[minor musk]

Ok

[rich meadow]

Why do operations on congruences such as division, roots, etc require the modulo to be prime (or the divisor and the modulo to be coprime in divisons) ?
For example if I were to say 6
4x² ≡ 4 mod 8
What makes this different than if the modulo was prime let's say 5 for example

[carmine tide]

“Dividing” is really the same as multiplying by the inverse. Now recall the condition for an inverse to exist.

[rich meadow]

I'm not sure I understand this
Wouldn't that be just that the inverse multiplied by the number = 1, and that the number is different than 0?

Unless I'm having a different idea of an inverse

[rugged locust]

the difficulty is that inverses are only guaranteed to exist when you taking modulo a prime

[lilac bronze]

Are you asking about $4 x^2 \equiv 4 \pmod 8$

[sterile pumice]

Pseudo (Cat theory #1 Fan)

[rich meadow]

That's just a random example but yes ig

[lilac bronze]

A nice way to think about this is

This is equivalent to $8 | 4 x^2 - 4$

[sterile pumice]

Pseudo (Cat theory #1 Fan)

[lilac bronze]

You can show this is equivalent to $2 | x^2 - 1$

[sterile pumice]

Pseudo (Cat theory #1 Fan)

[lilac bronze]

I.e. $x^2 \equiv 1 \pmod 2$

[sterile pumice]

Pseudo (Cat theory #1 Fan)

[rich meadow]

But is that different than the original one?

[rich meadow]

Is that a property of prime numbers?

[lilac bronze]

This is equivalent to the original one

[rugged locust]

yes

[lilac bronze]

Its equivalent to being prime in fact

That everything nonzero mod n is invertible

[rich meadow]

I guess that kinda makes sense

[lilac bronze]

(Well apart from n = 1)

[rich meadow]

I assume this holds generally for coprime values?

But what about square roots for example

[lilac bronze]

Yes because of bezout’s identity

[lilac bronze]

I think even for primes this is weird

$x^2 \equiv -1 \pmod p$ for example

[sterile pumice]

Pseudo (Cat theory #1 Fan)

[lilac bronze]

I think this equation has solutions only if p = 2 or p = 1 mod 4?

[rich meadow]

I'm not sure I understand the second solution, but my idea is that you generally can work around division and multiplication algebraically
So for instance, division might not hold because if you have something like $4x \equiv 2 \pmod 8$
Then that's just $4x = 8k+2$ for any integer k
Then you can divide the whole equation by 4 and make adjustments to the k value

[sterile pumice]

ScoobySnacks

[lilac bronze]

You may be interested to know the following

[rich meadow]

But this doesn't work out with square roots, similarly it doesn't always hold logically

[lilac bronze]

$a | bc \iff \frac{a}{\text{gcd}(a, b)} | c$

[sterile pumice]

Pseudo (Cat theory #1 Fan)

[rich meadow]

Sounds about right

[unique cypress]

When the modulus is not prime you have to be careful since you can't always invert elements. The reason you can always do this when the modulus is prime is because you are working over a field so every element has an invertible element for free

[granite sky]

I solved 9.a but have absolutely no clue how to handle the rest of them

[ionic latch]

that's a nice theorem

[granite sky]

I have tried for multiple hours to solve it and also took the help of ai and have basically gotten no lead on 9. b

[ionic latch]

Sadly I don't know about the formal/proofs side of continued fractions, so I can't help you 😔 but I would wonder how you proved D is periodic without being able to prove (b) that the continued fraction is periodic

[granite sky]

I basically used the pigeonhole principle

And that each term is determined by the previous term (I haven't properly expressed it but I hope you can get what I'm saying)

[ionic latch]

Hmmm

By inspection I see this is true but this is also somewhat simple for square roots

I must be taking a lot of shortcuts if this is a hard problem based on what the tools you have available

[ionic latch]

If no one comes by to help I'll look at the continued fraction part of my number theory book and see if there is a theorem that can help you maybe something that encapsulates the process I am using

[rich meadow]

Hello everyone 👋

So I've come across this issue where if you have an equation of the form

ax + by = c
I usually would solve this using congruences such that:

• x ≡ c (mod b)
• y ≡ c (mod a)
  Which generally works, but I've always had some inaccuracies which I've come to realize why
  So when it happens to be the case where there's only one form of solutions, the constant k can differ. For example:

x = bk + d
y = ak' + p
It's easy to overlook the fact that k and k' aren't the same

And the solution I've come to is that my method is incorrect and that it's not always correct, instead I should be substituting my x (or y) values in the main equation to get the y (or x) expression

But now I'm having a different issue, which is when is it the case that substitution is enough and when do I have to solve for x and y separately

My only note is that when b is negative, the k value is followed by opposite signs + and - for x and y

Which might be the case as to why there are different forms of sols

[wooden glen]

I think, assuming a and b are coprime, the usual approach would be to solve ax+by = 1 using the extended Euclidean algorithm, and then multiply by c. That gives a single solution (x0,y0), and the other solutions are then (x0+kb, y0-ka) for integer k.

[rich meadow]

So basically finding a specific solution and then solving a system of linear equations?

[wooden glen]

Yeah.

(Of course if a and b are not coprime, then c had better be a multiple of their gcd, and you can divide through by the gcd before solving).

[rich meadow]

Ok I still get two different sets of solutions nonetheless

So you get:

a(x-x0) + b(y-y0) = 0
That gives either

• (y - y0) ≡ 0 mod a
• x-x0 ≡ 0 mod b

Which is essentially two different solutions upon substituting

Two sols for (x ; y)

(for any integer k ofc)

So I guess my question is that, is it always the case that you find two possible sols? And if it isn't (you find only one sol), how can you tell?

[west glade]

its not the same k in both formulas

both families are the same (i.e. if you consider the sets you get when you plug in all possible integers for k, you get the same sets)

you can write 7k+5=7(k-1)+7+5=12+7(k-1)=12-7(1-k) and if you now set m=1-k then this is just 12-7m so just the second formula

similarly for the other formula

@rich meadow

[rich meadow]

Oh so one suffices?

That's interesting

I feel like it's intuitive to ask, why is it so different?

[west glade]

flip the sign of the k and they already look near identical to me

[rich meadow]

Yeah that was interesting, it almost makes so much sense

That's why I could notice the "second formula" more when ax and by had the same sign ++/--

Because the k values had to be of opposite signs, therefore it looked very different than usual

But I guess that's very relieving

Thank you

[west glade]

yw

[open tangle]

where can i learn modular arithimetic online?

[quaint gate]

any number theory book

[open tangle]

nothing online?

ok i guess

[jade vessel]

silverman a friendly intro to number theory

golden book to start off

pun intended

[lime lotus]

you can also find a playlist over it on youtube or something
michael penn or richard borcherds are some good people with playlists over number theory in good depth

[spring light]

Can anyone have a look at this?: We call a polynomial P good mod n if all the coefficients of the polynomial are coprime to n and P(x)=0 (mod n) for all x coprime to n. Let d(n) denote the minimum degree of a good polynomial mod n. How can you efficiently determine d(n)? Its a little vague but basically reduce the problem to something so that we can compute d(n) for n<100 in a reasonable amount of time

so far I have just found 2λ(n)-1>=d(n)>=max prime dividing n - 1

[wooden glen]

Hmm. If n is odd I think given one solution you can always find a polynomial with any larger degree that is also a solution, so then we can just look at prime-power n and take their maximum.

[spring light]

how do we increase the degree?

[wooden glen]

I've only fully thought through the case where n is a prime, but then we can just either add or subtract x^k - x^(k-p+1), according to which direction won't kill the existing coefficient of x^(k-p+1).

(This immediately generalizes to odd squarefree n by the CRT, of course -- prime powers may need more thought).

[spring light]

right

i feel like it works for prime powers too no?

it cant be that c+1 and c-1 both are divisible by odd p

where c is the coefficient of the smaller degree

[wooden glen]

My gut feeling is it does too, but I can't rattle off a proof just yet.

(I'm not completely sure how far I can stretch the gut feeling, because Z/p^m is not an integral domain, so e.g. the usual rule about how many roots a polynomial of a given degree can have is not available).

[spring light]

like if n=9

then -1-x-x^2...-x^5+x^6+x^7+...x^11

(lambda(9)=6)

so we add x^12 - x^(6) or add -x^12 + x^6

latter here

like it always works

https://math.stackexchange.com/questions/3387540/polynomials-that-induce-the-zero-function-mod-n

this gives that d(2m) = 2

if m odd

we take m(x^2+x) because x^2+x is always even

wait no

mb

doesnt work

[wooden glen]

I agree that that polynomial of degree 2lambda(n)-1 has to work -- but I'm not yet quite convinced it's always necessary to go that high when n is a prime power.

[spring light]

yeah its mainly more of a proof of existence than a good upper bound

a problem is that since i cant come up with an efficient algorithm i dont have a good table of data to conjecture with

[wooden glen]

So with my extension property above we can improve 2lambda(n)-1 to max of 2lambda(p^m)-1 where p^m ranges over the prime-power divisors of n.

On the other hand, even if some p^m has a solution of degree smaller than 2lambda(p^m)-1, we can't necessarily extend that to every higher degree, so just taking max of d(p^m) may not always work.

[spring light]

i dont get that

[wooden glen]

For a concrete example, suppose n=49. Then we know the systematic solution mod 49 would have degree 2·6·7-1 = 83. But for all we know so far, it might be that by some fluke there is a solution mod 49 of degree 35. If there is, then it's not given that we can extend that to have degree 36 too, because we only know how to introduce terms modulo 49 if there's already a term 41 degrees below it to cancel it out.

[spring light]

right

hm

so when d(p^k) < phi(p^k)

[wooden glen]

Only when p=2 and k>=3, I think.

Sorry, I mistook d for lambda there for a moment.

[spring light]

all ok

such a polynomial has more roots than degree

but that is definitely possible

[wooden glen]

When p^k is an actual prime -- that is, k=1 -- I think we're good. If there was a solution of degree < 2phi(p)-1 = 2p-3, then we could reduce that to some polynomial of degree p-2 (not necessarily with nonzero intermediate coefficients) with p-1 roots mod p, which is not allowed. So in that case the 2phi(p)-1 bound is tight.

[spring light]

so you're saying that firstly d(n)>=p-1 (as stated before) and if d(n)<2p-3, we can reduce every power >=p-1 to a power <p-1 and not affect the coefficient of p-2 (which is nonzero), thus we dont get a zero polynomial

nice!

does that mean d(p) =2p-3?

this also gives an explicit solution for odd square free numbers

[wooden glen]

Yes, that's how far I've gotten.

Even squarefree numbers too, because being a solution mod 2 only requires that the degree is odd, and 2p-3 is that.

[open tangle]

ok

[spring light]

wait i dont exactly see how we can directly combine the polynomials with CRT. by your extension property, we can increase their degree but the polynomials for every prime wont necessarily be the same coefficient wise

[wooden glen]

No, but use the CRT on each coefficent, to get a combined coefficient that equals the original ones modulo each p.

[spring light]

ahhh

i get it

[spring light]

d(9) < lambda(9)

P(x) = 1 + x + x^2 + x^3 + 7x^4+ 7x^5 works

so you are right the extension does not necessarily work for p^k

(btw d(9)=5)

[wooden glen]

Yes, I was just about to post the same solution, calculated independently.

[spring light]

lol

the next non square free odd prime power is more difficult to brute force

[wooden glen]

The next one to try would be n=25, which is a heck of a matrix to row reduce ...

[spring light]

i wish i knew the magic to do these

[spring light]

this was brute force nothing clever about it

maybe ill write a program in c instead of python

[wooden glen]

(1+x+x^2+x^3)(1-2x^4+x^8) = 1+x+x^2+x^3 - 2x^4 - 2x^5-2x^6-2x^7 + x^8+x^9+x^10+x^11 works modulo 25.

[spring light]

wow fast

[wooden glen]

(And this is actually too short to be extended by adding/subtracting a binomial).

Actually 1-2x^4+x^8 is already 0 mod 25 for all coprime-to-25 inputs; the other factor is just to make every coefficient nonzero.

[spring light]

huh

thats a good way to get solutions

thats (1-x^4)^2

[wooden glen]

Ah, neat.

[spring light]

so if we look at (1-x^{p-1})^2(1+x+x^2+...x^{p-2})

at least for p^2

an upper bound is 3p-4

it can be generalised

p^n is (n+1)p-n-2

[wooden glen]

I found the above by deriving conditions on the coefficients for n=25 by Gaussian elimination, and the pattern I see looks like there are actually solutions for all degrees >= 11 .. even though the simple extension method I proposed first won't work.

[spring light]

oh this may not work for n>2 (binomial coefficients not coprime)

[spring light]

hm

[spring light]

this works for n<p

[wooden glen]

Yeah, then the binomial coefficients in (1-x^(p-1))^n start vanishing.

[spring light]

which is (almost) always less than lambda(p^n)

a similar thing could be achieved by taking the solution in p and raising it to the power n

(though the bound is worse)

[wooden glen]

I'm not sure, there might be a risk of cancellation in the middle coefficients.

[spring light]

well we could apply the multinomial theorem

which p much guarantees they wont

[wooden glen]

That's more than I can visualize without reaching for paper. :-)

[spring light]

i was thinking about degree p^2

i think it is the case that if the degree is <3p-4

the polynomial looks like $a_0 + a_1x + a_2x^2 + ... + a_{p-2}x^{p-2} -a_0x^{p-1}-a_1 x^{p} ...-a_{p-2}x^{2p-3} + ...$

wait i might be wrong

[sterile pumice]

CherryMan

[spring light]

yeah i made a mistake

but it will be true if degree <2(p-1)

btw 3p-4 = 3(p-1)-1 which is kind of interesting

also i think this proves that d(p^2) > 2(p-1)

which we knew already

:(

ignore all this then

[rich meadow]

Quick question:
Consider a congruence of the form

ax ≡ b (mod n)
So we say that this has solution if gcd(a,n) (let's call it d) divides b, so d|b

Apparently from what I've seen, we should get d many solutions, each separated by the integer (n/d)

So if we have

5x ≡ 20 (mod 50)

• We have sols since 5|20
• We should get 5 solutions separated by 50/5 = 10

We get:

x ≡ 4 (mod 10)

So here's what I don't get

Supposedly we write this again with the original modulo then we add 10 each time to the remainder; so:

x ≡ 4 (mod 50)
x ≡ 14 ≡ 24 ≡ 34 ≡ 44 (mod 50)

And those should be our 5 solutions

So my question is, wouldn't it suffice to just go off of:

x ≡ 4 (mod 10)
And therefore: x = 10k + 4 for any integer k

And this should cover all 5 solutions?

[golden pebble]

This:

34 ≡ 44 (mod 50)
makes me go "whaa??"
But I do understand what you mean. FWIW, I think x ≡ 4 (mod 10) is correct (and good enough)

[wooden glen]

You don't get that x ≡ 14 (mod 50) and x ≡ 24 (mod 50) are the same solution, just that both of them are solutions.

[rich meadow]

Yeah I meant to say

• x ≡ 4 (mod 50)
• x ≡ 14 (mod 50)
• x ≡ 24 (mod 50)
• x ≡ 34 (mod 50)
• x ≡ 44 (mod 50)

[rich meadow]

It all boils down to x = 10k + 4

The rest are just different k values

I just happened to hear that there exists x many solutions, which I presumed was x many forms of solutions

[wooden glen]

I agree with ElNando that "x == 4 (mod 10)" is a perfectly good description of the solution set. Unless perhaps you were specifically looking for solutions as elements of Z/50Z.

[rich meadow]

Aight, thanks a lot 🫡

[spring light]

i think this is as far as we go

[wooden glen]

By my calculations from yesterday, (1+x+x^2+x^3)(1-2x^4+x^8) is optimal for n=25.

[spring light]

i think that just gives d(25)<=11 no?

also interestingly for the composite numbers it is the maximum of d(n) over all divisors n of that number

like d(16) = d(8) = 3

d(20) = d(10)=d(5)=7

[wooden glen]

No, because my program (doing partial Gaussian elimination mod 25) actually gave me exact relations the coefficients need to satisfy:
a0 + a4 + a8 == 0 (mod 25), a4 + 2a8 == 0 (mod 5)
a1 + a5 + a9 == 0 (mod 25), a5 + 2a9 == 0 (mod 5)
a2 + a6 + a10 == 0 (mod 25), a6 + 2a10 == 0 (mod 5)
a3 + a7 + a11 == 0 (mod 25), a7 + 2a11 == 0 (mod 5)

[spring light]

oh alright

[wooden glen]

Basically treating the system
a0 + 1·a1 + 1²·a2 + .. + 1¹¹·a11 == 0
a0 + 2·a1 + 2²·a2 + ... + 2¹¹·a11 == 0
a0 + 3·a1 + 3²·a2 + ... + 3¹¹·a11 == 0
...
a0 + 24·a1 + 24²·a2 + ... + 24¹¹·a11 == 0
as twenty equations in the unknowns a0, a1, ..., a11, and then applying standard methods from linear algebra to describe the solution set.

[spring light]

can you link any resources that would tell me how to implement this

[wooden glen]

Many textbooks in linear algebra lead with a description of this early on. A good keyword for a web search would be "Gaussian elimination".
The textbook methods are only phrased for cases where the coefficients come from a field, which the integers modulo p^2 unfortunately isn't. I had to deal with that by ad-hoc workarounds, which I'm not sure are described anywhere, and they worked out nicer in this case than I think I had any right to expect a priori.
(Namely: sometimes allow a pivot element to be 5 instead of 1, and accept that it cannot clear rows above and below completely. The equation I described as a4 + 2a8 == 0 (mod 5) above actually came out of the matrix as 5a4 + 10a8 == 0 (mod 25)).

[west glade]

you can use the hermite normal form over Z which would give you a row-reduction and doesnt lead to fractions, although the numbers might explode

maybe a sequence of compute hnf, reduce mod, compute hnf, reduce mod, ... might give you a good system

[ionic latch]

<@&268886789983436800>

[gentle mountain]

jesus fucking christ, I'm a Sonic fan, rings shouldn't be giving me trouble

anyways I'm forgetting what number theoretic transform (NTT) is supposed to be doing and how I should be implementing it even though I studied rings before in my postsec math courses and cryptology

[unique cypress]

[wanton gorge]

Is there any relation between 2-adic numbers and Collatz Conjecture?

[unique cypress]

[rugged locust]

It’s true though, the collatz conjecture are about numbers and the 2-adics are also numbers

[supple acorn]

idk why yall are reacting like this, there are pretty deep connections tmk

im not well educated on them though. I've only like. researched something adjacent before

[supple acorn]

i think one research direction that often tends to be pursued is how, yeah, it's pretty straightforward to extend the collatz map from Z to Z_2 (the 2-adics) and then from there people do dynamic systems analysis stuff

I'd say more but, the reason im not well educated on it is cuz im not a dynamic systems person

you might want to ask in that chat

[supple acorn]

but in particular, to do collatz, you really just need a way to

• multiply by 3 and add 1
• determine if a number is even or odd
• divide even numbers by 2

note that for p-adics with p>2, there won't be a sense of even vs. odd because then 1/2 is a p-adic

i can elaborate if needed, idk your knowledge level

[supple acorn]

well okay what i can say is this: the benefit of extending to Z_2 is that you get a lot more topological structure to work with. a huge part of dynamical systems is studying the topological behavior of maps from a space to itself, so a lot of tools can start being used that couldn't be used on Z. the downside ofc is that they don't actually resolve collatz lol

[wide snow]

At least for me the reaction was less to do with the 2-adics and more a gut reaction to Collatz

As 99% of discussions of the problem lead to crankery

[supple acorn]

ok i won't lie. on one hand, i was gonna reply saying "that feels like it could throw the baby out with the bathwater", but then again, i searched OP's message history, and i am realizing that they are actually someone who claims to have proven collatz

ok, here's my argument for taking the question seriously anyway. firstly, i think it's pleasant to be encouraging, especially in a good direction, as opposed to just saying "no dont do that"

secondly, i think there is interesting mathematics to talk about here

[wide snow]

I think that is the right approach to every problem but Collatz XD

I think we can and should warn early stage mathematicians "if you work on this you will be seen as a crank, build a reputation first"

[supple acorn]

i would argue that "trying to prove collatz" is actually a healthy activity when treated as a "im probably not gonna do this and im just trying to get a sense of why it's so hard", the issue is when people get stuck on it

on the other hand im being naive. you're right that there should be a clear reputation warning

[wide snow]

Yeah, the path is lined with skulls 💀

[supple acorn]

well put

anyway im a little heated cuz i have an emotional connection to specifically using ring completions to study collatz

[south storm]

i proofed collatz

[supple acorn]

when i was first learning ring theory, i rediscovered an obscure result from 1987: there's actually a known nontrivial example of an unbounded collatz sequence in the ring F_2[x], if we use a multiplication factor of x^2+1 instead of 3, and divide by x instead of 2

i only found that what i had found had been found already after the fact but. it was fun

the reason is that the orbit actually converges x-adically, i.e. in F_2[[x]]

[supple acorn]

also i didn't prove it, i just found it computationally

https://www.sciencedirect.com/science/article/pii/0022314X87900321?via%3Dihub

if yall are curious about the details. (obviously i wasn't alive in 1987 but i should probably link the people who found it first rather than my own writings lol)

tl; dr i personally has a positive experience w/ thinking about collatz stuff, although maybe i should accept im in the minority

[wooden glen]

So the Collatz conjecture is false if you ignore (binary) carries.

[supple acorn]

essentially
well, it's true if you naively use x+1 as a multiplication factor, just by a degree argument

[wooden glen]

Ah, x^2+1 rather than x+1. Missed that. So it's the 5n+1 version that would be false.

[supple acorn]

yea

i believe x^2+x+1 is open still

and probably just as dangerous to one's career

there's a paper from 2006 that proves asymptotics on it though

[silk ibex]

10/10 grammar

Proved*

[wooden glen]

You proofed Frog.

[gleaming creek]

I am curious as to what the author meant by the last statement.

[carmine tide]

,w (1003/2)^2 - (1001/2)^2

[sterile pumice]

Results provided by WolframAlpha

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

Requested by civil_service_pigeon

[carmine tide]

[ionic latch]

I wonder what exactly exercise 64 has in it

rationals are closed under addition but $1002 + y^2$ is always irrational

[sterile pumice]

Coolempire93

[gleaming creek]

[gleaming creek]

yeah

[carmine tide]

so um

[ionic latch]

also does modular arithmetic even work properly in fields

I feel like you need a ring specifically

since a field is more than just a euclidean domain

it's a PID

[gleaming creek]

true but well the exercise is from the first chapter called "Integers" from a book on Abstract Algebra, so I suppose the reader is not expected to know rings and fields

[ionic latch]

Thankfully you don't need to know algebra to know hypocrisy

[carmine tide]

all nonzero elements are units

um

that's the end of my thoughts

[ionic latch]

Yeah

That's the issue

[carmine tide]

pigeon.exe has stopped working

[ionic latch]

$a = kb$ is satisfied by everybody

[sterile pumice]

Coolempire93

[ionic latch]

Because b always has an inverse

well nonzero blablabla

[gleaming creek]

uhm?

[carmine tide]

yeah I feel like it would be trivial since either it's all gonna collapse or nothing changes

perhaps I'm being thick though

[ionic latch]

I'm still confused as to how the reader is expected to prove 64 is what I'm saying

[carmine tide]

$64 \in \mathbb{Z} \in \mathbb{Q} \in \mathbb{R} \in \mathbb{C}$

[sterile pumice]

Civil Service Pigeon

[carmine tide]

[gleaming creek]

oh for a moment I thought, you were demeaning me

yeah well

[ionic latch]

No no 😅

hypocritical writers

[carmine tide]

writing is hard

[gleaming creek]

[ionic latch]

me when embeddings

It's really interesting how algebra makes numbers more than just numbers

[carmine tide]

$[64]_{64} \in \mathbb{Z}/64\mathbb{Z} \in \mathbb{Q}/\mathbb{Q} \in \mathbb{R}/\mathbb{R} \in \mathbb{C}/\mathbb{C} \cong {0}$

[ionic latch]

oh no that's horrible

[sterile pumice]

Civil Service Pigeon

[ionic latch]

hm

If you quotient a field with itself

do you just get {0,1}

or is it just {0}

I think it's just {0}

Oh you wrote that

maybe if I took the time to read

[carmine tide]

yeah

we did this in linear

[ionic latch]

Yes ideals and field extensions are very interesting

I guess this means that the index of a field with itself is 0

me when 0 dimensional vector space over myself

[carmine tide]

pigeon.exe has stopped working.

[ionic latch]

Oh

wow I just made the connection to the vector space of polynomials over R

[carmine tide]

orz

[ionic latch]

I assume that's related to how dimension of the field extension arises

beri interesting

[carmine tide]

🍓

why does this strawberry

look really

not it

[ionic latch]

literally

[midnight cloak]

wtf

[carmine tide]

[ionic latch]

<@&268886789983436800>

[red yacht]

help please

[mint stone]

||Let x=k²q, y=7²(k²+q²) and r=(x: y).
Then r must divide both qy-7²x=7²q³ and k²y-7²qx=7²k⁴, so r can only be 1, 7, 7². Just choose some examples.||

[red yacht]

what?

[ionic latch]

They just replaced a with k and b with q

[red yacht]

yes but

why qy - 7^2x = 7^2q^3

where is that coming from

[red yacht]

@ionic latch @mint stone

you guys here?

[mint stone]

Just substitute

qy-7²x=q7²(k²+q²)-7²k²q=7²q³

[red yacht]

you skipped some steps I dont follow

what do you mean?

I am at d = gcd(x,y) with x = k^2 . q and y = 7^2 . (k^2 + q^2) @mint stone

[mint stone]

can you expand brackets?

[red yacht]

I am at d = gcd(x,y) with x = k^2 . q and y = 7^2 . k^2 + 7^2 . q^2 @mint stone

[mint stone]

so, substitute this into qy - 7^2x and expand brackets

[red yacht]

Wut

[mint stone]

I don't understand what is unclear for you in this solution

[red yacht]

why qy - 7^2x = 7^2q^3

[mint stone]

because we have
qy-7²x=q7²(k²+q²)-7²k²q=q7²k² + 7²q³ - 7²k²q
so, the last term cancels with the first one, since they are equal

and we are left with 7²q³

[red yacht]

I dont think I follow how you got there from

I am at d = gcd(x,y) with x = k^2 . q and y = 7^2 . k^2 + 7^2 . q^2 @mint stone

[mint stone]

multiply q by y and expand brackets.

[red yacht]

you mean multiply y by q?

[mint stone]

sure. It's standard in math to write qy if you want to multiply q by y, or abc if you want to multiply a by b by c

[red yacht]

care to elaborate? I dont understand how you got here

[mint stone]

I don't know, it's just a basic math, like a(b+c)=ab+ac. Maybe it's worth revisiting those first

[red yacht]

dude I was at d = 7^6*gcd(k^2 . q , 7^2 .q^2 + 7^2 . k^2)

@mint stone

[mint stone]

Exactly. And here #elementary-number-theory message I wrote the rest of the solution

[red yacht]

the second line is what I dont understand

Then r must divide both qy-7²x=7²q³ and k²y-7²qx=7²k,

[mint stone]

r divides both x and y, so it divides any number of the form sx+ty where s,t are any integers

[dense sage]

Are there some ways to compute factorisation of ideals in a ring of integrs of some finite extension of QQ, if we know its generators? At least for some good fields like QQ[sqrt(-3), sqrt(5)].

I know how to do it for QQ[sqrt(d)]. If I is an ideal in O_k, we can find n s.t. I = (n) J and ZZ+J= O_k. Than O_k/J= ZZ/(J cap ZZ) = ZZ/norm(J).
In ZZ/norm(J) we can find minimal decomposition of (0) to a product of prime idels and take their preimages in O_k. This is factorization of J.
To factorize (n), it's sufficient to factor (p), p is prime in ZZ. It's done for example here
But I cant generalize even for biquadratic fields.

[ionic latch]

Is this still considered elementary NT and not #advanced-number-theory 🥴

[dense sage]

Is it better to send this question there?

[ionic latch]

I think so

Actually reading again groups rings fields may have been better 🤡 well we'll see what the good people of that channel tell you

[rain wren]

does even the problem of

what would the smallest square number to start with 777
belongs to ENT?

[wooden glen]

Debatable. It doesn't take much trial and error to find 882² = 777924, but there's not much theory going into it.

[kindred moss]

most questions that depend on what base you're looking at aren't that interesting

maybe thats an overstatement but usually the interesting ones will look at properties of the base number

[wooden glen]

$ calc 'sqrt(0.777)'
    0.88147603484156051104
$ calc 'sqrt(0.778)'
    0.88204308284799785056
$ calc 'sqrt(0.0777)'
    0.27874719729532707895
$ calc 'sqrt(0.0778)'
    0.27892651361962706036

So 882 is the smallest natural number whose square is written as 777 followed by an odd number of digits, and 2788 and 2799 are the smallest natural numbers whose squares are 777 followed by an even number of digits.

[red yacht]

how can you prove that if gcd(a,b) = 1 then gcd(a^n, b^m) = 1 for n != m

[wooden glen]

Assume p is a prime that divides gcd(a^n,b^m). Derive a contradiction.

[red yacht]

ok so, for example

Let p be a prime such that p | a^n and p | b^m

then, it follows that p | gcd(a^n, b^m)

then what?

[wooden glen]

p | gcd(a^n, b^m) is what I suggested you assume.

[red yacht]

ok sorry lets start again

Let p be a prime such that p | gcd(a^n, b^m)

by the definition of gcd, the gcd of two numbers divides both numbers,

then,

gcd(a^n, b^m) | a^n and
gcd(a^n, b^m) | b^m

then because divisibility is transitive
p | a^n and p | b^m

[red yacht]

how?

[wooden glen]

That's a good start.

[red yacht]

but I got stuck

[wooden glen]

I'll let you think about what more you can conclude now.

[red yacht]

I mean if p | a^n and p | b^m then gcd(a^n, b^m) >= p

[rich meadow]

That was actually so simple, I love the approach

[minor musk]

Prove $\phi (mn) = \phi (m) \cdot \phi(n) \cdot \frac{d}{\phi(d)}$ \ where $(m,n) =d$

[sterile pumice]

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

[ionic latch]

Thats a nice theorem

[midnight cloak]

what is (m, n)

[ionic latch]

Greatest common divisor

[midnight cloak]

number theorists coming up with the worst notation known to mankind

[ionic latch]

[a,b] is lcm

[midnight cloak]

$$\left(\frac{m}{n}\right)$$

[ionic latch]

oh yeah the legendre symbol is the worst

[unique cypress]

Use chi(m) if you're annoyed by it

But the legendre symbol gives you a nice way to look at reciprocity

[midnight cloak]

$\chi(m)$

[rugged pasture]

nah, man, don't talk trash about my beloved phi

[rugged pasture]

$\lambda\alpha\tau\varepsilon\chi$

[sterile pumice]

Vanellope von Schmugz

[minor musk]

I have no idea how to start

[ionic latch]

Do you know under what condition $\phi(mn) = \phi(m) \cdot \phi(n)$

[sterile pumice]

Coolempire93

[minor musk]

When m and n are coprime

🤕

[ionic latch]

Good 👌 sorry for the delay I was trying to cme up with a way to prove this without invoking prime power factorization but I could only come up with ways to do it through using it

Do you know the formula for $\phi$

[sterile pumice]

Coolempire93

[minor musk]

$\phi(p^a) = p^a-p^{a-1}$ ?\

[sterile pumice]

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

[ionic latch]

👌 we can use that

[minor musk]

Alr

[ionic latch]

Rewriting a little bit, $\phi(p^a) = p^a\left(1 - \frac{1}{p}\right)$, right?

[sterile pumice]

Coolempire93

[minor musk]

Ok

[ionic latch]

So using the fact that phi is multiplicative for coprime numbers, consider this:

We can write $n = p_1^{a_1}p_2^{a_2} \cdots p_n^{a_n}$ as the prime power factorization of $n$ (are you familiar with this?)

[sterile pumice]

Coolempire93

[minor musk]

Yep

[ionic latch]

Perfect

So then $\phi(n)$ = what

[sterile pumice]

Coolempire93

[ionic latch]

if it has the prime power factorization above

[minor musk]

$\phi(n) = n \prod (1- \frac{1}{p_i})$

[sterile pumice]

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

[ionic latch]

✅

So all we need to do is characterize the prime power factorizations of m and n

Say $d = p_1^{a_1}p_2^{a_2} \cdots p_i^{a_i}$ and $n = p_1^{a_1 + b_1}p_2^{a_1 + b_2} \cdots p_i^{a_i + b_i}q_1^{b_{i+1}}q_2^{b_{i+2}} \cdots q_j^{b_{i+j}}$ and $m = p_1^{a_1 + c_1}p_2^{a_2 + c_2} \cdots p_i^{a_i + c_i}r_1^{c_{i+1}}r_2^{c_{i+2}} \cdots r_k^{c_{i+k}}$

Ah I forgot to add d

This is annoyiwng xd

[sterile pumice]

Coolempire93

[minor musk]

It's alr take ur time

[ionic latch]

So what we have here is q represent prime factors unique to n

r represent prime factors unique to m

And d is the gcd

Now all we have to do is write out $\phi(mn)$

[sterile pumice]

Coolempire93

[ionic latch]

And we can simplify to the form that you were given

Well really writing out the right side will be easier

And then simplifying to phi(mn)

So based on the prime power factorization what is $\phi(m)$

[sterile pumice]

Coolempire93

[ionic latch]

Should be easy since the powers don't matter

[ionic latch]

(what I'm saying is to use this)

Funnily enough the rest of this process comes from definition of gcd, so the powers were really just for formality 😭

[minor musk]

$\phi(m) = \prod (1- \frac{1}{p_i}) \prod (1- \frac{1}{r_i})$ something?

[sterile pumice]

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

[ionic latch]

Exactly 👍

Don't forget the m in the front

But yeah

$\phi(m) = m\prod\left(1 - \frac1{p_\ell}\right)\prod\left(1 - \frac1{r_\ell}\right)$

[sterile pumice]

Coolempire93

[ionic latch]

Okay now how about $\phi(n)$

[sterile pumice]

Coolempire93

[minor musk]

$\phi(m) = n \prod (1- \frac{1}{p_i}) \prod (1- \frac{1}{q_j})$

[sterile pumice]

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

[ionic latch]

Finally, what about $\phi(d)$

[sterile pumice]

Coolempire93

[minor musk]

$\phi(d) = d \prod (1- \frac{1}{p_i})$

[sterile pumice]

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

[ionic latch]

\hsize=2000pt
$\phi(m)\phi(n)\frac{d}{\phi(d)} = m\prod_{\ell = 1}^n\left(1 - \frac1{p_\ell}\right)\prod_{\ell = 1}^k\left(1 - \frac1{r_\ell}\right) \cdot n\prod_{\ell = 1}^n\left(1 - \frac1{p_\ell}\right)\prod_{\ell = 1}^j\left(1 - \frac1{q_\ell}\right) \cdot \frac{d}{d\prod_{\ell = 1}^n\left(1 - \frac1{p_\ell}\right)}$

Useless latex

[sterile pumice]

Coolempire93

[ionic latch]

Better I guess

You should be able to simplify the common terms here

And then realize that the result is phi(mn)

And then as a final step I'll summarize what we did more succintly since I added a little bit of unnecessary stuff in the middle

[minor musk]

Okae

[ionic latch]

let me know once you finish simplifying

[minor musk]

[ionic latch]

Does that mean done 😆

[minor musk]

So what I get here is ....

\hsize=2000pt
$mn\prod_{\ell = 1}^n\left(1 - \frac1{p_\ell}\right)\prod_{\ell = 1}^k\left(1 - \frac1{r_\ell}\right) \cdot \prod_{\ell = 1}^j\left(1 - \frac1{q_\ell}\right)$

[sterile pumice]

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

[ionic latch]

✅

Which is exactly $\phi(mn)$

[sterile pumice]

Coolempire93

[minor musk]

Okkkk

[ionic latch]

Okay now for the more succinct version

So at the beginning we showed that if $n = p_1^{a_1}p_2^{a_2} \cdots p_n^{a_n}$ is the prime-power factorization of $n$, then $\phi(n) = n\prod_{i=1}^n\left(1 - \frac{1}{p_i}\right)$

[sterile pumice]

Coolempire93

[ionic latch]

But notice that in that formula for phi(n), we never use the a_i

So we can write this a bit more clearly

If $P$ is the set of prime factors of $n$, then $\phi(n) = n\prod_{p \in P}\left(1 - \frac{1}{p}\right)$

[sterile pumice]

Coolempire93

[ionic latch]

We can now manipulate this for our problem

[minor musk]

Okk

[ionic latch]

Let $m$ and $n$ be natural numbers with $Q$ the set of prime factors of $m$ and $R$ the set of prime factors of $n$. Then if $(m,n) = d$, the set of prime factors of $d$ is $P = Q \cap R$

[sterile pumice]

Coolempire93

[ionic latch]

Do you agree with that so far

[minor musk]

Yup
Makes sense

[ionic latch]

Perfect

[tall arch]

this can be done just by individually considering the multiplicity of a singular prime p on both the LHS and RHS right?

acc nvm

[ionic latch]

Yeah, that's ultimately what I'm trying to do now

[tall arch]

oh alr

[ionic latch]

The powers are unnecessary, we just need the primes

[ionic latch]

So then $\phi(d) = d\prod_{p \in P}\left(1 - \frac{1}{p}\right)$

[sterile pumice]

Coolempire93

[ionic latch]

And now we have our final result

\hsize=2000pt
\begin{align*}
\phi(mn) &= mn\prod_{p \in P}\left(1 - \frac{1}{p}\right)\prod_{q \in Q \setminus P}\left(1 - \frac{1}{q}\right)\prod_{r \in R \setminus P}\left(1 - \frac{1}{r}\right) \
&= m\prod_{p \in P}\left(1 - \frac{1}{p}\right)\prod_{q \in Q \setminus P}\left(1 - \frac{1}{q}\right) \cdot n\prod_{p \in P}\left(1 - \frac{1}{p}\right)\prod_{r \in R \setminus P}\left(1 - \frac{1}{r}\right) \cdot \frac{1}{\prod_{p \in P}\left(1 - \frac{1}{p}\right)} \
&= m\prod_{q \in Q}\left(1 - \frac{1}{q}\right) \cdot n\prod_{r \in R}\left(1 - \frac{1}{r}\right) \cdot \frac{d}{d\prod_{p \in P}\left(1 - \frac{1}{p}\right)} \
&= \phi(m)\phi(n)\frac{d}{\phi(d)}
\end{align*}

(notationwise, if P is the shared factors of m and n, then Q \ P is the set of prime factors of m that are not prime factors of n, and Q \ R is the set of prime factors of n that are not prime factors of n)

Oh I guess I can add in one more line so that is clearer

Oh I put the q in the wrong place too

okay give me a sec to fix that

[sterile pumice]

Coolempire93

[ionic latch]

a lot of tracking of terms has to go on here but let me know if anything is confusing

[minor musk]

After putting $\prod_{p \in P} \left(1- \frac{1}{p}\right)$ in both numerator and denominator

[sterile pumice]

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

[ionic latch]

Mhm 👀

[minor musk]

Oh wait since d is common divisor of m and n putting them gives the full factorization of m and n

Nvm I got it

Tysm ✨🍁

My dumb ahh finally got it

[ionic latch]

No problem 💃

Glad that you got it 🙂

I think this leads to probably what I think is most fun

That $d\phi(m)\phi(n) = \phi(d)\phi(mn)$

[sterile pumice]

Coolempire93

[minor musk]

Ig the proof skills in me is still not polished yet

[ionic latch]

(Which I think can be proven by some form of counting argument but seems annoying )

[ionic latch]

This one was just particularly difficult without the formula for $\phi$

[sterile pumice]

Coolempire93

[ionic latch]

It would require you to actually work with the powers in the prime factorization

long algebraic process

[minor musk]

Sure

[ionic latch]

But in general if you're given an equality you can just plug whatever formulas you have into each side

Cancel like terms, etc, until you reach a tautology

Which is what you would have had to do

[minor musk]

Thanks again
Finally I can sleep it's almost 3 am

[ionic latch]

Yes sleep sleep

[minor musk]

Goodnight ✨🌸

[ionic latch]

Goodnight

[red yacht]

how can you prove that if x in Z such that x > 1 then his prime factorization contains at least one prime?

[ionic latch]

Well-ordering principle helps with this one

[red yacht]

care to elaborate?

[ionic latch]

Essentially what we are proving is that every positive integer > 1 has a prime divisor

One way to go is by contradiction

So suppose the set of positive integers > 1 with no prime divisor is nonempty

By WOP it has a smallest element, call that y

If y is prime, then it has a prime divisor (itself), so y cannot by prime

But if y is not prime, what does that mean

(think: what does it mean for a number to be composite)

[red yacht]

what is wop

wopper?

[ionic latch]

Well-ordering principle

That every set of positive integers has a smallest element

[red yacht]

idk

you tell me

[red yacht]

idk

[red yacht]

im new to wop

[ionic latch]

Simply, it's the principle that every set of positive integers has a smallest element

every nonempty set

So since the set of positive integers > 1 with no prime divisors is a set of positive integers, when we suppose that it is nonempty, that means that it has a smallest element

[ionic latch]

What is your definition of prime

[red yacht]

positive divisors himself and 1

[ionic latch]

More specifically, $x$ is prime if it \textit{only} has as positive divisors $1$ and itself

[sterile pumice]

Coolempire93

[red yacht]

why cant the smallest element cant be prime

[ionic latch]

The only here is the keyword

[red yacht]

ok

[ionic latch]

Because if y is prime, then y has a prime divisor

Which is itself

[red yacht]

what?

how so?

[ionic latch]

If $p$ is prime, then since $p | p$, $p$ has a prime divisor

[sterile pumice]

Coolempire93

[red yacht]

oh yeah x | x for any x in Z

that's basic

[red yacht]

what about it

[ionic latch]

Since we know it has a smallest element, and it is not prime

We consider

[ionic latch]

What is the negation of this

What does it mean to not be prime

[red yacht]

I dont understand

[ionic latch]

What do you not understand

[red yacht]

WOP

@ionic latch

[ionic latch]

What do you not understand about it

Why it is true, or how I've applied it?

[red yacht]

how

[red yacht]

the latter

@ionic latch

[ionic latch]

To write it in symbols, WOP says that $\forall S \subseteq \ZZ_{> 0}, S \neq \emptyset \implies \exists s \in S(\forall t \in S, s \leq t)$

If we define $S = {x \in \ZZ_{>1} : x \text{ has no prime divisors}}$

[sterile pumice]

Coolempire93

[ionic latch]

That is, S is the set of positive integers greater than one with no prime divisors

[sterile pumice]

Coolempire93

[ionic latch]

For our proof by contradiction, suppose S is nonempty

Then since S is a set of positive integers, WOP applies

S being nonempty means that S has a smallest element

Therefore the set of positive integers greater than one with no prime divisors has a smallest element

[cunning forge]

But it is empty

[ionic latch]

It is a proof by contradiction

You suppose it is nonempty to show that it cannot be

[cunning forge]

Oh ok

[ionic latch]

[eager silo]

What is the asymptotic density of the set of all x^2 + y^4 asymptotically equivalent to

Or what is #{x^2 + y^4 <= n for x,y>= 1} asymptotically equivalent to (and then divide that by n to get the other one I guess lol)

I just heard it be mentioned as a "sparse set that wasn't as sparse as the set of all x^2 + 1's" so I was curious

I guess you could frame this question as, what is its sparseness asymptotically equivalent to

[eager silo]

Ok one thing

this is bounded above asymptotically by x^(3/4) that is for sure

because the amount of x^2 + y^4's
is lower than or equal to the amount of (x,y)'s that satisfy x^2 + y^4 <= n,
which is lower than or equal to the amount of all (x,y)'s such that there exists a y1 and x1 such that x^2 + y1^4 <= n and x1^2 + y^4 <= n,
ake the product of the amount of x's for which there exists a y1 such that x^2 + y1^4 <= n and the amount of y's for which there exists an x1 such that x1^2 + y1^4 <=n,
aka the product of the amount of x's such that x^2 + 1 <= n and the amount of y's such that y^4 + 1 <= n
aka floor(sqrt(n-1)) * floor(fourthRoot(n-1))
which is lower than or equal to sqrt(n) * fourthRoot(n) aka n^(3/4)

It lowkey does seem to be asymptotically proportional to n^(3/4)

and what is this weird ~0.7 value its approaching?

[eager silo]

for 10000000 (10^7), I optimised the code to make it so that it only calculates it for each floor(10^7 * m/1000)

Honestly I am kinda confused by the growth rate

[eager silo]

I got the fact that the amount of (x,y)'s such that x^2 + y^4 <= n is asymptotically equivalent to n^(3/4) * (integ from 0 to 1 of sqrt(1-k^4) dk)

but that is still technically not the same as the amount of x^2 + y^4's <= n

ok lets be real its probably (very likely) asymptotically the same but I know not of how to prove that

more specifically, I need to prove that the amount of duplicates is o(n^(3/4))
I mean its obviously true but uuuuh I don't know how to do it

the obvious duplicates (from x^2, y and y^2, x) are o(n^(3/4)), but I don't know if they are all the duplicates

[eager silo]

Honestly the graph is weird considering that the amount of x^2 + y^4's is likely n^(3/4) * (value in picture), but it still does seem correct even with that

(the picture in question)

like it does seem to approaching this value but like why so slowly lmfao

I looked at it a bit in desmos, I think I sorta see where it comes from (there is an O(sqrt(n)) factor in the o(n^(3/4)) difference between n^(3/4) * (value in picture) and the amount of (x, y)'s)

the formula at the bottom (x,y's) is not necessarily the same as my intended result (x^2 + y^4's) but still

[proud badger]

Wait… Is that an integral? I thought number theory was about ℕ?

[eager silo]

I'm estimating the sum with the integral

[eager silo]

Sweet summer child, you seem to know nothing of analytic number theory, not that what I'm doing here is anything close to that

[unique cypress]

Daily reminder this is number theory

[rugged pasture]

hodge-podge

[eager silo]

It seems the amount of x^2 + y^4's approaches the amount of (x, y)'s asymptotically very slowly

Even after 10^7

Even 10^8

Like holy fuck what is the algorithmic complexity of the amount of duplicate (x, y)'s (that have to be cut to give the amount of x^2 + y^4's)

[placid stratus]

does anyone find it interesting that there is a one page proof that every prime is an s unit solution in lesser primes?

[loud maple]

What does "s unit solution" mean?

[placid stratus]

((p-1)+(p+1))/2 = p
(p-1) and (p+1) are <p smooth
expressed as an s-unit equation, u-v=2

in other words, if you enumerate a friable monoid (of primes up to some p) in sorted order, the first gap is the next prime

by siegel's there are finitely many u-v=2 and the upper bound on the exponents is large, empirically there are large solutions

all solutions are coprime to the prime set

a google search says this theorem is not known, but the proof is a trivial one pager
idk if it's one of those things that is so obvious no one writes it down, but i find it interesting

notably you can do stuff like express any statement about primes in terms of s units

and in fact any statement about integers becomes expressible in terms of s units

any number = product of s unit solutions, recursively

[minor musk]

Any site where I can get notes for cryptography

Need for these topics

[slow birch]

Just read the relevant chapter on David M. Burton. Well written imo.

[minor musk]

Okae

[orchid dawn]

anyone have a good free pdf to learn number theory from

[carmine tide]

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

[orchid dawn]

thanks

i didnt see that channel

[carmine tide]

[orchid dawn]

damn that channel could be a real goldmine

[orchid dawn]

yeah this one looks great thanks a ton again

[carmine tide]

[eager silo]

I've asked this before here and I'll ask it again, anyone have a proof that these are the same (of course 1. -> 2., but how do you get 1. from 2.)

look at the condition for b for 2.

because such a condition isn't there for 1.

it's all integers for 1.

[wooden glen]

There's a theorem later in the article that Carmichael numbers are always square-free, and if that can be proved just from definition (2), then (1) would follow using the Chinese remainder theroem.

[eager silo]

I get what you're saying

b^n = b^(p1, p2...., pm) -decompose> b^p1, b^p2, ..., b^pm = b, b, ..., b -recompose> b

[wooden glen]

In fact: Suppose n is not square-free. Then n = p^k·m, where p is prime, k>=2, and m is coprime to p^k.
The multiplicative group modulo n has order p^(k-1)·(p-1)·φ(m), so by Cauchy's theorem it contains an element b of order p.
Since b^p == 1 (mod n) we also have b^n == 1 (mod n) and in particular b^(n-1) == b^-1 (mod n). But b^-1 is not 1 because the order of b is p > 1.
Thus, this n does not satisfy the second definition.

[red yacht]

can I get some help with this?

is asking that for the following predicates with p in N, p > 1, which of them are a definition to the prime numbers p

[supple acorn]

what have you been able to figure out so far

[red yacht]

quite a few things but nothing really productive

say for example if a) is a characterization of primes p, then
p is prime <=> a)

you can prove right (=>) and left (<=) direction

[supple acorn]

yea, a) is a definition of primes

[red yacht]

what about b)?

can we prove both directions? left and right that is

[supple acorn]

good question

so, prime => b) is true, because the only divisors of p are 1 and p, and p^2 ∤ p

but on the other hand, <= is false

here's a hint: what happens if a number doesn't have any square divisors? (except 1)

[red yacht]

care to elaborate?

[supple acorn]

for example, think about p = 2 * 3

[red yacht]

here p is composite, what about it

[supple acorn]

does 6 satisfy b) ?

[red yacht]

say p = 6, then take d = 3 , d > 1 yes because 3 > 1 and also d | p yes because 3 | 6
furthermore 9 does not divide 6, this is also good, and then b) holds but p is not prime, thus
b) => p is prime
is false as shit

[red yacht]

are you here? @supple acorn

[supple acorn]

ah thanks for the ping

[supple acorn]

yea

also you would need to check d = 2 and d = 6 cases

but ultimately it works because the only square divisor of 6 is 1

so yea so far we have a) is a definition of primes and b) is not a definition of primes

[red yacht]

why

not necessary.

[supple acorn]

cuz it says ∀

[red yacht]

?

[supple acorn]

∀d ∈ N

the statement has to be true of all d

[red yacht]

thats the thing, we just need to find one d such that p is not prime and we good.

[supple acorn]

oh to be clear the free variable in the statement is p

d is bound to the quantifier

[red yacht]

what about it

[supple acorn]

you are correct if you say "we just need to find one p such that p is not prime"

and we chose p = 6

then we need to show that p satisfies b)

and to show that, we need to show it holds for all d

so we then see that we first require d > 1 and d | p

the only d that satisfy this are d = 2, 3, 6

and indeed, for all such d, d^2 ∤ p

[red yacht]

only one d is enough

[supple acorn]

that is not how the ∀ quantifier works

[red yacht]

I dont think I follow?