elementary-number-theory

[vernal widget]

integer multiplication

[sleek cove]

too bad you don't commute with 2d girls

[steady nest]

how would one solve this

?

Please tag me if you solve

[sterile pumice]

suck2015:

[steady nest]

im stuck on this portion

like was the process correct?

[fervent crest]

Looks good to me

But you can simplify your answer

What is the multiplicative inverse of p-1?

[sacred junco]

does anyone want to be my guinea pig for a lecture series I'm making on algebraic number theory

you just have to sit back and pretend to be a student free of charge ;) and enjoy

yes

I do not have enough mathematical maturity for algebraic number theory but yes

[swift shard]

Sure haha. I don't know much ant so I could use some learn

[sacred junco]

It's a very gentle intro and I only have the intro lecture so far which is even more gentle so I wouldn't be worried

Kaynex I imagine the first two lectures would be stuff you already know but after that it gets hot 😳

but srs dm me if either of you are interested as to when you're free :)

[sleek cove]

how much algebra is needed for pre req

[sacred junco]

none really lol if I get deep enough into the series I'll introduce group theory, literally no algebra prereqs
a little mathematical maturity and some basic knowledge of modular arithmetic and divisibility is all really

[sleek cove]

hm i mean i'm interested, what would like the first lecture cover?

[jovial hemlock]

so

Chinese Remainder Theorem only works for finitely large collections of numbers, right?

I assume I can’t say “Take X to be the number which is 1 modulo every prime, except 3, it’s 2 modulo 3”, for example

because no such number exists?

[jovial hemlock]

So

If I imagine an infinite-dimensional space

where the “first” dimension can have points on either 0 or 1, the second dimension on 0,1, or 2, the third dimension on 0,1,2,3, or 4, and so on- the n’th dimension has the values from 0 to the n’th prime - 1

and I think of these coordinates as representing modularities

then the coordinates, for example, (0,2,3,1,8,8,8...) where it’s just 8s forever, would represent the number 8

If I had the coordinates (a,b,c...z,n,n,n...) repeating on “n” forever

and I knew that at least one of a - z was 0

oh okay never mind I solved my problem thank you

I tried something recently where I simply had each line represent a prime number and the coordinates represented the products

it turned out not useful, because any number can be found on any given line from the origin, although I’m sure the infinite-dimensional shape traced out by the coordinates representing “6” would be interesting to look at if we could process it

which construction?

haha I took linear algebra last year and now I can’t help but try to convert everything into vector spaces

usually my problem comes from forgetting scalars don’t have to be integers

ik

then I get rid of vector

and just have a space

I don’t know what that is but I’m super excited to learn when I look into abstract algebra

I’ve found that just trying to work around with different random unsolved problems in number theory gives me a lot of insight into what makes it fun and lets me do creative stuff. My goal isn’t to actually solve a problem, just to throw various ideas which I’m sure were tested at the wall and find out exactly why they don’t work

couple months ago I got myself confused because I thought an idea did work, and everyone thought I was a crank trying to share a proof so it took me a long time to be able to find my mistake

to be clear my confusion was that I knew it was too obvious to work and there must be some mistake but I couldn’t find it

honestly the more I learn about number theory, the more fun it seems

The reason I’m doing this is that it’s what makes sense at the moment

I’m going to college soon, planning on math major, and I’d like to focus on branches that interest me

but it’s also easier for me to learn them in the actual class

so for now I’m working on testing what I can of various branches, seeing what I like and what I don’t, and coming in here if I can tell I’ve confused myself into thinking something that’s wrong

and the idea I tried to bring up earlier this conversation- I made a mental mistake and was confusing infinitely many dimensions with infinitely long dimensions, and while I believe my original problem would have been correct with a restricted number of infinitely long dimensions, it was the count that mattered and I didn’t realise that until I went to explain my confusion

That’s what I plan on

I’m mostly focusing on getting a better grasp on basic set theory, proofs, and LaTeX (so I can properly ask questions) right now, and when I feel comfortable there I’ll probably move on to abstract algebra

and also a bit of real analysis I’m trying to work through on the side as well rn

The thing with elementary number theory is, whenever I learn a new concept, my natural response to try and tighten my intuition is to see how it applies to numbers and the natural number system

and this leads me to getting questions about numbers I wouldn’t have had otherwise

like when I learned about vector spaces, I immediately tried representing numbers with their coordinates representing their prime factorisation, and the results of that experiment gave me good insight as to how vector spaces were really helpful and also where they can be limited

that sort of thing has proven excellent for helping me understand what I’m learning, but it keeps coming at the cost of some questions about number theory which I’m not always able to answer myself (I wish I was)

This subject is, I suppose, the perfect storm of interesting questions and applications I can fully imagine with my current knowledge, and absolutely no way to understand or use them or answer my questions about them without years more study

can I ask a silly question?

How do I NOT do number theory

No, like in the sense that thinking about other things always leads to thinking about number theory

more specifically, it leads me to questions in number theory I can’t answer and wind up getting hyper focused on

It winds up being truly interesting often

and maybe not even number theory in particular

Like, the other day I was playing around with patterns in primes and wound up in #topology asking about lines on the surface of a torus

I have exactly enough knowledge to ask interesting questions (to me) and make interesting connections without being able to understand anything about the answers or results, and that winds up being difficult for me to accept and leads to my progress stalling and sometimes leaves me more confused than when I started

Do you have any sort of short term way to avoid the lure?

wax while I row past the sirens?

This might come across as... I dunno, something not good

I genuinely want to know how to avoid getting sidetracked like this

Yeah, even my tiny tiny bit of set notation proved insanely helpful

Would you recommend stopping real analysis for now to learn algebra?

for notation & stuff?

[jovial hemlock]

I meant as in

do abstract algebra, and then return to analysis

not just stop analysis all together

@sacred junco does that change your opinion?

cause like

remember the question I was asking in #topology?

I couldn’t understand a thing you guys were saying

because I didn’t have algebra

see, if I do algebra, then when I have a question, I can both ask and answer it

ask and understand answers I mean

I can’t do that now

I don’t think it’ll get me to number theory faster

I think it’ll be what I need to understand things when I get confused and look online for guidance and stuff like that

no I could tell

like lifts were tooological

but Z^2 / R^2 I’m pretty sure is algebra right?

that’s what I’m trying to do is my point

but the basic topics are algebra and analysis

well for that question sure

but overall

oh

really?

nice

I like topology- I don’t understand a bit of it, but I like the concepts as I understand them, so I’m looking forwards to that

can I ask

do you have a good source online for where I can learn those things?

books are expensive haha

I will be yeag

I’m trying to do what I can in the meantime though

well I hope I will be anyway :P

neither

I’m on a gap year starting this fall

yeah,

I had decided before Covid hit, and now I have a really good reason lol

I want to keep my math skills fresh over break though

yeah I took a semester last year

started there, ended with eigenvectors and stuff

why?

You mean before analysis & all those?

I have more experience in self study then I’d like

had to learn for like three years on Khan Academy alone

see actually, linear algebra is a great example of why I want algebraic

I could understand the computations, but not conceptualise what I was actually doing

well but

see, I did conceptualise it eventually

by coming up with different ideas for vector spaces in the context of numbers and seeing the results

