1 to 2, 2 to 3, 3 to 1
#elementary-number-theory
leaden compass
so to undo it
we map 2 to 1, 3 to 2, and 1 to 3
This is just (132)
Right?
(the convention is to write 1 in front)
cerulean plover
Oh
leaden compass
(oh also for S_4 and S_n in general you can also have guys like)
(12)(34)(56)
so this just means 1 goes to 2 and 2 goes to 1
3 goes to 4 and 4 goes to 3
etc
cerulean plover
Ok
leaden compass
But anyways
Yeah if you have (1 a b) then the inverse is just (1 b a) right
Since (1 a b) o (1 b a) is, 1 goes to b goes to 1
b goes to a goes to b
a goes to 1 goes to a
Right
We just undid everything
leaden compass
Anyways cool this is a really important group
In fact there is a famous theorem, cayley's theorem, that roughly states that every group is basically the same as a subset of a symmetric group
a symmetric group is just a S_n
the group of permutations on {1, ..., n}
But I won't get into this for now
cerulean plover
Ok
leaden compass
So what is a ring?
Well it's a lot like a group
But it has two binary operations
denoted + and x
And satisfying some axioms
(since they are binary operations this means there is closure)
(so a + b in R and ab in R for any a,b in R)
here R is our ring
also i am again denoting a x b by ab
for convenience
this is standard
cerulean plover
Yeah np
leaden compass
So + must be
- associative
- have an identity in R
- have inverses for every a in R
Or in other words
(R, +) is a group
Ah, so if we just take the set R and forget about the operation x
(R, +) is a group
Ok?
So yeah a ring is basically a group with added structure
cerulean plover
Ok
leaden compass
Moreover it is an abelian group
an abelian group is a group (G, *) where ab = ba
basically, where the operation is commutative
Ok?
cerulean plover
And that's the same as a ring?
leaden compass
So for example (Z, +) is abelian
nope
a ring has another operation
Well if you just consider the ring's set and the + operation
Yes
It is an abelian group
(R, +)
A ring is R, +, and x though
cerulean plover
Moreover it is an abelian group
@leaden compass got confused here
leaden compass
right so an abelian group is one where the operation is commutative
a ring with respect to addition, +, is an abelian group
this means that a + b = b + a
for a, b in the ring
Ok?
cerulean plover
Yeah
leaden compass
This mimics what happens for normal addition
which is commutative of course
1 + 3 = 3 + 1
in Z
cerulean plover
Yeah
leaden compass
Multiplication isn't required to be commutative though
Like matrices
Ok I'll give you some examples in a second once I complete the definition of a ring
cerulean plover
So does a ring always have to be an abelian group?
leaden compass
Ok so it has a set R, the operation + with respect to which (R, +) is an abelian group, cool
Well (R, +) must be an abelian group
but it must also have x
another binary operation
cerulean plover
Yeah ok I got it then
leaden compass
And x satisfies associativity, identity only
Not inverses necessarily
Nor commutativity
Let me give you an example
The ring (Z, +, x) where +, x are as usual
Ok so we already noted that (Z, +) is an abelian group
right
1 + 3 = 3 + 1 etc etc
and (Z, x) is a monoid— a monoid is a group except we don't require inverses
So yeah, (a x b) x c = a x (b x c) for sure
associativity check
and a x 1 = 1 x a = a
cool, identity
but... what's the inverse of 2?
well, 1/2 would satisfy 2 x 1/2 = 1 the identity
but 1/2 is not in Z
see? so 2 has no inverse
cerulean plover
Oh wow
leaden compass
Yeah
So Z with the usual addition and multiplication is a ring
in fact it's basically what the notion of a "ring" was based off of
they just generalized these properties
cerulean plover
That means (Z,*) cant be a group?
cerulean plover
Wow ok got it
leaden compass
The set of 2x2 matrices with real coefficients is a ring too
with the usual matrix + and x
Note that invertible matrices have no inverses
Sorry non-invertible*
lol
no multiplicative inverses of course
they do have + ones
Ok?
cerulean plover
Yea
leaden compass
Oh the additive identity is usually denoted by 0
and the multiplicative one by 1 usually
These aren't really numbers
just notation
So like 1 in this context is
1 0
0 1
this matrix
and 0 is
0 0
0 0
right?
cerulean plover
Yes
leaden compass
Now when a ring has inverses wrt x
It's a field
So when (R, x) is a group as well
and not just a monoid
For example (Q, +, x) is a field
Because, for 2, 1/2 is its inverse
and 1/2 in Q
Right?
cerulean plover
Yeah
leaden compass
Cool
So anyways
the final thing is
- and x are related by a distributive property
k(a+b) = ka + kb
(a+b)k = ak + bk
again, just generalizing the familiar ring (Z, +, x)
Right?
cerulean plover
Right
leaden compass
Cool
So
Z/9Z is a ring
its elements are equivalence classes [0], [1], ... [8]
And +, x behave just as you think they would
You can think of it like this
We take Z, and then we quotient out by 9Z— essentially we identify {0, ..., 8} with {9, ... 17} and so forth
cerulean plover
Ok
leaden compass
So it's basically just the normal (Z, +, x)
but we always reduce mod 9
this means we take the remainder mod 9
So 5*3 in Z/9Z will be, 15 = 9 + 6 so just 6
Okay?
cerulean plover
Is it just a notation?
leaden compass
It's notation yes
the quotienting thing is standard
you can quotient rings by ideals... but I won't get into that now
cerulean plover
Ok I'll just keep that in mind
leaden compass
Z/9Z has the set {[0], [1], ..., [8]}
and normal +, x
Now [a] + [b] = (9Z + a) + (9Z + b)
but this is really just the same as 9Z + (a+b) right
cerulean plover
Right
leaden compass
And [a][b] = (9Z + a)(9Z + b) = 9Z + ab really
Like for example
(9m+a)(9n+b) = 81n^2 + a9n + 9mb + ab
Of course 81n^2 + a9n + 9mb are just an element of 9Z
so it's just in 9Z + ab
leaden compass
Ok
So anyways we can answer your first question already
This is a ring though
no inverses for [3] though
or [6]
Why?
Well basically we want an m such that 3m is 1 mod 9
Since 1 is the multiplicative identity
But.. this is impossible
3m will either be 0, 3, or 6 mod 9
Ok?
cerulean plover
Mm
leaden compass
So here it's F_17 instead of Z/17Z
because Z/17Z is a field
so we can write F_17
instead, if we wish
why is it a field?
because 17 is prime
so all the [0], ..., [16]
have inverses
The only way for somebody to not have an inverse is if you can multiply and get 0 mod 17
But that's impossible because it means it's a divisor of 17
cerulean plover
Right
leaden compass
whereas for Z/16Z
well; all the even numbers are not invertible
Anyways
You want an x such that [5]x = [3]
To do this you can just multiply by the inverse of [5]
Since you have [5]^-1[5]x = [5]^-1[3]
x = [5]^-1[3]
Right?
cerulean plover
Yeah
leaden compass
here 5 has an inverse since it doesn't divide 9
so yeah just, compute it
You want an m such that 5m is 1 mod 9
cerulean plover
Where do we have 1 mod 9 from?
leaden compass
1 is the multiplicative identity
m is 5^-1
this means that 5m = 1
we're working in Z/9Z so we're working mod 9
cerulean plover
Yes I get that part
cerulean plover
Ok right
leaden compass
So then x is 6
Just 2*3
and you can indeed check that 5*6 = 30 is 3 mod 9
Okay?
Oh wait
We're working in F_17 for the first question
lol
Nevermind
the inverse of 5 mod 17 is
7
Ok
So just multiply by 7
x = 4
Yeah?
leaden compass
yeah 21 mod 17 is 4
cerulean plover
Right
leaden compass
Ok now
x^2 - 2x + 4 = 0 (mod 9)
is what we want
That is, (x-1)^2 = -3 (mod 9)
Right?
cerulean plover
Yes
leaden compass
yeah and -3 is what mod 9
cerulean plover
Eh
leaden compass
do you know modular arithmetic
cerulean plover
Still -3?
leaden compass
Ok so mod 9 means just take the remainder mod 9
cerulean plover
I do but I get confused when there's a - in front
leaden compass
-3 = 9*1 - 6 right
Oops
Ok think of it like this
-3 = 9*-1 + 6
so you ignore the multiple of 9
and take the remainder
cerulean plover
So its 6 in this case
leaden compass
Yes
So we want an x such that (x-1)^2 = 6 (mod 9)
just compute it
1^2 = 1 mod 9
2^2 = 4 mod 9
3^2 = 0 mod 9
4^2 = 7 mod 9
5^2 = 7 mod 9
cerulean plover
6^2 = 0 mod 9
leaden compass
Wait lmao 6 is not a qr mod 9?
cerulean plover
Huh?
cerulean plover
Dang
leaden compass
lol
cerulean plover
So that equations wrong?
leaden compass
Well the equation isn't anything
it's just that it asks you to find an x
also it's not an equation
it's just a congruence
it asks you to find an x
but there is none
leaden compass
I would just ask your professor or something if they made a typo
cerulean plover
Thanks a lot you're amazing
leaden compass
np
cerulean plover
I wish you were my prof haha
leaden compass
lol
cerulean plover
How did you know all this that's insane
Well anyways thanks! I should better try it all out by myself again
leaden compass
ok
alpine jasper
the book told me to use the corollary and proposition:
but i still don't get the idea
i also tried replicate this proof but also no luck
@winter bear help me papa
winter bear
number of sols to x^m=a
winter bear
e is just eulers
leaden compass
what's xi
alpine jasper
yes i think i know how 8.15 works
winter bear
ok so for pub
we have done a lot of gcd stuff like this in the book right
where this is in two parts
alpine jasper
so if m | p - 1 we refer to 8.15 and we only consider m does not divide p - 1?
sterile pumiceBOT
JohnDoeSmith:
supple furnace
Honestly just describe the characters and then everything falls into place
alpine jasper
i'm not sure where you're going with this though
winter bear
ok the idea was this gives us sum over chi^d= 1
and then that x^(m/d) is an automorphism of F_p*
rip forgeting by greek
winter bear
oh whoops meant=a
alpine jasper
ok cool
so we can basically throw the x^(m/d) out and replace it with like... a new x, because it's automorphism
winter bear
basically yeah
winter bear
if u like call it a new variable instead of x
alpine jasper
ok gimme a min let me see if i can write up a soln
Following identically to the argument offered in Proposition 8.15, let $\chi(g)=e^{2\pi i/d}$ where $a=g^l$ for a generator $g$ and some $l$. It follows that $\varepsilon,\chi,\ldots,\chi^{d-1}$ are $d$ distinct characters of order dividing $d$. Now, if $a=0$, then $\sum_{\chi^d=\varepsilon}\chi(0)=1$ as desired. If $a\neq 0$ and $x^m=a$ is solvable. Then it has precisely $d$ solutions (because $x^m=x^{(m/d)d}$ and $x^{(m/d)}$ is a bijective map from $F_p^\times$ to itself since $(m/d,p-1)=1$. And indeed, $\sum_{\chi^d=\varepsilon}\chi(a)=\sum_{\chi^d=\varepsilon}\chi^m(g)=\sum_{\chi^d=\varepsilon}\varepsilon(g)=m.$
sterile pumiceBOT
Publius:
alpine jasper
i lastly have to deal with x^m = a being unsolvable right
wops the last equality is = d and not = m
alpine jasper
sure
supple furnace
Yeah unsolvable case is similar
alpine jasper
i think it's identical to the one already in the book
unless i'm missing somethin again
stoic bear
Looks fine to me @long wasp
sacred junco
I don't get how u went from the 3rd line to the 4th line in the inductive step
stoic bear
On the LHS, you factor out a 2
On the RHS, you use the identity that n! = n times (n-1)!
long wasp
Thanks for looking it over for me, I find it hard to explain inequality proofs eloquently, my professor is quite picky
dreamy rain
so this is a proof numbers in a primitive pythagorean triple are relatively prime pairwise
i dont understand why the bottom explanation is required
what are we missing from the top part
is it just a diff way to explain the same thing
fervent crest
Hmmmmmmm
Oh
I see
You are supposed to prove that all three numbers are pairwise relatively prime.
Since the statement is $$\text{if }s>t\geq1\text{ and }\gcd(s,t)=1\quad\text{then}\quad st,\frac{s^2+t^2}{2},\frac{s^2-t^2}{2}\text{ are pairwise relatively prime}$$
sterile pumiceBOT
Whoever:
fervent crest
@dreamy rain the fact that a prime divides all three numbers doesn't immediately imply a contradiction with the assumption
dreamy rain
hm yeah thats true if this was just a standalone question, but if we are in the context of ptimitive pythagorean triples, would the top part be enough because we are not allowed a prime that divides all 3?
but yeah this was a standalone question so makes sense
supple furnace
The goal is to show that if p divides two of the three (equivalent to gcd of two of them being greater than one), gcd(s,t)>1.
We can’t get that from just the top part.
However, the end part is way longer than it has to be. If p|(s^2-t^2)/2 and p|(s^2+t^2)/2, then p|s^2 and p|t^2, so gcd(s,t)>1.
Much shorter
dreamy rain
ahhh yeah thats nicer
but i dont see how thats necessarily the goal
especially if we are given the fact that the 3 numbers make a PPT
fervent crest
The whole point is to prove that given s,t that satisfy the condition, the expressions will produce a primitive pythagorean triple
You are not given the fact that the 3 numbers make a PPT
dreamy rain
but if i were would it be ok?
supple furnace
You need s,t to be odd relatively prime integers tho
fervent crest
Well if you were given the fact that 3 numbers make a PPT, then the first part will be enough
dreamy rain
oke yea thank you, i think this makes sense then
also
if ur not given the fact that its a PPT, whats even the point of the top part
wont the seconf part be enough
i.e. just proving that gcd(s,t)=/= 1
when 2 of the numbers arent coprime
im probably overthinking all this lol
it doesnt matter too much
fervent crest
The top part reduces all three cases into a single case
So say the three numbers are a,b,c, then we want to prove that gcd(a,b)=1, gcd(a,c)=1, and gcd(b,c)=1. The top part says that if gcd(a,c)>1 or gcd(b,c)>1, then gcd(a,b)>1
so if gcd(a,b)>1 creates a contradiction, then so will gcd(a,c)>1 and gcd(b,c)>1
@dreamy rain
supple furnace
Yeah the top part works well in condensing those cases. It’s just that the (s^2-t^2)/2 and (s^2+t^2)/2 are so much more compatible than the pair they chose after that.
alpine jasper
if $J(\chi,\rho)=a+bi$, then $J(\chi^{-1},\rho)=a-bi$ right, where $J$ is the jacobi sum
sterile pumiceBOT
Publius:
alpine jasper
im not sure if that's true or how to prove it
hmm
$J(\chi^{-1},\rho)=\sum_{a+b=1}\chi(a^{-1})\rho(b)$
sterile pumiceBOT
Publius:
alpine jasper
help
alpine jasper
umm idk man
um oh wait
quadratic character
right, yeah, $\rho(b)=\overline{\rho(b)}$
tyty
sterile pumiceBOT
Publius:
winter bear
yep
alpine jasper
even with the hint i don't see it 
if $a=2n+1, b=2m$, then\
$p = 4n^2 + 4n + 1 + 4m$,\
this also means $(2n+1) + (2m)i$ in $\mathbb Z[i]$ can only be divisible by $\pm1$ or $\pm i$
sterile pumiceBOT
Publius:
alpine jasper
am i suppose to show that every prime in $\mathbb Z[i]$ has a unique norm
sterile pumiceBOT
Publius:
alpine jasper
wops that should be a 4m^2
harsh mirage
Maybe another hint: a^2 + b^2 = (a + ib) (a - i b), and if an element in Z[i] is prime, then so is its complex conjugate
stray crane
Guys i have a weird question for you. I was thinking about irrationality, and i asked myself if there are integers a,b such that sqrt(a) and sqrt(b) are both irrational , but sqrt(a) + sqrt(b) is rational
i think they don't exist, but i don't really know how to prove it
Sorry if this is trivial but i'm learning number theory rn so i'm not good
torn escarp
try assuming sqrt(a)+sqrt(b)=q for some rational q
rearrange it by some algebra to reach a contradiction
play around for a bit and show me what you get if you get stuck and can't think of anything more to try
stray crane
ok i'll let you know
if sqrt(a) + sqrt(b) = a/b ---> (by some algebra) ab has to be a perfect square, so $ab = q^2$. but that means $q*sqrt(1/b) + sqrt(b)$ is rational, and multiplying by b, i get that $sqrt(b) * (q+b)$ must be rational, contradiction
sterile pumiceBOT
Ricky the Crow:
stray crane
i cannot use latex sorry
torn escarp
the proof I had in mind was
harsh mirage
i think you did the right thing but you should've called your fraction differently
torn escarp
sqrt(a)+sqrt(b)=q, q is not necessarily a/b though
stray crane
if q is rational, it is a/b for a and b integers
torn escarp
you already used a,b
stray crane
oh you're right
harsh mirage
yeah, other than that it's correct
stray crane
i'm stoopid
torn escarp
how I worked it was slightly different
sqrt(a)+sqrt(b)=q
sqrt(b)=q - sqrt(a)
square both sides
b = q^2 -2qsqrt(a)+a
maybe this is what you did
rearrange to solve for sqrt(a)
harsh mirage
oh that's nice and even quicker, lol
torn escarp
and it's now rational, contradiction
torn escarp
yup you're welcome
terse geode
hey gamers need some help here
A soccer field is a rectangle 90 meters wide. Each day the coach asks players to run from one corner to the other corner at a diagonal distance of 150 meters. What is the area of the soccer field?
it has some to do with
Pythagorean therom
obtuse mason
well how long is the field?
sacred junco
@terse geode u use the pythagorean theorem to find the length, then multiply the length with the width
burnt swallow
Not quite sure how to formally explain this, but if anyone can offer insight:
Is it possible to have two distinct linear ciphers that send every plaintext letter to the same ciphertext letter?
My thought process is to say brute force and there will probably be a collision
fervent crest
Well if you consider $b_1=1$ and $b_2=n+1$ to be distinct
Otherwise, if $a_1P+b_1\equiv a_2P+b_2\pmod{n}$ for any $P$, then $a_1\equiv a_2\pmod n$ and $b_1\equiv b_2\pmod{n}$
Because you can first plug in $P=0$ to get $b_1\equiv b_2 \pmod n$, then plug in $P=1$ to get $a_1+b_1\equiv a_2+b_2 \pmod n$, but since $b_1\equiv b_2 \pmod n$ we have that $a_1\equiv a_2 \pmod{n}$
fervent crest
@burnt swallow
fervent crest
You're welcome
burnt swallow
Requesting someone to help on how to clear up my proof. Not sure if the "(p+3)/2" reasoning is strong enough, but it made sense in my head
Here is the problem pertaining to above*
burnt swallow
oh that's true
that's the part i'm having a hard time on: closing the gap on that reasoning unless i was supposed to rewrite the exponents in a different way after foiling out (p-1)(q-1). @light flicker
light flicker
p must be either 1 or 3 mod 4
burnt swallow
I thought the legendre symbol being = 1 or -1 is irrelevant. Isn't $p \equiv 1 \pmod{4}$ or $p \equiv 3 \pmod {4}$ relevant, based on the corollary to the theorem, such that $\left(\frac{-1}{p}\right) = 1 \ \textrm{if} \ p \equiv 1 \pmod{4}$ or $\left(\frac{-1}{p}\right) = 1 \ \textrm{if} \ p \equiv 3 \pmod{4}$
sterile pumiceBOT
Eigenspace:
light flicker
Ah sorry I misspoke
I meant to say that p - 1 = p + 3 (mod 4)
And so (p-1)/2 and (p+3)/2 will always both be even or both be odd
burnt swallow
@light flicker How come we are allowed to introduce the (mod 4)? Not quite following
eager tendon
Hello someonle here ?
I have some questions about primes nature
I would like to discuss it with someonle
<@&286206848099549185>
hushed ether
just throw the questions here I think would be best
eager tendon
Wait I need to translate words
Greatest common divisor of A and B = d , exist just if d|A, d|B and if for any c|A and c|B then c|d
c|A and c|B then c|d where can I find the proff that the greatest divisor of an integrer can be divided by all the lowest divisord ?
I hate doing thing and not knowing why they are made that way
trail matrix
Can anyone hint at or help me find an easy way to find x's and y's for which
x = -y mod xy
By easy i mean computationally quick
trail matrix
Well not much really
The expression stems from trying to find integer solutions to 1/x + 1/y = 1/n for some n
But i'm not sure where to look
sacred junco
You want to find all x and y given a fixed n?
trail matrix
Yes
sacred junco
That^
trail matrix
Yeah the mod doesn't depend on n
sacred junco
If you want to solve that Diophantine equation I’d highly suggest factoring
winter bear
play around with it and see factoring yeah
sacred junco
Easiest way to solve the equation of that form
trail matrix
Factoring?
sacred junco
Yes, find something to add to both sides and factor the equation
trail matrix
Ah
sterile pumiceBOT
JohnDoeSmith:
trail matrix
Never heard about that, i'll look into it
winter bear
try factoring it first though, we can worry about the other stuff later
sacred junco
Yea and it will be pretty easy to finish once it is factorized
sacred junco
Correct
eager tendon
Because if n is prime then n can be too
eager tendon
if n is prime the -n is also prime
eager tendon
If we consider a prime number as any n that can be just divided by 1 -1 -n and n
So if the definition claims
Just n and 1
The primes should be >1
winter bear
so a prime is defined as a non-unit such that $p|ab \implies p|a$ or $p|b$
sterile pumiceBOT
JohnDoeSmith:
eager tendon
Wikipedia define primes as numbers >1
shrewd marsh
So do you think -7 is composite?
eager tendon
Of course no
winter bear
are you familiar with some ring theory?
eager tendon
Yep
winter bear
in a general ring the p|ab implies p|a or p|b is how we define a prime, given p is not a unit
now if p and p' are associates (i.e differ by a factor of an unit) and one is prime, so is the other
1,-1 are your units for Z
so p and -p are both primes (see if it satisfies the defination)
the fundemental theorem of arithmetic is still safe with this btw
because in a Unique factorization domain, each element has an unique factorization into primes upto units
the upto units part is important
because otherwise for example 6=2*3 = -2*-3 would not be unique
trail matrix
Alright, using Simon's Favorite Factoring Trick i got that xy-xn-yn = 0 can be written as (x-n)(y-n) = n^2 but what does this entail?
sacred junco
n^2 is fixed right?
sacred junco
^
winter bear
now unfortunately you'd have to test it out with all the factors
sacred junco
there are a finite number of possible values for x-n and y-n
trail matrix
Yeah you're supposed to use a computer to find the solutions
and i did make a brute force script
winter bear
yeah so use your favourite factoring algorithim now
trail matrix
Aight, i'll try!
Thanks
Oh, right so the number of distinct solutions will be the ceiling of the number of factors of n^2 halved
Of course
I hope this is quick enough tho
sacred junco
are you considering (x1,y1) the same solution as (y1,x1) or not?
trail matrix
They are the same
That's why i need to halve the number of factors
they will be repeats
i think
sacred junco
yea
it should be plenty fast enough unless n^2 is extremely large
the run time is approximately the time it takes to find all divisors of n^2
the other steps are negligible
trail matrix
I need to find the "least value of n for which the number of distinct solutions exceeds four million"
So it will be big
But i don't need to know the factors only the number of them
sacred junco
interesting
trail matrix
I'll have to look into divisor functions i guess
winter bear
oh u can construct this without computing actually
sacred junco
hm each divisor of n^2 gives gives rise to one unique solution doesn't it?
is the question equivalent to finding the first perfect square with 4 million divisors?
winter bear
well depends
trail matrix
I think i'd be 8 million
winter bear
do we count only positive or negative sols too
sacred junco
oh forgot about that
winter bear
if positive then 8 million and 1, if negative then 4 million and 1 i think
trail matrix
My old program says that n = 180180 has 1013 unique solutions but n^2 has 2025 factors
winter bear
anyhow you want to use that
$\sigma_0 (p_1^{k_1} \dots p_m^{k_m})= (k_1+1)\dots (k_m+1)$
sterile pumiceBOT
JohnDoeSmith:
trail matrix
Uuuh
winter bear
where sigma_0 is divisor count
winter bear
the idea is that you figure out the ks
trail matrix
of a given n?
winter bear
well if you wanna go brute force on n sure
trail matrix
Couldn't i just find a product that exceeds 8 million and then work backwards
winter bear
yeah that was the idea
trail matrix
Right
I'll try and implement it
Hmm but this is tricky, right?
because i want a high k for small primes but i don't want it too high
winter bear
yeah its a bit tricky
trail matrix
But all k's need to be a multiple of 2 because it's squared
torn escarp
what are you able to get by simplifying with euler's theorem?
you might need to use the chinese remainder theorem
oh I see I missed the paper you wrote before you posted the question
I just ignored it cause usually people post the other direction haha ok I see
fervent crest
Lol
97 divides it means it’s congruent to 0 modulo 97
So the question is basically asking whether 83 is a quadratic residue modulo 97
burnt swallow
yeah got it
i got this far into the proof, but not sure how to close it out since i think i'm stuck with the logichere
fervent crest
I mean
All the numbers in S have negative least residue, so the mu there is just (p-1)/2
And the result follows form gauss's lemma
dreamy rain
im trying geometrically to find the infinite solutions to the linear combination ax+by= gcd(a,b), but i cant seem to get the correct result.
i managed to find the solutions geometrically when gcd(a,b)=1 using the method i posted above, but im stuck for gcd(a,b) greater than 1
btw the question might not make sense cus i made it up lol
just messing about
i can post where i got up to if that helps
sacred junco
I don’t really get where the geometry is coming in. This looks like pretty classical linear diophantine solving with one line about geometric interpretation. Is that all you mean?
dreamy rain
well yeah i guess so aha
just wondering how come i cant use the same technique when gcd isnt 1
sacred junco
There is definitely a theorem for solving equations of this exact form in burton number theory
dreamy rain
is that a book?
sacred junco
The one in the book suggestion channel
winter bear
just do $(x,y)\longrightsquigarrow (x+b,y-a)$
sterile pumiceBOT
JohnDoeSmith:
dreamy rain
ah oke
sacred junco
It has no geometric interpretation but it might help to read about it there
dreamy rain
i mean ik how to figure this out without the geometric interpretation, u can just divide ax+by=gcd(a,b) by the gcd to form a new equation that equals 1 and u can then use the same method as i figured out above
it is the geometric part im more interested in
it doesmt seem like the geometry applies here though, idk
not a big deal anyway
sacred junco
Explain why it doesn’t work
dreamy rain
hm
not all points on the line ax+by=gcd(a,b) will actually give a solution?
idk tbh
sacred junco
Do they need to satisfy some congruence?
The case for gcd=1 is much simpler than when it’s not 1
dreamy rain
i see
and idk if they need to satisfy some congruence
i dont have too much knowledge on diophantine eqs or anything
should i just leave this if its a lot more complicated lol
sacred junco
No this Diophantine equation is a great introduction to Diophantine equations
sacred junco
So are you not finding the solutions successfully when gcd isn’t 1?
Geometric interpretation ignored
dreamy rain
well i can use this to get the solutions, thats not a problem
and i do understand where that comes from
sacred junco
Ok yep that’s the right theorem
So where is the geometric interpretation going wrong?
Can you describe in words, not math, the family of solutions?
dreamy rain
hm idk if this counts as math, but could i use those set of coords in the theorem, along with (x_1,y_1j (since we know that this point must also lie on the line) to form an equation for the line of all solutions?
i really domt know how to describe in words
sacred junco
you might find it easier to go from english words to geometry instead of purely symbolic math to geometry
sacred junco
um if that means what I'm thinking then it's too trivial lol
dreamy rain
probably
i really wanna try figure this out without just being given it, but idk if thats going to happen D:
do u have any sort of hints
sacred junco
luckily/unluckily for you I don't really have an answer and have never thought about this before lol
dreamy rain
LOL
alright
ill just keep thinking ahaha, maybe one day ill figure out
someone here will prob have an answer though
sacred junco
I still don't understand why it doesn't translate well into the case where the gcd isn't 1
isn't the unit shifting just at a different rate?
b/g and a/g are still fixed
they are just b/g and a/g instead of b and a now
but it's still fixed
dreamy rain
yea i mean i have no idea, thats sorta what i was questioning as well
sacred junco
so what's wrong with whatever you are doing?
dreamy rain
eh i didnt really do anything tbh, nothing noteworthy
im not really able to figure much out
sacred junco
but I'm confused how understanding the gcd=1 interpretation doesn't translate to gcd not 1 interpretation
dreamy rain
yes thats also my question i asked at the start, but uve worded it more concisely
im not so good with words lel
sacred junco
sacred junco
was the gcd=1 case reached by geometric means?
or a geometric interpretation tacked on?
dreamy rain
if im being honest, idk how id tell the difference
i treated ax+by=c as the actual graph
so i feel like that makes it geometric
but perhaps not
sacred junco
can you tell me what in here used geometric means and not symbolic math and number theory means?
https://cdn.discordapp.com/attachments/418981682117345288/709978418745311322/image0.png
the only geometry here was interpretation
no use of geometry to solve the equation
so you can do the exact same thing for the gcd not 1 case
describe the family of solutions geometrically, like where they would appear on the graph
but not "solve" anything with geometry
sacred junco
geometric interpretations are common when working with diophantine equations, and often geometric problems and diophantine problems can go hand in hand, or describe the exact same problem
but any solutions to such problems will always require symbolic math to be convincing
sacred junco
for example... proving non existence of rational points on a circle may come down to proving a related diophantine equation has no solutions
and no problem
but yes actually, you should be interested in geometric interpretations of diophantine equations
just not using geometry to "solve" them
dreamy rain
yeye
vagrant moat
Hello. I am pretty new to the Legendre Symbol and I'd like some help with showing this: $\bigg(\frac{1(1-m)}{p}\bigg) + \bigg(\frac{2(2-m)}{p}\bigg) + \dots + \bigg(\frac{(p-1)(p-1-m)}{p}\bigg) = -1$.
sterile pumiceBOT
PolyBeanDip:
vagrant moat
do let me know if this is the right place for this question
also, m is an integer in [1,p-1]
brittle patrol
I think this is the right place @vagrant moat
I found a solution but it's pretty complicated
Can I know know where you got this problem? I would know if I should expect a simpler solution or if mine might be the intended one
btw this is a really great problem
sacred junco
can u show your solution?
if its long and u dont want to latex it cna u just sketch without the details
brittle patrol
Yeah sure
so since it's Legendre's symbol, all of those are between -1 and 1, and so the sum is between -p+1 and p-1
and at least one of those zeros out (for a=m)
it's enough to show that the sum is congruent to -1 modulo p
$\bigg(\frac{x}{p}\bigg)\equiv x^{\frac{p-1}{2}}$
sterile pumiceBOT
Gonzo17:
brittle patrol
so the sum is congruent to $\sum\limits_{x=1}^{p-1} (x^2-xm)^{\frac{p-1}{2}}$
sterile pumiceBOT
Gonzo17:
brittle patrol
That is a sum of the form $\sum\limits_{x=1}^{p-1} P(x)$ for a polynomial $P$ with degree $p-1$ and constant term equal to 0
sterile pumiceBOT
Gonzo17:
brittle patrol
But there's a lemma that $\sum\limits_{x=1}^{p-1}x^i=0$ for any positive integer $i$ not divisible by $p-1$
sterile pumiceBOT
Gonzo17:
brittle patrol
The proof of the lemma is to take the generator $g$ in the group $(Z/p)^{\times}$
sterile pumiceBOT
Gonzo17:
brittle patrol
then $\sum\limits_{x=1}^{p-1}x^i\equiv\sum\limits_{k=0}^{p-2}(g^k)^i=\frac{g^{(p-1)i}-1}{g^i-1}$
sterile pumiceBOT
Gonzo17:
brittle patrol
and the numerator of the latter is divisible by $p$ because of Fermats Little Theorem, and denominator isn't because $g$ is a generator and $p-1\nmid i$
sterile pumiceBOT
Gonzo17:
brittle patrol
So, now we have $\sum\limits_{x=1}^{p-1}x^i\equiv 0$ for all $i$ between $1$ and $p-2$
sterile pumiceBOT
Gonzo17:
brittle patrol
and so back to the sum from the problem, which is $\sum\limits_{x=1}^{p-1}(x^2-xm)^\frac{p-1}{2}$
sterile pumiceBOT
Gonzo17:
brittle patrol
The only thing that matters here is the coefficient by $x^{p-1}$, because all other will sum up to 0 by the lemma
sterile pumiceBOT
Gonzo17:
brittle patrol
the coefficient by $x^{p-1}$ is of course 1
sterile pumiceBOT
Gonzo17:
brittle patrol
so the original sum is congruent to $\sum\limits_{x=1}^{p-1}x^{p-1}=\sum\limits_{x=1}^{p-1}1=-1$
sterile pumiceBOT
Gonzo17:
brittle patrol
And thus equal to it
Lol I should have typed this into a document, sorry for the messy writing
@sacred junco
sacred junco
I see, cool, thanks!
brittle patrol
@vagrant moat I just posted the solution to your problem in here, if you don't want it spoiled then don't read back
You can ping me for some hints, or clarification if you read this proof
light flicker
There's an easier solution here
You can rearrange this to be a Jacobi sum
i.e.
$\sum_{x = 1}^{p-1} \left( \frac{x(x - m)}{p} \right) = \left(\frac{-1}{p} \right)\sum_{x = 1}^{p-1} \left( \frac{x(m - x)}{p} \right)$
sterile pumiceBOT
Zopherus:
trail matrix
Can someone give me a hint?
Assume p = 1 mod 5, and that x has order 5
I need to show that $(2(x + x^{-1}) + 1)^2 = 5 \mod p$
sterile pumiceBOT
Wrrr...:
light flicker
x has order 5 mod p?
brittle patrol
You can try expanding the left side and rearranging
trail matrix
I tried
But didn't seem to get anywhere
just end up with $4(x^2 + x + x^{-1} + x^{-2} +1 ) = 0 \mod p$
sterile pumiceBOT
Wrrr...:
brittle patrol
Yeah that's ok
That's what you want to prove
Now, it would be good to get rid of the inverses
Or maybe another way
You know that x^5=1
trail matrix
I could write it $4(x^4 + x^3 + x^2 + x +1 ) = 0 \mod p$
sterile pumiceBOT
Wrrr...:
trail matrix
But i don't see how that changes much
brittle patrol
Yeah that's what I was thinking about
So now, you have to show that from the facts x^5=1 and x isn't 1
trail matrix
x can never be 1 because then i'd have order 1 but it has order 5
sterile pumiceBOT
Wrrr...:
trail matrix
I think i got it from here, thanks a lot my dude
brittle patrol
Np man
vagrant moat
Wait, so, I don't rly get how Zopherus's proof works
light flicker
I left out like most of the proof lmao
It's not really easier
because from there, you have to use facts about jacobi sums that tell you that the sum is equal to -(-1/p)
vagrant moat
oh, I see
perhaps I should just share the original problem
I'm trying to evaluate $\sum_{a=0}^{p-1}g(a,p)g(-a,p)$
sterile pumiceBOT
PolyBeanDip:
vagrant moat
where $g(a,p) = \sum_{n=0}^{p-1}\bigg(\frac{n}{p}\bigg)\zeta_{p}^{an}$
sterile pumiceBOT
PolyBeanDip:
vagrant moat
I'm guessing that it's p(p-1), but I'm not rly sure how to prove it
light flicker
is this an exercise in ireland rosen
vagrant moat
Well, I got the problem down to proving $\bigg(\frac{1(1-m)}{p}\bigg) + \bigg(\frac{2(2-m)}{p}\bigg) + \dots + \bigg(\frac{(p-1)(p-1-m)}{p}\bigg) = -1$, but then I got stuck
sterile pumiceBOT
PolyBeanDip:
vagrant moat
I got this from expanding g(a,p)g(-a,p) and finding the coefficient of \zeta^(am)
I already know that the coefficient of \zeta^(0) is p-1 so if I can show the other coefficients are -1, then I can use the fact that -1*(Phi_{n}(\zeta_p) -1) = 1
to show that g(a,p)g(-a,p) = p
for all a not equal to 0 that is
noting g(0,p) = 0, the result follows
But, it looks like proving the coefficients are -1 hasn't rly simplified the problem
winter bear
i suggest just expanding it into a triple sum first
you ight observe something from there
vagrant moat
triple sum?
vagrant moat
yeah
winter bear
so just write it out fully
winter bear
well even if you are not, as a general rule when you have something like this you should try to write it out explicitly
in hopes of observing something
vagrant moat
I see
winter bear
(ping me once you have something
vagrant moat
ok
winter bear
or if you want a hint
vagrant moat
wait, but I don't rly think writing the sum explicitly for all a would help tho
wouldn't showing g(a,p)g(-a,p) = p (for non-zero a) be the way to go?
btw, I can't use quadratic reciprocity (cuz I haven't prove that yet)
winter bear
hmm i mean i know the solution and writing the triple sum is a direct way
no QR required
(just plug in the expression for g(a,p) and g(-a,p))
vagrant moat
brittle patrol
Omg that's so clean
dreamy rain
is there a nicer way to obtain the result that ive highlighted in green
their explanation makes sense, but its not very... nice? idk
or intuitive
dreamy rain
idk its just that if u werent given the final result, i dont think many people would come up with that process?
i came up with this
idk how to explain it more concisely
and idk if everything i wrote is correct
but i feel like this is a nicer sort of approach
to finding the result that
$x_0+ k \cdot \frac{m}{g}$
sterile pumiceBOT
bri:
sacred junco
I think it looks fine
dreamy rain
ah great
sacred junco
I saw that
dreamy rain
yeahhh
was working on something
lemme post
would u be able to come up with a solution that directly
i think this is again a little more nicer
idk why im doing this
but ye
@sacred junco does that make sense?
thats meant to be an x_0 at the bottom
sacred junco
Umm
dreamy rain
i can try write it more clear that was kinda rushed, but what particularly do u not get
or is it just all of it
lol
sacred junco
https://i.imgur.com/K7VYAKJ.png I don't understand what's wrong with this
dreamy rain
ohhhh
sacred junco
but I might be lost in the naming convention you are using
dreamy rain
ok yeah what uve scribbled out is just some working to obtain the first solution
if that makes sense
but yea it doesnt really matter lol
as long as the bottom bit makes sense, then its fine lol
sacred junco
errr
I guess you would need the first/second line
well..
what are u and v doing?
they never get mentioned again
dreamy rain
u got mentioned again
butttt, ill just write this up neat in latex and ping u when im done
hopefully itll be more clear
sacred junco
yea I'm a little lost with what each letter is supposed to mean
dreamy rain
ye np
sacred junco
I think I read this as an a lol
https://i.imgur.com/x2nIyul.png I think I wanted this instead
actually
I don't really know, I can't follow the work
or what you are trying to do exactly
but yea, if you send something written in latex that defines all the variables then I'll read it 👍
dreamy rain
i think this should be a bit more clear
its only really the bottom bit im concerned with
also, do you know how ud explain the term 'residue class', i feel like thats not a term thats used anymore?
@sacred junco
i probably shouldnt have cropped so much at the top, but i think it should still make sense
sacred junco
what's wrong with residue class?
dreamy rain
idk i just havent heard it being used apart from in this paper from like 2007 lol
sacred junco
you could say all members of a residue class are congruent in modulo whatever
dreamy rain
ah yh
sacred junco
I still don't know where some of the variables are coming from
where is b introduced?
dreamy rain
we are tryna solve this
sorry yea i shouldnt have cropped so much lol
heres the full doc
the top bit isnt relevant
btw a lot of it is just a copy and paste from my textbook lol, but this is just for my personal use so i dont think that matters
dreamy rain
yikes
sacred junco
solving that congruence is equivalent to solving a linear diophantine equation
well
wait one second
hm nvm
dreamy rain
btw i do know that there is a simpler way to solve linear congruencess
my main motivation for this is that it gives some reasoning to these results
and also making links in maths i p cool
sacred junco
the bulk of the difficulty in the problem is proving rigorously that there are g residue classes that the solutions could have
dreamy rain
hm i see
sacred junco
I think the things you were doing before that are convoluted
you could just quote the previously established linear diophantine solving theorem
if you fix a, b, and m, then you are just solving a linear diophantine equation
nothing more to it
dreamy rain
hm yeah perhaps ive made it convoluted because i only really know how to solve linear diophantine equations of the form ax+by=g where g is the gcd of a and b. but idk how to solve ax+by=kg, for an integer k. im guessing theres an easier way to solve ax+by=kg than how ive done?
i think ill just come back to this once i cover diophantine equations properly
sacred junco
what does the theorem that you learned say?
does it not prove that the solutions just depend on gcd(a,b)
and that it doesn't matter if the right hand side is gcd(a,b) or a multiple of gcd(a,b)?
if it doesn't include that, then I guess you've covered that for yourself now
dreamy rain
the theorem i learned is basically a copy past of what i write in that doc, the only part i didnt like was this
so i changed that bit
dreamy rain
ahh
sacred junco
ah I see the one you pasted now
dreamy rain
yea
sacred junco
I see why your work was more convoluted lol
dreamy rain
yeaaaaaa
sacred junco
since you were using a weaker theorem
dreamy rain
perhaps the book im using isnt as good as i thought
sacred junco
burton elementary number theory
sacred junco
I've never looked at it but that should be plenty good
dreamy rain
yea hopefully
sacred junco
I mean silverman
sacred junco
I'd use both
sacred junco
np