elementary-number-theory

[light flicker]

Z[x] isn't a field so that doesn't really make much sense

and whoops I made a mistake

[alpine jasper]

[light flicker]

its the other way around, we should have that f divides g

[alpine jasper]

is g = x - alpha? since an algebraic integer is an integer

[light flicker]

uh, what

algebraic integers are not integers

[alpine jasper]

let me look at the lemma proved in class

[light flicker]

rational algebraic integers are integers

[alpine jasper]

oh, i needed gcd?

[light flicker]

what

[alpine jasper]

what the hell

claim: suppose gcd(m, k) = 1, m != k, then m/k is not algebraic integer

is the thing i supposedly proved in class

[light flicker]

sure

I don't see how this means that all algebraic integers are integers

[alpine jasper]

i missed the gcd part when i claimed that

so good, 1 less misunderstanding

...

[light flicker]

uh

no

[alpine jasper]

wtf

[light flicker]

all rational numbers m/k can be written so that gcd(m,k) = 1

[alpine jasper]

so like 2/3 would not be alg. int

rational algebraic integers are integers
so was i missing complex alg. ints?

[light flicker]

yes

[alpine jasper]

okay i see

[light flicker]

like I said, all rational algebraic integers are integers

[alpine jasper]

yup yup good

so f divides g

let me see if i can convince myself that

can i conclude that f is irreducible?

i want to apply this lemma

[light flicker]

you can prove this yes

[alpine jasper]

hmm alright

okay, idk how to show that f is irreducible

i know that it is monic and least degree

[light flicker]

well what does it mean for a polynomial to be irreducible

[alpine jasper]

umm

wops

it means it cannot be factored

but i don't know how to formalize that

this is disappointing

okay

so f being irred. means if i write f = gh, then either g or h must be constant

[stone void]

ily zoph

[light flicker]

yeah thats what it means

so use the fact that f has the lowest degree now

[alpine jasper]

hmm alright

well i know that i must also assume a being root of f right

if not, then x^2 - 4 = (x - 2)(x + 1) would be a counter example

[light flicker]

uh, f is defined so that f(a) =0 so yes?

[alpine jasper]

oh yeah right.

well ok

let $f = gh$, then plugging in $\alpha$ we know $f(\alpha)=g(\alpha)h(\alpha)=0$, this means $g(\alpha)=0$ or $h(\alpha)=0$, but since $\deg f = \deg g + \deg h$, and $g,h$ clearly can't be constant functions, contradiction since either $g$ or $h$ have lower degree than $f$ and $\alpha$ is a root of them

[light flicker]

yes

[sterile pumice]

Publius:

[alpine jasper]

ok good.

alright

so by proposition (that i will read later), we have f | g

let me see what i can do from there

thanks

[alpine jasper]

i cannot crack this nut open my dude

so i pick p that divides k and find a coefficient that p does not divide, this will show kf is primitive

i just don't know how to find it

don't mind the pink

i did not expect to get bullied this hard by nt when i left algebra

[alpine jasper]

@light flicker papi i need your assistance

[light flicker]

choose k to be the smallest possible like you did

yeah so kf is primitive

do the same thing for l

[alpine jasper]

well i don't know how to prove that kf is primitive

[light flicker]

if there's some number that divides all the coefficients

then you could've chosen k to be smaller

which contradicts the fact that k is the lcm

[alpine jasper]

wow huh...

let me think about that

i'm being mega dumb again

ok i see

that makes sense

same for lh

and since g = fh, lkg = lkfg
but since RHS is a product of primitive poly. it means lkg must also be primitive, but multiply by any constant other than 1 will ruin its primitivity

so k = l = 1

but kf = f only has integer coefficient,

something like that?

[light flicker]

yeah

exactly

[alpine jasper]

[rigid swallow]

a really dumb question probably but if m is an integer and m=sqrt(n) . sqrt(2*n+1) n should be a perfect square , but how can this be proven? ( i assume by contradiction?)

[rigid swallow]

4 has the property that if one adds it to double its square, it yields a perfect square. In other words for natural numbers m,n:
n^2+n^2 +n=m^2

There are four such n<10^6
.If 4 is the smallest nn, what is the second smallest n?

@torn escarp @sacred junco

[sacred junco]

Okay so you know that n*(2*n+1) is a perfect square

[rigid swallow]

yep!

[sacred junco]

Now note that gcd(n,2n+1) = gcd(n,n+1) = 1

[rigid swallow]

gcd is ?

[sacred junco]

So both numbers are relatively prime hence either of them is a perfect square

[rigid swallow]

sorry

[sacred junco]

Greatest common divisor

[rigid swallow]

ohhh

OHH

so if there are two relatively prime numbers they are perfect squares?

[sacred junco]

If you have a product ab = x^2 and gcd(a,b) = 1 then yes

[rigid swallow]

aha i see

how do we prove that though ? @sacred junco ( sorry for the tag let me know if it annoys you)

[sacred junco]

No worries, use the fact that the prime factorization is unique

[rigid swallow]

so the FTOA?

fondamental theorem of arithmetics*

[sacred junco]

Yep

[rigid swallow]

aye thanks : )

[long wasp]

In this Diophantine problem I understand everything except for where 9t and -7t come from. How were they found?

[light flicker]

reduce down the original equation, what do you get

[long wasp]

x = 1/7 (5 - 9 y)

[light flicker]

9 and 7

[long wasp]

Okay, so whats the next step after reducing the original equation?

How does this help me get to the fact that x = 20 + 9t and y = -15 -7t

Solving for y i get y = 1/9 (5 - 7 x)

[light flicker]

so given one solution for x and y

such that x = 1/7(5 - 9y)

you know that the right hand side is an integer

how much would you have to increase y by, so that it remains an integer

[long wasp]

I'd want (5-9y) to be equal to a multiple of 7 right?

[light flicker]

yeah

so you know that 5-9y is a multiple of 7

but how much would you need to change y by, so that its still a multiple of 7

[long wasp]

well if y = -2/9

then 5-9y = 7

[light flicker]

uh, y is an integer

so is x

[long wasp]

if y = 6

5 - 9y = -49

[light flicker]

sure

but now, what would you need to increase/decrease y by, so that its still a multiple of 7

[long wasp]

I feel like I'm not sure what you're asking me

[light flicker]

when y = 6, 5 - 9y is divisible by 7

increasing y by 1 doesn't work, because that would make y = 7 and 5-9y is -58, which is not divisible by 7

so how much would you need to increase y by

[long wasp]

by 7

[light flicker]

and that's why its 7t

[long wasp]

Okay thank you

is there any correlation with the fact that

72/8 = 9, 56/8 = 7

[light flicker]

that's exactly why

I mean, that's how you reduced the equation right

[long wasp]

So my last step in solving these types of problems could be to take (x coefficient/gcd) to get scale for y and vice versa?

Think I get it now. Thanks for the help I really appreciate it

[alpine jasper]

so i'm thinking about 7)

how do i show that all alg int in Q[\sqrt D] has the form a + b\sqrt D?

isn't that like trivial

oh nvm, a and b integer

okay

let me do a quick ms paint to show my attempt ig

nvm i can tex my hand is too cold to write with mouse

so by question 5, i assume $r+s\sqrt D$ is algebraic integer if and only if $2r,r^2-Ds^2\in\mathbb Z$