and that led to a lot of confusion, though it was helpful in the end

but with algebra, I could express my confusion, and it would have been a lot easier

understand what?

abstract algebra sorry

i’m

basic set theory, rings, fields, stuff like that

I thought- is that wrong?

right

and that’s what I need

expressing confusions

well like

[jovial hemlock]

huh this is neat

really simple, but I just noticed that the reverse distributive property holds for numbers that sum to 1

e.g. if a+b+c = 1, then a+(b*c) = (a+b) * (a+c)

[harsh mirage]

hahaha, wow, that's cute

[jovial hemlock]

with the exception of b or c being 0

edit: I have no idea why I thought it had that exception, it does not

[abstract flax]

Lol

[jovial hemlock]

I love things like this

tiny useless tidbits that could one day be relevant to happen to know years down the line

[unborn egret]

too bad most of us don't have a good enough to store them perfectly for that long

[torn escarp]

funny I figured this out earlier this year too haha @jovial hemlock

#chill message

here's a kind of related question you might enjoy, when is the cross product associative for 3 vectors and the result nonzero?

[wise oyster]

Including vector direction or just magnitude?

Or is this in 2 dimensions

[torn escarp]

do whatever you have to to get an answer

[wise oyster]

Oh well im dumb anyways you cant cross 3 vectors in 2D

Lemme try work it out

Oh wait

You said associative

Ive been toiling with the problem in my head for commutative

[torn escarp]

haha 😛

[wise oyster]

Alright sounds easier

Alright i think i got it

If the product is a x b x c, then it is associative and non zero if a = c (and the individual cross products arent 0 ofc)

@torn escarp

I didnt actually prove it though but from looking at the equations it seems to be the case

[torn escarp]

looks like the right track, I don't think this is the most general answer but I don't have the solution here myself I'll have to work it out again to check

but yeah, I guess give more of your reasoning/argument

[wise oyster]

Haha it's incredibly weak i should probably prove it

I just worked through the algebra of the two cases, and when comparing the final vectors, a sort of replaced the role c had in the first equation and vice versa

There's probably a much simpler way to do it by thinking about it visually

However it is not too hard visually to see that my case does work

I dont know if it's the only case

Additionally, the result of the cross product will be b when a and b are perfectly perpendicular and of equal norms

[torn escarp]

here's what I have in mind, put c=ka for a scalar k and then use the property axb =-bxa to flip stuff around a bit if necessary and move the k around

(axb)xc = (axb)xka = (kaxb)xa = (cxb)xa = -ax(cxb) = -ax(-bxc)=ax(bxc)

[wise oyster]

How did you get to your third equality

I mean the third expression

[torn escarp]

I moved the scalar k around

[wise oyster]

Oh yeah ofc

[torn escarp]

basically to flip flop a and c

[wise oyster]

Yeah that looks like it works to me

Nicely done

[torn escarp]

but I don't feel satisfied that this is the most general solution

[wise oyster]

So simple and then there's me with my tedious cross product algebra XD

[torn escarp]

😛

[wise oyster]

Yeah there might be a more general solution

[torn escarp]

I guess here a,b are arbitrary vectors and then c is always a scalar multiple of a, so only slightly more general than your answer but

[wise oyster]

Well it's a lot more powerful

[torn escarp]

I guess the answer I'd like would be like a set of vectors that all mutually are associative maybe

[wise oyster]

Mine was only the special case k = 1

[torn escarp]

yeah still you made a huge dent in the problem by figuring that out

you would have got the scalar multiple part eventually I think

that's a tinier leap to make

[wise oyster]

Is there some cross product identity for a x (b +c)

Im trying to prove this must be the general case

[torn escarp]

oh good idea, yeah it distributes

[wise oyster]

Thanks

Proved it i think

So if c is not ka

Oh wait haha i already see a flaw

Okay well ive only proved that it 's not true for c = any other vectors spanned by a and b

Because then we have (axb)x(ka + lb) = (axb)xka + (axb)xlb

Additionally we have ax(bx(ka+lb)) = ax(bxka + bxlb) = ax(bxka) + ax(bxlb) we know from your earlier proof that this is (axb)xka + ax(bxlb)

So if we assume associativity then (axb)xka + (axb)xlb = (axb)xka + ax(bxlb) => (axb)xlb = ax(bxlb)

But bxlb is not a vector so this cant be true

Is that a valid proof?

@torn escarp

Also this doesnt really belong in this chat does it?

[torn escarp]

sec need to focus on it but

oh well, I guess not but too late at this point

it was related to the other problem lol

this channel is usually not that busy anyways

[wise oyster]

Does the proof look valid?

[torn escarp]

hmm I'm not sure

[wise oyster]

Oh no

A step in particular?

[torn escarp]

well ok since earlier I said it had to be non zero and you showed it ended up giving (axb)xlb = 0

then it doesn't work because of that

I guess I'm not sure which thing it's proving, I'm just distracted right now

[wise oyster]

Haha alright

I would just feel very good about myself if my proof was correct XD

[torn escarp]

I think the idea is good

like representing a vector in terms of other vectors like that

I'm too preoccupied to really check it but seems like it could work

[wise oyster]

Haha thanks dw about it

[jovial hemlock]

I found a more general result, I think

a x (b x c) = (a x b) x c iff b x (a x c) = 0

[wise oyster]

Ooh nice

[jovial hemlock]

This can happen either if a is a multiple of c, or if b is a multiple of their cross product

[wise oyster]

So that takes into account all multiples of a for c, plus additionally axc being a multiple of b

[jovial hemlock]

but I do want to test an example out quickly just to feel more confident

[wise oyster]

Wait

I have an example where we get a 0 cross product

Let a = (1,0,0), c = (0,1,0) and b = (0,0,1)

Then ax(bxc) is 0 so it doesnt work

[jovial hemlock]

wdym that doesn’t work

[wise oyster]

The original question was asking about associativity and non zero cross product

bx(axc) is 0 sure, but so is the actual product we're interested in

[jovial hemlock]

technically I didn’t make any limitations to check that the result was non-zero, that would be quite difficult

but it does find, for example, the following group that does work

a = (2,3,4), b = (-6,12,-6), c = (5,6,7)

To find only non-zero groups, you’d have to add on the shoe-horned restrictions that a is not a multiple of b x c and b is not a multiple of c, but honestly I think the more general solution here is cooler

@torn escarp is this what you were thinking of?

[wise oyster]

Yeah it's still a cool solution. Howd you come across it?

[jovial hemlock]

Simply doing it component-wise

doing a x (b x c) manually based off of their components, doing (a x b) x c based off of their components

[wise oyster]

Do you have a proof, would be nice to get one though im pretty convinced

[jovial hemlock]

sure

it’s a little lackluster because I didn’t write down anything in words though

on the first page I expand (a x b) x c, on the second page I expand a x (b x c), then on the second page I set them equal and do some manipulations on the equation for the x-component (y and z are the same manipulations but not written down) and plug my equations back into vector form, and on the third page I show that the result is an expansion of b x (a x c) = 0

[wise oyster]

Nice

I didnt have the resilience to go through the algebra and go further than just finding the expressions for the two associate cross products

Nicely done

[jovial hemlock]

this isn’t a formalized proof, I didn’t write it to be one when doing it

