elementary-number-theory

[sour rivet]

Ah OK that is very helpful, thank you

[south oar]

I realized I used "numbers" twice

I meant if the a_i's form a periodic sequence then the number this continued fraction represents is the root of a quadratic equation with rational coefficients

[sour rivet]

Yeah thank you for clarifying, thats what I assumed was meant

Sqrt2 is nice because it's 1, 2, 2, 2, ...

But this other number won't have a periodic sequence because it's not the root of a rational coefficient quadratic

(In other words, because it's transcendental?)

[south oar]

😅 I don't know enough number theory to know if this is transcendental

But if it is then it certainly won't be the root of a polynomial as that would be algebraic

[torn escarp]

yeah basically that's it

although it's true for algebraic ones like you were saying that aren't those nice special quadratic case

[cyan fox]

Oh i see thanks

[cyan fox]

But actually i think i have to use different k aswel

Like k1 and k2

[last cove]

how would i start thsi

[still flare]

Think about what values of alpha and beta can be put in. Hint: they are completely separate and can be varied independently.

[last cove]

so what do i do with the x then

[still flare]

The x is not a variable; it is the argument of a function.

[last cove]

so is there a formula i could use or do i just guess the numbers

[still flare]

There shouldn't be any guesswork involved

You will have to come up with a formula.

[last cove]

yea i have no idea how to do that

is there any videos that you'd recommend for me to watch for this question

[still flare]

I doubt there are any

[last cove]

so what is the question actually asking

like this is the last question but i dont understand it at all

[last cove]

@still flare

[still flare]

Do not ping me to demand help. I am not always available or willing to answer questions.

[last cove]

my bad

[torn escarp]

an enciphering function has to be invertible. you're multiplying by alpha and adding beta, so you need to know when can you invert multiplication and addition?

[pulsar coyote]

I need help on this question

[wooden glen]

Not really number theory, but https://en.wikipedia.org/wiki/Cesàro_summation gives some ideas for the second part.

[pulsar coyote]

thanks

what about the first part.

Also where does this belong to

proofs

or discrete

[wooden glen]

I'd say calculus or real analysis. I'm always in doubt about that distinction.

[modest oriole]

63N1=1(mod5) => 3N1=1 (mod5) => N1=2

I can't understand how to this work

I need some help

[pliant carbon]

You mean how it went from 63n1 to n1?

[pearl gyro]

Hello! Can I have some push in the right direction to prove this? I know the equation should have a perfect square form so I should prove that, but I am not sure how to start it

[torn escarp]

if it has at least one solution, then you can factor out a linear term from it

[inner anchor]

Multiply both sides by 4 and factor

[still flare]

Doesn't work for p=2.

The multiplying by 4 method, that is

[inner anchor]

Not a very hard case to consider separately

[grave echo]

ye

[torn escarp]

then if both roots are the same, you can equate the coefficients on (x-r)^2=x^2+x+1 mod p and work out what restriction that puts on the root r, and it leads to it being impossible

[pearl gyro]

so like this?

[analog onyx]

If I have a diophantine equatoin ax+by = c where gcd(a,b) =/= 1 , and then i find the solution (x1,y1) to (a/d)x + (b/d)y = (c/d) (assuming d | c ), then (x1, y1) will also be a solution to ax+by = c?

[ionic pier]

Yes, you just multiply by d

[wind glacier]

In how many ways 2 bananas can be distributed among 5 persons if each person can get any number of things?

i got the answer 21 but is it right? also is there any general formula for these types of questions

[brisk belfry]

x^2 can be written as abc, x^3 can be written as dace. x^4 can be written as dfgba. Same letters mean same numbers. Find the number x

I know, that the answer is 13, but i would like to prove it, not to solve it by coincidence, please help

[latent hare]

Hmm, you can set a bound on x first (try to find which numbers have a square that is 3 digit along with the numbers whose power of 4 has 5 digits) ||10 <= x <= 17||
From here just checking all cases?

[brisk belfry]

yes, i did so, but i am not allowed to check cases

I need to set such bounds that there is only one number left

[austere sorrel]

Is this a correct proof? I saw this statement in a book and tried to write a proof of it myself.

[wooden glen]

You'll probably want to replace that screenshot with a tighter crop that doesn't self-doxx you...

[austere sorrel]

oh, thank you

[sacred junco]

Quick question, i wanted to find 4^9 mod 13. I know 4^12 mod13 will be 1 because of fermat's theorem. So i just raise the congruence $4^12 \equiv 1 mod13$ by $frac{1}{4}$ which gives 4^3mod13=1 then i can square it to get 4^9mod13=1 but this is wrong

I should be getting 12 instead

$4^{12} \equiv 1 mod13$ by $\frac{1}{4}$

[sterile pumice]

N0chin

[sacred junco]

Perhaps taking the 4th root is wrong but i thought it shouldn't be a problem since 4 and 13 are coprime

[stiff rivet]

a^4 = 1 does not imply a = 1

@sacred junco

the solutions to this are a = 1, -1, i, -i

which in this case are 1, 12, 5 and 8

[sacred junco]

Oh yes, but i didn't know if i can include imaginary numbers too

I see

[stiff rivet]

hm, maybe that was misleading

its not a complex number, its shorthand for "a number that squares to -1"

notice that -1 = 12 mod 13

and that 5 and 8 both square to 12 = -1 mod 13

[sacred junco]

Looks like my basics are not clear

[stiff rivet]

maybe this isnt too important

the important part is x^4 = 1 does not imply x = 1

[sacred junco]

Yes

[stiff rivet]

so you cant just take 4th roots on both sides

[sacred junco]

I see

Thanks

[stiff rivet]

there are (in this case) 4 solutions for x

so you would have to consider 4 different cases

[sacred junco]

Yes, i guess i can't be lazy with roots

So how can I find 4^(105)mod13 if you don't mind

[stiff rivet]

use fermats theorem to reduce the exponent

then probably just calculate

[sacred junco]

I see, i was going through Engel's book

So there was an exercise for this

[white lion]

Excercise 10 the answer is a_n

Im fairly certain what I need to do with Excersice.11 is set a_n= n+2/2(n+1)

then find a_i/a_i-1 such that a_i is = i+2/2(i+1) and a_(i-1) is easy to find

then once I find a_i/a_i-1 it should be equal to the expression that is inside the multiplication notation

which would then be equal to a_n and a_n is equal to what i set it too.

but when I try to solve a_i/a_i-1 I dont get the expression I want, namely the expression inside the multiplication notation

[wooden crater]

recall that a^2 - b^2 = (a + b)(a - b)
apply this with a = 1, b = 1/(i+1)
@white lion

should help you recognize ai/ai-1

[white lion]

@wooden crater no not really

hm.

[white lion]

😦

[torn escarp]

here's one way to look at it, make same denominators and then simplified to $$\prod_{i=1}^n \frac{i(i+2)}{(i+1)^2} $$ then since you want it to match up you can group i with i+1 and i+1 with i+2 like this: $$\prod_{i=1}^n \frac{\left(\frac{i+2}{i+1}\right)}{\left(\frac{i+1}{i+0}\right)}$$

[sterile pumice]

Merosity

[white lion]

I’m definitely going to try that thanks!

[white lion]

nvm im an idiot i figured it out

its not what you said

[uncut pumice]

this is a version of the generalized binomial theorem on wikipedia. where r is a complex number, x and y are real numbers with |x| > |y|.
Question: what if x or y is negative and the exponents require the computation of the n th root?
e.g. Put x = -2, y = 1, r = 1/4

the fourth root of a negative number has 4 values to choose from, how should I pick the roots?

[upper gale]

r is an integer in [ 0, +infinite [ if i recall

for all r *, so 1/4 won't work

[uncut pumice]

nvm, I found it on the same wikipedia page

[torn escarp]

It's easier to look at as coming from $$(1+\frac y x)^r =\sum_{k=0}^\infty \binom{r}{k}\left(\frac y x\right)^k$$. Since in the sum you only ever have $\frac y x = -\frac 1 2$ being raised to integer powers $k$, there's no root to consider on that side. The root is entirely decided from factoring out $$(1+\frac y x)^r = \frac{(x+y)^r}{x^r}$$ so you're really taking the 4th root here and deciding which one, so when it's multiplied to the other side, it just is consistent with this choice.

[sterile pumice]

Merosity

[potent wharf]

Could someone help me understand what congruence classes are, I don’t see how they link a=k+b and [a]_1

[torn escarp]

one way to look at it is two integers are in the same congruence class modulo n if they have the same remainder when divided by n

all integers have 0 remainder when divided by 1, so all integers are in the same congruence class modulo 1

I'd recommend not focusing on modulo 1 for a bit since it's so simple of a case that it can be confusing, focus on understanding modulo 2 and 3, or maybe modulo 10 might be easy too since mod 10 is just the last digit of the number

[potent wharf]

I see, in terms of what [a]_1 represents, is that when modulo n=1 and a is all the integers that have the same remainder when divided by 1?

[torn escarp]

that sounds about right to me

a is a specific number, it's a representative for all other numbers that share the same remainder when divided by 1

[potent wharf]

I see so [a]_1 isn’t a set? But rather one thing

[torn escarp]

[a]_1 is the set of numbers, a is just one number

so while a != b, [a]_1 = [b]_1 since they are the same sets

[a]_1 is a set, which is one thing

maybe at some point you learned even*odd = even or even + odd = odd

this is really the same thing, working with congruence classes modulo 2

[potent wharf]

Okay I think I understand now I’ll ask if I do have more questions, thanks 🙂

[torn escarp]

you're welcome, good luck

[languid spade]

In Gaussian Integers, does anyone know why $\gcd(x+2i,x-2i)=\gcd(x+2i,4)$?

[sterile pumice]

TheUnTamed

[languid spade]

I'm applying division algorithm but can't seem to find a pair which produces r=4.

I know that $N(x+2i)=N(x-2i) \le 4$, which hints towards division algo and applying the fact that the Gaussian Integers are a Euclidean Domain following $N(r) < N(b)$ for $a = bq+r$.

Where N(k) is the norm function.

Context:

[sterile pumice]

TheUnTamed

[somber timber]

are you guys even elementary now??

[languid spade]

Sorry, I don't really use this server 😖

Is this #advanced-number-theory ?

[languid spade]

Ok I think a convoluted possible explanation is if $p|\gcd(x+2i,x-2i)$, then $N(p)|\gcd(N(x+2i),N(x-2i),N(2x) \implies N(p)|\gcd(x^2+4,4x^2) \implies N(p)|\gcd(x^2+4,x^2-12) \implies N(p)|16 \implies N(p)|N(4) \implies p|4$ since $p$ is irreducible. The last step doesn't seem very rigorous but if anyone has a better explanation please tag me.

[torn escarp]

just the euclidean algorithm gcd(a,b)=gcd(a,b-a) and factoring out a unit since it doesn't matter

[languid spade]

Oh my god.

You're right.

I forgot i was a unit.

♿

Thanks!

[torn escarp]

😛

you're welcome!

[tranquil briar]

if m and n are congruent modulo p

and v and w congruent modulo p

are mv and nw

[still flare]

They sure are

[uncut pumice]

I think this is correct, is there a name for this? and how do I prove it

[still flare]

This is Euclid's lemma, rephrased

This states that if b | ap and p does not divide b, then b | a

Now we usually state it as follows, contemporarily:

If $a \mid bc$ and $a$, $b$ are coprime, then $a \mid c$.

[sterile pumice]

Boytjie

[still flare]

The typical proof of this is a nice application of Bézout's lemma.

[uncut pumice]

bravo, thanks!

[still flare]

No worries

[icy kayak]

Anyone here ever play with the Collatz conjecture?

[still flare]

I'd rather waste my time doing something more fun

[sacred junco]

why not Riemann hypothesis you will get 1 million i guess if you solve it

[sacred junco]

how might I prove this?:
if S is the set {1,2,3,...,20}, prove that for any element a of S there exists an element b in S such that a^2+b^2 is congruent to 0 mod 41

have so far that 1^2,2^2,...,20^2 are all distinct mod 41

[torn escarp]

if you have a^2+b^2=0 mod 41 for some a, b in {1,...,40} you can always replace b with 41-b if it's larger than 20, so you can be a bit lenient if that helps

because S are invertible elements and 41=1 mod 4 you have solutions to x^2+1=0 mod 41

[sacred junco]

how would I use that in the proof

[torn escarp]

well if I say any more I'd just be proving it entirely, but I think I was ambiguous there

you can use the fact that there is some x that satisfies x^2+1=0 mod 41 to turn it into a^2+b^2=0 mod 41

hint: ||multiply both sides of the congruence x^2+1=0 mod 41 by a^2||

[sacred junco]

Ooohh the b I'm looking for would just be a*x right

[torn escarp]

not necessarily, but nearly

it might not be in S

[sacred junco]

And if it isn't i can just have it be 41-b

[torn escarp]

exactly 👍

[sacred junco]

Thanks

[torn escarp]

yup you're welcome

[icy kayak]

Lol, because I can actually comprehend the problem of Collatz

Not sure if it is new, but I managed to generalize the problem to the reals, so I could make irrationals "converge" to other irrationals in the limit of an infinite amount of iterations. If I can prove that (more than doubtful), then the Collatz conjecture will also be proven. It was fun to work on, but yeah feels like wasting time mostly.

[sacred junco]

Good luck! Who knows everything possible

[icy kayak]

Thanks! I haven't really worked on it hardcore in a few years, but I started thinking about it again last night.

[tropic yarrow]

some japanese ceo i believe is also offering around a million dollars for the collatz conjecture solution

[uncut pumice]

how does this inequality work? here n is floor(x) so that n <= x < n+1

might have been a typo?

[uncut pumice]

• log (x + 1) would make more sense than - log x + 1 in second numerator

[sacred junco]

given 7x = 2 (mod 20), why can't we multiply by 6 to get 42x = 2x = 12 (mod 20)? because now, if we multiply by 6 again, we get 12x = 72 = 12 (mod 20), but 1 is not a solution to the original congruence. what happened?

[left jetty]

is the negative base representation of a number unique? for example -2 base.

[stiff rivet]

6 is not invertible mod 20 (in fact it is a zero divisor), so this is not an equivalence transformation
your original problem is equivalent to solving 7x - 2 = 0 (mod 20); now if you multiply this by 6*6 = 36 = -4 (mod 20), you are instead looking at solutions of -4(7x-2) = 0 (mod 20)
now note that -4* 5 = -20 = 0 (mod 20) and thus you introduced the nontrivial solution x = 1

[sacred junco]

36 is not = 12 mod 20

@stiff rivet

[stiff rivet]

uh

sure

[sacred junco]

But you wrote that it is

[sly talon]

Where do the 19^n and 9^n dissapear?

and why does it dissapear?

[stiff rivet]

edited

the argument stays the same

you introduce new solutions due to 6 (or 6*6) being a zero divisor

[sacred junco]

But I can prove that if a = b mod m then ac = bc mod m

So what goes wrong?

[stiff rivet]

you cant go backwards

ac = bc mod m does not imply a = b mod m

[sacred junco]

Okay

[stiff rivet]

you keep the original solutions

you just also introduced new ones

[sacred junco]

I see, okay, so with that in mind, how do I still get the original solutions alongside these new ones? Because as you wrote, x = 1 is an obvious solution, but it clearly isn't in the original equation

[stiff rivet]

i dont think what you did helps with that

[sacred junco]

Why?

[stiff rivet]

because you just end up with a different linear congruence, except this one is worse

why not do what you would do "normally" and find the inverse of 7?

gcd(7, 20) = 1

so using the euclidean algorithm you can find integers a, b such that 7a + 20b = 1

then a is an inverse of 7 mod 20

and you multiply by this

[sly talon]

?

[sacred junco]

What do you know about modular arithmetic?

[sly talon]

almost nothing

[sacred junco]

Well, have you read your book or whatever other material?

[sly talon]

yes but it does not tell that

[sacred junco]

I don't believe you

[sly talon]

its prolly something with a+c=b+d

it has only basic poperties

[sacred junco]

You can think of it that way, if it helps

Try expanding 36^n = (34 + 2)^n

[sly talon]

and how does that help

[sacred junco]

Have you tried?

[sly talon]

but what do i get from it

[sacred junco]

The answer to your question?

[sly talon]

hows

[sacred junco]

Try expanding and you'll see..

(and 34 = 17 * 2 if that's not clear)

[sly talon]

well ok i get 2^n+17^2n+17^n+2^n-2^n+1

oh

[sly talon]

thanks mate i forgot about (a+b)^n could also be c^n

[sacred junco]

No problem

[sly talon]

it is still not clear but can i like show for each bracket that it does not divide and then sum up the results which make 0?

(2+17*2)^n/17 and (17+2)^n/17 and -2^n+1/17

all with mod 17 and then show 2+2-4=0

cause i still dont know how to get to that eqn

[sacred junco]

how would I prove that 3^1, 3^2, ..., 3^6 are the only residues of order 7 mod 1093?

it's easy enough to show that those all work since 3^7 is congruent to 1 mod 1093 but how can I show there aren't any others

[wooden glen]

Do you know that 1093 is prime?

[sacred junco]

yeah it's given

[wooden glen]

So Z modulo 1093 is a field.

In a field, the polynomial x^7-1 can have at most 7 roots.

[sacred junco]

is there a way to prove it without abstract algebra that you know of

this was on a mock amc 12

[wooden glen]

I don't know how to even speak about orders of residues without algebra.

[sacred junco]

oh then carry on then

[sacred junco]

sorry I meant "carry on" as in keep going with the proof

[wooden glen]

There's nothing more to it. You know 7 different roots of x^7-1, namely 1, 3, 3², 3³, ..., 3^6. Because Z_1093 is a field, there can be no others.

[native monolith]

Nice question

[wooden glen]

The first half of the hint doesn't seem to do anything useful.

[torn escarp]

I was thinking they meant once you know what to do when n is prime lets you say when n is composite X^n +1 =(X^(n/p))^p + 1 can then be factored the same way

[wooden glen]

Hmm, okay.

But at least in the solution that immediately strikes me, the key fact that X^n+1 factors in a certain way if n is odd and >1, independently of whether it is prime or not.

[torn escarp]

true, I didn't think too much about it

just thinking once I get an odd prime, then that covers all cases by induction but

you can just go directly for the whole thing when odd

[native monolith]

Yeah it's a red herring 😂

I just considered cases, n was odd then $(a+1)$is a factor so not prime. If it is odd then take $n=2^k y$ but then $a^n+1=a^{2^ky}+1=(a^{2^k})^y+1$ as y is odd then it can be factored like before.

[sterile pumice]

Max..

[analog onyx]

anyone know how i can derive the formula F_(k+1) * F_(k-1) - (F_(k))^2 = (-1)^k where F_k is the kth fibonacci number? I’ve played around w it a bit but i can’t seem to derive it from scratch

[torn escarp]

have you tried the closed form in terms of the golden ratio? that's what I'd try personally

not the one with rounding, the one that involves both roots of x^2-x-1 to powers

[analog onyx]

with phi and -1/phi?

i havnt, i’ve been using the recursive formula but i’ll play w it using the one i think you’re talking about

i’m not sure what you’re referring to about the rounding one though not that it matters

[buoyant mason]

I don't know if this is the most efficient way but you can look at the forms a number with $2020=2^2\cdot 5\cdot 101$ divisors must be in. For example $p_1^3\cdot p_2^4\cdot p_3^{100}$ is one way

[sterile pumice]

layla💜

[buoyant mason]

p_1, p_2, p_3 distinct primes

and p^(2019) is another way for example, but that's not going to be smaller than the smallest number of the other form

[west glade]

that is definitely the way to go about doing this

[buoyant mason]

and of course we just want to pick the smallest primes

any form with an exponent >= 201 is not going to be worth looking at

so that narrows down it already

[buoyant mason]

because 2^201 is larger than a number you can find in this form

7^3 * 5^4 * 2^100 < 2^201

@sacred junco following so far?

:c

np ^-^

[dapper anchor]

Can we have negative classes in integer mod 3?
I know [2] =[-1] but does that mean [-1] is in Zmod3

[west glade]

it doesn't matter which number you use to represent a particular class

like you said,[2] and [-1] are the same thing

so if [2] is in Z_3 (which it is), then [-1] is aswell

for doing calculations it is sometimes pretty useful actually to use negative numbers for representing a class

e.g. calculating the powers [88]^n mod 89 would suck, but the powers of [-1]^n mod 89 are very easy to compute

[dapper anchor]

Thanks 👍

[sly talon]

if i have 3n^5=x mod 7 can i take the ^5 off?

[sly talon]

?????

[west glade]

no

why should you be able to just ignore that

[sly talon]

thats the same

like 3n^5 should be same as 3n?

[west glade]

no those are not the same

[sly talon]

so what should i do?

[west glade]

you could just bruteforce it

7 is pretty small

[sly talon]

wdym?

[west glade]

well just try out every element n=0,1, .., 6

[sly talon]

wtf thats boring

why cant i ignore the 5

[west glade]

because it's wrong

3n^5 is not the same as 3n

for example n=2

[sly talon]

its not but isnt there a^c=b^c mod m

[west glade]

3*2^5=5 but 3*2=6

if a=b then a^c=b^c, yes

but the other direction is false

also even if it was true, where is another ^5 in your question

[sly talon]

well answer is the same

no its not

[sly talon]

so how to ace number theory if i am learning it on my own?

[torn escarp]

one way to get started is if $n=0$ then $x=0$, otherwise by fermat's little theorem $n^6=1 \mod 7$ so $n^5=n^{6-1}=n^6 n^{-1}=1n^{-1}=n^{-1}\mod 7$.

[sterile pumice]

Merosity

[torn escarp]

I think most people find books to work through

[sly talon]

good one?

[torn escarp]

what's your goal in learning number theory

is it a class you're taking in university, you're a highschool student wanting to study for olympiads or just learning for fun on your own or something else

I like Silverman's A Friendly Introduction to Number Theory

but it might be a bit too slow paced for you and not enough practice problems if you're interested in competition math

[sly talon]

olympiad

like i have only 2 weeks left for fast one and like 4 months till next one

[upper gale]

hi, there is one way (=>) idk how to start/prove it. The other one (<=) is the easiest one (thanks to Gauss theorem)
n is an integer*
Show that 7|n if and only if 7|5n

[sly talon]

maybe 7/n * 1/5 ?

idk if that helps and it works like that

[prime sparrow]

that direction is even easier since n | 5n, 7 | n and divisibility is transitive

[upper gale]

ah this direction stands on one line

Ty

[torn escarp]

which Gauss theorem is that? I was thinking more like Euclid's lemma for (<=)

[upper gale]

huh idk how you call this theorem but i call it Gauss theorem

if a|bc and (a and b are prime? coprime? idk the wording for GCD(a,b) = 1)
then a|c

[torn escarp]

I see, gotcha

[uncut pumice]

is there a proof for this? where B_j is the j-th Bernoulli number

my lecture notes has this recurrence relation, I guess it's provable by induction?

[pearl gyro]

Hello! can I substitute with congruence equations?

this is the function f, and I am trying to show that n \equiv f(f(f(f(n)))) \mod 9

like this

[still flare]

You can indeed do that.

[mossy rampart]

Find all $(a,b) \in \mathbb{Q}$ that are such that the numbers $\frac{ab+1}{a} , \frac{ab+1}{b} \in \mathbb{Z}$

[sterile pumice]

Emmanouel

[pearl gyro]

thank you! which property of congruences would this be using?

[still flare]

This is not really a property of congruences. You have proved that for any n, n = f(n) mod 9. So we choose appropriate n twice to get that this is true.

[pearl gyro]

ah I see!! thank you so much for the help~~~

[mossy rampart]

guys any help...

[torn escarp]

do you know how to evaluate the euler phi function normally?

think of it as phi(2^N)

[runic token]

what's a 3-perfect number

[torn escarp]

googling out of curiosity, https://oeis.org/A005820 seems to be when sigma(n)=3n

[pearl gyro]

hello! is my reasoning here okay?

[torn escarp]

what's f(n)?

[runic token]

uhhhh note that u have $2^k3^2p = 3 + p + \sum_{c=1}^k2$

[sterile pumice]

valley

[runic token]

you can use that to get a lower bound on k with induction (hint: ||try a fairly low number||)

and then you can wrangle that into a lower bound on p (hint: ||subtraction and grouping!!||)

fun problem!

i wish i had a more elegant solution tho ngl lol

u have to check a few cases this way

[torn escarp]

that's not quite right for the sum of divisors

[runic token]

.>

do you need to include n as a divisor?

[torn escarp]

tons of other divisors are missing, like 2p, 3p, 4p, etc

[runic token]

hmm

[torn escarp]

it's a multiplicative functions o assuming $p \ne 3$, $$\sigma(2^k3p)=(2^{k+1}-1)(1+3)(1+p)$$

[sterile pumice]

Merosity

[runic token]

aight hol up cuz i got actual numbers

1s lemme check this shii

FUCK ME

[torn escarp]

that'll get all the combinations of divisors together when you multiply it out, I compressed the 1+2+...+2^k into 2^{k+1}-1 as a geometric series of course but

[runic token]

this is not happy im malding fr

[torn escarp]

heppens to all of us sadly

[pearl gyro]

this!!

[torn escarp]

Simplifying a bit since those factors are relatively prime I get those two integers make $9$, $$\frac{2^{k+1}-1}{p}*\frac{p+1}{2^{k-2}} = 9$$ then basically this forces one of three scenarios for how to distribute the $3$s as divisors, in a fancy way can be written as $i=0,1,2$ on the conditions $p=-1 \mod 3^{2-i}$ and $2^{k+1}=1 \mod 3^i$. I feel like a little more can be done, since $\mathrm{ord}_3(2)=2$ and $\mathrm{ord}_9(2)=6$ we can say $k+1=2m$ and $k+1=6m$. It's starting to get a bit gross though so maybe it's worth stepping back and seeing if there's some other approach to take before pushing further

[sterile pumice]

Merosity

[torn escarp]

oh, set $2^{k+1}-1=pa$ and $p+1=2^{k-2}b$ with $ab=9$ and substituting with the $2^{k-2}$ from the second one into the first one with multiplying through by $b$ to get $$b2^{k-2}2^3-b=pab$$ $$(p+1)8-b=p9$$ $$p=8-b$$ Since $b$ is only either $1,3,9$ it means $p=7$ or $p=5$ are the only solutions.

[sterile pumice]

Merosity

[torn escarp]

then make sure to work out what k can be

[runic token]

OKAY I FUCKING FIGURED IT OUT

ONLY TOOK 30 MINUTES

goddamn

so apparently you have ||3n=(4p+4)\sum_{c=0}^k 2^c|| and you can use that

gods that took so much longer than it should have

strategy is the same

[torn escarp]

my final answers I got for checking ||120 and 672||

[runic token]

and i got two numbers and im correct according to the oeis link so im fkin done

||120 and 672?||

yes

THANK FUCKING GOD

i would have actually fr cried if i'd gotten that wrong

also shit it's 1:34 and i have a chem test tmrw i was gonna study for

uhhh stay up til 2 and study or js sleep

i have to wake up by 6:30

.>

[upper gale]

Hey!
How may I prove this way? (it is originally an equivalence and the other way is easy for me)

Let p, prime number
a, b, two integers

p|a or p|b => p|ab

[buoyant mason]

the other way was easier? interesting haha

this way should be easier?

[upper gale]

Idk how do I proceed to get p|ab at the end

[buoyant mason]

what does p|a mean?

[upper gale]

p|a => GCD(p, a) = p, since p is a prime number

[buoyant mason]

how about the definition of p|a?

[upper gale]

There exists k in Z such that a=pk

[buoyant mason]

yea, so how might that relate to the expression ab?

[upper gale]

Multiply by b? I guess

[buoyant mason]

sounds good

[upper gale]

Okay Im convinced now

Ty!

[buoyant mason]

np 🙂

[tawdry sapphire]

I would like too ask how to show the following is true? I have proved that the order of 3 is 3^(2^(n-2))

I am stuck at proving elements are pairwise incongruent part, idk how to show 3^i is never congruent to -3^j 🥲

[uncut pumice]

from my lecture notes, does this miss the condition that a and b are coprime? otherwise, put p = 7, 1/2 is considered a p-integer, but not 7/14.

[still flare]

Yes, good catch.

[sterile pumice]

Emmanouel

[potent wharf]

Could someone explain to me how to go about this question, my understanding is quite lacking on modulo

For something to be a field it must satisfy all the axioms on the binary operation of addition and multiplication

I know that [a]+[b]=[a+b] and [a][b]=[ab]

I’m probably overlooking a lot of things but surely the two above properties means that all the axioms will be satisfied?

[still flare]

No.

You should look back and review the definition of a field.

[potent wharf]

It says that a field is a set F that satisfies all the field axioms?

[still flare]

Right, so perhaps you should check the field axioms.

[potent wharf]

I’ve done it already for addition

Is this correct?

[still flare]

This is not all of the axioms.

[potent wharf]

I know, but just the axioms of addition has my working shown that it does work there?

[still flare]

Saying "obviously" is not really working, but I'm not interested. List out the field axioms, and think about whether or not your observation that [a] + [b] = [a+b} and [a][b] = [ab] proves them.

I realise I said "check," but I meant you should review them.

[potent wharf]

Do you mind giving me a specific axiom to review on?

[still flare]

I don't know the specific list of axioms you've been given since you haven't posted them

But I will point out one property

Perhaps this is listed

[potent wharf]

The multiplicative inverse?

[still flare]

There we go, yes

This one is not implied by what you stated

This is the crucual property of a field, that distinguishes it from a commutative ring.

You surely know that Z with addition and multiplication satisfies almost all the field axioms!

However of course, it doesn't have multiplicative inverses. This should show you why the reasoning you gave above is not sufficient.

[potent wharf]

Z as in the integers?

[still flare]

Z is the set of integers, yes

[potent wharf]

In relation to the question posted above

We did just show that Z_n is not a field hence Z_7 and Z_4 aren’t fields, for something to be an ordered field it must also satisfy the property of a field

Would the answer be the last option?

[still flare]

Who says Z_n is not a field, sorry?

[potent wharf]

I set [a] and [b] to be two distinct congruence classes in Z_n?

[still flare]

I don't see how it follows that Z_n is not a field.

In fact, Z_n is actually a field for some numbers n.

So can you elaborate on your thought as to why Z_n is not a field?

[potent wharf]

Because it didn’t satisfy the axiom of multiplicative inverse?

[still flare]

I didn't say it didn't

I said you haven't proven it did

[potent wharf]

Okay, I’ll have a go at it

[still flare]

Just a reminder, you only need to check the case that n = 7 in the question.

[potent wharf]

I’m not sure as to how to prove it

I’ve come across a theorem in which [a] in Z_m has an inverse iff gcd (a,m)=1

[torn escarp]

use bezout's theorem

[potent wharf]

Using that I can deduce that Z_7 has inverses for all a whereas Z_4 doesn’t in the case [2]_4

[still flare]

You can also just check all elements of Z_7.

There are only 6 nonzero ones, after all.

[potent wharf]

Another question I have is if
[x][y]=[0] does either x or y=0

[still flare]

Not always, no

In fact, it's not obvious, but this is true exactly when Z_n is a field

[potent wharf]

Since [x][y]=[xy]=[0]

[torn escarp]

check your Z_4 example

[potent wharf]

So when x=y=2?

[still flare]

That is an example, yes

[uncut pumice]

Lecture notes claims $2^j = (1 + 1)^j \ge j + 1$ for positive integer $j$. I don't understand the inequality. What's the thought process?

[sterile pumice]

Mattuwu

[torn escarp]

it's taking the first two terms of the binomial expansion as a lower bound

[sterile pumice]

Merosity

[uncut pumice]

wow! thanks!

[torn escarp]

you're welcome

[jovial bison]

The reduced residue set of 8 is {1,3,5,7}. All 4 of those are their own multiplicative inverses mod 8. Why/when does this happen.

[stable grotto]

Let f be a polynomial with integer coefficients. Show
that a − b | f(a) − f(b) for any integers a, b. This is the same as saying f(a + d) ≡ f(a)
(mod d).

[torn escarp]

you could factor directly for $f(x)=\sum_{n=0}^N c_nx^n$, $$f(a)-f(b)=\sum_{n=1}^N c_n (a^n-b^n) = (a-b) \sum_{n=1}^N c_n \sum_{k=0}^{n-1}a^{n-1-k}b^k$$

[sterile pumice]

Merosity

[strange turtle]

What reading should I do to learn some basic number theroy?

[mint wolf]

Anyone know how to do this without contrapositive

not sure how to do the direct proof

[sweet mist]

what the fuck is the love heart operation lmao

[pearl gyro]

can I just introduce a system of congruences like this?

this was the q

[mint wolf]

kiss

nevermind that i solvedit

[runic token]

uhhh hi i know this is a little late but i wanted to lyk that there's probably a much easier way to solve the problem

than uh whatever ur doing

idk if ur allowed to use this to start with but it's very easy to show:

if b and c are coprime then gcd(a,bc) = gcd(a,b) * gcd(a,c)

let b = n-1 and c = n+1

then they are coprime since n is even and since we know gcd(a,b) and gcd(a,c) divide b so must their multiple

thus the congruence relation ax \cong b mod(n^2-1) is solvable

(by givens)

im like 99% sure this proof works and it looks easier than urs

[runic token]

uhh this fact follows from the fact that the gcd function is distributive and associative and commutative

if i pinged u already sry lol idr but jic @pearl gyro

[pearl gyro]

ahhh I see :0 but my professor told us to use that method so I want to learn how it works 😢 thanks though!!!

[runic token]

huhh nw loll yw

your prof told you to solve it the way you were?

[mossy rampart]

If the 4-digit Integer $A=a_{3}10^3 + a_{2}10^2 + a_{1}10 + a_{0}$ has digits such that $a_{0}>a_{1}>a_{2}>a_{3}>0$, determine the sum of the digits of the number $9A$.

[sterile pumice]

Emmanouel

[uncut pumice]

this part of my lecture notes is confusing to me. Here $p$ is a prime, $k$ is an nonnegative even integer, and $S_k(p) = 0^k + 1^k + 2^k ... + (p-1)^k$.

Where is Fermat's Little Theorem involved?

[sterile pumice]

Mattuwu

[torn escarp]

r^k=1 mod p since they say (p-1) | k

[native monolith]

Question on primitive roots and can't find the ans on stack.

"Show if g and h are primitive roots of an odd prime p, then the least residue of gh is not a primitive root of p"

Proof:
$\$
$g^{p-1}\equiv h^{p-1} \equiv 1 \mod{p}$. Now $\phi(p)=p-1$ so $2|p-1$. So $h^2$ is not a primitive root (by if a has order t mod m. Then $a^k$ has order t mod m iff $(k,t)=1$.) So $g^{p-1}h^{p-1}\equiv h^{2p-2}\equiv (h^2)^{p-1}\mod{p}$. So then $gh\equiv h^2$ so gh is not a primitive root.

@sterile pumice rip?

[torn escarp]

where's a^k coming from, I don't see how the next part follows. You can do something similar since g is a generator write h=g^k with (k,p-1)=1 to get gh=g^(1+k) =(g^((k+1)/2))^2

[native monolith]

That's just a lemma from the notes I'm quoting

[native monolith]

That's really clever

[torn escarp]

the problem is what you're saying after that is false, since you're reasoning about 1. Your last statement is clearly false, look at 2,3 as generators mod 5, but 2*3 != 2*2 mod 5

[native monolith]

Ah nice yea I thought something was wrong just wasn't sure what, your method is very clean 🔥

[torn escarp]

thanks 👍 yeah, the problem is "rooting" is not a function I guess is another way to think of it here

[uncut pumice]

doesn't Fermat's little theorem require the exponent to be a prime? in r^k, k is not a prime

[torn escarp]

the second one in your screenshot is what I usually think of as flt

[uncut pumice]

and the second one requires $a$ not divisible by $p$, also the exponent is $p - 1$

[torn escarp]

right, the sum only goes over numbers not divisible by p and the exponent is divisible by p-1 so

(p-1) | k means k=(p-1)m for some m

r^k = (r^m)^(p-1) = 1 mod p

[uncut pumice]

AHH

[torn escarp]

lol

[uncut pumice]

thanks!

[torn escarp]

you're welcome

[uncut pumice]

you have a polymerous pfp ;)

[torn escarp]

lol 😌 indeed

[sterile pumice]

Mattuwu

[uncut pumice]

looks like some contrapositive of Fermat's Little Theorem..

😫 I can't figure out why

[torn escarp]

let $g$ be a generator, then write $k=q(p-1)+r$ with $0<r<p-1$ (because $p-1 \not | k$, it has nonzero remainder). $$g^k = (g^{p-1})^qg^r = g^r \mod p$$ We know $g^r \ne 1 \mod p$ because $r<p-1$ and $g$ is a generator with order $p-1$.

[sterile pumice]

Merosity

[uncut pumice]

🤯 thanks I'll have a read

looks not trivial at all, my notes is so hand waivy

[torn escarp]

kind of similar trick used to prove that if a^k=1 mod p, then k divides p-1, so sort of inspired from that, but I suppose that is not itself trivial, but part of the basic stuff to be proved when doing elementary number theory

[torn escarp]

what's the course called, I imagine it skims this stuff cause you were talking about p-adic integers the other day, so probably assumes you know this stuff

[uncut pumice]

since you are here, can you also help with this? I'm actually writing an email to ask my prof about this. the g is the same g such that g^k not congruent to 1 mod p

it's not homework or anything, just proofs of theorems

[torn escarp]

I'm actually not here, timer just went off on the oven for my fish 👋

[uncut pumice]

haha! that's fine!

I'm pretty inexperienced on elementary number theory I'd say. The course I'm taking is a MSc math course "Combinatorics and Analytic Number Theory"

[inner anchor]

Try using the geometric series formula

Should drop out of that

[uncut pumice]

wow I don't know you can just pick generators of a certain order like that. I just came across this theorem and I guess Z_p just have nice properties

[torn escarp]

I don't think it matters what g is here, so long as it's not divisible by p. the mapping f(x)=gx is a bijection of the set {1,...,p-1}, just think from the group theory perspective of the multiplicative group gG=G

the sums are the same because it's really just the same terms in different order

also figured I should mention it, a handful of the stuff you're proving seems similar to proving the chevalley warning theorem

might be fun to just look at that, one of my favorite theorems at least

[uncut pumice]

whoa that's very cool!

thanks

[uncut pumice]

it's not a geometric sequence though, the powers are the same.

[sterile pumice]

Emmanouel

[sturdy nacelle]

Could I get some help? I want to know an approximation for $\sum_{p \leq x} \sqrt{p}$, where $p$ are primes. Currently the best approximation I have is $\frac{2}{3}x^{3/2}\sqrt{\log{x}}$, but I'm pretty sure that is for the first x primes, not the primes below x. I got the approximation here: https://math.stackexchange.com/questions/394796/sum-of-square-root-of-primes

[sterile pumice]

Trashtalk

[sturdy nacelle]

I've got a post in #1021175428326633542

[uncut pumice]

do we have a name for these groups?

[pale raven]

What areas of math are a general prerequisite for number theory

[dusty dragon]

It turns out that such an element is invertible in Z/qZ so we call this group the group of units of Z/qZ

[uncut pumice]

are they exactly the units of Z/qZ?

[dusty dragon]

Yes. It is a necessary and sufficient condition for an element to be a unit

[uncut pumice]

that's very cool! Thanks!

[low plaza]

Hey guys. Im struggling on a question on finding incongruent solutions of a congruence

I need to use hensels lemma but it gets confusing

Q3

So i bring everything over to the lhs and get x^3 -25 = 0 mod 64

Then i try solutions to x^3 - 1 = 0 mod 2

So i get f(1) that works

And i try f(1) for mod 4 and mod 8

And it works for them too but it stops working for mod 16

And now i dont know what to do

[torn escarp]

You can think of each step as uncovering a digit in the base 2 expansion of the number, $$x=a_0+a_12+a_24+a_38+a_416+a_532$$
Since $f(1)=0 \mod 8$, but $f(1) \ne 0 \mod 16$, this means when you uncovered the digit $a_38$ but you had chosen $a_3=0$, so the only other choice is $a_3=1$. So that means you have $x=9 \mod 16$ and you can continue that way, testing if the digit $0$ works and if it doesn't making it $1$.

[sterile pumice]

Merosity

[torn escarp]

there's more to say since there are other ways to do this, and hensel's lemma also comes with the number of distinct roots too

[torn escarp]

@mossy rampart those were fun, thanks

[mossy rampart]

Does anyone know a trustworthy place online were someone can find good competition math teachers?

[boreal drift]

i'm trying to find solutions to the 2 variable system p^2+4x^2=k^2 for integers x, k and prime p and I'm struggling with how to reduce it to a problem of just completing the square

[dusty dragon]

Observe that you obtain p^2 + (2x)^2 = k^2 which is equivalent to generating a Pythagorean triple. The general solution is p = m^2 - n^2, 2x = 2mn, k = m^2 + n^2 for a pair of integers (m, n). If p = (m - n)(m + n), then one of m - n or m + n must be 1; otherwise you obtain a composite integer

[languid spade]

Was about to type that ^.

[boreal drift]

i see, thank you that actually makes a lot of sense

[high hinge]

How would i prove that x^4 + x^2 = y^4+5 ? Would it be with Fermat's infinite descend principle?

[languid spade]

You could try that, looks a bit hairy though with the constant 5 term.

[high hinge]

Yea that’s the part that’s stressing me out

Would there be any other ways?

[torn escarp]

I would try factoring it a number of different ways

$x^2(x^2+1)=y^4+5$, $\frac{x^6-1}{x^2-1}=y^4+6$, or $(x^2+y^2)(x+y)(x-y)=5-x^2$ are some ways that immediately pop out at me, no clue if they're fruitful or not but it's something to try

[sterile pumice]

Merosity

[torn escarp]

oh, reducing the equation modulo 5 is the key

first ||assume that one of x or y is 0 mod 5, then it forces the other to be 0 mod 5, but if you then substitute in and divide through you end up with a new equation that gives 0=1 mod 5||
second ||now that we know x and y are not 0 mod 5, when we reduce we can use z^4=1 mod 5 by fermat's little theorem so it becomes x^2=0 mod 5. But we already know x is not 0, so there are no integer solutions||

[high hinge]

Oh wow thanks @torn escarp 🙂

and thanks @languid spade

[valid quartz]

can someone explain why their doesnt exist some smallest possible number n

[uncut pumice]

I just came across something interesting. So you can always split a number into two relatively coprime parts. But in particular, you can "extend" any divisor of a number to a maximum divisor that is coprime to its quotient. This can be done by checking the prime factorization of both the dividend and the divisor and enlarging the divisor by powers of its prime factors. Does this remind anybody of anything?

Here's what I mean technically:

\(q \in \mathbb{Z}_{\ge 2},\ d\in \mathbb{Z}_{\ge 2} \) and \(d \mid q\). \(q\) has prime factorization \(q = \sum_{i=0}^l p_i^{a_i}\), \(d\) also has prime factorization \(d = \sum_{i=0}^l p_i^{b_i}\) for some \(l \ge 0\), \(a_i\ge 0\) for \(0 \le i \le l\), \(p_i\) the \(i\)-th prime.

We can then split \(q\) into \(q = q_1q_2\) with \(q_1,\ q_2\) coprime by ``extending'' \(d\) by letting \(q_1 = \prod\limits_{\substack{i = 0 \\ p_i\mid d}}^l p_i^{a_i}\), \(q_2\) is composed of the complementary factors: \(q_2 = \prod\limits_{\substack{i = 0 \\ p_i\nmid d}}^l p_i^{a_i}\)

[sterile pumice]

Mattuwu

[abstract sundial]

{1, {1}, {1,1} △ {1, {1}} = {{1,1}} is this true?

[uncut pumice]

yep, but how is this number theory 😂

[abstract sundial]

Sorry didnt know where else to put this

{1, 2, 3} ⊕ N ⊆ N \ {1, 2, 3} How about this?

Also true, right?

[uncut pumice]

what do you mean by ⊕?

[abstract sundial]

symmetric difference

[uncut pumice]

wait I thought △ was symmetric difference

[abstract sundial]

Yes

[uncut pumice]

that's also true, noting that {1, 2, 3} ⊕ N is empty

oh wait, it's not empty

it's exactly the same as N \ {1, 2, 3}

thus it's also a subset of it

[uncut pumice]

so all the divisors of q that are greater than 1 form a bounded join-semilattice with lcd

the map from a divisor d to its extension this way is actually a semi-lattice endomorphism

[torn escarp]

not sure I fully understand what you mean, but if I understand you correctly, if we denote w(n)=number of distinct prime divisors of n, then there are 2^w(n) ways of factoring a number into two relatively prime factors, since you either include the whole power of the prime or don't

in particular I just don't know what you mean by extend to be a maximum divisor, like I would think n=1*n would be the maximum or something idk

[uncut pumice]

a maximum divisor that has the same set of prime factors as the divisor itself

[torn escarp]

oh ok

[uncut pumice]

that's cool, and 2^w(n) is actually the cardinality of the image of the endomorphism. An immediate implication is then the inequality that 2^w(n) < n , but that's kinda obvious.

[torn escarp]

oh which homomorphism? also that doesn't seem right cause for n=1 and n=2 it's an equality

well you probably meant <= and I'm being pedantic or something lol

[uncut pumice]

for a number q, ({divisors of q >= 2 }, lcd) is a bounded semi-lattice with q itself being the top. And the map from a divisor to the the maximum divisor sharing the same prime factors is actually an semi-lattice endomorphism

it's also a monoid endomorphism as it maps q to itself

what is \🥬 😂 😂

algae?? hahahaha

[torn escarp]

oh, I don't really know much about semilattices but I can see why divisors would fall naturally on a lattice I guess

[dusty dragon]

what do you mean by "write zero"

assuming gringo is the ASP tool here

[verbal cedar]

what would the general process be to solve an equation of the form a^2-2b^2=1? for a,b integers ofc

[dusty dragon]

my first thought is to use abstract algebra and look at solutions over the field extension Q(sqrt(2))

In particular, observe that $a^2 - 2b^2 = 1$ can be re-expressed as $(a - \sqrt 2b)(a + \sqrt 2b) = 1$. Observe that the Galois group over $\mathbb Q(\sqrt 2)$ is generated by sending $\sqrt 2$ to $\pm \sqrt 2$ and so the norm of $a + \sqrt 2b$ is exactly the left side. You can turn the expression into computing the units of the form $a + \sqrt 2b$ with positive norm. But I suspect that there's a more elementary method than to consider the purely algebraic version

[dusty dragon]

Following this train of thought though, we aim to compute all units of the form $a + b \sqrt 2$ over the ring $\mathbb Z[\sqrt 2]$. But these are precisely of the form $\pm (1 + \sqrt 2)^n$ for $n \in \mathbb Z$; you can then equate coefficients to generate all solutions $(a, b)$

[torn escarp]

check out pell's equation

[verbal cedar]

lmao rip i was trying to do this to prove that all the units of Z[sqrt2] are of the form +-(1+-sqrt2) 😆

[verbal cedar]

thank you, this is exactly what i was looking for

and thank you @dusty dragon !

[vernal void]

Been struggling with this one for an hour:

would appreciate if anyone could help!

❤️

[torn escarp]

do you know how to simplify $\sum_{k=1}^nk^2$ @vernal void

[sterile pumice]

Merosity

[vernal void]

no @torn escarp

=[

I am extremely novice

[torn escarp]

there are multiple ways to derive it, or you could look it up and use it now and work out how to get it later

$$\frac{n(n+1)(2n+1)}{6}=\sum_{k=1}^n k^2$$

[sterile pumice]

Merosity

[torn escarp]

use this to write out the sum of quadratic residues

[vernal void]

so hey i kinda get where ur going with that

but im using this proposition

so right now i have

S (the sum)

equal to

S = 1+2+...+p-1/2

then I do

2S = 1+2+...+p-1

but then idk where to go from there =[

[torn escarp]

that won't work, you need the sum of squares

[vernal void]

so I should square both sides?

[torn escarp]

no, the individual terms are squares

[vernal void]

why 😮

the quadratic residues are the a's in

[torn escarp]

$$\frac{n(n+1)(2n+1)}{6}=1^2+2^2+\cdots+n^2$$

[sterile pumice]

Merosity

[vernal void]

x^2 = amodp right

?

[torn escarp]

yes, but the numbers you've written aren't guaranteed to be squares

[vernal void]

https://math.stackexchange.com/questions/764563/p-divides-the-sum-of-the-quadratic-residues-bmod-p

like look at this example online

could u help me understand it

seems very similar to u 🙂

[torn escarp]

one thing at a time here

they're doing it slightly differently than I'm describing

[vernal void]

i just need to be taken through from the start 😮

like the question is so simple

[torn escarp]

they're double counting by putting all numbers, which is a fine way to do it

[vernal void]

and i have that nice proposition

but i dont understand how u are coming to ur conclusion

[torn escarp]

that proposition tells you half the numbers are squares and the other half aren't

but it doesn't exactly tell you which ones, however we can make squares directly by just squaring numbers

because k^2 = (p-k)^2 mod p, you can make all the quadratic residues by squaring numbers <= (p-1)/2

[vernal void]

merosity im down bad

could i dm u about this? i feel bad flooding the channel with questions

i have so much number theory to do tonight =[

[torn escarp]

I'm busy right now, maybe someone else can help, I think the link you posted is good

try following that, take it slow and try to understand each step one at a time

[drifting mantle]

Hi, is $$ \sum_{i=0}^{n} \sum_{j=0}^{n} 3^{i+j} = \sum_{i=0}^{n} 3^i \sum_{j=0}^{n} 3^j $$?

[sterile pumice]

Opify

[torn escarp]

yep

[drifting mantle]

ok thancc

[drifting mantle]

hi is $$\sum_{i=1}^{n} \sum_{j=1}^{n} (i+j) = \sum_{i=1}^{n} i + \sum_{j=1}^{n} j$$?

[sterile pumice]

Opify

[fervent crest]

No

In general $\sum_i(a_i+b_i)=\sum_ia_i+\sum_ib_i$, so $\sum_{i=1}^n\sum_{j=1}^n(i+j)= \sum_{i=1}^n\sum_{j=1}^ni+ \sum_{i=1}^n\sum_{j=1}^nj$

[sterile pumice]

CS person

[drifting mantle]

Oh

Ok thancc

[uncut pumice]

is this correct? what's can be said about this?:
If $a \equiv b\ (\mathrm{mod}\ c)$ then $\gcd(a, c) = \gcd(b, c)$

[sterile pumice]

Mattuwu

[torn escarp]

sure, wlog suppos a>=b then a=b+cn so gcd(a,c)=gcd(b+cn,c)=gcd(b,c)

actually inequality is unnecessary if n is an integer

[uncut pumice]

gcd(b+cn,c)=gcd(b,c)
what is this relation called?

[torn escarp]

euclidean algorithm

gcd(x,y)=gcd(x-y,y)

[uncut pumice]

some induction required

[torn escarp]

idk if it has a name

[uncut pumice]

this somehow reminds me of the determinant of a matrix, where adding multiples of rows won't change the determinant

[torn escarp]

I think there is a way to represent the euclidean algorithm as like row operations on matrices with integer entries

so maybe it's more than coincidence, although really if u,v are integers and d divides x and y, then d divides ux+vy

so I am not thinking about anything super complicated I feel

writing it more explicitly might make it more obvious, x=dX and y=dY then ux+vy=udX+vdY=d(uX+vY)

[white lion]

when solving using "second induction" or "strong induction"

is it safe to assume that for example an equation also holds for k-1 if it holds for k

[dusty dragon]

strong induction assumes that a statement holds for all j <= k instead of just assuming that the statement holds on k, so yes

In other words, we can assume that P(1), P(2), ..., P(k) are all true to prove that P(k + 1) is true

[high hinge]

If I can show that an equation has no solution mod n, does it mean it doesn’t have solutions at all?

[torn escarp]

integer solutions, yep. If it had integer solutions, you could reduce mod n to get solutions mod n, but there are none - contradiction

[high hinge]

Oh alright! Thanks 🙂

@torn escarp

[torn escarp]

you're welcome 👍

[misty valve]

If you’re talking integers solutions, yes.

[runic token]

hey hi hello i know i already solved this much simpler but can't you also just like construct a solution?

you know it's solvable for n-1 and n+1, so you have:
f: ax = p(n-1) + b
g: ax = q(n+1) + b

f - g --> 0 = p(n-1) - q(n+1)
so we see that
p = n + 1
q = n - 1
plug q back in to f
h: ax = (n+1)(n-1) + b
now we need to show it's solvable for (mod n^2 - 1)
then we need to show we have ax = k(n^2 - 1) + b
but when k = 1 this is just h, which we know is true from givens

[runic token]

i might be wrongggg lmk

[torn escarp]

the step where you write

0 = p(n-1) - q(n+1)
so we see that
p = n + 1
q = n - 1
this is not necessarily true, you could have p=t(n+1) and q=t(n-1), but even worse, if n is odd it would make gcd(n+1,n-1)=2 meaning p or q might not necessarily be a multiple of n+1 or n-1 respectively. For instance, n=3 could make 0=p2-q4 so hypothetically p=2 and q=1 would work even though p=2 !=n+1 and q=1 != n-1.

I suppose in part, maybe it's possible you already are assuming this when you say

you know it's solvable for n-1 and n+1, so you have
but I thought I'd mention it

[runic token]

yeah i was assuming n was even 📔 but ur still correct on the first pointtt

but i think it still works because then just set k = t

and everything is still satisfied 😌

[torn escarp]

yeah, I would just mention if n is odd, the congruences aren't solvable, so assume it's even at the start to be clear was really all I was getting at. and you're right for the other part, once you get that it turns into ax=t(n^2-1)+b and so you are already there and can throw out the rest of the stuff

[runic token]

hmm right right

but my issue is that i was trying to not use the solvability condition :/

and now im looking for a way to show n has to be even without it

oh

wait

thats easy

an even number mod an even number can't be odd, but b mod even is odd

so ax \equiv b (mod even) gives even (mod even) \equiv odd (mod even) which is even = odd which is not cool

and that can be written out in a few symbols

so we're good

ty for pointing out the t(n+1) and t(n-1) tho

it didn't affect it but it def could have in other problems and i would have missed it then too

[torn escarp]

wait, you're wanting to remove the fact that they tell you ax=b mod n+1 and n-1 is solvable but only leave the fact that a is even, b is odd?

[runic token]

oh nonono

im just trying to not use gcds haha

or gcd(a,m) | b

wait am i using it implicitly here or something >.>

[torn escarp]

well, you came to the wrong final answer since it's possible that ax != (n^2-1)+b even though ax=t(n^2-1)+b

[runic token]

OH

WAIT UR RIGHT

BC THE MULTIPLE ACTLY AFFECTS IT

omgggg

[torn escarp]

haha

[runic token]

how did u spot that

i wouldn't have seen it

even if you told me there was an error

[torn escarp]

well I know that p(n-1)=q(n+1) doesn't mean p=n+1 and q=n-1 😛

there are two problems with it potentially

p and q can have more factors (that was t) and n+1 and n-1 can share factors (that was potentially only 1 or 2 in our case)

gcd(n+1, n-1)=1 was forced on us which is why the problem makes a even and b odd

otherwise the problem becomes harder

maybe try to think about that, what happens when n is odd and we aren't forced to put the parity conditions on a, b

[runic token]

so immediately n-1 and n+1 aren't coprime

and are we still trying to show what the question asked?

[torn escarp]

nah, this is extra credit

[runic token]

oooh gotta love extra credit

okay okay so n-1 and n+1 aren't coprime, and we don't know parity of a or b

all we know is that n >= 2

[torn escarp]

at this point the problem might not even be true, so we might have to change things or find a counter example

[runic token]

hmm

[torn escarp]

like by change things I mean, maybe htis only implies ax=b mod (n^2-1)/2 is solvable from what's given (not necessarily saying this is true, just a suggestion)

[runic token]

one sec lemme grab some paper

so we have
ax = b mod(n-1)
ax = b mod(n+1)
is solvable
-->
ax = b mod(2c)
ax = b mod(2c+2)
but then we know x = y mod(z) --> 2x = 2y mod(2z)
so if n is odd then ax is even and b is even

hmmm

[torn escarp]

I wouldn't focus on what a or b are

you can work similarly to how you worked on the last one by writing it out like ax = p(n-1) + b

[runic token]

hmmm

so are we still assuming it's solvable for n+1 and n-1?

[torn escarp]

yup

[runic token]

oki oki so then

huh

doesn't my proof just

work?

then

because the only thing it uses is solvability of the original two functions and definition of mod

[torn escarp]

not entirely, there's still the problem of n+1 and n-1 having a common factor

[runic token]

ohh right

you know it's solvable for n-1 and n+1, so you have:
f: ax = p(2c) + b
g: ax = q(2c+2) + b

f - g --> 0 = p(2c) - q(2c+2)
so we see that
p = t(c + 1)
q = t(c)

js copy and pasting there

reindexed a little

[torn escarp]

yeah

well slight change

you should divide by 2 before saying what p or q is

since that extra 2 might not be in them

[runic token]

oooh right right

so then if we plug that into f
ax = t(c+1)(2c)+b --> ax = t(2c^2 + 2c) + b
and we're trying to show ax = k(4c^2 + 4c) + b

so k = t/2

[torn escarp]

actually no now

[runic token]

i feel like something is wrong

[torn escarp]

since we don't actually have the information to say that

maybe it'll be a bit clearer if I write it out, cause there's an important point about p and q too

p(n-1)/2 = q(n+1)/2 since we know gcd(n+1,n-1)=2, and actually we might go further and say t=gcd(p,q)

I used n instead of c cause I like it better

and divide through by t

[runic token]

i thought we already used n otherwise i would have loll

[torn escarp]

wait backup maybe it's not clear where this is coming from

ax-b = p(n-1) = q(n+1) from the congruences right

[runic token]

right

yes

[torn escarp]

that last equation, I'm just dividing through by some gcds, 2=gcd(n+1, n-1) and t=gcd(p,q) so I get

$$\frac p t \frac{n-1}{2} = \frac q t \frac{n+1}{2}$$

[sterile pumice]

Merosity

[runic token]

hmmmm

okay i follow so far

[torn escarp]

the point is I know that p/t and q/t have no common factors, so p/t must equal (n+1)/2

similarly for q/t=(n-1)/2

[runic token]

ohhhhhh

okay okay that tracks

[torn escarp]

yeah now you can go back to ax-b=p(n-1) and plug in, ax-b=t(n+1)/2 * (n-1)

so really we just have that ax-b = 0 mod (n^2-1)/2

that's what we get from ax-b=t (n^2-1)/2 that we just got

[runic token]

whoaa okay so all we did was relax some conditions and suddenly we get a whole new answer

[torn escarp]

yeah, although if we had put gcd(n+1, n-1) there instead of 2

it would have given both answers

since it changes to 1 when we need it

[runic token]

oh man

that's nice

👀

[torn escarp]

in fact, if we follow this whole thing through with f(x) instead of ax-b we could say even better

[runic token]

wait whatt

[torn escarp]

$f(x)=0 \mod m$ and $f(x)=0 \mod n$ then $$f(x)=0 \mod \frac{mn}{\gcd(m,n)}$$

[sterile pumice]

Merosity

[torn escarp]

you could even put more variables in the function there too, not to mention it doesn't need to be linear

😛

[runic token]

this is actually pretty general 👀

which

like

what

???

that's so crazy to me

[torn escarp]

yeah, you've heard of the chinese remainder theorem before right?

[runic token]

bc like as far as proofs go this one is pretty easy and i feel like we just said a really surprising amount

[runic token]

yup!

it's the one that uses bezouts and EA, right?

[torn escarp]

so we actually got that for free as a special case when gcd(m,n)=1

[runic token]

WAIT

OH RIGHT BC IT SPECIFIES COPRIME

WHAT

THATS SO COOL

omg

[torn escarp]

nice haha

[runic token]

my mind is blown

that was so fucking cool

i didn't see that coming at all

[torn escarp]

yeah make sure it all checks out and you can do it on paper and I'm not lying to you and there aren't some details we left out that are critical or something lol

yeah pretty fun stuff, did sort of fall out of nowhere, kind of funny how going more general actually can make things simpler. certainly convenient that we could lift the a,b parity conditions and not have to get in the weeds with n-1 and n+1 being coprime or not lol

[runic token]

'sort of fell out of nowhere' we looked at
ax = b (mod n-1)
ax = b (mod n+1)

and got to CRT

it did more than js fall out of nowhere thats actually so cool to me

maybe one day ill go 'oh this is trivial' but for now

[torn escarp]

yeah most of it was just stuff you already came up with on your own, just zoomed out a bit

[runic token]

mannn

mero i dont think you get it

ill remember this for the rest of my life

[torn escarp]

hahaha I've been there myself 😛

[runic token]

this was so nice

thank you

so much

[torn escarp]

you're welcome glad I could help!

[fast orchid]

how do you go about proving b?

[plain flare]

Notice that the i goes over each element in S

[still flare]

(And use part a!)

[fast orchid]

I think I get it now, we just have i is k

and n+i must be p for gcd to be p

or multiple of p

[pearl gyro]

Hello! can I get some push in the right direction here?

I am trying to use the fact that x^2 == -1 (mod p) is solvable if p == 1 (mod 4) and not solvable if p == -1 (mod 4)

but since we are dealing with the number of solutions I am so lost 😢

would x == 1 (mod n) always be a solution?

[stiff rivet]

you need to count solutions of the system of equations you gave

1 and -1 is always a solution

you can see this in the factorization you produced

and unless p=2 you have 1 \neq -1

so each equation (except for p=2) gives you 2 solutions

but you might have more, corresponding to roots of x^2 + 1 mod p (how many?)

so uhh

maybe take a step back and consider the example of n = 6 since you know this behavior

x^4 = 1 (mod 2) has 1 solution and x^4 = 1 has 2 solutions

so you should get 1*2 = 2 total

and you can verify this algorithmically

then now maybe look at an example with a prime p = 1 mod 4

say n = 30

still small enough so you can play with it and verify with a computer

[pearl gyro]

this is bc prime p > 2 is odd, right?

[stiff rivet]

not really

[pearl gyro]

if p == 1 mod 4, then we will have 2 more solutions ±((p-1)/2)! and if p == 3 mod 4 then no solution?

[stiff rivet]

sounds right

[pearl gyro]

oh no why is it?😱

I was thinking it was because if p is odd, the residue class is {0, ±1, ..., ±p-1 / 2}

[stiff rivet]

uh well

1 = -1 mod p gives you 2 = 0 mod p

that cannot be true unless p = 2

if p > 2, this wont happen

[pearl gyro]

ahHHHH

my goodness lysm!!!!!

[stiff rivet]

so yeah, if you consider n = 30 = 2*3*5, you get 1 solution mod 2, 2 solutions mod 3 and 4 solutions mod 5, right?

[pearl gyro]

yesh

[stiff rivet]

which makes 1*2*4 total

[pearl gyro]

yesss!!!!! that helps so much thank you :'))))

[stiff rivet]

and if you want you can verify that

should be 8 1s

ye, np; i think you got this

[uncut pumice]

lecture notes on the definition of a index is very confusing. q is positive integer and q >= 2. g is not mentioned anywhere before. which primitive root? any primitive root?

can somebody help clarify?

context: right after this definition is a construction of dirichlet characters

[torn escarp]

yeah, since there are phi(phi(n)) generators, you can pick any one, it's a bit ambiguous notation I agree

it'd be nice if they just called the index "log base g"

since that's basically what it is

I should be more clear, they haven't said it explicitly, but what they're doing is picking a specific g and fixing it

and then the index depends on this choice of g

for instance if I'm working with q=5, I could pick g=2 or g=3, if I picked g=2 then v(2)=1 and v(3)=3, while if I had picked g=3 then v(2)=3 and v(3)=1.

[pearl gyro]

hello... 😢 can I get another push for this question please?

[sacred junco]

whats the question

do you need help understanding the proof

[pearl gyro]

nono I need help proving it :<

that's what i have so far

[sacred junco]

oh

[uncut pumice]

omg thanks!!

[torn escarp]

yw 👍

[white lion]

hey quick question, the division algorithm a=bq+r, the theorem states that it works for any a and b>0, but it clearly doesn't work when b>a for example when a=56 and b=100, there isn't any unique q and r (with r being an integer that is less than b and greater than 0 ofcourse)

what am I misunderstanding here?

[torn escarp]

a=b*0+a when b>a

cause a is the remainder itself

you can make exactly 0 multiples of 100 out of 56, with 56 left over in other words

[white lion]

yes I was thinking something along those lines thanks!

[torn escarp]

yup you're welcome

[crimson forum]

hi i have a really random q idk if right catogry but how would i find integer solutions to the following (x^2)+x-(y^2)-1=0

ive tried factorising in diff ways but just goes round in circles

[visual path]

Hmm so I guess you could view it as x(x+1) = y^2 + 1

I’m not sure what an analytic solution would look like but there’s a simple algorithm we could use by cycling through for different values of x and filtering out those where x*(x+1) - 1 does not have an integer square root?

[crimson forum]

hmmm

ok i mean i was thinking of trying to add a constant to both sides making it easier to factorise but was unsure what one to use

because there was this example i saw and it was similar like x^2+x-y^2=0 then they added 1/4 to both sides and got (x+1/2-y)(x+1/2-y)=1/4 then multiplied by 4 and so on

and they got (x,y)=(-1,0) and (0,0) but the only thing i didnt get like how did they know add by 1/4

[crimson forum]

and if so with this equation what would we add by

and ik this problem (x^2+x-y^2-1=0) has 4 sols just dk how to get to it

[crimson forum]

okk i figured it out you just had to add 1.25 to both sides then its easier to factorise and solve so wed get (-2,-1),(-2,1),(1,-1),(1,1) as all possible integer sols

[knotty oriole]

hey, I've got an issue with comprehending a step in the proof of van der waeden's theorem on arithmetic progression

im posting the proof till where i got stuck

... and that's where im stuck

"it is clear the two arbitrary segments... are of the same type"

but so far in the proof we have only shown that an arithmetic series of segments with some distance d2 exists in each Segment, but not that they are of the same type

it's clear to me that the subsegments of each segments are equal, but not to the subsegments of other segments

[high hinge]

Let f: N --> N be a function such that: 1. f(2)=2 2. f(m)>f(n) for m>n 3. f(m*n)=f(m)*f(n) if m and n are relatively prime. I want to show that f(n)=n for all n. How can I do that?

[torn escarp]

it's completing the square

[torn escarp]

should be able to do induction, try working out the first several cases by hand, like n=3, n=4, n=5 to try to get an idea of how the argument should go, then try to generalize that argument for induction

[visual path]

You can show that f(1) = 1 since 1 is coprime to all N. The next part is tricky, you need to show that f(n) = n is the only possible mapping such that statement 2. holds but not entirely sure what that would look like

[high hinge]

Alright I'll try these things out thanks @torn escarp @visual path

[crimson forum]

sorry for late reply but oh ok ig didnt see it cuz 1/4 divided by 2 would be 1/8 not 1/2 ... also didn't u can do with y squared n x squared tog too ngl but thanks for reply

[torn escarp]

not sure what you mean exactly but to complete the square on x^2+x you need 1/4 because the coefficient on x is 1, so half of that squared is 1/4

yeah you're welcome 👍

[crimson forum]

oh okk i think i was taught completing the square differently when i was in school so maybe got confused but makes sense- so im guessing we do tht all the time look at coeffecient of x?

cuz with the similar promlem added -1 at end i just used that e.g and did it bacwards lol

[torn escarp]

yeah basically

[crimson forum]

ok that makes sesne then - thanks 🙂

[torn escarp]

yup yup

[north pagoda]

please stop spamming shit across multiple channels

also please read a mathematics textbook

(also the frequency of primes is "expectedly predictable", we have an asymptotic formula for it.)

(that's far from the biggest fallacy in your wall of text, though; your reasoning would apply to numbers of the form n² for n an integer, but there are obviously infinitely many of those.)

(or perhaps e^n is an even better example since the frequency of numbers of this form shrinks at an even faster rate than the frequency of primes)

(see the prime number theorem)

glad to see you're being intentionally belligerent and ableist, gives me a good excuse to ban you

[dense scroll]

Does anyone have a hint for this?

[still flare]

Calculate some small powers of 3 mod 10

[dusty dragon]

Note that 3^2 is -1 (mod 10). Try showing that 3^{14102019} is -3 (mod 10)

[dense scroll]

Try showing that 3^{14102019} is -3 (mod 10)
Mhmm so this is where I'm stuck. I don't know how to show this

So I'm thinking I could put this in terms of its factorisation and show that that is -3mod10

But it feels like there should be a better way to do it

[dusty dragon]

Notice that 14102019 = 2 * 7051009 + 1; therefore, 3^{14102019} = 3^{2 * 7051009 + 1} = 3 * (3^2)^{7051009}. But modulo 10, 3^2 is -1 so modulo 10, (3^2)^{7051009} = (-1)^{7051009} = -1

[torn escarp]

since 100 is divisible by 4, and 3^4=1 mod 10, you can chop off everything except the last two digits to simplify it to 3^19+3 mod 10. ||Since 19=20-1, it becomes 3^-1 + 3 mod 10. 3^-1 = -3 mod 10 (because -3*3=1 mod 10)||

[wanton viper]

Hallo!
Im having trouble understanding the details of the newton-polygon of p-adic numbers. Mainly with the part that for a given polynomial with p-adic coefficients the valuation of a root is the same as one of the slopes of the polygon

does anyone know a thing or two about this?

[torn escarp]

yeah

the length along the x-axis below the slope is how many roots have that valuation

[wanton viper]

my main problem is that im trying to understand why the valuation has to be one of the slopes.

ord is valuation

why does that last part has to be on the slope

[torn escarp]

maybe I misunderstand what sense in which you're asking

the slope is "rise over run" so that is exactly how the slope is on the graph when you put the valuation of the coefficients up to make the newton polygon