[sterile pumice]

Publius:

[dire sapphire]

yes (x - r)^2 - Ds^2 has a root r + s sqrt(D) so if x is alg int r, s in Z

[alpine jasper]

i deduced that $r=\frac2k$ for some $k\in\mathbb Z$, this means,\
$\frac{k^2}{4}-Ds^2\in\mathbb Z$\
$\implies k^2-4Ds^2\in\mathbb Z$\
$\implies Ds^2=\frac{l}{4}$ for some $l\in\mathbb Z$

[sterile pumice]

Publius:

[alpine jasper]

so like, if $D\equiv2,3(4)\implies$ all alg. int. have the form $a+b\sqrt D$ is the same as $D\equiv2,3(4)\implies a=\frac{k}{2}$ and $Db^2=\frac{l}{4}$

ugh..

[sterile pumice]

Publius:

[alpine jasper]

and i want to show this implication

am i on the right track..?

i don't know

what am i suppose to show exactly

is this right?

[alpine jasper]

actually it should be like this but i still have no clue

help me @light flicker papa

[vagrant moat]

hint pls

[vagrant moat]

<@&286206848099549185>

[vagrant moat]

got it, I think

Let $p$ (a prime) divide $2^{2^{n}} + 1$. I.e. $2^{2^{n}} \equiv -1 \pmod{p} \implies 2^{2^{n+1}} \equiv 1 \pmod{p}$. Notice that $2^{n+1}\mid p-1 \implies p \equiv 1 \pmod{2^{n+1}}$. It follows that $r \equiv 1 \pmod{2^{n+1}}$.

[sterile pumice]

PolyBeanDip:

[supple furnace]

For n>1, you can prove that r=1 mod 2^(n+2) actually

[sleek cove]

the euler product is cool

[sleek cove]

defining Zeta(s) = sum of 1/n^s is only for the positive integers, correct?

or is it also used for negatives, like -1

Ive heard of this being used to get 1+2+3+4.... = -1/12, but it doesnt seem right

[plain fable]

that sum only converges for Re(n) > 1

also please never mention that sum of integers = -1/12

[sleek cove]

yeah

[plain fable]

will cause mathematicians to want to kms

$\zeta(s) = \frac{1}{\Gamma(s)}\int^\infty_0 \frac{x^{s-1}}{e^x-1}dx$

[sterile pumice]

PorosInMyAshe:

[plain fable]

zeta can be defined like this

[sleek cove]

we havent even looked at the gamma func, just learned the basics today

[swift shard]

Now, you can define zeta(s) for negative numbers, but you can't use the same definition to do so.

See the reflection formula

[sleek cove]

yes thats what i meant

[plain fable]

I think the definition I posted works for all s

[sleek cove]

I saw on wiki it using B, but idk what that is...

[swift shard]

Oh shoot really? Even complex?

[plain fable]

Let me make sure

[swift shard]

That makes sense since 1/Γ is holomorphic

[plain fable]

Ya wikipedia defines it that way too

[winter bear]

yeah the integral is a common defination for zeta

this defination still needs re(s)>1

for integral to converge

[plain fable]

oh really?

I thought it converges for Re(s) < 0 as well

[winter bear]

yeah u need func eqn for re(s)<0

[plain fable]

ah I see

the functional eqn def is ugly

[sleek cove]

it would be false to say that zeta(-1) = sum of 1/(n^-1)

[winter bear]

yes that would be false

the latter is a divergent sum

[sleek cove]

yeah

[winter bear]

zeta for Re(s)<1 is defined different

[plain fable]

no 1+2+3+... = -1/12 definitely

[winter bear]

the easier one is between 0<Re(s)<1

so the sum $\sum_{\bN} \frac{(-1)^n}{n^s} = (1-2^{1-s}) \zeta(s)$

[sterile pumice]

JohnDoeSmith:

[winter bear]

for Re(s)>1

now we can analytically continue this for Re(s) between 0 and 1

and the sum converges

the Re(s)<0 is a bit ugly

[sleek cove]

are you allowed to "pull out" the product? i havent taken analysis yet so im not sure

both products converge so maybe?

[fervent crest]

$\frac{\prod_p\frac{p^2}{p^2-1}}{\prod_p\frac{p^{2s}}{p^{2s}-1}}=\prod_p\frac{\frac{p^2}{p^2-1}}{\frac{p^{2s}}{p^{2s}-1}}$

[sterile pumice]

Whoever:

[winter bear]

products are basically exponentiated sums

as long as the sum thing converges ur fine

[sleek cove]

ok great, thanks

[winter bear]

so if u want

[sleek cove]

i realized i started writing a 2 at some point instead of an s. my handwriting is top tier

[sleek cove]

you can definitely do the same thing with infinite sums, with the same indices and if both converge, correct

[alpine jasper]

okay, idk how to continue

i also have a feeling that it's completely wrong

please help

ok yeh my past paragraph is total shit, u and v can also be both odd

[gilded tinsel]

4 divides v^2-4Du^2. Since 4 divides 4Du^2 this means 4 divides v^2 so v is even. You need'nt go through other cases.

also i see you cancelling 4's in mod 4

not allowed to do that since 4 is 0 mod 4 so its like dividin by 0

you can only cancel when the thing you want to cancel is coprime to the modulus

[alpine jasper]

Oh I see

That was completely bullshit that I wrote

Multiple of 4 reduced mod 4 is 0

[fervent crest]

[sacred junco]

Not sure if this is the correct place but any help with the second part would be great

[light flicker]

the left hand side is an increasing function of x

so just check that the inequality is true when x = y - 1

[sacred junco]

Then I just get x^2 + x > 0

[light flicker]

uh what

how did you get that

[sacred junco]

Substitution of y = x + 1

And then rearranging to cancel out

[light flicker]

I mean okay, yeah, the point is that that inequality is always true

[sacred junco]

I’m trying to make the inequality of 0 < x <= y - 1 into what’s needed

[light flicker]

since x^2 + x > 0 is always true

you can work backwards from this statement, to the statement that you want to prove

[sacred junco]

Right I see, I get that bit but is there a way to rearrange to condition to get the x^3 + x^2 < y^3 - y^2

[light flicker]

no

You have to use the fact that x^3 + x^2 is increasing her

[sacred junco]

Right. Thanks

[inland hawk]

what im getting is that (N_0*phi) = 1
and that summation equals to whatever n is
so it would be (1)(15) = 15 in the end and thats how you get the answer?

@light flicker should i remove the question in #help-9

[light flicker]

N_0*phi is a function

Not a number

[inland hawk]

sorry i should have added this for clarification

[light flicker]

Sure, it's clarified in your picture

[inland hawk]

so any n for this function would come out to 1 cause n^0 = 1

[light flicker]

Sure

What's your point

[inland hawk]

thats what i meant when i said (N_0*phi) = 1

i just want to know if im going about this correctly

[light flicker]

do you know what dirichlet multiplication means

[inland hawk]

not really

[light flicker]

Then why do you think you're doing this correctly

Why are you even trying to do a problem where you don't understand the main point of the problem

[inland hawk]

cuz i need to understand it for my number theory class

[light flicker]

Sure, but why are you even doing this problem

without trying to figure out what the question is even asking