I’m glad that I recognized the bottom equations on page 2 as being equal to b x (a x c) = 0 so quickly

[wise oyster]

Yeah good job

[jovial hemlock]

this is honestly the only time I’ve ever had fun with cross products lol

[wise oyster]

Can you do the same with c x (b x a)

Wait nvm i misread

Thought for a moment you might be able to

[jovial hemlock]

I mean

hm

I suppose that is equal actually right?

[wise oyster]

Plus if c x (b x a) = 0 then (a x -b) x -c = 0 so (axb)xc = 0

[jovial hemlock]

because a x b = - b x a

can you pull negativity out?

[wise oyster]

Yeah

No

[jovial hemlock]

if you have c x -(a x b) does that equal -(c x (a x b))?

because if so c x (b x a) does equal (a x b) x c

[wise oyster]

Oops edited

But no

Oh yeah i see i made the same mistake

Sorry

[jovial hemlock]

haha

[wise oyster]

Shouldnt be able to cancel out my negatives i dont think

[jovial hemlock]

actually why not

I think

yeah you can cancel out

[wise oyster]

Wait actually

Yes sorry

What you said is true as well

c x -(a x b) = -(c x ( a x b))

[jovial hemlock]

and therefore (a x b) x c = c x (b x a)

[wise oyster]

Yes

[jovial hemlock]

that’s interesting, cross products have a weird 3-vector commutativity

[wise oyster]

Yeah

[jovial hemlock]

now here’s a challenge for you. You have 10 seconds.

[wise oyster]

Oh no

[jovial hemlock]

If * is for dot product, when does (a*b) * c = a * (b * c)?

[wise oyster]

Itll take me 10s to read XD

Never

[jovial hemlock]

why

[wise oyster]

Because any two vectors dotted is a real

[jovial hemlock]

haha

[wise oyster]

Cant dot a real and a vector

[jovial hemlock]

yep

[proven dagger]

What if your vector space is R?

[jovial hemlock]

toldja you could do it :)

[wise oyster]

Fair @proven dagger

[jovial hemlock]

it’s still not a vector

it’s a scalar

[wise oyster]

But we're referring to common high school geometry vector spaces

[jovial hemlock]

6 =/= [6]

[wise oyster]

@jovial hemlock it is technically

And at that point your metric is just regular multiplication

[jovial hemlock]

I mean sure you could say it is, but I don’t see why it would be a vector instead of just a scalar

[wise oyster]

No but if your vector space is R, then scalars are vectors

[jovial hemlock]

you mean R1?

is R shorthand for that?

[wise oyster]

The reals

I just mean the reals

[jovial hemlock]

that doesn’t... that doesn’t make sense to me

hmm

I mean I understand why you could say that if you wanted to

[wise oyster]

It has to do with the actual definition of a vector space

[jovial hemlock]

but I don’t see why you’d want to

[wise oyster]

A vector isnt especially an arrow

It doesnt really matter for our purposes they were being pedantic

[jovial hemlock]

I know, but I thought a scalar doesn’t exist in a vector space

I thought a scalar was an operation you do on a vector

and it seems strange for operations to themselves be vectors like that

[wise oyster]

Yes but when your vector space is R, the pool of scalars can still be R

[jovial hemlock]

I’d think that even in R, 6 =/= [6]

[wise oyster]

So i believe scaling vectors is the same as applying the metric

[jovial hemlock]

It comes out to the same result yeah

[wise oyster]

I doubt you ever use that vector space

[jovial hemlock]

This conversation has truly shocked me

I did not know cross products could be fun

[upbeat wren]

Um, is there a "standard" proof for this?

For any even 2k > 2 and any positive integer n, (2k)^n - 1 is never a prime except when n = 1 and 2k - 1 is prime?

I have a proof. Just wondering if there is a "nicer" "accepted" one?

[fervent crest]

Use the fact that $x^n-y^n=(x-y)(x^{n-1}+x^{n-2}y+\cdots+xy^{n-2}+y^{n-1})$ to factor $(2k)^n-1$ and notice that if $n>1$ then both factors are not $1$, and the case of $n=1$ and $2k-1$ is not prime is easy

@sterile pumice

[sterile pumice]

Whoever:

[fervent crest]

I wouldn't say this is "the standard proof", but it is fairly obvious that you should do something like this

[upbeat wren]

Wow. Thank you.

[median gorge]

if u do the zeta function as the input as each prime

$p\in \mathbb{P} \sum_{n=1}^{\infty} \frac{1}{n^{p_n}} = \alpha $

[sterile pumice]

consciousness is quantum:

[median gorge]

i did a program and it looks like it may converge? or am i jus wasting time

[fervent crest]

It does converge

You can do an easy comparison test with 1/n^2

Since all primes are greater than or equal to 2

@median gorge

[median gorge]

epic is this a pointless number then?

@fervent crest is there something i can read about this sum?

[fervent crest]

I don't know anything about this sum

[median gorge]

what emoji

:GWczoLoliShrug:

[sacred junco]

LoliShrug

[sacred junco]

was hoping to get some help with this, solving the pell equation is no problem, but i'm stuck when its like this

[void widget]

divide both sides by 4

then you can use the continued fraction of sqrt(21)

[4; 1, 1, 2, 1, 1, 8]

in fact you can even just use 5^2 - 21*1^2

CF gives you 55^2 - 21*12^2 = 1

23^2 - 21*5^2 = 4 came before that

[sacred junco]

Let $\phi=\frac{1+\sqrt{5}}{2}$, how do I prove that there is no unit $u\in\bZ[\phi]$ such that $1<u<\phi$

[sterile pumice]

critter:

[junior sapphire]

One way to prove that is by calculating the fundamental unit of $\bZ[\phi]$, which is in fact $\phi$. By Dirichlet's Unit Theorem we know that the $\bZ[\phi]^*$ is generated by $\pm \phi^{k}$, therefore such an $u$ can't exist.
Or more elementary: Assume there exists a unit $1<u<\phi$. Then $u=\frac{x+y\sqrt{5}}{2}$ for some $x,y \in \bZ$ and
$$\pm 1 =N(u)= \frac{x+y\sqrt{5}}{2}\frac{x-y\sqrt{5}}{2}$$
Since $1<u$ you can write
$$-u < -1 \le N(u) \le 1 < u$$
Divide by $u\neq 0$ , then $-1 < \frac{x-y\sqrt{5}}{2} < 1$.
Now add that last inquality to $1 < u <\phi$. So $0 < x < 1+\phi$. Since $x$ is an integer we have $x=1$ or $x=2$.
If $x=1$, then $1^2-5y^2=\pm 4$ has solutions $y=\pm 1$. If $x=2$, then $4-5y^2=\pm 4$ has the solution $y=0$. But all these units don't satsify $1<u<\phi$.

[sterile pumice]

Ceana:

[sacred junco]

Thank you!

What is Dirichlet unit theorem tho?

Just curious

[junior sapphire]

It basically says that the unit group of a ring of integers is isomorphic to the product of a finite group and some free group of rank n=r+s-1 for certain r and s.

[sacred junco]

I see

[sacred junco]

this was assigned in the unit about diophantine equations, it seems unrelated so i'm struggling

[sacred junco]

how to go about it :/

[timber blaze]

