Can I just create my own fields lmao.
#elementary-number-theory
vernal ibex
sacred junco
Finite fields are great too, their multiplicative groups are cyclic and you can actually write the elements as finite strings in a base natural to that finite field which makes doing operations by hand very simple
And the lattice of subfields is in a very nice form too
sacred junco
Can I just create my own fields lmao.
Of course! If you make something that happens to exactly follow the axioms, then it will be a field no matter what
There is an important class of rings called "integral domains" that have a property allowing them to be naturally converted into fields
vernal ibex
Of course! If you make something that happens to exactly follow the axioms, then...
Woah!!!!
vernal ibex
There is an important class of rings called "integral domains" that have a prope...
I see WOAH.
leaden swan
Of course! If you make something that happens to exactly follow the axioms, then...
Well, Technically those fields already exist
sacred junco
Well that's in the realm of philosophy of math :P
torn escarp
create me a field with 6 elements
leaden swan
Ok,yea
rugged moth
$\mathbb{F}_6$
sterile pumiceBOT
regal cloud
i dont know if i have miss read this
but what does this mean by absolute value of each xj must be an nth power
any help would be much appreciated
wind glacier
sacred junco
but what does this mean by absolute value of each xj must be an nth power
Like for example -216 = (-6)^3 = (-2)^3 (3)^3
We can see (-2)^3=-8 and 3^3=27 are pairwise coprime, and -216 is (-6)^3. As the exercise guarantees, we have that |-8| = 8 is a 3rd power (2^3)
And |27| = 27 is a third power
leaden swan
https://media.discordapp.net/attachments/885521812065239110/933029041571778640/7...
Numbers of form 2^k
Pick the smallest divisor and call it p
Pick the second largest divisor,say k and note that k-p <k which implies k=2p
By induction you can argue (i+1)th divisor is of form ap
Which implies all divisors are of the form ap for some prime p
Which restricts our case to n=p^k(Why?)
This along with the second largest divisor being 2p shows n=2^k for some k(Why?)
Oh,nvm I assumed the second largest factor is not p+1
livid birch
does the law of quadratic reciprocity apply to finding the quadratic residue of 3 and 71?
idk if that sentence makes sense actually
sacred junco
Yeah not sure exactly what you mean but looking at whether 3 is a quadratic residue can be really simple via qr because it's so small, and after flipping you'll only have a few cases to go through since you're working mod 3 by then
and 71 isn't too large so after only a few flips you will get down to the result
livid birch
but doesnt it only apply if one of the two numbers is 1 mod 4
sacred junco
not sure what you're referring to since Legendre symbols work fine for any odd prime
you mean whether you pick up extra negative signs or not?
just keep track of em
sacred junco
idk much about Borcherd's series on youtube but I think you didn't finish the section cause you will learn that if p is 3 mod 4 then you pick up a negative sign
livid birch
maybe i just misheard him i'll rewind
sacred junco
it might come after
livid birch
but this is the new series he's uploading
sacred junco
You can express quadratic reciprocity like this
ofc one may move either Legendre symbol on the left over to the right since they just take on values of 1 or -1 with these odd primes
Basically if either of the primes is 1 mod 4, you can flip the symbol, meaning in that case the symbol is equal to itself but flipped
when both primes are 3 mod 4, then you can still flip, but you must pick up a negative sign
sacred junco
legendre seems interesting tho
I like to just think of the symbols as a "formalized" version of the question "hey is this thing a square mod this prime?"
Because that's all it is really
Instead of English the answers happen to come in the form of 1 for "yes", -1 for "no", and 0 for "lol this number is 0 mod p but sure it's a square, trivially"
wooden glen
Which makes "quadratic reciprocity" a bit of a clickbait name. Sure, there are two things that multiply together to ±1, very reciprocally -- but that's because they are both ±1 to begin with.
vernal ibex
<@&268886789983436800>.
muted kestrel
dusty dragon
You perform the Euclidean algorithm and then reverse it to find x and y
So at each step, you substitute out the remainder from the previous line
dusty dragon
47 = 30 * 1 + 17,
30 = 17 * 1 + 13,
keep going until you hit a remainder of 0
vernal ibex
Oohh.
Okay.
So.
If the equation were equal to another constant.
We would go on till we reached that?
Like if it were 47x + 30y = 4, then we go till we reach a remainder of 4?
dusty dragon
Nah, we still perform the steps until we hit a remainder of 0
That's basically your terminating case
vernal ibex
Okay I do not understand what exactly we do the entire time.
dusty dragon
we're trying to find the gcd of 47 and 30, using the Euclidean algorithm allows us to do so. It'll also tell us whether solutions to the Diophantine equation exist or not
vernal ibex
Hmmm.
wooden glen
Okay I do not understand what exactly we do the entire time.
If you're comfortable with symbolic algebra, it can help with seeing the big picture if we introduce some helper variables.
You want to solve 47x+30y=1. Rearrange that to 30(y+x)+17x=1 and introduce a new variable z=y+x.
Now you need to solve 30z+17x=1 which is of the same form as before, but the largest coefficient is now smaller so it's in some sense simpler.
Rearrange 30z+17x=1 to 17(x+z)+13z=1, introduce a new variable w=x+z and we have 17w+13z=1.
Rearrange 17w+13z=1 to 13(z+w)+4w=1, and introduce v=z+w.
Rearrange 13v+4w=1 to 4(w+3v)+1v=1, and introduce u=w+3v.
Rearrange 4u+1v=1 to 1(v+4u)+0u=1, and introduce t=v+4u.
Now all that remains to solve is 1t+0u=1. That's easy: we must have t=1 and u can be arbitrary. At this point we can either set u=0 to make the arithmetic simple and get a single solution, or keep u as an unknown and get the full set of solutions. The standard presentation of the algorithm sets u=0.
Since we now know t and u, we can compute v from t=v+4u.
Since we now know u and v, we can compute w from u=w+3v.
And so forth, unraveling the entire stack of helper variables until we get back to x and y.
The time-consuming part of the procedure is the division with remainder that tells us what to do in each "rearrange" step; the final unraveling is always just a single multiplication and a subtraction for each step.
In each step on the way down, the remainder of the division becomes a coefficient in the next equation to solve, and the quotient becomes a coefficient in the definition of the new helper variable.
wooden glen
If it had been =4 instead of =1, we would end up with 1t+0u=4, since the right-hand side is unaffected by all the variable-changing. The nonzero coefficient in the last equation is always the gcd of the two original coefficients, so whether the final equation can be solved depends on whether the RHS is a multiple of that -- but if it can, that's just an easy final division.
(For example, if the original equation had been 141x+90y=4, we'd end with 3t+0u=4, which tells us that 141x+90y=4 has no integer solution).
vernal ibex
If you're comfortable with symbolic algebra, it can help with seeing the big pic...
I will read this.
Wow that is a lot of variables lmao 💀.
Hmmmm.
I see.
vernal ibex
If it had been =4 instead of =1, we would end up with 1t+0u=4, since the right-h...
Oohh.
I feel you could express some of this with Modular Arithmetic.
vernal ibex
(For example, if the original equation had been 141x+90y=4, we'd end with 3t+0u=...
Like this.
sacred junco
Yes! As troposphere pointed out, the Euclidean algorithm is intertwined with the idea to finding solutions to linear Diophantine equations
Specifically those in the form ax+by=d
Where d=gcd(a,b)
We can also say ax = d (mod b), or by = d (mod a)
livid birch
isn't that just Bezout's Identity you're referring to then
sacred junco
Like this.
It's very common that working in mod arithmetic you want to find the inverse of an element in the group of units.
So we want to find some x so that ax=1 (mod b)
This is the same as finding some x and y where ax=1-by, or ax+by=1
vernal ibex
Yes! As troposphere pointed out, the Euclidean algorithm is intertwined with the...
I see.
Woahhh yessssss.
vernal ibex
isn't that just Bezout's Identity you're referring to then
Kinda
vernal ibex
It's all linked
YESSSSssss siree.
vernal ibex
It's very common that working in mod arithmetic you want to find the inverse of ...
I see.
I see.
sacred junco
Shamir's method is cool
regal cloud
im genuinely lost on this question
any guidance would be appreciated
i have tried via bezouts lemma but havent managed to spot something
torn escarp
might be helpful to just focus on a single prime power divisor
sacred junco
Woah that posted really small sorry, I'll just send the link
How does selecting some S in the authorized range guarantee the product of any k of those ms will be greater than S?
Wait, the smallest k of them are bigger than the product of the k-1 biggest ones so you always be mod something S will be fine in, since S will be less than that stuff
That's pretty clever
It's called we share a little secret 🕵️
I think what confused me is, why have the lower bound part of the range? Having any k of them multiply to something greater than S is enough to recover S, right?
Does making S large specifically in that manner add more security or something?
sacred junco
Wait I think I figured it out. If it's in the range, then mod any product of k-1 pieces you lose what S is, guaranteed, it gets reduced
Asmuth-Bloom is much better buch even a basic Mignotte scheme does this
So just for myself to remember, you need the upper bound to make S recoverable by any k pieces, and the lower bound to make S unrecoverable by any k-1 pieces
wooden glen
Even if S might be small, there's no obvious way k-1 conspirators could know that the small solution they recover by CRT is actually the original S. If the secret is chosen randomly and uniformly below the upper bound, I don't see that there's a particular problem with the risk that it might also land below the lower bound. It feels more like a pragmatic guard against a secret choice with low entropy that concentrates too much probability mass in a small interval.
E.g. if the upper end of the authorized range is only about twice the lower end, then the k-1 conspirators with the highest moduli could just add the product of their moduli to what the CRT tells them, and be sure they've found the only authorized secret consistent with their number.
(Hmm, that shouldn't be able to happen if the moduli are close to each other in magnitude, though).
sacred junco
Even if S _might_ be small, there's no obvious way k-1 conspirators could _know_...
I mean if S was originally less than the lower bound, which is a product of k-1 bois and now the k-1 conspirators have a unique solution mod that lower bound, so they have recovered S
I might be misinterpreting what you're saying sorry
But this convinces me that having both ends of this "authorized range" is necessary for the process of hiding S from k-1 or fewer fellas and recovering it with k or more
wooden glen
I mean if S was originally less than the lower bound, which is a product of k-1 ...
Only if the conspirators know that S was originally less than the lower bound. If the original S was random and the conspirators don't know whether it was small enough, then the solution they get from the CRT is just the smallest of many possible secrets that could have produced their numbers, and they have no particular reason to think this smallest candidate is more likely than any other of the candidates.
sacred junco
Oh I was assuming the scheme would be public
u right tho
But the thing you pointed out earlier about possibly choosing the sequence so that the authorized range is only like.. a few multiples worth of the lower bound long 
then k-1 fellas can rekk it by bruteforce after they get the solution reduced mod the lower bound
That makes sense to me as to why Asmuth-Bloom is preferrable
over Mignotte
cause you add a layer of obfuscation for free basically
wait I misread it 
it's a completely different thing you do with Asmuth-Bloom
wooden glen
Hmm, it looks like Asmuth-Bloom is more or less what you get if you try to fix up Mignotte by insisting that the secret be padded with enough unused randomness to avoid such shenanigans.
You just call the padding alpha and declare it to be part of the algorithm instead of depending on the guy who chooses S to do so with sufficient entropy.
sacred junco
I think I have figured out that actually I do not understand 
smoky palm
Do you think this is sufficient for proving there are infinitely many primes p=6n-1:
sterile pumiceBOT
Manix
analog sorrel
How do I prove that x! + y^2 = 987654 has no solutions in set of natural numbers
wooden glen
Do you think this is sufficient for proving there are infinitely many primes p=6...
What do the square brackets mean in the definition of N? And the star operator?
wooden glen
How do I prove that x! + y^2 = 987654 has no solutions in set of natural numbers
If x >= 10 then x! is too large for the RHS, so just check that 987654-x! is not a square for each x < 10 separately.
smoky palm
What do the square brackets mean in the definition of N? And the star operator?
multiplication and it's just N = 6 x 5 -1, N = 6 * 11 -1, ... N = 6*p-1
wooden glen
So N is a set of multiple numbers?
sterile pumiceBOT
Manix
smoky palm
ah wait, p>3 not p>=3
wooden glen
Are you saying N secretly depends on p?
smoky palm
n is odd and not divisible by 3
analog sorrel
If x >= 10 then x! is too large for the RHS, so just check that 987654-x! is not...
How do I check if number is square without using calculator?
wooden glen
Why would you want to do it without a calculator?
analog sorrel
I mean it shouldn't be hard I know that there are no solutions but I'm looking for a clever way to prove it. It has something to do with last digit.
wooden glen
How about: 987654==3 (mod 9) and 3 is not a square mod 9. That means that every x >= 6 is out. 3! and 4! are both 6 modulo 9, and 3-6 is not a square modulo 9 either, so we can exclude those. That only leaves 1!, 2!, 5! to check explicitly.
1! is excluded because 4-1! is not a square modulo 10.
Or we can just exclude 1!, 2!, 3!, 4!, 5! in one go by observing that 993² < 987654-5! < 987654 < 994².
urban sapphire
guys l have a problem with chinese junior math problem
triangleABC have 3 midline 、2018 2019 2020
what‘s its area
glacial python
that's quite the coincidental choice of years right
vernal ibex
Can every number in natural numbers be depicted as a multiple of sum or mix of product and addition of primes and 1?
Like 12 = 2×2×3.
And 18 = 2×3×3.
And 21 = 3×7.
And 8 = 3*2+3.
stuck shore
Can every number in natural numbers be depicted as a multiple of sum or mix of p...
Isn't this just the fundamental theorem of arithmetic
stuck shore
The number of Young diagrams gives you the addition version without the prime restriction
More descriptive https://yufeizhao.com/research/youngtab-hcmr.pdf
vernal ibex
Hello people can I get help with understanding Euclidean Algorithm to equations like 93x -27y = 6 or so? Like basically how the Algorithm works?
I understand that first we keep doing the quotient and remainder shortening.
But then after that we do some weird substitutions and stuff?
torn escarp
this might make it more confusing, but I'll try it anyways
when you do the euclidean algorithm, you're basically backtracking every step you made
vernal ibex
I see.
torn escarp
each step by itself basically gives us a simpler version of the same problem
vernal ibex
I see.
torn escarp
so if we just were to plug in one step instead after the first go, we'd have 93=3*27+12
vernal ibex
Yes.
torn escarp
so if you plug it in (don't do this usually) we'd have $(327+12)x -27y = 6$ and then we can rearrange it to make $$27(3x-y) + 12 x = 6$$ and then substitute $z=3x-y$ to get $27z+12x=6$
sterile pumiceBOT
Merosity
vernal ibex
Wait lemme show something.
torn escarp
this is now a similar type of problem but the coefficients have been reduced
vernal ibex
Like you understand how we got here.
So after the 3rd line I kinda lost it.
Can you explain from there?
torn escarp
the third line is the first line but solved for 3
vernal ibex
Ehhh what did they do after that?
torn escarp
then they take the 2nd line and plug in where 12 appears
they're "moving back up" to the original coefficients we broke down from
which were 93 and 27
torn escarp
that's why the 5th line they've combined the terms and left 27 and 93 alone in a sense they're like variables
vernal ibex
Okay so there in the brackets they apply 93 = 3 * 27 + 12?
But do we get 7 * 27 from 1 * 27 there?
The 1 * 93 term must be paired with the -2 term.
torn escarp
you distribute the -2 and have 6*27
vernal ibex
What?
torn escarp
vernal ibex
Oh.
torn escarp
that makes $127 - 293 +6*27$ yeah
sterile pumiceBOT
Merosity
torn escarp
haha
vernal ibex
SUcH CLEVER MANIPULATIONS.
BROOOOOO THEY SOOOO PROOOOOOO.
And you automatically understood it.
GENIUSSSSS.
HOWWWWW.
torn escarp
well you're taking a good first step, struggling at it and appreciating it when you finally see is really how you make it memorable and some of their tricks start to rub off on you
vernal ibex
YESS!
torn escarp
haha
vernal ibex
How
can
I
be
like that
Literally this is GENIUS and simpleeeee at the same time like WOOOOOOOOOOOOAHHHHHH DUDEEEEEEEE.
Okay so we.
First break the remainders down.
torn escarp
yeah, that's what makes it fun and interesting haha
vernal ibex
Then we do some pairing which makes some sense.
And how to pair correctly? How to know that?
Wait no.
That is just common sense and experience.
SUCH LIT MANIPULATIONS.
MATHEMATICS IS TRULY COOL.
torn escarp
yeah, work a few more examples and it wil become more clear what's happening
torn escarp
You're welcome 😎
vernal ibex
You are cool bro 
.
I look up to you .
Also.
You have p-adics stuff in your website !
What is the exponent lemma?
torn escarp
haha nothing substantial, I just threw up some test stuff to see if I could get things working, I wouldn't look there yet
vernal ibex
Yeah.
Oohh so you are involved with Number Theory a lot .
Also can I ask why you choose Chemistry Major instead of Mathematics major 
.
vernal ibex
Ah alright.
torn escarp
there are more solutions
and it's actually pretty easy to get those
you can think of it as just solving ax+by=0
if x_0 and y_0 are solutions then if you find a solution to this, adding it on won't change it
so you can add all multiples of this
specifically suppose you have $ax_0+by_0=d$ with $ax_1+by_1=0$
sterile pumiceBOT
Merosity
vernal ibex
there are more solutions
Yes.
vernal ibex
you can think of it as just solving ax+by=0
Oohh.
vernal ibex
and it's actually pretty easy to get those
torn escarp
then $x=x_0+kx_1$ and $y=y_0+ky_1$ are solutions
sterile pumiceBOT
Merosity
vernal ibex
.
torn escarp
ok so in our problem let's solve ax+by=0
vernal ibex
Okay.
What is that in our problem?
Like see.
How do we know that x = -4 -9k and y = -14 -31k is what needs to be solved?
torn escarp
93x -27y = 0
vernal ibex
0?!!? Not 6?!!?
vernal ibex
Oh no the main problem was 93x -27 = 6.
vernal ibex
so first off let's divide out their gcd
Okayyy.
torn escarp
since adding this pair to our solution (x_0, y_0) doesn't change anything
torn escarp
divide through by 3 we have 31x-9y=0
we have a very simple solution here we just have to flip the numbers and change the sign on one
$319-931=0$
vernal ibex
divide through by 3 we have 31x-9y=0
= 2, right?
sterile pumiceBOT
Merosity
vernal ibex
How?!!?
vernal ibex
Okay.
torn escarp
we're solving a slightly different problem
vernal ibex
Sorry for being dumb 😔.
torn escarp
you'll see why in a bit
vernal ibex
we're solving a slightly different problem
Oh alright.
torn escarp
93x -27y = 0 is what we're solving
torn escarp
31x-9y=0
vernal ibex
Yes.
torn escarp
so now we can just notice the very simple solution, (9,31)
torn escarp
but this isn't the only solution here
vernal ibex
2*(9,31) is also a solution to 31x-9y=0
Yes.
torn escarp
all multiples of (9,31) will be
vernal ibex
Actually every multiply of (9,31) I think.
vernal ibex
all multiples of (9,31) will be
Yess.
torn escarp
yeah good
vernal ibex
So now we have an equation.
torn escarp
so now you take your solution to the original problem, (-4,-14) and add all multiples
vernal ibex
For the solution.
torn escarp
(-4,-14) + n*(9,31) will be a solution
vernal ibex
so now you take your solution to the original problem, (-4,-14) and add all mult...
Hmmm?
Mutliples of (9,31)??
vernal ibex
*2 numbers in bracket with coma is not equal to G.C.D.
vernal ibex
plug this in and see what you get
Hmm okay.
IT IS A SOLUTION FOR n = 1!!!!
Ahaaaaa.
torn escarp
it's a solution for all integer n
torn escarp
yeah, so what's going on here, why is that
vernal ibex
We always find the solution for the equation = 0 instead of the constant????
torn escarp
by finding the solution to 0 we're adding on numbers that don't affect the solution we already have
vernal ibex
I see.
So.
Basically.
For a question like this.
First we find a pair of solution for the given constant with the exact given equation by doing all the manipulations and Euclid's Algorithms and stuff.
Then we find solution for the equation = 0 instead of the given constant.
Then the solution found in the first step + n*(a solution for 0) is all the solutions?
Is that it?
torn escarp
yeah
torn escarp
yeah, that's it
torn escarp
they did what I did basically just took a shortcut since they already knew
vernal ibex
Oh.
torn escarp
they divided by the gcd and put a constant, same exact solution
vernal ibex
So what is the x = -4 -9k and y = -14 -31k?!!?
torn escarp
(-4,-14) + n*(9,31) will be a solution
that's what I put here
I just wrote it in vectors
vernal ibex
Yess.
OOOOOHHHHHHH.
So both do they same thing and both are always same and accurate ?
torn escarp
yes
they just didn't explain what they did to get those numbers they just put them in
really you're just looking at 93x -27y and thinking "How do I make 0?"
vernal ibex
Yes they often do that 😔.
vernal ibex
really you're just looking at 93x -27y and thinking "How do I make 0?"
Looks easy lol.
torn escarp
well you factor out their gcd and then make one negative of the other to cancel out
vernal ibex
But both the methods look different lol.
Wait.
You divided by 3 because it was the GCD.
OOOOOOOOO.
So both are pretty same.
torn escarp
93x -27y = 3(31x-9y) now you pick x=9 and y=31
vernal ibex
Ahaaaaaaaa.
torn escarp
if you don't factor out the gcd you'll be skipping solutions
torn escarp
yeah
they just directly take the coefficients and change the sign on one of them and divide by the gcd
that's exactly what I'm doing
vernal ibex
BOIIIII AIN'T THIS COOOOOOOOOL.
vernal ibex
Number Theory cool .
torn escarp
what do you pick for x and y
vernal ibex
x = 1/5, y = 1/3.
torn escarp
nope, never want to divide
vernal ibex
Ah.
torn escarp
cause we are only looking at integer solutions
vernal ibex
Oohh yes.
torn escarp
also that would make 2 not 0
vernal ibex
Oh shoot.
torn escarp
let's fix that part first, I'll let you use fractions for the moment
vernal ibex
x = 0, y = 0 then lmfao.
torn escarp
heh
vernal ibex
But no that is a bad solution.
torn escarp
that's good, yeah we want a nontrivial solution
it's always a good idea though in number theory or math in general to find the easy solutions though too
it's easy to forget haha
what I had in mind was, x=1/5 and y=-1/3 would work
you see how that fixes it, if we were to use fractions
vernal ibex
it's always a good idea though in number theory or math in general to find the e...
Oh.
Yes.
Then it would be 1 and -1.
So 0.
But Fractions not allowed.
AAAA.
torn escarp
ok so now can we change this into an integer solution?
check this out, let's say $x_0$ and $y_0$ is a solution then is $kx_0$ and $ky_0$ a solution?
sterile pumiceBOT
Merosity
vernal ibex
Hmmm.
torn escarp
$$5(kx_0) + 3(ky_0) = k * (5x_0+3y_0) = k*0 = 0$$
sterile pumiceBOT
Merosity
torn escarp
so what should we multiply by to turn your solution into an integer solution?
vernal ibex
torn escarp
x=1/5 and y=-1/3 is a solution
vernal ibex
Yes but not in Z.
torn escarp
but I just showed you you can multiply it by a number and still have a solution
vernal ibex
Yes.
.
torn escarp
what number can you multiply 1/5 and -1/3 by to get an integer?
vernal ibex
Let me try to revise what we did in the last problem.
vernal ibex
what number can you multiply 1/5 and -1/3 by to get an integer?
(5,-3) and their multiples.
vernal ibex
Huh.
torn escarp
that you can multiply 1/5 by and you can multiply -1/3 by
vernal ibex
torn escarp
good do the same for y, and tell me what is our new pair of x and y
vernal ibex
(3,-5).
torn escarp
ah ok perfect
torn escarp
this isn't the path you want to take normally to get to the solution, but I think it's good to be able to know how to maneuver around
cause you had come up with a rational solution on your own, we just needed to play with it a bit to make it work for us
torn escarp
so now looking at 5x+3y if we want to make it 0 we can see we need 5(-3)+3(5)=0 which is sorta flip-flopping stuff around here
vernal ibex
The absolute values of both the number's sum should be their LCM?!!? Is it like that?!!?
Wait no.
LCM * 2.
vernal ibex
so now looking at 5x+3y if we want to make it 0 we can see we need 5(-3)+3(5)=0 ...
But it is a correct system.
torn escarp
I don't see where you're getting this from
vernal ibex
And the multiples of that system are all the multiples right?
torn escarp
these are all the pairs that make 0 yep
vernal ibex
I don't see where you're getting this from
Let me first think about what I mean to see if it makes sense.
torn escarp
in general you don't want to do anything with fractions
torn escarp
I'll give another similar example for you to try, 7x+11y=0 what should I pick for x,y
torn escarp
I think it may not apply for every case.
right now we're just looking at cases when the coefficients are relatively prime so you're not confused by extra stuff
one step at a time
torn escarp
oh, no that won't be useful here
vernal ibex
oh, no that won't be useful here
But still, is it true?
vernal ibex
I'll give another similar example for you to try, 7x+11y=0 what should I pick fo...
(-11,7).
vernal ibex
Or (11,-7).
torn escarp
But still, is it true?
maybe try to think about that and answer it yourself later
vernal ibex
maybe try to think about that and answer it yourself later
YESS!!!!
Certainly need to do that.
torn escarp
ok so let's do a more general example
or actually, one last easy example then we'll go on
-2x+13y
vernal ibex
I bet someone would have definitely discovered this before but if they have not then I made something new and possible useful 
.
torn escarp
make thi s0
vernal ibex
(13,2).
torn escarp
yeah good, ok so now let's try making it more complicated more like the one you were given
torn escarp
we want the simplest solution where all multiples give us all solutions
vernal ibex
Bro Mero you are a great teacher.
torn escarp
4x+6y
vernal ibex
we want the simplest solution where all multiples give us all solutions
Yes.
torn escarp
vernal ibex
(6,-4).
vernal ibex
<:catshrug:563818735085944843>
xD.
torn escarp
it would seem that way at first but there are more solutions than this
torn escarp
there are solutions which are not multiples of this that make it 0
torn escarp
yeah, good catch
torn escarp
you can divide in your answer directly actually
vernal ibex
Multiples of this I guess.
vernal ibex
you can divide in your answer directly actually
Ooooh.
vernal ibex
So all multiples of (3,-2) is the answer?
torn escarp
yeah
torn escarp
move?
torn escarp
yeah, I'm done I think with the lesson for today
vernal ibex
I hope not.
torn escarp
main thing is just to remember how useful it is to work through a bunch of examples
vernal ibex
Let me revise the problem.
Will ask for doubts.
Thank you very much for your help today Merosity 🙇!!!!
torn escarp
you're welcome
vernal ibex
I hope you can help me more with further doubts!
torn escarp
yeah maybe, but figuring out your own doubts and misconceptions is good too, builds character 😛
being stuck on something and overcoming it is part of what makes math rewarding I think
vernal ibex
yeah maybe, but figuring out your own doubts and misconceptions is good too, bui...
Yeah after that if I can not lol.
vernal ibex
being stuck on something and overcoming it is part of what makes math rewarding ...
Yes I guess 😌.
vernal ibex
Okay so I wanted to know whether there is this theorem.
It is hard to describe what.
vernal ibex
|5(-3)|+|3(5)| = 30 = 2(15) = 2 L.C.M.
But a Theorem which says that this done to 2 such numbers(5 and 3 here, respectively, from each term) is twice their LCM?
How would I state it?
vernal ibex
Ah.
Hmmm seems that it is a actually true for this case.
2x + 6y.
1 pair of solutions is (-3,1).
|-3|+|1| = 3.
3 × 2 = 6.
Wait what did I say.
Yeah so I was correct here.
Oh fuck.
I myself am confused.
So it is not twice LCM but LCM.
So Slim you are not a meanie after all 
.
Okay so is it x × LCM, x being an integer.
Or not even that?
Yeah.
So now it is super basic and hence a corollary of some well known theorem I guess.
glacial python
Is there a name for and anything special with integers of the form $A = p_1^{e_1}...p_r^{e_r}$ where $gcd(n, e_1, ..., e_r) = 1$?
sterile pumiceBOT
CelesteCrow
sacred junco
What's n? Just some other integer independent of the other stuff otherwise?
tough matrix
How would I go about solving this:
p,q are prime and pq+1 is a square number. Find |p-q|
I managed to show that |p-q| = 2 mod 4 and I found some solutions by hand (3,5) (5,7) (11,13) which makes me think the answer might be 2
lone forge
For any two numbers, (n)(n+2)=(n+1)²-1.
So yes, 2 indeed.
So that holds true for all prime numbers with a difference two as well.
tough matrix
Oh....... I approached it wrong completely. Thanks!
I should've verified it worked for non primes too
lone forge
You're welcome.
lone forge
I should've verified it worked for non primes too
Yes.
wise badge
Let p ∈ N be an odd prime and let a, b, c ∈ Z (integers). Show that if p does not divide ab, then the congruence ax^2+by^2 ≡ c mod p has solutions.
Could someone help me with this q?
I guess from start, p does not divide ab then p does not divide a and p does not divide b and so hcf(p,a) and hcf(p,b) are both equal to 1.
The congruence tells me that p | ax^2 + by^2 - c thus, ax^2 + by^2 - c = pk for some k in Z. So i need to show there exist x and y st that eq is satisfied^?
I am not sure how to solve this
leaden swan
@wise badge I think the plan is to solve ax+by=c and then find x and y such that both re quadratic residues
sacred junco
If I want to find every possible remainder when dividing by n, I just have to find remainders when dividing n consecutive integers by n? for example, for n = 8, i find remainders for -4, -3, -2, -1, 0, 1, 2, 3.
is that true?
oak sluice
sure
take the list of numbers 0, 1, 2, ..., n - 1. obviously their remainders are 0, 1, ..., n - 1. now add 1 to every number in that list, and see what happens to the list of remainders.
now do the same with subtracting 1 from the original list.
and in general, prove that if you add k, for any k in Z, the list of remainders is just a rotation (by k) of 0, 1, ..., n - 1.
sacred junco
thanks :)))
sacred junco
If $a_1\equiv x\pmod n$, $a_2\equiv x\pmod n, \dots a_k\equiv x\pmod n,$ can we deduce $a_1 \cdot a_2 \cdot \dots a_k\equiv x^{k}\pmod n$?
sterile pumiceBOT
mate
stiff rivet
yes
in general a = b mod n and c = d mod n implies ac = bd mod n
then extend to finite products with induction and yours is a special case
sacred junco
thank you :)
sacred junco
If $a\equiv b\pmod n$, is $x^{a}\equiv x^{b}\pmod n (a, b, n, x \in \bN)?$
sterile pumiceBOT
mate
stiff rivet
no
1 = 4 mod 3, but 2^1 = 2 != 1 = 2^4 mod 3
if you know eulers theorem, you can find the correct version of this statement
sacred junco
if you know eulers theorem, you can find the correct version of this statement
hm, im not sure what are you trying to say?
sterile pumiceBOT
Lochverstärker
stiff rivet
one can use this to reduce exponents in a congruence modulo n
sacred junco
For example $4^{16} \equiv 1 \pmod{17}$ and $4^{35} \equiv 4^3 \pmod{17}$ because $35 \equiv 3 \pmod{16}$?
sterile pumiceBOT
mate
sacred junco
oh nevermind im using fermats little theorem
sacred junco
so fermats little theorem is a special case of eulers theorem?
stiff rivet
yes
sacred junco
thank you very much :)
frigid path
- Prove that the sum
\begin{center}$1^k + 2^k + 3^k + \cdots + n^k$\end{center}
where $n$ is an arbitrary integer and $k$ is odd, is divisible by $1 + 2 + \cdots + n$
sterile pumiceBOT
dEePaNu
hollow kestrel
1 + 2 + 3 + .... + n = n(n+1)/2
frigid path
yep
hollow kestrel
u can do something similiar for the k case
frigid path
yep faulhaber
frigid path
ya faulhaber formula could be used
but it's too complicated
what about girard formula
shrewd lake
Hi, hiii
So is there a method to find the sum of the digits of 43¹⁰⁰ for example
Or 2³⁴⁵
Except the Sigma logarithm formula
sacred junco
Can we tell $3^5 \equiv 5 \pmod{7}$ without dividing 3^5 by 7?
sterile pumiceBOT
mate
Compile Error! Click the 
reaction for more information.
(You may edit your message to recompile.)
stiff rivet
yes
a computer will never divide anything
because it is computationally expensive
oh well i guess it depends what you mean by division
a computer will still do euclidean division (which does not perform any actual division)
so if that is fine, you can just compute 3^5 and then do euclidean division (or to be more computationally efficient, compute 3*3, reduce, multiply by 3, ...)
sacred junco
thank you. so still you have to compute it somehow (its not obvious like, for example, 3^6 = 1 mod 7)?
stiff rivet
hmm
if you know that 3 is a primitive root modulo 7 and use what you said, you know that 3^5 must be multiplicative inverse of 3 modulo 7
then you still have to calculate that, but its less work
but yeah, i dont think you can "just see" it immediately
stiff rivet
if you know that 3 is a primitive root modulo 7 and use what you said, you know ...
this can be verified by mental arithmetic
sacred junco
but yeah, i dont think you can "just see" it immediately
thanks :)
leaden swan
How do you find a non trivial x satisfying x^3=1 mod p^2? Where p is a prime
wooden glen
You can rewrite to (x²+x+1)(x-1) == 0 (mod p²). Since arithmetic modulo p² has zero divisors, a special case arises if we can satisfy x²+x+1=0 and x=1 simultaneously modulo p, which is the case for p=3 only. So in that case we have additional solutions 4 and 7.
In general, though, a nontrivial solution must satisfy x²+x+1 == 0 (mod p²). This is impossible for p=2, but otherwise we can complete the square and get (2x+1)² == -3 (mod p²) so you're now looking for square roots rather than cube roots.
wooden glen
It is enough to find a square root of -3 modulo p, because if a² = np - 3 for some n, then a bit of algebra will find you an m such that (a+mp)² == -3 (mod p²).
For p>3, quadratic reciprocity says that a square root of -3 exists iff p == 1 (mod 3) -- but that doesn't directly help with finding the square root. However, trial and error should go faster when we only need to work modulo p rather than modulo p².
wise badge
if x is an element of (Z/nZ)*(only containing elements that have multiplicative inverses), does that mean that x does not divide n?
wooden glen
Not necessarily -- x can always be 1, for example, and 1 divides everything.
swift shard
@tough birch
I don't really know if there's a proof to be had here. That's how we define [], no?
What's your definition of []?
tough birch
<@698387745864941658>
I don't really know if there's a proof to be had here. Th...
my definition is (TBD)
how do we write latex in this discord
never mind I think I figured it out
if $a \equiv b \pmod{m}$, then $(a, b) \in R$
sterile pumiceBOT
gtstudent
tough birch
We want to show set equality
Because $R$ is an equivalence relation, it follows the reflexive property. If $(a, b) \in R$, then $(b, a) \in R$. Assume some arbitrary $c$ in $[a]$. The definition of $[a]$ is ${q: a \sim q}$. This means that we have $(a, c) \in R$ and $(b, a) \in R$. By the transitive property, this means we have $(b, c) \in R$. By definition of $[b]$, we know that c is also in R. We can make a similar argument to show the other inclusion.
Now if we know that $[a] = [b] = C$. By definition of [a] and the fact that $R$ is reflexive, $a \in C$. By the same logic, $b \in C$. This means that $b \in [a]$. By definition of $[a] $, (a, b) is in R. All the coordinate pairs in the relation satisfy the fact that $a \equiv b \pmod{m}$
boom
sterile pumiceBOT
gtstudent
sacred junco
please hurry
wind glacier
please hurry
4
flint lintel
hello
i need help reviewing modular arithmetic
i was watching a video on youtube about modular arithmetic and the person showed this example
its on the left
how do you figure this out again
its been a few months since i studied this material
10a \equiv -2 \pmod{4}$
i dont know if that worked lol 🤣
sacred junco
i have to find 11^9 mod 17, how to do it (without a calculator)?
wooden glen
Square it three times (reducing mod 17 each time) to get 11^8, then multiply with 11.
Goes even faster if you remember that the square of a number is the same as the square of its negative, so when you're working mod 17 you have, 9²=8² and 10²=7² and 11²=6², etc.
So remembering just the multiples of 17 that are smaller than 64 is enough to do the reductions along the way.
sacred junco
thank you very much. sorry i am a beginner, could you try to explain again? :(( 1. what do you mean by square 3 times and reduce mod 17? and what is a negative?
wooden glen
Square, then square again, then square once more.
This gives you first 11^2, then 11^4 and then 11^8.
You know about negative numbers, right? The negative of 23 is -23 and vice versa ...
wooden glen
Why suddenly mod 27?
sacred junco
i edited sorry
wooden glen
Because if you square it theree times you'll get 11^8, and multiplying that with another 11 gives you 11^9.
You could also just start with 11 and keep multiplying by 11 over and over until you reach 11^9, but that will be more work.
sacred junco
So 11 = 11 mod 17
11^2 = 11^2 mod 17
...
11^8 = 11^8 mod 17
11^9 = 11^8 * 11 mod 17
sorry this probably isnt what you are trying to say but im stuck
wooden glen
All of that is true, but the first three of those only say that an expression equals itself ...
sacred junco
sorry seems like i dont understand your method.
wooden glen
Try it out! What is 11^2 mod 17?
sacred junco
oh i understand!!!
thank you very much
11^2 = 2 mod 17
so
11^9 = 2^4 * 11 = 176 = 6 mod 17
and also we could calculate 6^2 = 11^2 mod 17 because 6+11 = 17?
wooden glen
Yes, exactly.
sacred junco
Yes, exactly.
one more question
it is not true that a^n = b^n mod (a+b) if n > 2?
flint lintel
can I ask you guys a question
wooden glen
It holds when n is even in general.
flint lintel
Is this class an undergraduate class?
sacred junco
It holds when n is even in general.
thanks :):)
wooden glen
This is a chat, not a class.
flint lintel
I’m saying elementary number theory
In general
Is it an undergraduate course
Or no?
wooden glen
Probably varies between universities. It's a big world. ¯_(ツ)_/¯
flint lintel
Do I need to know some abstract algebra material?
Or no?
Before taking this course
silver knoll
heyo
sacred junco
how to solve 4^2015 mod 6?
oh i realize 4^n mod 6 is 4. why is that?
is it just a coincidence?
sacred junco
I mean when you multiply 4 by itself its basically 4*(3+1) = 12 + 4
sacred junco
mero 
wooden glen
oh i realize 4^n mod 6 is 4. why is that?
One way you can dignify it a bit is to use the Chinese remainder theorem. The value of (some expression) modulo 6 is uniquely determined by its value modulo 2 and its value modulo 3, so you just need to see that 4^n == 4 (mod 2) and 4^n == 4 (mod 3). But that reduces to 0^n == 0 (mod 2) and 1^n == 1 (mod 3), which are both obvious.
(Oh. Merosity already said that, but then deleted it after the bot processed it).
sacred junco
thanks :) unfortunately i didnt really understand (i am a beginner and we didnt mention chinese remainder theorem) but its okay. i will remember 4^n = 4 mod 6
wise badge
how would i answer this question?
torn escarp
do you know what the order of the roots of that cyclotomic polynomial are? Do you know the order of 2?
wise badge
do you know what the order of the roots of that cyclotomic polynomial are? Do yo...
in F_29, since 2 is a primitive root and 29 is prime, 2 has order 28? i am not sure about the 1st question
torn escarp
well what are the roots of cyclotomic polynomials
what is a cyclotomic polynomial
for instance, what is $\Phi_4(X)$?
sterile pumiceBOT
Merosity
wise badge
it is a polynomial whose roots are the primitive roots of the nth roots of unity
torn escarp
yeah perfect
so if you take a root of $\Phi_7(X)$, let's call it $r$, what power do you raise it to in order to get 1?
sterile pumiceBOT
Merosity
wise badge
if is a primitive root then its order equal to the order of the group consisting of the nth roots of unity (because it generates all of it) so 7?
wise badge
@torn escarp
wise stratus
oh i realize 4^n mod 6 is 4. why is that?
hi sorry this is a rly late response but ^_^ CRT is a fine way of doing it, but for this specific one you can note that 4^2=16, which is congruent to 4 (mod 6). That this will then hold for higher powers follows inductively
sacred junco
thanks got it :)
sacred junco
if a^b = x mod n, can i tell anything about a^(b-1) mod n
torn escarp
you know that a * a^(b-1) = x mod n heh
formal minnow
jolly mural
sacred junco
Let $p$ be a prime $\geq 7$. Prove $p$ divides $\underbrace{111\dots111}{\text{p - 1 digits}}.$
My attempt: $111\dots111 = 10^{p-2} + 10^{p-3} + ... + 10^0$ and $10^{p-1} \equiv 1 \pmod{p}$. But I am stuck here.
sterile pumiceBOT
mate
torn escarp
Let $p$ be a prime $\geq 7$. Prove $p$ divides $\underbrace{111\dots111}{\text{p...
hint: the sum is a geometric series
sacred junco
So it is (10^(p-1)-1)/9?
torn escarp
yeah good
sacred junco
sorry still stuck
torn escarp
try to simplify it mod p
torn escarp
write it as 9^-1 if that helps
sacred junco
write it as 9^-1 if that helps
so (10^(p-1)-1)/9 = (1-1)/9 = 0/9 = 0 mod p
is that correct?
im confused because 9^(-1) is not an integer
torn escarp
it's fine, all that matters is that 9 is invertible mod p, specifically that 9 != 0 mod p
$$9^{-1}*(10^{p-1}-1) = 9^{-1} * 0 = 0 \mod p$$
sterile pumiceBOT
Merosity
torn escarp
it just means 5 is the number you multiply 9 by to make 1 mod 11
because we already know $\frac{10^{p-1}-1}{9}$ is an integer, we don't have to worry about the fact that 1/9 on its own isn't an integer
sterile pumiceBOT
Merosity
sacred junco
thank you so much. one more question: when we write 9^-1 in modular arithmetic, does that represent 1/9 = 0.111... or? i now understand why 9^(-1) = 5 mod 11 but dont see how 0.111 * 5 = 1 mod 11
torn escarp
oh no these are different things
when we write $9^{-1}=5 \mod 11$ you can think of this as really saying
sterile pumiceBOT
Merosity
torn escarp
$$9*x =1 \mod 11$$
sterile pumiceBOT
Merosity
torn escarp
what integer can we multiply by 9 to make 1 mod 11?
that's the inverse in modular arithmetic
it's similar to how normally we say with real numbers 2^-1 we just write .5 or 1/2 because that's what we can multiply by 2 to make 1 there
you have to think of doing math with real numbers as separate from how you do math with modular arithmetic numbers, basically
wooden glen
The fully honest way to write it would be something like $$[9]^{-1} = [5]$$ (after we're agreed that the square brackets create congruence classes modulo 11)
which is basically how to interpret the "...... (mod 11)" notation: You're supposed to mentally insert brackets about all of the concrete numbers in the ".....".
sterile pumiceBOT
Troposphere
sacred junco
thanks merosity for all your help. however im confused because our sum contains 1/9 = 0.1111... then we rewrite it as 9^(-1) and then it becomes 9. i dont really understand why we can do that
sacred junco
which is basically how to interpret the "...... (mod 11)" notation: You're suppo...
does this represent equivalence classes
wooden glen
Yes, congruence classes are a special case of equivalence classes.
sacred junco
thanks Troposphere :)
vernal ibex
Can someone explain please?
@harsh solstice.
I will show another example.
@junior haven.
sacred junco
Have to find 6^2015 mod 30. I see its 6 , but am not sure how to expain it.
30 = 3 * 10, is that related?
or that is a property of 6?
(6^n mod 30 is always 6)
modest kestrel
So basically the lecturer used trial and error to find one of the primitive roots in F_7* . Since it is a primitive it generates the entirety of F_7* and so we can express each element in the group with powers of 3, which i understand. Then we need to find other elements in the group which have order 6, and when we talk about element in the group we can talk about powers of 3. Could someone, however, help me understand why hcf(k,6) = 1 imply that 3^k has order 6 and therefore is a primitive root.
stiff rivet
try to determine the order of 3^k, i.e. when is (3^k)^l = 1
modest kestrel
kl should be a multiple of 6 for power of 3 to equal to 1, so kl = 6m (for some m in N)? so order 3^k should be 6m/k?
stiff rivet
what happens to l
your end goal is showing l = 6
i would probably think of this in terms of prime factorizations:|| if hcf(k, 6) = 1, then the prime factorization of k does not include 2 or 3, so those must appear in l||
vernal ibex
Can someone explain please?
@sacred junco @low oasis.
vernal ibex
@sacred junco @low oasis.
low oasis
Oh those mfs
vernal ibex
low oasis
I think I can remember how to do it if all the mods are coprime
vernal ibex
Then it is easy I suppose.
sacred junco
Where in the solution are you struggling/whats the context?
sacred junco
looks like when you want to solve x = a +bn = c +dm for set a,b,c,d you want in general to look at mod n and mod m I guess thats what theyre doing
vernal ibex
Uh that helps?
Well wait I will give quadratic congruences what help I want after like 10 minutes when chess class ends.
Actually.
sacred junco
well it helps in a way that you can reduce to one integer in the general solution and if you follow the calculations in the example you get general solution x = 11 +42k
vernal ibex
Maybe I need to get motivation to learn instead of just asking for help and mehhhhhhh.
I see?
low oasis
I’ll see if I can remember the algorithm one moment
vernal ibex
I am lazy for NT right now 
.
sacred junco
this is crt right?
vernal ibex
?
sacred junco
yeah
vernal ibex
CRT?
low oasis
Not sure how it works when they’re not co prime
I think you split one of the equations into two cases mod some factors of the original. Not sure though
sacred junco
I mean probably senku will have to do the coprime cases
the algorithm explained is pretty much crt
low oasis
No this is not that.
Yes, it is
One moment I’m writing down the method
Ok so let’s say you have two coprime cases with $x = a mod m$ and $x = b mod n$. We can use bezout’s lemma to find $t$ and $s$ such that $sm-tn = 1$. So we have that $x = atn+bsm$
This is the algorithm I found in my 2nd year number theory notes 
sterile pumiceBOT
Wew Lads Tbh
vernal ibex
Yes, it is
Well I have not studied it from the text and these are not under that section.
low oasis
And it’s the Chinese remainder theorem because if m and n are coprime (thus their ideals are disjoint) then we’re using the fact that R/I_1 x R/I_2 is isomorphic to R/(I_1 I_2)
Without this fact we might not have a unique solution, or a solution at all
Which is why the example in your notes fails, 10Z and 4Z are not disjoint
vernal ibex
Hm.
sacred junco
wew do yo uthink youre cool when you use the word ideal and isomorphic when explaining congruences to a 14 yo
low oasis
I mean, how else do you explain it
low oasis
I mean you don’t need to know that it’s the crt to solve the problems
It’s just an explanation of why it works
sacred junco
yeah Ik Ik
vernal ibex
wew do yo uthink youre cool when you use the word ideal and isomorphic when expl...
He does.
He flexes hard.
KEKW.
sacred junco
He has a pass he will be doing phd 
vernal ibex
https://tenor.com/view/cat-cat-stare-stare-animal-funny-gif-21869355
Oh no I tried to read what he wrote, then I decided I will read the book and try doing some myself while I DM you and Wew for doubts if I have and went off to game now.
low oasis
**Wew Lads Tbh**
Focus on this algorithm senku rather than the explanation of why it works
It will illuminate the path that you must walk
formal minnow
this is literally senku right now^
this but unironically
torn escarp
catfan
sacred junco
mero
sacred junco
im wondering if there's a way to prove a^2+1 has at least one prime divisor of the form 4k+1 without using law of quadratic reciprocity (we didnt start studying quadratic residues)
snow dirge
sacred junco
You guys are cool for doing number theory.
you can do it too 😄
steel pewter
you can do it too 😄
I can't tbh algebra is killing me
killing my interest I mean, if algebraic number theory is anything related to it
sacred junco
im wondering if there's a way to prove a^2+1 has at least one prime divisor of t...
I think gauss has 6 proofs of quadratic reciprocity
Maybe you can find a hint by looking at those?
sacred junco
found another way
altho should've mentioned a isn't any integer. a is 2.p1.p2...pk where pi's are primes of the form 4n+1 (assuming finitely many of them)
so i proved 4 is the order of a mod p and using fermat's theorem that implies 4|p-1
hollow zenith
Ok so I solved this directly
however the hint my professor gave said use contradiction
and I cannot for the life of me figure out a proof by contradiction
soooooo anyone got any ideas on how contradiction would work for this? It just seems so counter intuitive to do it by contradiction.
sacred junco
I gotchu
c | a+b so a+b = kc
We also have, wlog, assuming for sake of contradiction d = (a, c) > 1. Now
a+b = da' + b = kdc' -> b = kdc' - da' and now d | b boom @hollow zenith
to be clearer d | b and the initial assumption d | a of course means we contradict (a,b) = 1
sacred junco
u r lovely and gaming and very poggers
rugged moth
(joke) c|a+b means (a,b)|c => 1|c, now 1|a so (a,c)=1
fiery zenith
Let $a,b,c\in\bZ, (a,b)=1, c > 0$.\
Prove ($\exists x\in\bZ)((a+bx,c)=1)$.
sterile pumiceBOT
Shuri2060
fiery zenith
Hint please 🤔
I have
(a + bx, b) = 1
I've tried playing around with bezout
Uh... I'm just kinda stuck
wooden glen
One way forward I think would be to prove it for prime c first and then extend to c's with more prime factors by induction.
Actually, scratch induction. Extend to more prime factors by CRT.
Alternatively, sledgehammer the whole thing with Dirichlet's theorem. :-p
vernal ibex
Are Linear Congruences in Multiple(2+) congruences a special case of the Chinese Remainder Theorem?
ionic pier
@vernal ibex what is your question exactly
vernal ibex
Linear Equations in Multiple Equations(Congruences).
Are they solved using The Chinese Remained Theorem?
ionic pier
Oh, so you mean like a system of linear congruences?
vernal ibex
Yeah.
ionic pier
Not necesarrily
You could, but only if the modulae in the system are two by two coprime
So if you pick one of the modulae, it has to be coprime to every other modulus for it to be legal to use Chinese remainder theorem
For example if you have
$4x \equiv 3 (mod 5)$
$2x \equiv 1 (mod 6)$
$x \equiv 2 (mod 7)$
vernal ibex
You could, but only if the modulae in the system are two by two coprime
I see. But most of the times that is the case.
sterile pumiceBOT
DVD_Koce_DVD
vernal ibex
Hmmm.
ionic pier
Then you can use CRT , because (5, 6) = (5, 7) = (6, 7) = 1
ionic pier
But if the modulae were, say, 2, 3 and 4, then you cannot, since (2, 4) = 2
vernal ibex
I have not studied CRT yet but saw Linear Congruences in Multiple Systems before CRT.
vernal ibex
But if the modulae were, say, 2, 3 and 4, then you cannot, since (2, 4) = 2
So we just solve this using your normal Linear Congruences Method?
vernal ibex
Can someone explain please?
I.E., like this.
vernal ibex
Or this.
ionic pier
Well first of all it'd be great if you present them in the form $x \equiv a (mod ~n)$
sterile pumiceBOT
DVD_Koce_DVD
ionic pier
But you'll still be left with a bunch of congruences
So what you are talking about is gonna help you as much as expressing them in that form
There is an algorithm actually, which you can use to solve any system of linear congruences
vernal ibex
**DVD\_Koce\_DVD**
Yeah of course.
vernal ibex
There is an algorithm actually, which you can use to solve any system of linear ...
Can you please name it or tell me about it?
Would be very useful.
Ah after this I need to study Quadratic Congruences.
ionic pier
Lol they are generalised as congruences of higher order, but I'll dm you
vernal ibex
Cool.
stiff rivet
it might be worth noting that solving any congruence modulo some number n is a finite problem since there are only finitely many possibilities to try
so there is always a naive algorithm (just try every possibility)
the interesting part is coming up with better ways
to either tell if there is a solution at all and if there is to find that
ionic pier
Yes, but it becomes unpractical to check for numbers of order 10^1000 even with a computer 😆
vernal ibex
it might be worth noting that solving any congruence modulo some number n is a f...
Yes.
torn escarp
But if the modulae were, say, 2, 3 and 4, then you cannot, since (2, 4) = 2
@vernal ibex even in this case it's possible to use the CRT we just have to check that the overlap is compatible
since 2 is a proper divisor of 4 it's particularly easy in this case, suppose you have n=1 mod 2 and n=3 mod 4, since we can reduce n=3 mod 4 down to n=3 mod 2 and see this is equivalent to n=1 mod 2, we can throw out that requirement for mod 2
on the other hand if we had n=0 mod 2 and n=3 mod 4, they're incompatible so this means there's no solution at all and you can stop working entirely
vernal ibex
<@!723209758781472808> even in this case it's possible to use the CRT we just ha...
Hmmm.
vernal ibex
since 2 is a proper divisor of 4 it's particularly easy in this case, suppose yo...
Yes.
vernal ibex
on the other hand if we had n=0 mod 2 and n=3 mod 4, they're incompatible so thi...
Yeee.
Very well then, done with Linear Congruences pretty much.
Today Quadratic Consequences I guess.
*congruences.
vernal ibex
What is the proof that (m+1)^2 ||| (m-1)^2.
||| represents your congruent symbol, the 3 Horizontal lines.
And (m+2)^2 ||| (m-2)^2.
And so on.
(m+n)^2 ||| (m-n)^2.
formal minnow
the congruent symbol makes no sense if it’s not mod something?
keen marten
torn escarp
||| represents your congruent symbol, the 3 Horizontal lines.
please just put = lol
assuming you're talking mod m, since m=0 mod m, we're really looking at n^2 = (-n)^2 mod m, but since (-n)^2 = (-1)^2 * n^2, all you really need to see is that (-1)^2 = 1 mod m
daring barn
someone in my university posed this question, and I am curious to see an answer, but I dont like number theory enough to think about it too hard:
Let $n\in\mathbb{N}$. Let ${x_i}$ be a collection of positive integers, not necessary all distinct (distinct case is trivial) such that $\sum x_i = n$. Does $\Pi x_i , | , n!$?
sterile pumiceBOT
Migillope
wooden glen
Yes. One of the first x1 factors of n! is a multiple of x1. One of the next x2 factors of n! is a multiple of x2. One of the next x3 factors is a multiple of x3, and so forth.
daring barn
ordering n! from least to greatest?
wooden glen
Yes.
In fact, even $\prod_i x_i!$ divides $n!$; the quotient is the \emph{multinomial coefficient} $\binom{n}{x_1;x_2;\cdots;x_k}$.
sterile pumiceBOT
Troposphere
vernal ibex
assuming you're talking mod m, since m=0 mod m, we're really looking at n^2 = (-...
Oh wow I am dumb.
torn escarp
nah you're just learning
vernal ibex
(m+n)^2 ||| (m-n)^2.
What are you basically saying?
vernal ibex
@torn escarp.
torn escarp
I don't understand your question
mint peak
does everything divide 0? or does nothing divide 0?
sacred junco
does everything divide 0? or does nothing divide 0?
what do you think? 😄
(also don't forget the case of the other number being 0)
mint peak
if a|b, then ak = b for some k in Z. Here if b = 0, we have ak = 0, which is only true for k = 0, which is in Z... soo, yes? If a is 0, weird things happen right? that would probably be undefined
sacred junco
if a|b, then ak = b for some k in Z. Here if b = 0, we have ak = 0, which is onl...
yeah so every nonzero integer divides 0, and also we can say since 0 is a multiple of 0 that 0 divides 0 as well, but we have to remember that this is only in the context of integer division.
Basically there is an unfortunate distinction here between division, meaning divisors of integers, and division, as in business with multiplicative inverses
polar talon
so i'm trying to show that 3x^2 + 5y^2 = 4 has a rational solution and find said solution, i found a solution to legendres equation so there must be a rational point but i have no clue how to find the rational point
sacred junco
No clue but playing with around with the problem moved over to the integers (3x'^2 + 5y'^2 = 4z^2, z=lcm(xdenom, ydenom), x'=xz, y'=yz) you get examining mod 3 and 5 that x' is a multiple of 5, y' is a multiple of 3, and z is a multiple of 15.
Ah so then substituting and simplifying once again you get
5x''^2 + 3y''^2 = 60z'^2 (x'' = x'/5, y'' = y'/3, z'=z/15)
Examining in the same way, you get y'' is a multiple of 5, x'' is a multiple of 3
oh and holy shit
substituting once again and simplifying gives you a new equation 3x'''^2 + 5y'''^2 = 4z'^2, and these numbers are all entrywise less than the original triple (x',y',z) but satisfy the same equation
wait... doesn't this lead to infinite descent, at least for nonzero solutions?
grave carbon
So, with the phi function $\phi(n)$ that counts the number of elements in $[n]$ that's relatively prime to n, it seems like there's some Combinatorics going on involving counting the phi values of the prime factores of $n$. Does someone know what's happening here in a Combinatorics lens?
sterile pumiceBOT
beeswax
grave carbon
Perhaps some kind of inclusion-exclusion type of thing?
grave carbon
Just any n in general. So for example, take $$\phi(210).$$ We know that the prime factors of 210 are 2,3,5,7. I know that the value comes out to 48 using the theorems in Number Theory, but I just want to know how I can interpret this in terms of Combinatorics
sterile pumiceBOT
beeswax
sacred junco
For p^n there are p^(n-1) numbers between 1 and p ^n divisible by p
So phi(p^n)=p^n - p^(n-1)
I dont think there is any combinatorial proof besides counting the p^(n-1) divisors but thats barely combinatorics
But idk I suppose you knew that already
grave carbon
Yeah, the book used a counting argument for one of the theorems, so I wanted to see if I could interpret a more concrete example using combinatorics to understand it better
jovial bison
Can anyone give me a hint on this problem, please don’t reveal the solution:
$$ \sum_{k=0}^n \lfloor \sqrt k \rfloor $$
sterile pumiceBOT
Armani
jovial bison
I need to find a general formula for that summation using sqrt(n) and floor(sqrt(n))
wooden glen
Start by assuming n is the number just before a perfect square.