[inland hawk]

i am trying to figure it out thats why im here

[light flicker]

Sure, so go look in your notes and figure out what it means

Don't just randomly guess and try to do the problem without knowing what it means?

[inland hawk]

i found this is this the correct method for dirichlet multiplication

@light flicker

[light flicker]

that's right

now use it for your problem

[inland hawk]

i got 15 @light flicker

[light flicker]

that's right

just like it says in your picture

[inland hawk]

ok

idk i feel like the way the problem was written confused me

[light flicker]

I mean

I feel like you were confused because you didn't know what dirichlet multiplication was

[alpine jasper]

i'm stuck on proving the second part of the question

so i know i assume n odd and v even

my wording is also garbage

could i write that and use the same technique..?

@light flicker help me zoph papa

[light flicker]

uh, even the first line is wrong

27 is 3 mod 4, but isn't square free

[alpine jasper]

well.

[light flicker]

but this is overall the right idea

[alpine jasper]

i guess i should fix the part where i used D is square free and patch it up somehow

well hmm

since 7 is a continuation of 6, and in 6 D is square free

[light flicker]

yeah just assume that D is square free

[alpine jasper]

noice

okay, but i still have no idea how to do the second part

i tried the same trick but then 2a-b being an integer can mean a lot of things about a and b

so the coefficient of the monic poly in Z[x] that sends the thing i wrote in ms paint being integers doesn't really help me

[sacred junco]

i concluded that $\alpha=0$

[sterile pumice]

Slate:

[sacred junco]

im wondering if im wrong, ill supply my proof and reasoning if its outright incorrect

[quick furnace]

you are wrong indeed.

do share your proof @sacred junco

[gilded tinsel]

what about the normal integers as a subset of Z[i]?

[pallid jasper]

just want to make sure, a mod n = b mod n implies a = b, right?

I don't mean $ a \equiv b mod n$

[sterile pumice]

ntky:

[mighty cosmos]

like 4 mod 2 = 0 = 6 mod 2 ?

[sleek cove]

it means their remainders, r_1 and r_2, when didvided by n are equal

[pallid jasper]

isn't that congruence modulo n?

[sleek cove]

yes?

[forest mica]

Can anybody help me? Problem 46

Why did you delete that?

[light flicker]

What have you tried

[forest mica]

Divisibility properties

But I can't get any further than a^n - b^n I 2b^n

[sacred junco]

shouldn't that be a minus

[forest mica]

Yes, my bad

I mean, I'm trying to reach a contradiction. But I can't get any further

[sacred junco]

have you tried doing polynomial division

dividing both by a-b?

[supple furnace]

I recommend letting a=da’ and b=db’ where d=gcd(a,b).

[sacred junco]

oh i get it

[upbeat wren]

is someone still working on the a^n - b^n question?

[winter bear]

whats the question?

[upbeat wren]

46 up on the image file.

but I think they got their answer.

[winter bear]

oh

[upbeat wren]

What's the least representation that is composite in Every base (1s and 0s only as we need base 2). Note: "14" is composite base 10 but "14" is not composite base 13. Funsies.

[gilded tinsel]

do you mean 14 as a base 13 number?

so as 1+4*13?

[upbeat wren]

yes but 14 base 13 = 1x13 + 4 = 17.

[gilded tinsel]

oh yeah sry

what happens if the base is less than a digit?

[forest mica]

is someone still working on the a^n - b^n question?
@upbeat wren I am, but I couldn't get any further. With the aid of the gcd, I was able to deduce that we can assume (a,b)=1, but I can't get any further

[sleek cove]

how long do you reckon the proof of this should be? mines over 2 pages.....i feel i definitely can and should shorten it, and we assume convergence lol

[torn escarp]

do you know what a dirichlet series or convolution is?

[sleek cove]

nope

[torn escarp]

well that's a shame

[fervent crest]

What's lambda?

[torn escarp]

liouville function

[fervent crest]

oh right

lmao

[torn escarp]

the left side represents the convolution of a mobius function with a square indicator function

so you can kinda guess, since both have very particular behaviors to do with squares

[sleek cove]

i literally have no idea what that is lol

[torn escarp]

yeah that's why it's a shame lol

[sleek cove]

I used this, which i proved earlier, and showed that the RHS here is equal to the Sum in the above image

I used a bunch of like, actual writing/english, so it could probably be shortened via symbols and etc, but in general do you think that length is extreme?

[torn escarp]

idk I'd have to see what you wrote, but I am not imagining more than a single page

you said yourself that you're assuming convergence so I don't know what steps you're really taking

[sleek cove]

i mean that, like our prof said that since this is a basic num theory course, we wont dive into the analysis based section of the proof proving that it coverges

and after I try to clean it up, ill share what i did in a bit

[torn escarp]

I would just recreate the dirichlet convolution but not call it that personally

[supple furnace]

@forest mica assuming gcd(a,b)=1, prove that gcd(a^n-b^n,a^n)=1 and then conclude that (a^n-b^n)|2.

[torn escarp]

$$\frac{1}{\zeta(s)} = \sum_{n\ge 1} \frac{\mu(n)}{n^s}$$
$$\zeta(2s) = \sum_{m \ge 1} \frac{1_{sq(m)}}{m^s}$$

[sterile pumice]

Merosity:

[torn escarp]

multiply these together, interchange summation signs and substitute to make it in terms of one variable @sleek cove

that's how I'd go about it

[sleek cove]

hmm, idk what mu and 1_sq are lol

[torn escarp]

oh

$1_{sq}(m)$ is 1 when m is a perfect square, 0 otherwise

[sterile pumice]

Merosity:

[torn escarp]

just derive it in a step here, look:

$\zeta(2s) = \sum_{m \ge 1} \frac{1}{m^{2s}} = \sum_{m \ge 1} \frac{1}{(m^2)^s}$

[sterile pumice]

Merosity:

[torn escarp]

this is only summing over perfect squares

[sleek cove]

ah, yes

[supple furnace]

Just use multiplicativity of lambda (which is easy to see)

[forest mica]

@forest mica assuming gcd(a,b)=1, prove that gcd(a^n-b^n,a^n)=1 and then conclude that (a^n-b^n)|2.
@supple furnace How do you imply from the 2nd equation the 3rd one?

[supple furnace]

If (r,s)=1, then r|st implies r|t

[forest mica]

Ahhh

Now I understand

[supple furnace]

By Bezout’s Lemma, if (r,s)=1, then there is a solution to rx+sy=1, so t=rxt+sty=r(xt+(st/r)y), so r|t.

[forest mica]

And since a^n-b^n I 2a^n => what you said

Yes, I know that theorem

[supple furnace]

Yep

[forest mica]

Thank you!!

[supple furnace]

Np

[forest mica]

@supple furnace I can't think very clearly, and it may be very stupid, but a^n - b^n = 1 has clearly no solutions for n>1, but how can I prove that formally?

[supple furnace]

a^n-b^n>=(a^(n-1)+...+b^(n-1)), which will have at least two terms >1, so a^n-b^n>2 for a,b,n>1.

[forest mica]

What's the second part of the inequality (idk the english word)

[supple furnace]

a^n-b^n=(a-b)(a^(n-1)+...+b^(n-1))

Have you seen this identity

[forest mica]

Nope

It sounds somehow familiar