WLOG, choose $q \leq p$.

There are $p^2q^3$ integers divisible by $p$, and for every $p$ integers there are $[ p/q ]$ integers divisible by $q$.

Hence the number of integers divisible by $p$ and $q$ is

$$p^2 q^3 (1 + [p/q] )$$

So the number of integers not divisible by them is

$$(pq)^3 - p^2q^3 ( 1 + [p/q] )$$

$$= p^2q^3 ( p - 1 - [p/q] )$$

And by symmetry (given that p and q are coprime), the avg. is $\frac{(pq)^3}{2}$.

[sterile pumice]

Daniel Cann:

[timber blaze]

This does not seem right, could someone let me know what they think?

Because I have made a use of [...] in order to obtain the integer part of p/q

But there must be a way to do it without that

Although the formula appears to be giving a correct answer

There is no way that's right...

I think it's because my answer is not symmetric with respect to p and q

[abstract flax]

There are p^2^3 integers divisible by p? I'm assuming the context is not the whole of Z?

What are you trying to prove?

[junior sapphire]

https://media.discordapp.net/attachments/418981682117345288/740477311044026368/unknown.png

[abstract flax]

Lol, thanks. Didn't see the question

[junior sapphire]

Im not sure if q,p are primes or arbitrary integers tho

[abstract flax]

If they were primes, they wouldn't specify they were co prime

[junior sapphire]

Assuming p and q coprime the answer should be p^2q^2(p-1)(q-1)

[carmine delta]

How do we show that there always exists an integer $k \in \mathbb{Z}/m\mathbb{Z}$ for which $2^k \equiv k \pmod m$?

[sterile pumice]

NinthLyfe:

[junior sapphire]

What’s k for m=3?

[carmine delta]

Explain why not

[carmine delta]

How does that make it not well defined

not really

ok i just read it

that doesn't affect the problem does it? I'll just reframe it like this, then:

How do we show that there always exists an integer $0 \leq k < m$ for which $2^k \equiv k \pmod m$?

[sterile pumice]

NinthLyfe:

[carmine delta]

oh yeah i just remembered

k just has to be nonnegative

[supple furnace]

The case of m=1 is trivial. Suppose m>1 and that the claim holds for all n<m. Then there exist (arbitrarily large) r such that 2^r=r mod totient(m) (as totient(m)<m). Now setting k=2^r, we get that 2^(2^r)=2^r mod m holds for all sufficiently large r satisfying the above condition because 2^r and 2^2^r eventually vanish mod 2^v_2(m) and because 2^(2^r-r)=1 mod p^v_p(m) for any odd prime p dividing m by Euler’s Theorem.

This shows that there always exists such a k

But the bounds it gives are pretty bad

[native cave]

can anyone explain why any prime number "p" that satisfies ** p(mod4)=1** can we written as the sum of two perfect squares?

[junior sapphire]

Do you know about the gaussian integers?

[native cave]

i know the definition

[simple hearth]

There is an excellent mathologer video with the best proof of this claim I have ever seen

https://youtu.be/DjI1NICfjOk

There you go

[trim bridge]

How would you show that Y = {1/x : x ∈ X} is bounded above? If X is bounded below, X ⊂ ℝ and also inf X > 0.

I let inf X = α -> 0 < α

Y is bounded above because Y = 1/α

Then letting sup Y = β,
β = 1/α

[vernal widget]

is that n theory o.o

[trim bridge]

Is there a channel for Set Theory?

[vernal widget]

this looks like it could be in a lot of channels

gotta ask a mod tbh

maybe #proofs-and-logic

[trim bridge]

Maybe #advanced-analysis ?

[vernal widget]

could be

[trim bridge]

@vernal widget ty

[vernal widget]

np

[trim bridge]

@vernal widget It says I don't have permission to type in there

[vernal widget]

check #changelog

then go to #bots

[trim bridge]

Ah, ty very much @vernal widget 🙂

[vernal widget]

np

[jovial hemlock]

Given arbitrary natural numbers $a$ and $b$, where $b > a$, how can I find the smallest naturally number $n >1$ such that $a^n \equiv a \mod b$?

[sterile pumice]

Notchmath:

[torn escarp]

look up the carmichael function

that and the euler totient function

those would be some things to look at to get started

[jovial hemlock]

wait actually hm

I can't even guarantee there is such a number

[fervent crest]

Well if gcd(a,b)=1 then such number exists

[jovial hemlock]

if b is a power of a, for example, it doesn't

[fervent crest]

and it is phi(b)+1, where phi is euler totient function

Yeah

[jovial hemlock]

the carmichael function seems to almost be what I want

no it doesn't never mind

hm

[torn escarp]

it's an upper bound on what you want

and exact for some cases

[jovial hemlock]

see I was looking at- if in base 10 you pick a single digit number, say 7, and look at the last digit as you exponentiate it, you get 7, 9, 3, 1, repeating. And I'm curious as to the length of those cycles for the more general case

[torn escarp]

yeah

[jovial hemlock]

I'm not sure if there any cases where the cycle does not include its first member if b is not a power of a- if a is 3 and b is 9, you get 3, 0, 0, 0, 0, all the way 0s

[torn escarp]

lambda(10)=4

[jovial hemlock]

well certainly that's the maximum

[torn escarp]

all others are divisors of 4

have you learned lagrange's theorem?

I say all others but we are in the context of numbers relatively prime to 10, just to be clear

[jovial hemlock]

no

[fervent crest]

For now we assume $\gcd(a,b)=1$.

You can rephrase your problem to finding the smallest positive integer $n$ such that $a^n\equiv1\pmod{b}$. This number is called the order of $a$ modulo $b$ and let's denote this as $\operatorname{ord}_b(a)$.

Some elementary observation about the order of a number is that if $a^n\equiv1\pmod{b}$ if and only if $\operatorname{ord}(b)\mid n$. Therefore by Euler's theorem we have $\operatorname{ord}_b(a)\mid\varphi(b)$. Therefore to find the order of a specific $a$, you just need to look at all the divisors of $\varphi(b)$, and one of them is the order of $a$.

Then there is another lemma that can help you: let $a$ be an integer, and if $a^n\equiv1\pmod{b}$ but $a^{n/p}\not\equiv1\pmod{b}$ for any prime divisor $p$ of $n$, then $n=\operatorname{ord}_b(a)$.

Therefore here's what you can do to find the order of $a$ modulo $b$: Start with $n=\varphi(b)$. Find all primes $p$ dividing $n$, and raise $a$ to the power $n/p$ modulo $b$. If this number is $1$ for every prime then you're done. If $a^{n/p}$ is not $1$ for some $p$, then replace $n$ with $n/p$ and repeat your process.

[jovial hemlock]

yeah no I was clear

[torn escarp]

otherwise you just have to divide out the gcd

[fervent crest]

Oops accidentally wrote too much

The assumption gcd(a,b)=1 is to guarantee that the order exists

And it also allows you to cancel a in the equation a^n = a (mod b)

[jovial hemlock]

you mean if this number is not 1 for every prime?

[fervent crest]

Yeah

[sterile pumice]

Whoever:

[jovial hemlock]

I THINK the number exists iff a^2 is not a divisor of b, but I'm not sure of that in any way

so is the takeaway that there's no pattern to these, but simply an algorithm? That surprises me, I would've expected there to be something of some kind

[torn escarp]

a=6 and b=9

6^2 doesn't divide 9

[fervent crest]

I don't think there's a nice pattern to this

I mean you can use Chinese remainder theorem and some other stuff to make the structure of integers modulo n to look much nicer

And then the pattern is pretty nice and calculating the order is fairly easy

That involves some basic group theory

[torn escarp]

have you heard of the discrete logarithm problem @jovial hemlock

finding exponents is pretty much taking logs

[jovial hemlock]

"pretty much" you say

[torn escarp]

log(b^n) = n log(b)

divide out the log(b)

you're trying to do a discrete logarithm, a problem that is known to be hard

how do we know it's hard? cause lots of people have tried over a long time lol

[jovial hemlock]

huh

[torn escarp]

don't huh me lol

ask a question

[jovial hemlock]

what do you mean ask a question lol

[torn escarp]

I'm not psychic

[jovial hemlock]

I didn't have a question, I was absorbing what you said

like "huh, that's interesting"

[torn escarp]

idk what huh means, thought you were confused

[jovial hemlock]

sorry

[torn escarp]

hah it's fine

[jovial hemlock]

what do you mean by divide out the log(b)?

[torn escarp]

you asked "pretty much"

look if I give you a number and you want to know what power it is of something

what do you do?

[jovial hemlock]

I thought that was the definition of a log sort of

and "definition" is obviously inexact here

[torn escarp]

I think I was just being too careless

if you want to know what power of 10 some number, say x, is

you look at log_10(x)

that's the exponent on it, that's all

[jovial hemlock]

Oh, maybe you misunderstood my pretty much

[torn escarp]

I was just suggesting that if you don't log with the same base you get a constant multiplier

[jovial hemlock]

it wasn't "In what way is a log used to find exponents", it was "what makes the problem of finding a log different in any way from finding an exponent"

[torn escarp]

it isn't different

it's just giving what you're doing a name

in terms of how other people already talk about it

you are just kinda coming to it on your own way that's all

just read the first two or three lines of this

https://en.wikipedia.org/wiki/Discrete_logarithm

[jovial hemlock]

more accurately, it seems like there is no such number if there is a prime p such that p divides a and p^2 divides b

[fervent crest]

I think this is a sufficient condition for the number to exist: if p divides a and b, then a has more factors of p than b does

If this holds for all prime then there should exist a number n such that a^n = a (mod b)

[jovial hemlock]

not necessarily more

equal works too

[fervent crest]

I meant equal or more

Or equivalently gcd(a,b/gcd(a,b))=1

[jovial hemlock]

just playing around with data, it seems that if numbers a and b produce n according to the above conditions, then numbers A and b produce n, where A is the modular inverse of a with respect to b

not proven or anything, just something I noticed in a few test examples

[torn escarp]

I'd look at the rad(n) (the squarefree radical) as a way of describing stuff

if rad(a)=rad(b) for instance, then some power k of a, a^k=0 mod b

[hallow stratus]

Does anyone have any good textbooks

For learning Number Theory

[fervent crest]

@raven flint Since 3|17a and gcd(3,17)=1, by the fundamental lemma 3|a. Therefore 3|2a. Now since 3|2a and 3|(2a - 7b), 3 divides their difference 2a - (2a - 7b) = 7b. Since 3|7b and gcd(3,7)=1, applying the fundamental lemma yet again yields 3|b

[raven flint]

Thanks a lot!! 😄

[raven stag]

hey

for which irrational numbers is the product of two irrational numbers an irrational number??

how can I know which have that property???

I'm tring to know when is the this product irrational for n in the natural numbers

either

$ \sqrt{n^2 + \frac{2n}{3} + \frac{2}{3}} \in I \lor \sqrt{3n^2 + 2n + 2} \in I $

[sterile pumice]

jamperezmondragon:

[raven stag]

but how do I prove that???

huuuhh I'm so stupid

shouldn't have factoraized that

just assumed it wasn't the case

[sacred junco]

for which irrational numbers is the product of two irrational numbers an irrational number??
this is unsolved

[raven stag]

really????

[sacred junco]

yes

[raven stag]

but for radical irrational numbers it's simpler isn't it?? there are just two cases

[fervent crest]

I’m pretty sure we still don’t know whether πe is rational or irrational

[raven stag]

wooow

[sacred junco]

lol, that's the example I thought of when thinking it was unsolved

[raven stag]

I didn't know that

[fervent crest]

Not even multiplication but similarly for addition: we don’t know whether π+e is rational or irrational

[raven stag]

could u share a case for which the sum of two irrationals is a rational number??

[sacred junco]

pi + -pi

[fervent crest]

Damnit sniped

[raven stag]

ohhh hahaha

but is 0 rational though??

[sacred junco]

yea?

[raven stag]

0/1 how stupid am I

[fervent crest]

Isn’t that what you wanted?

[raven stag]

yes

Not even multiplication but similarly for addition: we don’t know whether π+e is rational or irrational
@fervent crest well how could anyone approach that problem??

[abstract flax]

If you wanted it not to be zero (1+π) - π

[raven stag]

ohh hahahh of course

so there are infinite cases

[fervent crest]

Well I'm not sure how to approach it either, otherwise it would be solved already, but I do know that you can easily show that at least one of πe and π+e is transcendental

If you assume π and e are both transcendental

[abstract flax]

Theorem: Every rational number is the sum of two irrational numbers. The proof is left as an exercise for the reader.

[raven stag]

jajajajajajajaj

[fervent crest]

So for a polynomial, if the coefficients are algebraic then the roots are also algebraic

[raven stag]

@fervent crest a trasendental number is such that it can't be expresed algebraicly

[fervent crest]

Therefore if the roots are transcendental then at least one of the coefficients is transcendental

A transcendental number is a real number that is not the root of some polynomial with integer coefficients

[raven stag]

okey

[fervent crest]

Therefore if the roots are transcendental then at least one of the coefficients is transcendental
Based on this, we have that (x-π)(x-e)=x^2-(π+e)x+πe is a polynomial with transcendental roots, so one of its coefficient must be transcendental

Well actually I'm assuming a lot of nontrivial facts

[raven stag]

either pi + e or pi times e

[fervent crest]

Yeah

Well from this you can at least conclude that at least one of them is irrational

Because polynomials with rational coefficients have algebraic roots

[raven stag]

and u can do the same with any irrational number isn't it ?

[fervent crest]

Any two transcendental numbers

[raven stag]

aahhh okay

yes

[fervent crest]

Because it is perfectly reasonable for a polynomial with integer coefficients to have irrational roots

[raven stag]

yeah

okay

[fervent crest]

And I don't know much more, probably Botn and Lunasong know more

xD

[raven stag]

u said that u assumed nontrival facts, are they proven???

Well from this you can at least conclude that at least one of them is irrational
@fervent crest is this a theorem???

[fervent crest]

What is a theorem

I mean if you say a theorem is a fact that can be proven then it is a theorem

[raven stag]

yea

a theorem is a fact that can be proven deductivly from the axioms you choosed isn't it?

well thanks anyways

[sacred junco]

Very interesting discussion @fervent crest @raven stag I’m new to number theory and find it appealing