[supple furnace]

Try to prove it

[forest mica]

Okay

but

(a^(n-1)+...+b^(n-1)

What's between the ...=

I don't get the pattern

[supple furnace]

a^(n-1)+a^(n-2)b+a^(n-3)b^2+...+ab^(n-2)+b^(n-1)

[forest mica]

Now I get it

I'll try to prove it

Thank you for your patience xD

[supple furnace]

Np

[sleek cove]

ok i got it down to like 1.75 pages lol

i could have simplified it some more but idk, also i got lazy with indices

@torn escarp

basically i looked at the number of primes with odd powers in each term to get the lioville func

[supple furnace]

Here’s how I’d do it: we want to find prod (1-p^(-s)+p^(-2s)-...) over all primes, which becomes prod 1/(1+p^(-s)) by the geometric series formula. But then prod 1/(1+p^(-s))=prod (1-p^(-2s))/(1-p^(-s))=zeta(s)/zeta(2s).

[sleek cove]

but how does that yield the liouville func

and i had alr proved that btw

in part a of that problem

[supple furnace]

Just notice that lambda is multiplicative and that unique factorization exists to break it up into a sum over prime powers.

[sleek cove]

uh, i get that lambda is muliplicative, but i cant see where negative coefficients would appear when expanding the product

Like, as you expand the prod, you would get terms with and even and odd number of prime factors so lambda should arise, but i feel they are all positive

[supple furnace]

Look at lambda at prime powers

lambda(p^k)=(-1)^k

[sleek cove]

yes, and lambda( (p_1^k1) x (p_2^k2) ) = (-1)^k1+k2, etc

so when you have an even number of factors, or the sum of k's is even your resulting term is positive, and odd=> negative

[supple furnace]

Yes, so the decomposition follows immediately since each lambda(n)/n^s can be uniquely decomposed into a product of lambda(p^k)/p^(ks) terms

And furthermore every product of lambda(p^k)/p^(ks) terms corresponds to some lambda(n)/n^s

There’s a 1-1 correspondence

[sleek cove]

ah

I was stuck on how expanding the product will yield only positive terms

Like i was trying to work out how to get negative terms in the sum after foiling

I wouldn.t have thought to use that equality for Zeta 2s/ Zeta s

Like part A was proving the geometric series result you used, and part B was proving the product of the alternating sum, and part C was the bonus problem

[supple furnace]

Hmm I see

[sleek cove]

yeah, usually when we have a, b, c etc the latter builds off of the problem directly prior

although it would work in both cases here

[gilded tinsel]

why are you doing dorichlet series when you dont even know dirichlet convolutions or what the mobius function is?

[sleek cove]

if i did, i was not intending to do so

[sleek cove]

@supple furnace after i submitted it my prof told me the same thing, and said it could be done in only a couple of lines

[dreamy rain]

could someone explain where ive went wrong for part iii

i think ive made some incorrect assumption at the top but idk why

well

the smallest possible positive integer combination is 13 so that must mean the hcf is 13 right?

[dreamy rain]

or maybe could someone explain how they would go about this

[stoic bear]

Hint: Factor 36n^2+3n-14

[dreamy rain]

ye ive done that

ig all u need to do is find the values for n when 12n-7/2n+ 1 is integer

not completely sure how id do that

[gilded tinsel]

12n-7=6(2n+1)-13 @dreamy rain

[dreamy rain]

ah right, so ull have 6-(13/2n-1) => 2n-1 must then ewual to one of 1,-1,13,-13

thats a nice way to do it yeah

do u have any idea to why my way that i posted above is incorrect?

[gilded tinsel]

jist because you can find x,y s.t ax+by=c doesnt mean gcd(x,y)=c

bezouts lemma is that the gcd can be expressed this way but not the other way around

e.g 3(1)+(-1)1=2 so by your logic gcd(3,1)=2 which is absurd.

besides, you messed up when you concluded h=13. 1 divides 13 too

so h could be 1

[sacred junco]

<@&286206848099549185>

[harsh mirage]

hint: this is (mostly) all you need https://en.wikipedia.org/wiki/Fermat's_little_theorem

[sacred junco]

Me?

[harsh mirage]

yeah

[mighty cosmos]

I'd be curious to hear how to answer that one, when you've got it figured out, Hrishabh0201

[sacred junco]

No

The link is not opening

But I know fermats little theorem

[stuck lintel]

use lifting the exponent

[sacred junco]

Send solutions

It’s a great idea

But can u send me a solution

[dreamy rain]

jist because you can find x,y s.t ax+by=c doesnt mean gcd(x,y)=c

yes, but if u find c such that it is the smallest possible positive integer combination, then that does mean it is the gcd, doesnt it?

in my case, i have found an integer combination which equals to 13. that will mean the gcd is either 1 or 13 right?

but because the question basically tells u that the fraction is reducible to an integer, the gcd must be 13 shouldnt it? (because if the gcd is 1, meaning that the numerator and denominator are coprime then the fraction can never cancel)

(ik im wrong but i cant see why)

@gilded tinsel

also really sorry for the late reply

[supple furnace]

Idk what the problem is, but n is representable in the form ax+by if and only if gcd(a,b)|n.

So if 13 is representable, gcd(a,b)=1 or 13

@sacred junco Check modulo 101 via modular arithmetic. (You could also note that 2^2+11^4 divides 2^1010+11^2020 (x+y divides x^1005+y^1005) and that 2^2+11^4=(11^2-22+2)(11^2+22+2)=(101)(29)(5).) Either way, the answer is 101.

[mighty cosmos]

I know very little about elementary num th, but I was looking at Hrishabh0201's problem like:

$(2^{10})^{101}+(11^{20})^{101} \equiv 2^{10}+11^{20} \pmod{101}$ ..

[sterile pumice]

Alek:

[mighty cosmos]

does that lead anywhere?

[supple furnace]

That’s how you do it via modular arithmetic. After that, note that 11^4=(20)^2=-4 mod 101.

So then 2^10+11^20=2^10+(-4)^5=0 mod 101

[mighty cosmos]

oh cool

[sacred junco]

Hi

How did you reach that tree

Can you tell in detail

[gilded tinsel]

11^2=121

[sacred junco]

Not that

The divisibility criteria

[gilded tinsel]

just factor

$x^n+y^n=(x+y)(x^{n-1}-x^{n-2}y+\ldots+y^{n-1})$

[sterile pumice]

rockpaperscissors:

[gilded tinsel]

for odd n

[solemn agate]

anyone know modern algebra?

I am willing to pay a tutor

someone to help me understand the problems

pm pleasse

[dreamy rain]

just post the specific problems u dont understand here

im still stuck on ii of this question

i tried to make my argument more clear

i dont quite know where ive went wrong

but i think its around where ive put the red bracket

ik theres another simpler method, but ive seen this method being used for other similar questions so im wondering why it doesnt work here

[harsh mirage]

(i don't know why or if anything is wrong b/c i'm not a number theory guy, but the h = 1 case is missing that the fraction can be an integer still, if the denominator is equal to 1; so n = 0 is also an option)

[dreamy rain]

ah true, that would also mean n=-1 works

thanks i hadnt considered that

[harsh mirage]

oh true

[dreamy rain]

anyone know why 13k+6 doesnt work for all k? it only works for k=0 and k=-1

[harsh mirage]

i think so far you've only shown that it's necessary that n = 13 k + 6 for some k

but not that all of these values have to give you an integer in this fraction

so there's not necessarily anything wrong with that proof

(it's just not complete yet)

[dreamy rain]

ye, so ive shown that if the gcd=13, n must take the form of 13k+6, and thats correct, so how would i show that it only works for k=0 and k=-1 only hm

[harsh mirage]

i think i see the light

you have another restriction, namely that 13 is the highest common factor of 2n+1 and 12n - 7; so see what happens to these expressions when you insert n = 13k + 6

you might be able to compare factors nicely; not 100% sure yet

[dreamy rain]

ooo i shall have a go at that

[harsh mirage]

uuuh or maybe not, not sure anymore

but yeah give it a try, you might see things that i don't

a 13 factors out of both expressions which looks promising

nah, i think even with k = 1, both of these numbers have highest common factor 13

oookay, this might be shit, but if you insert n = 13k + 6 into those two expressions, you get
2n + 1 = 13 (2k + 1), 12n - 7 = 13 (12 k + 5)

you want 2n + 1 to divide 12n - 7; thus, let us do some modular arithmetic with these expressions

modulo 13(2k + 1), we have:
13(12k + 5) = 13(12k + 5) - 5 * 13(2k + 1) = 13 * 2k

(this makes sense whenever 13(2k + 1) is a positive number)

so you have divisibility exactly when 13 * 2k = 26k is zero modulo 13(2k +1) = 26k + 13

for nonnegative k, this is exactly the case when k = 0, otherwise this can never happen

huh, i'm either not getting something or you could just have done modular arithmetic with 12n - 7 and 2n+1 from the very start

without going through the whole highest common factor trouble

[dreamy rain]

hmm

[harsh mirage]

so looking at 12n -7 mod 2n+1, always keeping in mind that you can only do this when 2n+1 > 0

and then probably just reversing the sign for the other cases in some way

[dreamy rain]

yeah lol,i dont see why that wouldnt work, ill have a go

yea

wait i dont think that would work because 2n-1 doesnt necessarily divide into 12n-7

[harsh mirage]

that's what you want to find out, right?

so assume 2n +1 > 0 for now; then we have modulo 2n +1 :
12n - 7 = 12 n - 7 - (6 * (2n +1)) = -13

so you get the restriction that -13 must be zero modulo 2n+1

whoops

wait i think i messed up somewhere

[dreamy rain]

hmmm, maybe this sort of method just wasnt made for this question lol

heres the simple way

i think imma leave it

im starting to confuse myself lol

[harsh mirage]

oooh, that's super close to what i was thinking though

but perhaps it's better to work with fractions like this rather than modular arithmetic when you divide by a potentially negative number

it's less confusing anyhow

[dreamy rain]

yeah

[harsh mirage]

at least i learnt something if you didn't, lol

[dreamy rain]

lol i mean ive been tryna figure this out for a while, ive def learnt something

and thats great that u learnt something as well :)

[sacred junco]

how did the definition of a cong b then (a - b)/m = k for k in Z come about

[light flicker]

this is a nice way to capture the idea of "remainder"?

[sacred junco]

why

[light flicker]

because two numbers have the same remainder mod n if this holds

[sacred junco]

prove it

[light flicker]

you can do it

use the fact that, given integers m,n there are unique integers q,r such that m = qn + r, where 0 <= r < n

This is "division" by n

[sacred junco]

i am reading my book

a friendly introduction to number theory

unfortunately congruences are yet to come i just saw this definition

[light flicker]

okay and?

[sacred junco]

so i will be only able to prove this later

[light flicker]

I mean, you can prove this now

[sacred junco]

that is possible but i would just be experimenting

[light flicker]

that's not a bad thing

[sacred junco]

it is if you don't know what you're doing then it is a waste of time

experimentation is not a bad thing if you have an idea of what to do in that subject

[torn escarp]

depends, I think fumbling around cluelessly makes me appreciate what to do when I eventually learn about it cause I have a reference point

otherwise I'm just inclined to brush it off as common sense or something

[gilded tinsel]

I am stuck on the following problem: Let w(n) be the multiplicative function counting the number of distinct prime divisors of n. Prove there are infinitely many positive integers n,n+1,n+2 such that w(n)<w(n+1)<w(n+2).

its easy to control the number of prime divisors of two consectuive integers but I can't do it for 3

I feel like im missing something obvious

[supple furnace]

Select n=2^a. We prove a lemma: if 2^r+1 is a prime power, then it is a prime or 9. Indeed, suppose 2^r+1=p^k and so 2^r=p^k-1. Then p-1 is a power of 2. If p=3 and r>1 (it’s prime for r=1), then mod 4 implies k is even, and so 3^(k/2)-1 and 3^(k/2)+1 are each powers of 2, forcing k=2 by size. Otherwise, p is 1 mod 4, and so LTE implies r=v_2(p-1)+v_2(k) and hence p^k-1=2^r<=(p-1)k, contradiction unless k=1 (easily seen by dividing by p-1). Therefore, w(2^a+1)=1 forces r=2^k for a>3. Consider each a strictly between 2^(r-1) and 2^r. By the lemma, the first inequality will hold, so it’s enough to find some a such that w(2^a+1)<=w(2^(a-1)+1). If there does not exist such an a, then w(2^a+1)>w(2^(a-1)+1) for each a, and so w(2^(2^r-1)+1)>=2^(r-1), so then 2^(2^r-1)+1>=3(4)^(2^(r-1)-1)=3/2(2^(2^r-1)), a clear contradiction for r>1. Hence this inequality cannot hold for each a, giving some working n between 2^2^(r-1)+1 and 2^2^r+1 for r>2.

[sacred junco]

how do you come up with this shit tree3

[jovial hemlock]

don’t know if this is the right math topic I think it is though

so here’s my question

How do I prove that, if an unknown number X is (a mod c) and (b mod d), where c > d and D = d/GCD(c,d), then X = (a + c * ((a - (b mod (D))) mod (D))) mod (LCM (c,d))?

I don’t actually know whether or not this formula is true.

I’ve been working on an attempted proof that makes heavy use of modulo operators, and as I’ve been doing I’ve been combining things- if X = 9 mod 20 and 5 mod 12 I put down that X = 29 mod 60, and I realised I wasn’t sure that was valid. So I looked up modulo combining rules and couldn’t find any. After a couple hours trial and error I came up with the above formula, but I don’t know how to prove it and I’d prefer to be able to trust what I’m doing. Can I get help?

[light flicker]

Yeah, this seems right and follows from the Chinese remainder theorem

[jovial hemlock]

I’m not quite sure how it follows

honestly the CRT uses terminology I’m not familiar with- I’m in Linear Algebra rn, can you explain it using words from there or lower? It’s not a conceptual issue it’s a terminology one

@light flicker

[light flicker]

Uh, which terminology are you looking at

[jovial hemlock]

any of it

Well one I don’t really get how the theorem shows mine to be true

it can show the result that combining things is okay to be true but it seems to give a verification, not a formula

this seems to be the only relevant bit on wikipedia about having a formula

and I don’t know what bezout coeffecients or extended euclidean algorithm or such are

and either way it seems to require iteration which mine doesn’t

[jovial hemlock]

Question

You are on a grid of width a and height b

and the grid forms a torus so going off one side puts you on the first one

you begin in the upper left corner, and put a 0 there

then move down and right, and put a 1

and so forth until you fill all the squares with their number

How, given the coordinates of a square, can you determine what number was placed inside it without replicating the path?

a >= b

[sleek cove]

did i miss something obvious, or was this problem supposed to be like super easy

[gilded tinsel]

nope

thats fine

[torn escarp]

it's just showing that you can take Omega and extend it to be a function of rational numbers uniquely

[sleek cove]

what does Omega bar represent though? like what does omega bar of (64, 21) mean?

[winter bear]

its as mero said, essentially its counting prime factors of 64/21

with things in the denominator counting as negative

[sleek cove]

wait

so does that mean Omega (x/y) = O(x)-O(y)?

[winter bear]

i mean thats how its defined there?

oh yeah

[sleek cove]

uh

[winter bear]

soz misread for a sec

notice that ad=bc means a/b = c/d

[sleek cove]

oh duh

[winter bear]

so yeah if two fractions are equivalent, you are gonna get same Omega, which is what you should expect

[sleek cove]

why is it written/defined in ordered pair format

[winter bear]

its just a construction of it

[sleek cove]

oh, i was just confused as to what (a,b) like actually was

[winter bear]

you first define the Omega of a pair, and then show that under ad=bc this remains the same

then u can say that this is well defined on fractions

[sleek cove]

it makes since that all rationals will have a ppf, although its kinda wierd saying ppf, since I'm used to exponents being non negative

thanks for clarification

[winter bear]

np

[jovial hemlock]

Question.

You are on a grid of width a and height b, a > b

and the grid forms a torus so going off one side puts you on the first one

you begin in the upper left corner, and put a 0 there, then move down and right, and put a 1, and so forth until you fill all the squares with their number.

How, given the coordinates of a square, can you determine what number was placed inside it without replicating the path?

[wild zinc]

eh

I'm going to assume ||gcd(a,b) = 1|| (which is required for all the squares to be filled)

in which case, this relates to ||chinese remainder theorem||

bc ||n is put in a square that has x coordinate n mod b, and y coordinate n mod a||

[jovial hemlock]

I know it relates to chinese remainder theorem but that requires iteration and such

is there a simple formula requiring no iteration?

[bitter barn]

umm this is probably easier for you guys but can you guys show me how to divide decimals like 2/5.12

[craggy solstice]

not the correctchannel please

#prealg-and-algebra

[wild zinc]

#prealg-and-algebra

[bitter barn]

oh sorry

[wild zinc]

@jovial hemlock the chinese remainder theorem method will be fastest (i.e. n = x mod b, n = y mod a, n = kb + x with k = (y - x) b^(-1) (mod a)), and the modular inverse can be calculated quickly with the extended euclidean algorithm

but yes, it will still be recursive

I don't think an explicit formula is known, and I doubt one exists

[jovial hemlock]

is there any non-recursive formula? it feels like there should be

[wild zinc]

because if there is one, it would give us a way to calculate modular inverses explicitly

[jovial hemlock]

“modular inverse” meaning

[wild zinc]

the modular inverse of x mod m is a number y (also denoted x^(-1)) such that xy = 1 (mod m)

[jovial hemlock]

and why can’t we get that explicitly

[wild zinc]

well I don't have a proof, but the way that they act makes this seem highly unlikely to have a closed form

[jovial hemlock]

wdym the way that they act

[wild zinc]

for example, the modular inverse of 2

hmm

bad example :P

it's always (n+1)/2 if it exists

[jovial hemlock]

3 then

[wild zinc]

okay so the modular inverse of 3 is

(n+1)/3 if n = 2 mod 3

and (2n+1)/3 if n = 1 mod 3

[jovial hemlock]

yeah

so?

[wild zinc]

what about the modular inverse of 7 mod n

[jovial hemlock]

(n + 7 - a) where n = a mod 7

unless n = 0 mod 7 in which case it’s just n

[wild zinc]

that's additive inverse

[jovial hemlock]

sorry

(n+7-a)/7

no

[wild zinc]

I don't think this works

[jovial hemlock]

aargh I’m messing up

((7-a)n +1)/7

[wild zinc]

(n+1)/7 if n = 6 (mod 7), (2n+1)/7 if n = 3 (mod 7), (3n+1)/7 if n = 2 (mod 7), (4n+1)/7 if n = 5 (mod 7), (5n+1)/7 if n = 4 (mod 7), (6n+1)/7 if n = 1 (mod 7)

we have this relationship between the modular inverses of 7 mod n and the modular inverses of n mod 7

[jovial hemlock]

you have two things if n = 6 mod 7

[wild zinc]

but other than that these permutations are essentially random

oops

fixed

[jovial hemlock]

what about 9

is there a list of these somewhere?

[wild zinc]

well (kn+1)/7 * 7 is always going to be 1 (mod n)

so it's just a case of this being an integer

i.e. kn = -1 (mod 7)

[jovial hemlock]

no no

like this is the numbers for x mod 7

[wild zinc]

k = -n^(-1) (mod 7)

yes I know what you mean

[jovial hemlock]

is there a list of the numbers for x mod y

[wild zinc]

I'm just showing you how to generalise it

in general the modular inverse of a mod b is (kb+1)/a, with k = -(b^-1) (mod a), provided gcd(a,b) = 1

[jovial hemlock]

what if gcd =/= 1

[wild zinc]

then it doesn't exist

you can use this to calculate the modular inverse quickly

but it would also have to be recursive

and I haven't checked but it feels like it parallels the extended euclidean algorithm, almost exactly

[jovial hemlock]

so the modular inverse of 2 mod 4?

[wild zinc]

that would require 2x = 1 (mod 4)

[jovial hemlock]

ah

[sacred junco]

[winter bear]

ok so first we define an arithmetic stuff

a function is said to be arithmetic if $f:\bN\mapsto \bC$

[sterile pumice]

JohnDoeSmith:

[winter bear]

(and 0 is not in N)

now some other definations

[tranquil stream]

sup yall

[winter bear]

a function $f$ is said to be multiplicative if $f(ab)=f(a)f(b)$ whenever $(a,b)=1$

[tranquil stream]

jk

[sterile pumice]

JohnDoeSmith:

[sacred junco]

Shush

[winter bear]

a function is completely multiplicative if $f(ab)=f(a)f(b)$ always

[sterile pumice]

JohnDoeSmith:

[winter bear]

we define a binary operation on the arithmetic functions

called the Dirichlet convolution

$(f\star g)(n)= \sum_{d|n} f(d) g\left(\frac{n}{d}\right)$

[sterile pumice]

JohnDoeSmith:

[winter bear]

so far so good?

ill let u guys verify a few axioms. Mainly that this is commutative and associative

[sacred junco]

Yes

[winter bear]

tell me when u have confirmed that

[sacred junco]

Okay go ahead

[winter bear]

oof ok

so if $f,g$ are multiplacitive, then so is $f\star g$

[sterile pumice]

JohnDoeSmith:

[winter bear]

this is one you should actually confirm btw

[sacred junco]

[winter bear]

just hand wave it lol, but this is important

[sacred junco]

Okay you can go ahead

[winter bear]

sigh ok

so a lot of important functions are multiplicative btw

for example euler toitent

or divisor count functions

there is also a dirichlet identity

lets call it e(n)

can u figure out what this function has to be?

identity as in $f\star e=f$ for all $f$

[sterile pumice]

JohnDoeSmith:

[winter bear]

dw the cool stuff is coming up

just bear with me

you working on it?

[sacred junco]

Can I just say 1 for e(1) and 0 otherwise?

[winter bear]

yep

nice

so next is moebius inversion

so moebius function is defined as a multiplicative function such that $\mu(p)=-1$ and $\mu(p^n)=0$ for $n\geq 2$

[sterile pumice]

JohnDoeSmith:

[winter bear]

basically returns 0 if not square-free

and (-1)^prime factors

if it is

define $1(n)=1$ be the constant function

[sterile pumice]

JohnDoeSmith:

[winter bear]

Here is why this is super strong

i want you to compute $1\star \mu$

[sterile pumice]

JohnDoeSmith:

[winter bear]

and tell me what you get

(remember convolution of mult functions is a mult function itself)

[sacred junco]

[gilded tinsel]

wait wats the problem?

[winter bear]

im showing him some basic stuff

no problems

[sacred junco]

How is mobius defined for 1? @winter bear

[winter bear]

oh forgot to say all mult functions are 1 at 1

[sacred junco]

So then wouldn't that composition be 0?

[winter bear]

what about at 1

[sacred junco]

[winter bear]

do you see what $1\star \mu$ is

[sterile pumice]

JohnDoeSmith:

[winter bear]

(btw we call it a convolution not composition)

[sacred junco]

It's the identity

[winter bear]

yep

so $1$ has an inverse

[sterile pumice]

JohnDoeSmith:

[winter bear]

ok so remember how we said

convolution is commutative and associative

heres the nice thing

So let $F(n) = \sum_{d|n} f(n)$ right, then $F= f\star 1$, so $F\star \mu= (f\star 1)\star \mu = f\star(1\star \mu)=f$

[sterile pumice]

JohnDoeSmith:

[winter bear]

that is to say

$$F(n) = \sum_{d|n} f(n) \implies f(n) = \sum_{d|n} F(d) \mu(n/d)$$

[sterile pumice]

JohnDoeSmith:

[winter bear]

This is known as mobius inversion

moebius*

this is a nice result, you can prove for example Z/pZ is cyclic using this

[sacred junco]

That's nice

[winter bear]

theres a lot more where this came from, which ill let u research on ur own

[torn escarp]

also show the form of cyclotomic polynomials

[winter bear]

yeah

thats my fav app of this

one final thing is dirichlet series

[torn escarp]

counting primitive strings in alphabet on b letters

[winter bear]

$D(f;s)= \sum_{\bN} \frac{f(n)}{n^s}$

[sterile pumice]

JohnDoeSmith:

[winter bear]

is the dirichlet series of f

heres the high power theorem that ill let u prove

$D(f\star g; s) = D(f;s)D(g;s)$ given convergence

[sterile pumice]

JohnDoeSmith:

[sacred junco]

[winter bear]

an application

if $\sigma_0(n)$ counts the number of divisiors of $n$, then $\sigma_0 = 1\star 1$ so $\sum_{\bN} \dfrac{\sigma_0(n)}{n^s} = \zeta(s)^2$

[sterile pumice]

JohnDoeSmith:

[gilded tinsel]

actually every multiplicative function has a dirichlet inverse

[winter bear]

yeah try constucting it

[gilded tinsel]

makes the multiplicative functions under dirichlet convolution a group

[sacred junco]

Thanks for the explanation btw

[winter bear]

ill show u some application of moebius inversion if u want, specifically that (Z/pZ)* is cyclic and a nice form for cyclotomic poly

@sacred junco

[sacred junco]

Sure

[winter bear]

ok so lets do (Z/pZ)* is cyclic

so this means that there is some element of order p-1 in that right

now if $d$ is the order of $x$. Then $x^d-1=0 $ in $\bZ/p\bZ^*$ right. also we must have $d|p-1$ by lagrange. The converse is clearly not true, as every element for example has $x^{p-1}-1=0$ but not every element has that order

[sterile pumice]

JohnDoeSmith:

[winter bear]

so far so good?

in a field a polynomial of degree n has atmost n roots

using this, i want you to find the number of roots of $x^d-1$ in $\bZ/p\bZ^*$

[sterile pumice]

JohnDoeSmith:

[torn escarp]

I just remembered something that I found a while back while playing around that you guys might like to see how to derive easily

$\prod_{d|n}d = n^{\tau(n)/2}$

[sterile pumice]

Merosity:

[torn escarp]

maybe try to derive this yourself first and ping me when/if you're ready

[winter bear]

yeah i see it

ill umm spoiler sol

|| S=sum ln(d) implies 2S= sum ln(d)+ln(n/d) = sum ln(n) = tau(n) ln(n)||

[gilded tinsel]

also an interesting identity is $\mu(n)=\sum_{k=1}_{(k,n)=1}^{n} e^{2\pik/n}$

[sterile pumice]

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

[gilded tinsel]

oh well im too lazy to fix the latex

[torn escarp]

http://mathb.in/41555

[gilded tinsel]

but the point is that mu is the sum of primitive roots of unity

[torn escarp]

I do what you do except I just describe it as being like a product rule how additive functions distribute over dirichlet convolution

I showed you that a long time ago now

[winter bear]

oh you might have

[torn escarp]

just trying to think of cute examples for fruct that are easy to reach

[winter bear]

yeah oof ithink he might have left tho

@sacred junco you here buddy?

[torn escarp]

he ded

✝️

have you heard of this problem of counting numbers of primitive strings of length n?

like say you have 0 and 1 and make strings with them like 110001

or 10101010

[winter bear]

i think i read about that in like a blog a while back

but idr much about i

it

[torn escarp]

11001100 is not primitive

cause it's a concatenation of a single string, 1100

1100 is a primitive string cause it can't be made by concatenating a single string with itself

[winter bear]

oh right i see how you could use mobius here

[torn escarp]

yeah how many length n primitive binary strings are there

or any number of symbols not just 2 if you want to go for it

I originally learned the problem from generatingfunctionology

[gilded tinsel]

oh thats pretty easy actually

[torn escarp]

apparently this kind of thing generalizes to necklace rings

[gilded tinsel]

just one application of moboius inversion

[torn escarp]

yeah

well don't spoil it just trying to give problems that are fun

[winter bear]

its like ||k^n convoluted with mobius for k characters and size n right||

[torn escarp]

yeah

actually this reminds me I think I generalized this problem and found a solution to it but as paths on complete graphs

[winter bear]

oh interesting

[torn escarp]

a primitive path is a path that walks on edges of a complete graph on n vertices but is not the same path repeated

basically serving the same purpose as that concatenation does

hopefully that's clear what I'm saying, that might be a little harder try that one

at least complete graph is easiest, doing it for any graph in general maybe that's extra credit Id on't remember if I solved that or just wrote down a formula for it

actually now that I'm thinking, well I could spoil it by saying how I wrote it I think so I won't say it let you think a bit

[winter bear]

hmm ok yeah i think i see

||in general if P(k) is primitive paths of lenght k, then number of paths of size k = P*1, in the case of complete its (n-1)^k = P*1 where n= vertices||

[torn escarp]

yeah I think that's what I got

I looked into it I remember writing it up somewhere when I found it, but I'm curious how you did it

the notes I left for myself weren't so great, but the general solution for an arbitrary graph is here

[winter bear]

oh i just said the overcounting is ||sum_{d|n, d!=n} P(d)||

if i understood what you meant by primitive properly

[torn escarp]

yeah

I think you did, I got uhh.. oh well I'm latexing I don't care if it's hidden at this point

[winter bear]

oh ok

[torn escarp]

$$P_v(n) = (v-1)^n + (v-1)(-1)^n$$

[sterile pumice]

Merosity:

[torn escarp]

v vertices, n steps

maybe I copy pasted my own wrong equation though

[winter bear]

hmm this is true for prime n

but not in general i think, atleast according to the thing i got

[torn escarp]

I think that's wrong

you're right

$$C_v(n) = S_{v-1}(n)$$

[sterile pumice]

Merosity:

[torn escarp]

I ended up writing this

[winter bear]

$P_v (n) = \sum_{d|n} (v-1)^d \mu(n/d)$

[torn escarp]

C_v(n) being v vertices and S for primitive words with v-1 number of letters

[sterile pumice]

JohnDoeSmith:

[torn escarp]

I'm trying to avoid saying what my work was to get it but it's a direct computation

yeah my C_v(n) is your P_v(n)

[winter bear]

oh good

[torn escarp]

well ok I should say how I did it, it's fairly simple once you know

powers of the adjacency matrix give you the number of steps to walk from one point to another

and the ones on the diagonal are exactly the closed paths

so the Tr(A^n) is the total number of paths on the graph in n steps

then mobius invert

[winter bear]

i dont know this graph theory stuff like adjacency matrix rip

[torn escarp]

my work was really just diagonalizing I think effectively the nxn adjacency matrix

a matrix of all 1s except 0s on the diagonal

adjacency matrix stuff is nice, basically you just make a square matrix, and put a 1 if there's a connection between the row and column corresponding to a numbering on your graph

[winter bear]

oh

[torn escarp]

the matrix multiplication ends up encoding a sum of if there's a connection, then there will be two 1s

it's probably better to think of it instead as representing weighted edges on a directed graph

that way you can put more than just a 1 on each edge

anyways, so like the geometric series gives you nice information here too

cause it's the number of ways to get from a to b in some number of steps or less

in each location

[winter bear]

oh yeah i think i see that

[torn escarp]

it's actually nicer if you put probabilities on them

that represent the probability of translating between states

well anyways you see how it's a handy tool for combinatorics and probability, just turns a lot of these things into something about matrices like diagonalizing or plugging into a power series

[winter bear]

interesting, yeah

[sacred junco]

@winter bear

[winter bear]

oh ur alive

did u try doing the thing for the proof?

[sacred junco]

Which?

[winter bear]

ok so given that a polynomial in a field of degree n has atmost n roots

how many roots does x^d-1=0 have in Z/pZ given d|p-1

(keep in mind x^(p-1)-1=0 has p-1 roots)

[supple furnace]

Hehe

Primitive roots proof?

[sacred junco]

[winter bear]

yep

[supple furnace]

This generalizes very nicely to cyclic groups in general

[sacred junco]

@winter bear isn't this d?

[winter bear]

mhm

how did u figure it out

[sacred junco]

[supple furnace]

(Finite fields and in general a finite multiplicative group of any field can be proven to be cyclic like this)

[sacred junco]

Okay gtg

Bye

[winter bear]

rip bai

[supple furnace]

Sleep again?

2 pm nap

[sacred junco]

@winter bear okay I'm back

The elements such that x^d = 1 is the subgroup of order d

[winter bear]

hmm how do you know its the subgroup of order d

[sacred junco]

@winter bear it's in Jacobson

[winter bear]

group theory will only get you its a subgroup

the order is what we are looking for

look at the things i said about roots of polys

[sacred junco]

Wdym it will give me that it is a subgroup

It gives me that it is the subgroup of order d

[winter bear]

elements with x^d=1 is a subgroup, and all lagrange tells u is d|order of subgroup

[sacred junco]

I don't mean Lagrange

[winter bear]

then how hmm

[sacred junco]

'If <a> has order r < infty then the subgroup of H of order q | r is the set of elements b \in <a> such that b^q = 1'

@winter bear

[winter bear]

yeah but see <a> is already cyclic

we are trying to prove Z/pZ* is cyclic

[sacred junco]

Oh lmao

Should have better read the question

[winter bear]

ok so given that a polynomial in a field of degree n has atmost n roots
how many roots does x^d-1=0 have in Z/pZ given d|p-1
(keep in mind x^(p-1)-1=0 has p-1 roots)

but yeah, look at the things i said here

[sacred junco]

Okay then I say at most d

[winter bear]

its till gonna be exactly d, but proving it requires some clever manipulation

(if your having troubles i can give u a hint: ||x^d-1 | x^(p-1)-1||

[sacred junco]

Tbh I'm not too interested into proving it now lel

Can we do it later?

[winter bear]

ok

[torn escarp]

Here's a problem, curious to see what people try. Draw a polygon with any integers you like at every vertex. Label the edges with the difference of the integers on the vertices. Now pick a single prime and write a list of the number of times each number on the edges is divisible by that prime. Prove the smallest number on that list always appears at least twice.

[plain fable]

"Now pick a single prime and write a list of the number of times each number on the edges is divisible by that prime"

what does this mean

[stoic bear]

"Pick a prime p. Write how many times p appears in the prime factorization of each number on the edges and put these into a list." is how I am reading it

[supple furnace]

Sum of all numbers is 0, so if the minimal v_p, for say a_i, is unique, v_p(-a_i)=v_p(a_1+...+a_n-a_i), which can’t happen

[torn escarp]

nice, I like that

[upbeat wren]

@torn escarp I am guessing 1) verticies can be negative and 2) the edges are the positive difference?

oops already solved.

[torn escarp]

either way is fine, negative or positive won't affect the divisibility by primes

[upbeat wren]

hmm but the sum need not be zero if you allow both positive and negative elements? 0,0,0,0,1,0 is either 0 or two.

I really like the problem, but it might require another slight restriction.

Okay so verticies: 0, 0, 0, 1, 2, 0, is a better example. edges: 0,0,1,1,2,0.

Even without zeroes ...

1, 2, 3, 4, 5, 0 --> 1, 1, 1, 1, 5, 1 ...

[torn escarp]

the sum being zero that tree3 describes is the sum of the edges

cause they come from the differences of the vertices in a cycle, that's how he does it at least

well, my argument that I have for the solution doesn't depend on the sign of the terms, and he could alter his to not depend on it either

[supple furnace]

Yeah the signs don’t affect the vps at all

[torn escarp]

well, if I say you are forced to put the positive number on the edges, then you can't add 0 in the way you did so cleanly

but you can still break it up by the ultrametric inequality to get it to work out anyways so it doesn't matter

[obtuse mason]

a^b + 1 is prime, then a even and b is power of two

How do I go about proving something like that?

[winter bear]

what did you try

[obtuse mason]

that's the problem I don't know where to start