[fervent crest]

Glad you find interesting

[raven stag]

yeah

@fervent crest all trasendental numbers are irrational aren't they?

[fervent crest]

Yes

[raven stag]

because all rational numbers can be expresed as the root of a polynomial with integer coeficients

[fervent crest]

Exactly

[raven stag]

ax + b

[fervent crest]

a/b is a root of bx-a

[raven stag]

yes

ok

but is Q union I = R?

are trasendental numbers defined soley as roots of polynomials with noninteger coeficients??

[fervent crest]

What

A real number is algebraic if it’s the root of some integer coefficient polynomial

A real number is transcendental of it’s not algebraic

Roots of polynomials not having integer coefficients still might have algebraic roots

Like x-sqrt(2)

Every real number r is the root of some polynomial, specifically x-r

@raven stag

[raven stag]

ahhhhhh duh

ok

I misunderstood the concept of algebraic numbers

but is Q union I = R?
is this true?

[fervent crest]

What’s I?

Do you mean irrational numbers?

Well that’s by definition true

Since irrational numbers are just numbers that are not rational, so I = R\Q, so Q union I = R

[raven stag]

duhhh hahah yes

thanks

[storm sinew]

whats one easy way to calculate 3^123 mod 4?

im pretty new to this

[swift shard]

@storm sinew
Start actually multiplying 3s together:
3¹ = 3 (mod 4)
3² = 1 (mod 4)

And look at that, we already got 1. That means:
3² × 3² × 3² × ... = 1 × 1 × 1 × ... (mod 4)
3^122 = 1 (mod 4)
3^123 = 3 (mod 4)

[storm sinew]

oh wow, yeah that makes sense, tysm

[runic vector]

how is

(n+1)!

equivalent to (n+1)*n!

[fervent crest]

Think about what is (n+1)! and what is (n+1)*n!

[raven stag]

what???

[fervent crest]

(n+1)! is the product of numbers from 1 to n+1. n! is the product of numbers from 1 to n, and when multiplied with (n+1), (n+1)*n! is the product of numbers from 1 to n+1, so (n+1)=(n+1)*n!

[raven stag]

yeah yeah

but

'
@runic vector what is this?

[runic vector]

a typo

[raven stag]

no

[raven stag]

I mean the image

[fervent crest]

? what about the image

[runic vector]

thats where it comes up

(n+1)! is turned into (n+1)*n!

which I don't understnad

[swift shard]

That's what ! is haha

[raven stag]

oh

simplify the 4s there

[fervent crest]

Ok so $(n+1)!=1\cdot2\cdots n(n+1)$. Then $n!=1\cdot2\cdots n$, so $(n+1)\cdot n!=1\cdot2\cdots n(n+1)=(n+1)!$

[sterile pumice]

Whoever:

[runic vector]

thats not my issue @raven stag 🤨

[raven stag]

aye but it's easier to work with

[swift shard]

3! = 3(2)!
(n + 1)! = (n + 1)n!

[raven stag]

what u're asking is true by definition

Whoever:
@sterile pumice this is it.

[runic vector]

😬

@swift shard thats helpful, I guess this was never stated by the teacher

[raven stag]

really????

wait

[swift shard]

It's the only thing worth saying about the factorial haha

Okay fine you can say other cool things about the factorial

[raven stag]

@runic vector where did u find that equation??

[swift shard]

But that's the definition. Everything comes from that

[runic vector]

jesus

im off thanks for the help

[raven stag]

ok

good luck

hahahahahah sorry tbh

[fervent crest]

The only cool thing about factorial is stirling's formula

[sleek cove]

says the uncool person weeb

[torn escarp]

legendre's formula is a cutie

[vernal widget]

laurent, anybody? no

ok

[storm sinew]

is it right to say that fermats little theorem is a special case of eulers theorem?

and how do i know if i should use FLT or eulers theorem when trying to find the remainder of a large number?

do i use FLT when dividing with a prime? or am i missing something

[sacred junco]

is it right to say that fermats little theorem is a special case of eulers theorem?
Yes

You are using Euler's theorem in any case

[storm sinew]

soo dividing by a prime, finding a remainder would give me the same answer using FLT and eulers theorem?

oh wow nvm, im stupid

the totient of a prime would just be p-1

which is fermats little theorem

got it now :)

[sacred junco]

the totient of a prime would just be p-1
^

[raven stag]

which euler's theorem r u guys talking bout? where can I learn more? @sacred junco @storm sinew

[sacred junco]

Euler's Totient Theorem

In Modular Arithmetic

[raven stag]

ahhh ok

thanks

[fervent crest]

@raven stag https://en.m.wikipedia.org/wiki/Euler's_theorem?wprov=sfti1
You can also learn this in any introductory number theory book, the most beginner friendly one I know is “A Friendly Introduction to Number Theory.” It’s pretty easy to read but still has a lot of content

[trim gust]

the proof is pretty nice too

[raven stag]

thanks!!!!

[storm sinew]

could anyone show me how you would solve 5^12 mod 11*13 using eulers totient theorem?

i got to 5^120 congurent 1 mod 11*13, but now im stuck

[raven stag]

do u guys have any general advice on getting better at mental arithmetic?? besides of identities and factorization

i got to 5^120 congurent 1 mod 1113, but now im stuck
@storm sinew 5^12 is congruent to 5^12n mod k

a is congruent to a^n mod k

[sacred junco]

Not really

[storm sinew]

then the remainder would be 1 aswell?

answer should be 14 according to my book

but idk how to get to that answer

[empty yew]

do mod 11 and mod 13 separately

if x = k mod a and x = k mod b, then x = k mod ab

[storm sinew]

oh wow, totally forgot that was a way of doing it

tysm!!!

okay so

i got 25mod11=3, and 5^12mod13=1 when doing it separately

but

i dont see how this is going to get me to the answer, which should be 14

[fervent crest]

@storm sinew @empty yew that is not true, for example x = 0 (mod 4) and x = 0 (mod 6) does not imply x = 0 (mod 4*6)

The statement that if x = k mod a and x = k mod b, then x = k mod ab is not true

But it is true if you assume gcd(a,b)=1

[storm sinew]

i mean, in my question, gcd(a, b) is 1

[fervent crest]

Indeed

So in this case you can use Chinese remainder theorem

[storm sinew]

but i dont see what to do next

[fervent crest]

Chinese remainder theorem states that if $x\equiv x_1\pmod{n_1}$ and $x\equiv x_2\pmod{n_2}$ and $\gcd(n_1,n_2)=1$, then $x$ has a unique solution modulo $n_1n_2$

[sterile pumice]

Whoever:

[fervent crest]

And here's how to find it

So right now we have two congruences: x=3 (mod 11) and x=1 (mod 13)

So by the first congruence, we have x=3+11n for some integer n

Right?

[storm sinew]

so, basically find an x that fits in both equations

[fervent crest]

Yes

[storm sinew]

i've worked with the crt before, so i think i'll be able to find it out now :)

[fervent crest]

Alright

[storm sinew]

i just didnt see what to do next

[fervent crest]

You just let x=5^12, and you observe that x=3 (mod 11) and x=1 (mod 13)

and then chinese remainder theorem gives you a solution modulo 11*13

[storm sinew]

yeah, totally see it now, thankyou :)

[fervent crest]

You're welcome

[empty yew]

oh hecc, true. sorry about that. i said it in passing without thinking about it too much, sorry

[raven stag]

@sacred junco how is this not true??

[sacred junco]

a is congruent to a^n mod k
2!=2^3 mod 5

[fervent crest]

What is a,n,k

[sacred junco]

Idk

[raven stag]

$ a \equiv n \textrm{mod}\b \implies a^k \equiv n^k \textrm{mod}\ b$

[sterile pumice]

jamperezmondragon:
Compile Error! Click the reaction for details. (You may edit your message)

[fervent crest]

\pmod{b}

Are you trying to say that $a\equiv b\pmod{n}\implies a^k\equiv b^k\pmod{n}$?

[sterile pumice]

Whoever:

[fervent crest]

That is true

[raven stag]

yes

that

and if b = 1

then a is congruent to a^k

[fervent crest]

Then a = 1 (mod n) too

[sacred junco]

Well that's different than this

a is congruent to a^n mod k

[fervent crest]

a is not arbitrary

[raven stag]

yeah but $ (a^{b})^{c} = a^{b\times c}$

[fervent crest]

Ok here is what happened: the statement I wrote above actually had an implicit statement in the beginning.

If $a,b$ are integers such that $a\equiv b\pmod{n}$, then $a^k\equiv b^k\pmod{n}$ for all positive integers $k$.

If you substitute in $b=1$ then the statement will become:

If $a$ is an integer such that $a\equiv1\pmod{n}$, then $a^k\equiv1\pmod{n}$

[raven stag]

no not that

[fervent crest]

Nonono

[sterile pumice]

Whoever:

[fervent crest]

That is not true either

a is not an arbitrary integer

[sterile pumice]

jamperezmondragon:

[raven stag]

I meant that

[fervent crest]

Ok

So?

[raven stag]

yes so $5^{120} \equiv 1\ mod{(11\times13)} \newline \newline \implies 5^{12} \equiv 5^{12\times10}\ mod{(11\times13)}$

[sterile pumice]

jamperezmondragon:

[raven stag]

ok

what ever

[fervent crest]

I'm not sure why that implies

[raven stag]

do u guys have any general advice on getting better at mental arithmetic?? besides of identities and factorization
@raven stag .

[fervent crest]

Oh mental arithmetic

Well I always have pencil and paper next to me

My mental arithmetic sucks

So....

[raven stag]

@fervent crest $\newline (5^{12})^{10} = 5^{12\times10} = 5^{120} \newline$ and then the theorem u stated

[sterile pumice]

jamperezmondragon:

[sacred junco]

\equiv for modulos

[raven stag]

ohh that's such a beauty

hahahah

[fervent crest]

Using what theorem I stated

Raising both sides to the kth power?

[raven stag]

yes

[fervent crest]

Ok so (5^12)^10 = 5^120

[raven stag]

1^10 = 1

yes

[fervent crest]

And you raised both sides to what poower?

[raven stag]

yes

yes yes yes

[fervent crest]

??

You didn't answer my question lol

[raven stag]

1^10 = 1
@raven stag .

well it doesn't matter

[fervent crest]

?

Hmmmmmm

[raven stag]

hahahahahahah

how do u do those latex renders with white background

???

[fervent crest]

,tex --colour white

Send this in #bots

[raven stag]

And you raised both sides to what poower?
@fervent crest Im doing it in reverse, I think that's what I did not say

Send this in #bots
@fervent crest ohh ok

thanks

[fervent crest]

You can't do that

You can't always do the reverse

Like in this case

[raven stag]

oh how so?

[fervent crest]

$(-1)^2\equiv 1^2 \pmod{p}$, but is $-1\equiv1\pmod{p}$?

[sterile pumice]

Whoever:

[raven stag]

ohhhh

does modular arithmetic applies to all Z? or R?????

omg

[fervent crest]

It applies to all Z

[raven stag]

does it applies to Q at least??

[fervent crest]

The definition $a\equiv b\pmod{n}$ means $n$ divides $a-b$ does not require $a,b$ to be positive

[sterile pumice]

Whoever:

[fervent crest]

Well

[raven stag]

ohhh wait

[fervent crest]

Modular arithmetic can be extended to arbitrary rings, which are basically number systems where you can do addition and multiplication

[raven stag]

but they don't need to be closed

[fervent crest]

wdym

[raven stag]

rings don't need to be closed under either addition or multiplication to be rings right?

[fervent crest]

Um

No?

[raven stag]

but they can be

[fervent crest]

Rings need to be closed under addition and multiplication

They can't

[raven stag]

ahhh ok

[fervent crest]

The definition is that they have two operations, or functions RxR -> R

[raven stag]

oh ok

so u can do modular arithmetic with any ring? like 2 by 2 matrices?

[fervent crest]

Yes

Gaussian integers

[raven stag]

how do u even define division there??

[fervent crest]

Why do you need division

[raven stag]

ohhh shit right

there are just partitions of ur ring isn't it? so ok

wow

that's mind blowing

[fervent crest]

Well the equivalence classes do partition the ring

You can do it in any ring, but only "nice" rings will have properties that you like

Like for "nice" rings, you sometimes will have that all nonzero elements are invertible, you can extend euler's theorem and etc

[raven stag]

oh

so

at some point

some sets that have especific characteristics can be subject of number theory

like the integers and stuff

but instead of numbers just the elements of the set

oh wow

that's rather amazing

[fervent crest]

Well numbers are elements of a set

In particular the set of integers

But yeah that's common in like all fields of math

[raven stag]

yea of course

[fervent crest]

Where you try to extend the result

[raven stag]

oh shit

[fervent crest]

You notice that some properties of integers only depend on specific features of the integers

[raven stag]

ok and u search sets with those features?

[fervent crest]

Yes

[raven stag]

omg

[fervent crest]

For example

You can notice that the fact that integers have unique factorization theorem can be proved using only a "division algorithm"

So we name rings that have a division algorithm to be "euclidean domains"

and euclidean domains will also have unique factorization

[raven stag]

ok?

ohh

wow

so

no wait

are there infinite euclidean domains??

[fervent crest]

Well of course

[raven stag]

so can we apply the ideas that build up criptography to all euclidean domains??

[fervent crest]

Cryptography?

[raven stag]

but with infinite sets of infinite prime numbers?

well I mean that based in prime numbers

[fervent crest]

Yeah

So euclidean domains will also have a set of prime "numbers"

[raven stag]

euclidean domains have infinite prime numbers I suppose

[fervent crest]

Not necessarily

[raven stag]

why?

[fervent crest]

fields are euclidean domains, but they have no primes

[raven stag]

oh

how so?

[fervent crest]

Because all elements are units

and units are not primes

[raven stag]

but can't the elements of a field be the primes of another set that has that field as a subset?

ok I'm just having a mental fap

I will research this

is it in the artin's algebra book that we where talking bout before? @fervent crest

the euclidean domains and stuff

[fervent crest]

It probably is? I don't know

I haven't reached that part yet

But it is in

"A Classical Introduction to Modern Number Theory" by Ireland, Rosen

It's in like the first chapter

ok I'm just having a mental fap
lmao ok

Not gonna judge

[raven stag]

I don't mean literaly

like it's just that I'm thinking of stuff that I cannot yet understand but still I'm wondering

[fervent crest]

Oh actually I think any euclidean domain with one primes has infinitely many primes

You can just extend euclid's proof

[raven stag]

ohhhh ok

hey talking bout that

[supple furnace]

Not true @fervent crest

Take Z_p for example

[fervent crest]

Hmmmm right

You can’t guarantee that the product +1 is not 0 or a unit

[supple furnace]

Yeah

[fervent crest]

But also Z_p has no primes

Wait

[supple furnace]

1

[fervent crest]

Nvm

Wdym by Z_p

[supple furnace]

p-adic integers

[fervent crest]

Ohhh

I c

[storm sinew]

how can i solve 3^12 mod 35?

[fervent crest]

Exactly the same as the last problem

35=5*7, so find 3^12 modulo 5 and 7, and combine them with crt

[storm sinew]

oh okay, wasnt sure if i had to find the totient of 35 before, and then split it

but that wont get me anywhere

[trim gust]

another way:

3^3 =27=-8, so do -8^4

which is 64^2=-6^2=1

[sacred junco]

Another way:
3^12=531441 = 15184*35+1

[patent oak]

Is there any chance I can reduce the following to something nice

$n!\cdot\sum_{k=1}^m\frac{1}{(n-k)!}$

[sterile pumice]

Nikolaj-K:

[sacred junco]

If you bring in n!, it looks similar to a binomial coefficient

[brave thicket]

https://en.wikipedia.org/wiki/Stirling_number

These might help

[craggy solstice]

@sacred junco nah but theres no k! In the denom

[trim gust]

well u have sum of k! times nCk

[sacred junco]

^

[sacred junco]

sum of nPk

[torn escarp]

that makes it the coefficient on the exponential generating function you get for coefficient 1 and k! which correspond to e^x and 1/(1-x) respectively so

well, no I'm assuming the upper bound is n not m

if m>=n then it's fine since the higher binomial terms are 0 and cancel out

even then the sum should start at 0 lol

well ok just to finish my original thought since it might be adjustable afterwards, the nth derivative of e^x/(1-x) evaluated at x=0 is the nth term if the sum goes from k=0 to k=m>=n

[slender moth]

for $b \geq 2$ and $n$ positive integers, let $F_b(n)$ be the sum of the digits of ($n$ written in base $b$). is there any formula for $\sum \limits_{n=0}^m F_b(n)$ for $m \geq 1$?

[sterile pumice]

Auvera:

[slender moth]

i see there are OEIS entries for F_b for small b

but i thought maybe the sum of the F_b(n) is easy to compute for certain m, like maybe m=b^k-1

like aren't the digits of numbers in [0,b^k) uniformly distributed? for example for b=10 and k=2, all numbers have two digits, and there are 10 numbers with first digit being i for each i in {0,1,...,9}. same with the second digit

so in that example we have $\sum \limits_{n=0}^{99} F_{10}(n) = 10 \sum \limits_{i=0}^{9} i + 10 \sum \limits_{i=0}^{9} i = 20 \cdot 55 = 1100$ i think

[sterile pumice]

Auvera:

[slender moth]

seems like that easily extends to general b and k

probably sounds like a silly problem but this came up while trying to prove average case complexity of an algorithm i'm working on

[sacred junco]

How to find the maximum value of $\dfrac {n(99)(98)(97) ... (101 - n)}{100^n}$ for integers n

[sterile pumice]

Barry:

[torn escarp]

you can take the log of it to separate it out into a sum, then approximate it with an integral so that you have something differentiable to find the max with calculus

you could also try stirling's approximation

probably the max value of that is near the integer value where it is at its max

[slender moth]

maybe i'm missing something but seems you can just find the N where the sequence is decreasing for all n larger than N. then check the finitely many n smaller than N for the largest value

[fervent crest]

Why do you have so many terms in the middle tho

[sleek cove]

relatedly, what is the product in the numerator supposed to be

[fervent crest]

Oh I think I see what he meant

[fervent crest]

$\frac{n}{100^n}\prod_{i=1}^{n-1}(100-i)$

[sterile pumice]

Whoever:

[fervent crest]

I think

[sleek cove]

~~what if n negative ~~

[storm sinew]

how can i solve this?

[trim gust]

Well anything above 3! Is just 0.....

[storm sinew]

oh wow youre right 😅

[storm sinew]

how should i start on this problem?

[ornate sonnet]

find the remainder when 6^n is divided by 98 for a few values until u spot a cycle

same with 8

then add

would be my idea

[storm sinew]

oh ill try that, i tried a much different approach, by splitting them up and using chinese remainder theorem and eulers theorem

but ill try your approach, sounds much easier

[ornate sonnet]

yh

my cycle for 6^n looks like

||(6,36,20,22,34,8,48,92,62,78,76,64,90,50,6)||

and for 8^n ||(8,64,22,78,36,92,50,8)||

[trim gust]

notice 6 =7-1, and 8=7+1

[ornate sonnet]

hm very smart

[trim gust]

and also 98 =7^2 times 2

therefore everything cancels excpet 2 times 98C0

so remainder is 2

[storm sinew]

oh wow

never wouldve thought of that lol

[stark bone]

Hi, does anyone know how to code the Chinese Remainder Theorem out in Python?

[fervent crest]

The main problem would be finding the multiplicative inverse

Once you have that it's fairly easy to explicitly write out a solution

[stark bone]

THanks, I'll try to figure it out

[storm sinew]

so, i basically figured out that n=12, but i dont see how i can find out what the 7th smallest possible value of n is..?

[fervent crest]

Remember by chinese remainder theorem

This solution is unique modulo 5*9*11

That means that there is only 1 solution in every interval of 5*9*11 numbers

[storm sinew]

could you please show me an example? :)

[fervent crest]

wdym an example?

example of chinese remainder theorem?

[storm sinew]

no i just didnt understand what you meant by every interval of 5 * 9 * 11 numbers

i mean

[fervent crest]

Oh

[storm sinew]

i dont see how i could find the 7th smallest possible value

[fervent crest]

So you said the solution is n=12, I'll assume that's correct

So the solution set is actually n = 12 (mod 5*9*11), so any number congruent to 12 modulo 5*9*11 is a solution

[storm sinew]

oh wow, so that would basically be multiplying 5 * 9 * 11 by 7 + 12

if im correct?

[fervent crest]

Yes so the answer is 5*9*11*7+12

Assuming 12 was a solution of that system of congruence

@storm sinew

[storm sinew]

12 was a solution, but 5 * 9 * 11 * 7 + 12 wasn't correct :|

actually had to multiply by 6 instead of 7

but i see why

[fervent crest]

Oh yeah oops

[storm sinew]

why wouldnt eulers theorem work here??

i usually put mod 10, and then use the totient of 10 which is 4

so 54^4=1 mod 10

but that doesnt seem to be the case here?

oh wait 54 aint coprime with 10

my bad

lol

[fervent crest]

Yes

What you should do here is first notice that 54^32 = 4^32 (mod 10)

Then calculate 4^32 modulo 2 and 5, and find the result modulo 10 using chinese remainder theorem

[trim gust]

the last digits cycles between 4 and 6

as 32 is even, last digit is 4