elementary-number-theory

[tidal canopy]

I see

Thanks!

[wise oyster]

Am I crazy or are they not proving 1?

theyve shown a different statement

must be a typo in 1 right?

cause i was thinking that product doesnt even mean anything

[leaden swan]

The n in phi(n)?

Yea the 1. Part in proportion doesn't make any sense

[wise oyster]

yeah and in the proof of the other too they keep using this result so it must have been a typo

[light flicker]

I assume they just meant what they write in the end of the proof

[meager ore]

I am trying to get a sense of the intuition for why this is true, but it isn't clear to me. I considered an example where m = 7, n = 3, q = 2, and r = 1 and confirmed the result, and compared the gcd's of not subtracting 1 and subtracting 1, but that didn't reveal much to me. I don't have a sense for why subtracting 1 from each of the values in the equation would make the gcd's become equal.

[leaden swan]

r=gcd(m,n)?

[meager ore]

Is that the case in general?

If we're dealing with the division algorithm m = qn + r

[leaden swan]

Let gcd(x^n-1,x^r-1)=y
Let's say a(x^n-1)+b(x^r-1)=y for some a,b. Then, Note (x^m-1)-x^(m-n)(x^n-1)=x^(m-n)-1

Repeating that, we get x^r-1 can be written as a linear combination of x^m-1 and x^n-1

Which means, a(x^n-1)+b(x^m-1)=y for some a,b

That is gcd(x^n-1,x^m-1) divides y

[meager ore]

what motivated you to use x^r-1?

[leaden swan]

Well, That's your proposition

[meager ore]

oh, sorry, I misread the syntax was all

[leaden swan]

Similary you can show y divides gcd (x^n-1,x^m-1)

The Intuition as to why this works is that we can make an "euclidean algorithm" work for powers(ok,we use this proposition to establish that)

That is if a|gcd (m,n)
x^a-1 can be written as a linear combination of x^m-1 and x^n-1

[meager ore]

Is it typical to look to represent a number as a linear combination in order to show divisibility?

[leaden swan]

idts

Wait,You mean ax+by=c implies gcd(a,b) divides c?

If so, Kind of yes

[meager ore]

yes, I mean that. Because that is essentially the approach you took

I mean, it makes sense that if something divides a and b then it will divide c

I just never would have thought to use a linear combination

[leaden swan]

There are Basically 2 kinds of approaches in elementary number theory

1)Make a linear combination like what I did above

2. Prime Factorisation

[meager ore]

okay, noted. So, some clarifying questions: a, b are not necessarily constrained to the integers, correct?

[leaden swan]

Here,yes

[meager ore]

Ah, well if they are why do I know that the gcd will necessarily be able to be represented by such a linear combination of a(x^n - 1) + b(x^r - 1)?

[leaden swan]

You know the proof for why that can be done for natural numbers?

[meager ore]

No, I do not. To be clear, I don't have experience with elementary number theory.

[leaden swan]

The proof for why polynomials can be written that way is extremely similar

[meager ore]

Okay, so in the case of the natural numbers it would be a proof for why any natural number can be written as a linear combination of two other natural numbers?

[leaden swan]

Yes

I mean,it doesn't hold for N,it holds for Z

Because you obviously can't write 1 as a natural number combination of 7 and 3

[meager ore]

yes, that's true

[leaden swan]

But,1=7+(-2)3

[meager ore]

okay, I'll look into that. It makes sense to me, though because the only distinction really is that in one case I'm dealing with the integers themselves, in the polynomial case we're dealing with integers as polynomial coefficients, but it amounts to the same thing

[meager ore]

Now, the step following "then, note" is not clear to me, and also how "repeating" that note will lead us to the conclusion that x^r - 1 can be written as a linear combination of x^m - 1 and x^n - 1

[leaden swan]

Let's say m-n>n

Now do (x^{m-n}-1)-(x^{m-2n})(x^n-1)

You end up with x^{m-2n}-1

[meager ore]

I agree

But why are we using this construction? We could continue constructing x^{m-kn} - 1 in that sort of fashion

but where does that lead us?

[leaden swan]

This works as long as m-kn>n

Because we are multiplying (x^n-1) with x^(m-(k+1)n)

We can do that only as long as m-(k+1)n>=0

i.e., m-kn>n

So,after sufficient number of steps,you end up with x^{m-qn}-1

=x^r-1

[meager ore]

We can only keep doing this so long as >0 because these are supposed to represent natural numbers?

[leaden swan]

Polynomials can have only non negative powers

[meager ore]

Okay, so if I've understood correctly, we are applying this construction iteratively until we arrive at what would be the construction for x^r-1. And the fact that we know that we will eventually end up with x^r - 1 tells us that yes, we can represent x^r - 1 as a linear combination of x^m - 1 and x^n - 1

[leaden swan]

Yes

[meager ore]

Okay, so this makes sense, but can you elaborate on why we know that from m-kn > n implies that m-qn will equal r before necessarily becoming negative

I played with the equality a bit, but I'm probably forgetting some constraint on m and n

[leaden swan]

Remember how divison is defined?

[meager ore]

By the euclidean algorithm?

[leaden swan]

m=qn+r,if q>r>=0 ,q is the largest number such that m-qn>0

[meager ore]

Yes, I remember that

[leaden swan]

So,You reach x^(m-qn)-1 via this algorithm

Because m-(qn)>0,(m-(q-1)n)>0...(m-n)>0

where q is the largest such integer

Now m-nq=r by that condition

[meager ore]

Hm, so is the iterative process that we went through sort of like a euclidean algorithm for polynomials?

[leaden swan]

We are doing euclidean algorithm on a where x^a-1 is the polynomial

[meager ore]

Ah, I see

[leaden swan]

If you know Euclidean lemma, You can show this is true pretty easily

I am talking about given natural numbers a,b!=0
a=bq+r for some natural numbers q and r<q

[meager ore]

Okay

I'll do that

[leaden swan]

Another important hint is every nonempty subset of N has a minimum element

[meager ore]

Noted

Okay, well thanks for your help! I think I'm going to look over our discussion and try to summarize this in my head, but this process makes a lot more sense to me now

[meager ore]

Hey, I was reviewing this, and regarding the conclusion that x^r - 1 can be written as a linear combination, I am not clear on why we can regard (x^(n - (q - 1)n) - 1) - (x^(m - qn))*(x^n - 1) as a linear combination, simply because this is not the form of a linear combination.

[leaden swan]

You can rewrite $x^{m-(q-1)n}-1$ in terms of $x^{m-(q-2)n}-1$ and $x^n-1$

[sterile pumice]

DrunkenDrake

[leaden swan]

And $x^{m-(q-2)n}-1$ in terms of $x^{m-(q-3)n}-1$ and $x^n-1$

And so on

[sterile pumice]

DrunkenDrake

[leaden swan]

It's like if d=m b+ n c
and c=pa+qb
d can be written as a linear combination of a and b

A linear combination in R[x] of polynomials p(x) and q(x)
is m(x)=a(x)p(x)+b(x)q(x) for some polynomials a,b

[meager ore]

Ah, I was thinking of linear combinations along the lines of a_1*x_1 + a_2*x_2...

But it's perfectly fine to regard this as a linear combination because we're dealing with a polynomial vector space

[leaden swan]

No

a(x) and b(x) are not part of a field

[meager ore]

Oh, okay

So what is R[x]?

[leaden swan]

Polynomials with coefficients in R(set of real numbers)

[meager ore]

Okay. So, it fits the form of a linear combination in R[x]. No problems.

Thanks for the clarification!

[sterile pumice]

Shuri2060

[fiery zenith]

Does this look easy to prove by a. Induction b. Directly?

Just wondering - thought over it for a few minutes and don't see a way yet

Edit: I see a way by induction

[sterile pumice]

Shuri2060

[sleek cove]

if you can show its a probability then you're done

[fiery zenith]

ik but its not a number theory way

[sleek cove]

true, you probably should ask your prof, but induction seems the safer choice

[fiery zenith]

aha not an actual Q or anything --- its something I thought of after finding that probability

[late cape]

I see another way to approach this problem:
divide by $n^{n-1}$ on both sides
You get $(1+\frac{1}{n})^{n-1} \leq n$
Which you can prove directly by expanding the LHS and doing a bit more work.

[sterile pumice]

Dagnyr

[sleek cove]

what does this represent

[fiery zenith]

yh thats how i got induction

Take a sequence of a n-sided die roll results. Find the probability one of the partial sums of the series is exactly equal to n.

===
eg. 6-sided dice. Keep rolling and adding on result to total. Probability of reaching exactly 6 is 7^5/6^6

[broken igloo]

Given a function f mapping integers to integers, if a-b divides f(a)-f(b), can we say f is an integer polynomial?

[torn escarp]

no, take f(x)= x(x+1)/2 @broken igloo

maybe I misunderstand 'divides' here though

oh, I think the example still works in either case lol

[broken igloo]

yeah because 2-0 does not divide f(2)-f(0)=3, so that's not a counterexample

[torn escarp]

pick a,b of different parity

it's contingent upon when it divides

3-0 divides f(3)-f(0), but f is not an integer polynomial

[broken igloo]

oh I see, you are treating it as for some a, b. I was thinking of for all integers a, b.

[torn escarp]

I guess when a=b you're dividing by 0, or I guess you can exclude that if you want that way or

maybe I need to rethink the question now

[broken igloo]

but 0 divides 0 so we are fine

[torn escarp]

0/0 😩

I guess sure lol

[broken igloo]

0 = 0x for some integer x

[torn escarp]

I originally was thinking it was like polynomials in Q[x] and so trivially x-y divides f(x)-f(y) but

well ok I guess not a specific a, b hmm try to think of something

ok I think I have it now

f(x)=1/2

f(a)-f(b)=0

and a-b divides 0

0 = (a-b)*0

no no nevermind doesn't map integers to integers wew

[broken igloo]

what I know so far is if f(x) is a solution, then so is g(x)-g(x-k)

[grave carbon]

So, I thought I finished this proof,but I made an arithmetic mistake where the pink question marks are. So, I erased and now I’m a little stuck.

If I add 39a_0 to both sides, I would have a multiple of 13 on the LHS. I’m not quite sure how to finish it off.

[grave carbon]

Wait, would
$$10(10^{n-1}a_n + ... + 10^0a_1) \equiv 0 (\bmod 13) $$
$$ \implies (10^{n-1}a_n + ... + 10^0a_1) \equiv 0 (\bmod 13)???$$

[sterile pumice]

beeswax

[leaden swan]

Yes

Multiply with 4 on both sides

[grave carbon]

Both sides of what?

[leaden swan]

This equivalence:
$$10(10^{n-1}a_n + ... + 10^0a_1) \equiv 0 (\bmod 13) $$

[grave carbon]

I just guessed the implication was true, because that would give me what I want, but I'm foggy on why it's true

[sterile pumice]

DrunkenDrake

[sleek cove]

ab=0 mod p => a or b = 0 mod p

[grave carbon]

ahhhh

[sleek cove]

its just using the fact that things have multiplicative inverses in Z_p, so you can 'cancel' one of the terms and the other has to be 0 then

[thorny venture]

Person A flips a coin twice. Person B flips a coin 3 times. What is the probability that A obtains more heads than B?

[light flicker]

#probability-statistics or #discrete-math

[opaque elm]

o we have diophantine equation

91x + 23y = 5000.

and I did reverse euclidian algorithm on it, and we get our particular solutions (-1,4), now why would you multiply it with 5000 ?

[leaden swan]

Because you end up with
91(-1)+23(4)=1?

[opaque elm]

sure, but that doesn't make sense as to why you would multiply it with 5000

[leaden swan]

a=b <=> 5000a=5000b

[opaque elm]

but what has 5000 to do with it

look 91x + 23y = 5000

[leaden swan]

91(-1)+23(4)=1

5000(91(-1)+23(4))=5000

91(-5000)+23(4*5000)=5000

[opaque elm]

I don't get that tho

[leaden swan]

Which step do you not get?

[opaque elm]

5000(91(-1)+23(4))=5000

[leaden swan]

This

[opaque elm]

but why don't this dude do that ? his particular solution is x_0 and y_0 while I have to do all these other steps

https://www.youtube.com/watch?v=5DcoG69NyO0&ab_channel=GlennOlson

[leaden swan]

I mean, That's not exactly direct

You can show given a specific solution (a,b) all solutions are of the form (a+ (k b/(a,b)) ,
b-(k a/(a,b))) for some k

[opaque elm]

yeah I know

but the thing is

his x_0 and y_0 are the particular solutions

while

In my case particular solutions were not x_0 and y_0

[leaden swan]

Doesn't matter

You will still end up getting the same set of solutions

[opaque elm]

but then I dont have to do

then we have x = -1 -23n
and y = 4+91n

right?

instead

@leaden swan

[leaden swan]

Yes

[opaque elm]

but why would you do it the other way?

but if I get this right x = -1 -23n
and y = 4+91n is the general solutions?

[leaden swan]

Yea, That's the correct approach

[opaque elm]

but how would we get all our infinite solutions @leaden swan

I mean I can't test all n's

[leaden swan]

See this

[wind parcel]

Can someone explaint he fundamental theorem of arthimatic? like i understand it some what but how can we say that $n=p_1p_2...p_s and n=q_1q_2..q_r$

[sterile pumice]

cRaZyNiChOlAs12

[light flicker]

Are you looking at a proof of the fundamental theorem?

And this part is showing the uniqueness of the factorization?

[wind parcel]

I dont need the proof i just dont quite get what the q and p represent? is it the prime factorization of just n?

[light flicker]

I'm just asking you to put this in context? Because it seems like the context is someone trying to prove the uniqueness of this factorization

Like, where did you see this?

[wind parcel]

yea i mean the book already has the proof written out for me

um can we talk about this a little later i have to go to class lol sorry

[bleak robin]

does anyone here know the creteria for an ellipse to have integer solutions?

[light flicker]

The Hasse Minkowski theorem?

[bleak robin]

i have no clue what that is lol could you give something to read about it?

[desert kindle]

What do yall consider the "end" of elementary number theory? i.e. when should you start moving on to algebraic/analytic?

Is it around quadratic reciprocity?

[torn escarp]

just whenever you're interested enough

I got into NT cause I had a bunch of friends who would do them and after a while I just grew out of it and had a taste for more

my entry point was the dirichlet convolution and that got me into more analytic number theory stuff

[light flicker]

https://en.wikipedia.org/wiki/Hasse–Minkowski_theorem

[bleak robin]

ty

[wind parcel]

yea so in my abstract alg class which is just number theory the book goes over the fundament theory of arithmetic. but what i dont understand is since n can only have 1 unique set of primes (or maybe it can have more than that idk im assuming here) then how can it have p_n and q_m?

[light flicker]

I really need more context about where you're seeing this

like the surrounding text or something

[light flicker]

Yeah this is what I said earlier

[light flicker]

]

[wind parcel]

so doesn't n have to have a unique set of factorization though?

[light flicker]

No, they're stating the uniqueness here

The point is that you can't write it two different ways

The theorem is saying that if you write it down in two ways, then those two ways have to be the same

[wind parcel]

oooohhh ok that makes a lot more sense when u say it like that

so basically the q is just representing p but in a different spot in the order

[light flicker]

Right, and potentially adding some negatives

like you have that 15 = 3 * 5 = (-3) * (-5)

so prime factorization isn't completely ""unique"", but its basically unique up to these negatives and the reordering

[wind parcel]

ok that makes sense, so could u help me with a proof quick involving that?

[light flicker]

uhhhhhhhhhhh

yeah so

basically you need gauss's lemma

[wind parcel]

no no not like the proof of it its a seperate question

[light flicker]

oh okay

yeah sure

[wind parcel]

prove that there are no nonzero integers a,b such that $a^2=2b^2$

[light flicker]

only put dollar signs around the math things

[wind parcel]

oh okie

[sterile pumice]

cRaZyNiChOlAs12

[light flicker]

This is actually the same thing as saying that sqrt(2) is irrational, maybe you've seen that proof before?

[wind parcel]

yea its the 2nd part of this question lol

but it asks us to use the arithmetic thing to prove this

[light flicker]

ah okay

Yeah cool

so maybe the first thing to think about is what the prime factorization of squares look like

Is there something special about the prime factorization of a^2 for example?

Maybe try some examples like 12^2 or 15^2

[wind parcel]

that its only 2 and 3s?

[light flicker]

uhh not quite

15^2 has 5's in its prime factorization

[wind parcel]

uhhh

uh sorta, the book asks me to use fundamental theorem of arithmetic to prove there are no nonzero integers a,b such that $a^2=2b^2$

[sterile pumice]

cRaZyNiChOlAs12

[light flicker]

So what does the prime factorization of 15^2 look like

[wind parcel]

$335*5$

[sterile pumice]

cRaZyNiChOlAs12

[light flicker]

Right, what about 12^2?

[wind parcel]

$22223*3$

[sterile pumice]

cRaZyNiChOlAs12

[light flicker]

So we can write the first one as 3^2 * 5^2

[sterile pumice]

mirzathecutiepie

[light flicker]

and the second as 2^4 * 3^2 for example

so maybe you can start to see a pattern on what happens on the prime factorization of something squared?

Please scroll up. They're trying to prove that sqrt(2) is irrational in the next part.

Another way to see this, if you have that $n = p_1 p_2 \cdots p_m$ is the prime factorization of $n$, then what does the prime factorization of $n^2$ look like?

[sterile pumice]

Zopherus

[wind parcel]

idk it has to do something like $p_1^2$ right?

[sterile pumice]

cRaZyNiChOlAs12

[light flicker]

Yeah

Play around with more examples, and try to come up with something thats true about the prime factorization of squares

in particular, look at what the powers are

[wind parcel]

that its always 2 3 of 5?

[light flicker]

Uh no?

what happens to 7^2

[wind parcel]

it becomes prime?

[light flicker]

or 14^2

Is 7^2 prime?

[wind parcel]

no lmfao nvm

holy brain ded

one of the factors is always squared?

[light flicker]

Is it just one of the factors?

I mean, what happens to 36^2?

[wind parcel]

both the factors are to the fourth

[light flicker]

Right

So what is happening when you square a number?

[wind parcel]

its factors are also squared?

i feel like it is right in front of my face and im just missing it lol

[light flicker]

Yeah its factors are squared

so what does that mean about the powers that show up in the prime factorization?

[wind parcel]

they are either 1 or multiples of 2?

well no cause

nvm um

[light flicker]

uhhhh, can they be 1?

[wind parcel]

i thought i found an example earlier when i was messing with them

ye $38^2=1444$

[sterile pumice]

cRaZyNiChOlAs12

[wind parcel]

and $2^2*349$ is the prime factorization

[sterile pumice]

cRaZyNiChOlAs12

[sage fern]

nope

2^2 * 361

ie. 2^2 * 19^2

because 38 = 2 * 19

[wind parcel]

ah so then its factors are always squared or multiples of 2?

[sage fern]

factors' powers are always multiples of two

[light flicker]

yeah I'm not sure what you mean by "factors are always squared"

since 2 is a multiple of 2

[wind parcel]

yea thats what i meant i was just complicating it

[light flicker]

Right, so back to the original idea

a^2 = 2b^2

so what can we say about the prime factorizations of both sides

[desert kindle]

really late reply, but I want to get into elliptic curves, and get more practice with my algebra to slowly shift into algebraic geometry

[wind parcel]

that the factors are always raised to a multiple of 2?

[light flicker]

Well that's true for a^2 and b^2 separately, but the right hand side is 2b^2 right? How does the 2 affect the prime factorization?

[light flicker]

yeah, quadratic reciprocity, and things like how (Z/pZ)* is cyclic is all you really need

[desert kindle]

I took a modern algebra course that went up to the beginnings of galois theory, so I should be good to go!

[wind parcel]

it would make the factor half of what it is supposed to be?

[light flicker]

Is that true?

Play around with some examples again, what happens to 2 * 6^2 or 2 * 8^2 or 2 * 12^2?

[light flicker]

Sorry, I should've specified that that's all the knowledge you need from elementary number theory. To do things like elliptic curves, you preferably need knowledge of Galois theory and preferably some (classical) algebraic geometry

[wind parcel]

it makes one of the factors powers odd?

[desert kindle]

I appreciate the advice. I'm currently doing some self study from a mix of Dummit/Foote and Jacobson for the algebra stuff, so hopefully I can get a good intuition from there

[light flicker]

Exactly

So why can't it happen that a² = 2b²

[wind parcel]

becaues a^2 has to have even powers while 2b^2 has to have odd

and that means that they cant be equal

[sage fern]

ayyy

[light flicker]

And this is where you use your theorem

If n = a² = 2b²

Then you get two prime factorizations of n

And you can use your theorem to say that they're the "same"

[wind parcel]

oookkkkk

this makes so much more sense lol

another thing i dont get is proving congruence from modular thingys

[light flicker]

Do you have an example?

[wind parcel]

so something like proving $a+c=b+d (mod n)$

[sterile pumice]

cRaZyNiChOlAs12

[light flicker]

Do you know what it means for a = b (mod n)?

Like what the definition is?

[wind parcel]

b-a=nk

for some integer k

right?

or im sorry a-b

[light flicker]

Actually either one works

[wind parcel]

oh yea it can be negative too

[light flicker]

(And it's part of showing that equality mod n is a equivalence relation)

[wind parcel]

so a-b=nk and c-d=nj

[light flicker]

Right

So now what are you trying to show

[wind parcel]

that (a+c)-(b+d)=nm

and then a-b+c-d=nk+nj=n(k+j)

which proves congruency yea?

[light flicker]

Yeah exactly

[wind parcel]

siiiiiiiick

math is fun when u understand it lol

[blazing bison]

Reposting my Mathematica function in case anyone can benefit from it:

HighlyCompositeNumberList[n_Integer] := 
 Parallelize[
  Pick[Range[n], 
   FoldPairList[{#2 > #1, Max[#1, #2]} &, 0, 
    Table[DivisorSigma[0, i], {i, 1, n}]]]]

[dusky glacier]

Got a puzzle that i cant seem to solve

if i have a person that can move double the position he moved previously, i want to check if it can reach a certain position

for example, if i want the person to move to (3,4), they can go to 1,0 -> 3,0 -> 3,4 (only parralel to axis)

i cant think of a general way to solve this for any coordinate, can anyone help?

[regal aspen]

I'm sorry, I don't quite understand how he can move?

Ah I see

[dusky glacier]

let me clarify

[regal aspen]

nah I got it

[dusky glacier]

ok

(only parallel to axis)

[regal aspen]

Wait, does he have to move double the previous length, or can he choose?

[dusky glacier]

yes doublwe

double

starting at 1

[regal aspen]

Right off the bat, any number that sums to 2^n-1 is possible to achieve

And actually, I think that solves the problem

@dusky glacier

[dusky glacier]

hm

[regal aspen]

Lemme try with 5,2 -> 1, 0 -> 1,2 -> 5,2

ye ok, I recommend thinking in terms of binary

[dusky glacier]

binary? why

it looks like anything that sums to 2^n -1 works

[regal aspen]

Or rather, think of the 2 coordinates in terms of binary

Notice that if they share a digit, aka if the first is 1021 and 1121, you won't be able to reach it cause they both require a jump of length 2

thus, they cannot share a common digit. However, each jump must be double the length of the previous, so we get the total to 2^n-1

(1 + 2 + 4 + 8...2^n = 2^(n+1) -1)

[dusky glacier]

hm didnt get this

[regal aspen]

I think the best thing to do is just try it out

like, try to get (10,6)

[dusky glacier]

are you talking about binary the number system?

[regal aspen]

yes

[dusky glacier]

so how did you write 1021 and 1121

in binary

[regal aspen]

uhhhhhhh

that is binary

Oh shit

I meant 1010 and 1011

my bad

[dusky glacier]

ok i see

lol

thank you so much tho

[regal aspen]

np

[bleak robin]

Could someone explain quadratic forms to me?

[light flicker]

What exactly are you confused about?

[bleak robin]

a lot, so i get the general defintion but this example im doing doesn't make sense to me

[light flicker]

What here doesn't make sense? @bleak robin

[bleak robin]

So I get the 4-dimensinal part and how we get to m_theta but from there how do you get the for a in k part?

[light flicker]

{1, theta, theta^2, theta^3} is a basis for K over Q

[bleak robin]

Oh ok I read that so off then lol

Thank-you

[light flicker]

what book is this?

[bleak robin]

It's The Hasse-Minkowski theorem by Adam gamzon, it's a thesis I'm reading for a research project

[light flicker]

Ah cool

[karmic crest]

could anyone expand on the hint for b? I can't get anything useful beyond S has to have all elements odd or all elements even and all elements are equal mod 3

[light flicker]

If the first k primes are p_1, ..., p_k, and their product is m, then try to use the fact that #S_(p_i) <= p_i/2 for all i to say something about #S_m through the chinese remainder theorem

@karmic crest

[karmic crest]

do you mean S[m]? @light flicker

[light flicker]

No I mean #S_m, but information on #S_m gives you information about S[m]

[karmic crest]

oh was confused cos they only define S_p for prime p then, sounds good I'll have a go

I'm assuming if you have #S[m]/m -> 0 you can then get #S[N]/N -> 0 quite easily?

[light flicker]

Yeah, but you can define S_m in the same manner

yeah

[karmic crest]

ah k, have a clearer idea of the aim now

cheers

[bleak robin]

how do i check for solutions in p-adic fields R?

[light flicker]

Uh, R is not a p-adic field

But for Q_p, things like Hensel's lemma and the legendre symbols are helpful

[bleak robin]

alright thanks

[light flicker]

https://math.stackexchange.com/questions/1004639/why-doesnt-the-equation-have-a-solution-in-mathbbq-2/1004670#1004670

is a good example

[bleak robin]

thank you so much, im hoping to go into my uni years in 3 years and this really helps :)

[light flicker]

np I'm always happy to talk about nt

[sleek cove]

i want to talk about nt with you 🥺👉👈

[karmic crest]

man's doing algebraic number theory in high school?

[bleak robin]

yea xD

[light flicker]

What are you doing this research project for?

[bleak robin]

fun lol

[light flicker]

Are you doing it under the direction of a teacher or?

[bleak robin]

yea, I have a prof from a local university thats helping me

[light flicker]

Nice

[bleak robin]

thanks

[karmic crest]

so to make sure I'm on the right lines: you'd take x \in S and say x \equiv y (mod m) for 0 <= y < m which is equivalent to x \equiv y (mod p_i) for each i by CRT then count each possible y using #S_p <= p/2?

[light flicker]

vaguely yeah

[karmic crest]

vaguely? :p

[light flicker]

I was thinking of it slightly differently but its the same idea

[karmic crest]

wait isn't it just, p_i/2 possible values mod p_i, so maximum of \prod p_i/2 = m/2^k possible combos overall, then #S[m]/m = 1/2^k -> 0? @light flicker or am I missing something

[light flicker]

yep thats what I was thinking

[karmic crest]

ohhh and then the uniqueness part of CRT ensures that we don't have to do any more counting (I was confusing myself by multiplying that by something else too)

that makes sense

[karmic crest]

to be a pain, showing #S[N]/N -> 0 from #S[m]/m -> 0 doesn't seem to be as simple as it looked, I'll sleep on it though

[light flicker]

@karmic crest Hint: ||(x-1)/(y-1) < x/y as long as x > 1 and x < y||

[karmic crest]

turns out I'm just a smoothbrain then lmao

[light flicker]

You see how this implies what we want right

[karmic crest]

i'll have a think but I'd imagine it won't be that bad

actually no it's obviously not ignore that lol

but my strategy would be to have S[N]/N <= S[(some m depending on, and increasing in, N)]/(that m again) then RHS -> 0

[light flicker]

Yeah thats the right idea

[karmic crest]

i'll try to iron out the details tomorrow, getting late

[dusky glacier]

its not clear to me that r and s should be relatively prime

can anyone help?

[leaden swan]

if d is gcd(a,b) a/d and b/d are coprime

Because you removed the common prime powers from a and b

[dusky glacier]

it equals c tho?

[leaden swan]

a/d=r

b/d=s

[lilac star]

if r and s had any common factors they would have been included in gcd(a,b)=d

[dusky glacier]

ok, thanks makes sense ty

[sterile pumice]

Yes

[torn escarp]

suppose it doesn't and look at what happens mod 3

[glad robin]

Opps

Wrong server

Sorry

[karmic crest]

@light flicker sorry to be a pain again, but looking at it again the details don't seem easy to iron out lol, I picked m_N to be the m nearest to N then #S[m_N]/m_N >= (#S[N])/(m_N - (#S[m_N] - #S[N]), but then the denominator is >= N so that doesn't seem to go anywhere

I'm probably overcomplicating it

[light flicker]

Try picking m_N to just be greater than N

[wind parcel]

um can i post a question in here it doesnt get answered in questions :/

[karmic crest]

my issue is that for the denominator <= N you have to have m_N - N = #S[m_N] - #S[N], but there doesn't exist such an m_N for all N, eg. if N isn't in S, surely?

I guess I could try to make the denominator <= 2N, but I still see issues if there are large gaps in S?

[light flicker]

Okay yeah, actually my bad, this idea doesn't work you're right

[karmic crest]

haha nw, I was worried I was going mad :p

the fact that #S[m]/m -> 0 can still be used here right? Or did they mean something else with CRT

[light flicker]

Yeah its kinda weird

If you assume that the limit does exist, then the limit has to be 0 since the m's give a subsequence that converge to 0

[karmic crest]

ye but it seems hard to prove that

my only idea is bounding but I would have thought that strongly depends on S, since S might not even be infinite etc.

[bleak robin]

hint: try to write a in a way that you can reduce it to its last digit modulo 10

[wind parcel]

it would have to be someting like $a_1-10$ yea?

[sterile pumice]

cRaZyNiChOlAs12

[bleak robin]

i was thinking something like a = 10b + d, where b and d are natural

[wind parcel]

that makes more sense cause mine would only work for digits 11-19

[bleak robin]

so you just need to prove that any nonnegative integer a can be written in that form, which isn't too difficult

[wind parcel]

what is the equation for a modulo again, b-a=nk? right?

or a-b

yea im confused lol

[bleak robin]

wait are you asking if a = b (mod c) that a - b is divisble by c?

[wind parcel]

yea isnt that the equation for it? a=b (mod c)=a-b=nk

[bleak robin]

yea

[wind parcel]

so then i would have to put it into that form yea?

[bleak robin]

well in mod 10, 10b is congruent to 0 and you'll be left with d, which is your last digit

[wind parcel]

so 10b+d=mod 10

but how do u prove that a non-negative integer cant be used

[regal aspen]

wdym?

[bleak robin]

im confused by the question too

[wind parcel]

this

how do i prove that a nonnegative integer cant take the from of 10d+b

[regal aspen]

Uhhhhh

[bleak robin]

it can

[regal aspen]

They said the opposite?

[wind parcel]

oh my lord...

[regal aspen]

rip

[wind parcel]

sometimes man sometimes

[regal aspen]

ye

it do be like that

[wind parcel]

so then the proof would be like. $suppose a=10m+n. Therefore 10m+n=10k which will then leave us with just with the remaining digit$

[sterile pumice]

cRaZyNiChOlAs12

[regal aspen]

Uh, hm ig you could do it like that? But one thing to note with mods is that writing out = 10k is not really worth doing unless you're doing some fancy algebraic manipulation that you are sure will result in an observation that helps you solve the problem.

A quicker way to do it is just directly let 10m = 0 mod 10, so you get 0 + n mod 10

[bleak robin]

yea thats what i would do

what tenimus said

[regal aspen]

writing out =10k is good and all for like, when you're just starting out, to gain an intuition, but after a certain point it's just tedious imo

[wind parcel]

so i can just say what i said but just say 10m+n=0 (mod 10)?

[regal aspen]

Ah no

See, the only things you can say are 0 mod 10 are ones you know are multiples of 10

10m is a multiple of 10, so it's 100% 0 mod 10

however, you don't know about n

so you just write 10m + n = n mod 10

[wind parcel]

um one more quick question. so do i have to explain that 10m+n=n mod 10 is 10m+n-n=mod 10? or can i just leave it as 10m+n=n mod 10

[regal aspen]

it's the same thing

what you're asking is the equivalent of "do I need prove that 2 = 2? Or should I prove that 2 -2 = 0?"

[wind parcel]

yea ik but im guessing i dont have to actually like right it out and show more of the equation

if that makes sense

[regal aspen]

nah it's understood

[wind parcel]

sweet, thanks

[dusky glacier]

16. An integer is said to be square-free if it is not divisible by the square of any integer greater
    than 1. Prove the following:
    (a) An integer $n > 1$ is square-free if and only if n can be factored into a product of
    distinct primes.

[sterile pumice]

Yes

[regal aspen]

Assume the opposite

i.e. assume one of pair of primes is not distinct

[dusky glacier]

ok, starting with the forward

n is square free

so a^2 is not a divisor of n

$p_1^{2k_1}\dots p_r^{2k_r} \nmid q_1 \dots q_s$

[sterile pumice]

Yes

[dusky glacier]

(from a previous question, intergers squared are of this form)

[regal aspen]

mm no don't think that much

[dusky glacier]

ok

[regal aspen]

"it is not divisible by any square"

So like, if I have a single square in a the prime factorization, it's over

To illustrate, take 45

45 = 3^2 * 5. Although the 5 might not be a square, 3^2 is

so 45 is not square free

[dusky glacier]

yeah

cant seem to show distinctness generally tho

but obviously i can see that if the canonical form has powers that are larger than 1 then it cant be square free

so a bit stuck :/

[karmic crest]

it's very close to the definition

[regal aspen]

Alright, so let a = p*q*r....etc. or however you want to write it. Now, assume there exists a prime that isn't distinct from the others, WLOG(without loss of generality) let it be p. Thus, you get the final form as p^2*q*r......etc. However, taking q*r*...to be some integer, say k, a can be written as kp^2, which is a multiple of a square. So we're done

[karmic crest]

that's pretty much it

[dusky glacier]

i see

ty

[wind parcel]

prove that if $p>=5$ and p is prime, prove that $[p]=[1]or[p]=[5] in Z_6$

[sterile pumice]

cRaZyNiChOlAs12

[wind parcel]

so i need to prove for each [2] [3] and [4] do not work. So something along the lines of $p=0(mod 6)=p-0=6k$ for k is an integeer, and 6 cannot divide p since it is a prime. Right?

[sterile pumice]

cRaZyNiChOlAs12

[sage fern]

if i understand what you're saying, yes

[wind parcel]

ok so how do i prove that 5 would work? like how do i say that mod 5 works but only in the case of p being 5

[sage fern]

don't do that

just prove that all the others can't work

well i mean 5 is just a direct example so it can work

[wind parcel]

so by proving that 2 3 and 4 dont work it proves that either 1 or 5 does work

[sage fern]

2, 3, 4 and 0/6 don't work so it has to be 1 or 5, yes

you want to stick with mod 6 the whole way btw

no mod 5

[wind parcel]

yea thats what i mean sorry, 5 (mod 6)

right?

or 1 (mod 6)

[sage fern]

yes

[wind parcel]

ight perfect thanks

just wanted to get a second opinion lol

[light flicker]

What's your math background and why are you trying to learn number theory?

[wind parcel]

ok so like, something written as x= 2 (mod 6) is just x-2=6k and then is that just x=6k+2? right just using simple math skills. cause when i looked at this like review my prof had it written as x=6k-2

[sage fern]

yeah so that'll be for x = 4 (mod 6)

[wind parcel]

wait, why

[sage fern]

so say x = 6k - 2

6k - 2 = 6k - 6 + 4 = 6(k-1) + 4 = 6j + 4

bc it all loops around

-2 = 4 mod 6

-3 = 3

or they just meant to write +2 idk

[wind parcel]

well now im mega confused lmfao

i dont remember learning this at all

[sage fern]

hmmm

[wind parcel]

so like p=4 (mod 6)

p-4=6k

[sage fern]

yes

[wind parcel]

p=6k+4

[sage fern]

yes

[wind parcel]

ok so then p=2(3k+2)

[sage fern]

yes

[wind parcel]

lmfao let me show u what he did

cause maybe i am missing something

p-4=6k=p=2(2k-2)

also what does the notation k' mean is that a specific notation

[sage fern]

yeah so that's wrong

p - 4 =/= p

it shouldn't all be on one line

[wind parcel]

yea sorry thats my fault hold on

p-4=6k

p=6k-4=2(3k-2)

that is what he wrote.

[sage fern]

yeah that's wrong

[wind parcel]

so why did he write it as -4 not a positive 4

[sage fern]

the minuses in the second line should all be pluses

i think they got confused

[wind parcel]

ok thats what i thought

gaht

thought profs were supposed to be perfect

[sage fern]

if only 😔

[wind parcel]

thanks again

this channel has literally helped me sooooo much more than anything i have ever found online

[sage fern]

so it goes

[placid frost]

David Burton Elementary Number Theory

[dusky glacier]

I like burton too

[dusky glacier]

For any integer a, the units digit of $a^2$ is 0, 1, 4, 5, 6, or $9$.

[sterile pumice]

Yes

[dusky glacier]

anyone know how to do this?

[light flicker]

the units digit of a^2 only depends on the units digit of a

[bleak robin]

whats the limit in the middle called?

[light flicker]

@bleak robin https://en.wikipedia.org/wiki/Inverse_limit

[bleak robin]

ty

[bleak robin]

If i want to show the following, would I just say let there be f(c) = c^2 + 1, then use Hensel's Lemma for c=2?

[light flicker]

yes

[sterile pumice]

beeswax

[leaden swan]

No

It's a value that satisfies

Not the smallest

The smallest value will be order of a in (Z/nZ)*

If you mean for all such a,then it's in some cases and it's not in others

[grave carbon]

I'm having trouble finding a counterexample

[leaden swan]

Take n=8 and a=3

phi(n)=4 smallest such number is 2

[grave carbon]

ah

[leaden swan]

infact a^2=1 mod 8 for any coprime a

[grave carbon]

What was your intuition on choosing n?

[leaden swan]

I just knew this beforehand

[grave carbon]

Wait, is there some kind of formula for phi(n)? I cant find one in my book

[leaden swan]

yes

[sterile pumice]

DrunkenDrake

DrunkenDrake

[grave carbon]

I see

[leaden swan]

$phi(p^k)=p^k(1-\frac{1}{p})$ where p is prime

[sterile pumice]

DrunkenDrake

[grave carbon]

Oh, that clears things up

[grave carbon]

How did you make it so that your TeX has a white background on it?

[leaden swan]

idk,that was default for me

[inner anchor]

the carmichael function $\lambda$ is defined to be the minimal exponent such that $a^{\lambda(n)} \equiv 1$ for all $(a, n) = 1$

[sterile pumice]

Pappa

[regal aspen]

it's also known as the order for primes if I'm not wrong

[regal aspen]

Mod 10 looks good

[silk vine]

Suppose that I have a n×n system of linear diophantine equations over $\mathbb{Z}$ is there criteria to know when do solutions exist?

[sterile pumice]

MisterSystem

[regal aspen]

Yeeah

iirc, there was some matrix stuff you can do

[light flicker]

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

[regal aspen]

ye, kinda like that

[silk vine]

What exactly do I have to do?

Ooooh

I can see somehow how this may be useful

But still not so sure

[sterile pumice]

beeswax

[grave carbon]

Because $ar_1,...,ar_s$ is also a residue system for n

[sterile pumice]

beeswax

[light flicker]

They're the same mod n?

[grave carbon]

Yeah, that's what I was guessing

That's only true when a and n are relatively prime im guessing?

[light flicker]

Yes

[grave carbon]

Does this have something to do with Euler's Theorem

[leaden swan]

This part?

[grave carbon]

Yeah

[light flicker]

You can use this to prove euler's theorem yes

[grave carbon]

I'm not quite seeing how/where

[light flicker]

Those two products are equal mod n

You can cancel out all the r

[bleak robin]

Is this kind of like the Legendre Symbol, so like if i want to find (3, 4)_p, id solve z^2 - 3x^2 - 4y^2 = 0, in Q_p which i'd use Hensels Lemma or something in that area to do?

[torn escarp]

yeah, along with doing some simplifications you can do on the hilbert symbol itself

like in the case you gave (3,4)_p = (3,1)_p = 1, you can see the first equality comes from writing 4=2^2 and pulling it into the variable, the second equality comes from seeing once you have 1 you can just set x=0 and have y^2=z^2 so just pick y=z !=0

[bleak robin]

alright thank you.

are there more properties that wuld help me that are not listed here?

[torn escarp]

also aside from the characteristic 2 case, you're guaranteed to have solutions mod p so long as a,b are p-adic integers from the Chevalley-Warning theorem because the trivial solution is 1 solution and you're guaranteed a multiple of p solutions

so you can sort of go to the derivative case to check more immediately

for the sake of Hensel's lemma I mean

[bleak robin]

oh thats really helpful, thanks

[torn escarp]

I guess more precisely, if a,b are nonzero mod p, then you know there's at least one of x or y that's nonzero to make z^2=ax^2+by^2 so you simply pick the nonzero one and plug the other two numbers in to make it a single variable function, wlog let's say it's x we want to lift, then 2ax != 0 mod p clearly (except in characteristic 2)

so this solves a huge chunk right away

[bleak robin]

how would i prove this? they left it as an exercise for the reader

[bleak robin]

one last question, how would I express a number a = p^b * u, where u is a unit in Q_p for a given prime?

[light flicker]

@bleak robin the proof of that follows from quadratic reciprocity

For the second question, if you think of a p-adic number as (x_1, x_2, x_3,.... ) as in the inverse limit definition of Q_p, then this is a unit if and only if x_1 is nonzero

Thus, given some p-adic number a = (0,0,...., 0, a_1, a_2, ....) with a_1 non-zero, you can write this as p^b (a_1, a_2, ....) and the latter element is a unit

[bleak robin]

ok that makes a lot more sense, thank you

[gentle lily]

Here is a good problem: Three of the elements in the solution set of the simultaneous system$$ x^{x+y} = y^4, \qquad y^{x+y} = x $$are ordered pairs of integers $(x, y)$. Find these ordered pairs.

[sterile pumice]

LifeSource

[gentle lily]

I don't need help with it by the way

[torn escarp]

hmm I'm missing one of the 3

I got (1,1) and (4,-2) but the way I solved makes me think they're the only solution, I suppose if we say 0^0=0 then I have a 3rd solution as (0,0)

but morally I wanna believe 0^0=1 for integers lol

@gentle lily let me know if there's a third solution I didn't get or it really is (0,0), I'll play with it tomorrow

[sudden orchid]

i don't get part b

i did part a, how would i use that for part b

[torn escarp]

what'd you get for part a

[sudden orchid]

u=4, v=-13

[torn escarp]

and gcd is?

[sudden orchid]

1

[torn escarp]

your equation is pretty similar to what you need, you can multiply through by 31

but that's just one solution

well, does that make sense so far?

[gentle lily]

Well when we have $y^{(x + y)^2 - 4} = 1$, we also have to consider $y = -1$

[sterile pumice]

LifeSource

[torn escarp]

I never got that

[sudden orchid]

yeah kind of

[torn escarp]

I plugged in for x into the other equation to get $(y^{x+y})^{x+y}=y ^4$ so $y^{2(x+y)}=y^4$ and then I put $x+y=2$ in the exponent, from there I plugged into $y^{x+y}=x$ to get $(2-x)^2 = x$, expanded the quadratic

[sterile pumice]

Merosity

[torn escarp]

then factored it for the 2 roots

i guess that was my mistake

it's (x+y)^2 not 2(x+y)

hah just did it completely wrong

[gentle lily]

XD

[torn escarp]

@sudden orchid what do you mean kind of

[sudden orchid]

yeah i got it actually

but u said there were more than these two solutions?

x=124 and y=-403

[torn escarp]

yeah, to get those we need to add 0 in a fancy way effectively

we can make 0 with those numbers in infinitely many ways

and add those on to our single solution

777x+239y=0 has a surprisingly simple solution

just pick x=-239 and y=777

now adding any multiples of this pair to your solution will still be a solution

[leaden swan]

You also need to show all solutions are of that form

[neon hollow]

Anyone have any advice for reducing exponents that involve mods? Not sure if this is elementary number theory or advanced ... let me see if I can lay it out. I'm trying to simplify to X with substitution.

The gcd of b_1 and b_2 is 1

Ah wait am I interrupting another discussion?

[leaden swan]

Just find c_1 and c_2 such that c_1b_1+c_2b_2=1

[neon hollow]

I was advised to start here and start plugging in C1 and C2, but quickly got overwhelmed

Note: Exclusively doing this with variables, no numbers

[leaden swan]

Yea,Just do ${Y_1}^{c_1}{Y_2}^{c_2}$

[neon hollow]

_> this bot lol

[sterile pumice]

DrunkenDrake

[leaden swan]

LHS will be $x^{b_1c_1+b_2c_2}=x$ mod(n)

[sterile pumice]

DrunkenDrake

[neon hollow]

ok let me try that out, thank you

[leaden swan]

Actually, That's not quite correct

c_2 or c_1 will be negative

And if gcd(Y_1,n)!=1 or gcd(Y_2,n)!=1 you can't raise them to a negative power

[neon hollow]

Substituting everything got ugly quick, but I’m not super familiar with multiplying different mods

I suppose the inverse of b is why we’re able to remove one of the mods?

How did you get ${Y_1}^{c_1}{Y_2}^{c_2} \ from \ {Y_1}^{c_1}({Y_2}^{c_2})^{-1} \ mod \ n$?

:|

F

[leaden swan]

I assumed c_2 can be negative

[sterile pumice]

hurricane

[neon hollow]

There we go

lol

[leaden swan]

Do you know (x,n)=1?

Yea, You assumed c_1b_1-c_2b_2=1

[neon hollow]

I do not 🤔 this is actually for RSA public key cryptography hilariously, scrambling backwards finding if that property needs to hold true

[leaden swan]

I assumed c_1b_1+c_2b_2=1

[leaden swan]

That step is wrong if gcd(y_2,n)!=1

[neon hollow]

I know that both gcd(b_1, Phi(n)) and gcd(b_2, Phi(n)) = 1, but I dont think thats helpful here

[leaden swan]

In that case inverse is not defined

[neon hollow]

Ah, we can assume that gcd(y_2, n) = 1 in that case

We also know for certain that x is a real whole number

I'll have to poke at this some more

Thank you for your insights

[neon hollow]

Well I got confused so went the substitution route anyways, got real close

But now am stuck again trying to get rid of the mod n; which apparently is ok

Leading me to conclude that Math is indeed for Masochists 😂

[leaden swan]

This is why mods are messy

$y_1^{c_1}{(y_2^{c_2})}^{-1}=x mod n$ is what you get when you do that simplification

[sterile pumice]

DrunkenDrake

[leaden swan]

Which is what you want

[neon hollow]

I stand in awe every day of whoever it was that came up with this stuff

[outer brook]

Got a quick question regarding some number theory stuff

suppose a is a unit in Z/n, and b is a zero divisor in Z/n, how can I show that the product of a and b is also a zero divisor in Z/n

[leaden swan]

let bk=0

Then (abk) is clearly 0

[outer brook]

Can you provide a more formal way of saying that

This was a quiz question that I didn’t quite know how to go about, It mentioned saying that a*b =/= [0]

It wanted me to verify that

[leaden swan]

Let's say a is a unit in a commutative ring R,and b is a zero divisor,
Let n be a nonzero element such that bn=0,then a.(bn)=a.0
(ab)n=0

Implying there is a non zero element n such that (ab)n=0

[outer brook]

Why does it want me to verify (i)

[leaden swan]

I don't think 0 is generally included in the set of zero divisors

This is how D and F defines it

apparently, It's convention. Ask your professor

[outer brook]

Hmm I don’t quite understand this, could you provide an example of where this holds true

[leaden swan]

Take (Z/6Z)

[outer brook]

Ok

[leaden swan]

a=5

b=2

Then 2(3)=0

Consider ab=10=4

4*3=12(divisible by 6)=0

[outer brook]

Oh I see

Okay I just got confused with their hints because aren’t we supposed to show that [a][b]=[0], i.e. the product of a b is a zero divisor

[leaden swan]

[0] is not a zero divisor

Some people exclude zero in the defn

[outer brook]

Oh ok

Wait so how do I verify that, a, b are nonzero so there is no need for verification

[leaden swan]

2(3)=0 in Z/6

Product of 2 non zero numbers can be 0 in Z/n

You use the fact that a is a unit and do a contradiction

[outer brook]

Oh I see

So show that n doesnt divide ab

Wait why do people not include 0 as a zero divisor

[sage fern]

i think they do, just not a nontrivial zero divisor

[leaden swan]

idk

Not including zero makes it less awkward to state certain facts like "A integral domain has no zero divisors"

As opposed to "A integral domain has no zero divisors other than 0"

[outer brook]

Oh ok

[sage fern]

an integral domain has no nontrivial zero divisors

good enough

[leaden swan]

This is like how some people don't include 0 in N

Mostly pointless

[sage fern]

most ppl

eh

[bleak robin]

how would I change (x - M/2)^2 + (y - M/2)^2 + xy into a quadratic form?

[regal aspen]

uhh

Be a little more specific pls

[bleak robin]

I have (x - M/2)^2 + (y - M/2)^2 + xy = M^2/2 - N, and I want to able to change it into x1^2 + x2^2 = f(M, N)

[torn escarp]

make the 2x2 symmetric matrix and then diagonalize it

the eigenvectors of a symmetric matrix are orthogonal, so the matrix of eigenvectors is orthogonal and so you can use it as a change of basis

$v^T A v = v^T(E^T D E)v = (Ev)^T D (Ev) = u^T D u$

[sterile pumice]

Merosity

[fervent crest]

Wait a quadratic form should only have terms with degree exactly 2

But the left hand side has -xM and -yM

Or am I just dumb

[torn escarp]

oh you're right that might be a problem

when trying to put it into diagonal form like that, $v^TAv +b^Tv + c$ will not be able to remove the terms by getting us $u^T Du + (Eb)^T u + c$ since the eigenvectors are linearly independent.

[sterile pumice]

Merosity

[bleak robin]

does that mean that i'd need to bring it M/3 down on both sides and get x^2 + xy + y^2 = -n, then solve from there?

[bleak robin]

does this include p = infinity?

[light flicker]

use #prealg-and-algebra

[verbal flame]

Ok thx

[sleek cove]

ur welcome

[tidal spoke]

hi, may be somebody can help me with example related to groups/groups notation. Im confused by example 2.8 of ":Guide to pairing based cryptography": https://by1lib.org/book/2932885/2b8bd1?regionChanged=&redirect=196496375

here is a screenshot of example 2.8

as I understand they use theorem 2.2 -> they take elements from group Z_13 and raise them to the 5-th degree under modulus 13

Im confused by Z_13{5}

I mean 2**5 mod 13 = 6... or... what?

[leaden swan]

They aren't doing that

They are finding numbers p such that p^5=1

[tidal spoke]

hm but does 2^5 =1?

[leaden swan]

No

There's something wrong here

[tidal spoke]

yah... that is my point... and Im trying to understand is it my math is wrong or... authors

[torn escarp]

weird mistake, obviously the only thing in that set is 1 cause 5 doesn't divide 12

[floral ice]

Let $0 < a,b < p$ where $p$ is prime. and $a, b \in \mathbbN}$. How can I prove that: $p = \frac{ab}{x}$ has no solution over $\mathbb{N}$ where $x \in {1, ... p}$ ?

[sterile pumice]

Kas.st

[floral ice]

figured it out: w.l.o.g $p = a \cdot \frac{b}{x} \Longrightarrow \frac{b}{x} \in \mathbb{N}$, which is a contradiction since $p$ is prime. Thus there isn't a solution

[sterile pumice]

Kas.st

[fervent crest]

the implication does not hold

the thing is that, ab/x, even if it is an integer, cannot have any factor of p

[floral ice]

why doesn't it hold? I forgot to mention that a, b are integers aswell

[light flicker]

@floral ice I mean if you take like a = 2, b = 3 and x = 2, then 3/2 is not an integer

[floral ice]

but b = p which isn't allowed

[light flicker]

I'm saying that the implication that a \cdot b/x implies that b/x is an integer is not valid

[late prism]

a b = p x, therefore p divides a b. But a product is divisible by a prime only if one of the terms is - and they can't be, because they are smaller than p.

Your way, meanwhile, doesn't really work. Why must b/x be an integer? You only know that (a b)/x is.

[stoic jacinth]

Can anyone help me understand why

ϕ(8) = 4 with elements {1,3,5,7}

Rather than

ϕ(8) = 5 with elements {1,3,5,6,7}

Is it just gcd(8,6) = 2 being the reasoning?

Rather than 1

[leaden swan]

Yes

[stoic jacinth]

Thank you

[stoic jacinth]

In inclusion-exclusion principle for example, do you always add the intersection of all sets given it is more than two sets eg

$A \cup B \cup C \cup D = |A| + |B| + |C| + |D| - A \cap B - A \cap C -..... + A \cap B \cap C \cap D$

[sterile pumice]

Harbh

[stoic jacinth]

This is what I found online; I'm not sure if its the same formula
n (A U B U C U D) = n (A) + n (B) + n (C) + n (D) – n (A ∩ B) – n (A ∩ C) – n (A ∩ D) – n (B ∩ C) – n (B ∩ D) – n (C ∩ D) + n (A ∩ B ∩ C) + n (A ∩ B ∩ D) + n (A ∩ C ∩ D) + n (B ∩ C ∩ D) – n (A ∩ B ∩ C ∩ D)

[fervent crest]

Um

Yes

It is indeed correct

But why

Why would you write it out

[stoic jacinth]

Well to make sure I did it correctly for adding and subtracting the individual parts

Not for actually writing it out if you get me; just to make sure I know what parts to plus and what to minus

Trying to find how many numbers are not divisible by 2, 5, 7 and 13 by inclusion-exclusion principle

Thank you!

[fervent crest]

Ok well I guess that makes sense

It’s just kind of disgusting

Basically it’s

• sum of all the single sets

• sum of all intersection of two sets

• sum of all intersection of three sets

• sum of all intersection of 4 sets

• ...

[stoic jacinth]

Ahhh that's very good to know thank you!

That's quite convenient

[fervent crest]

The pattern holds for not only $|A\cup B\cup C\cup B|$ for 4 sets but $n$ sets in general

[sterile pumice]

Whoever

[stoic jacinth]

Nothing better than a general rule for anything maths

[torn escarp]

I prefer to write the inclusion-exclusion as $$\varphi(n) = \sum_{d|n} d \mu(n/d)$$

[sterile pumice]

Merosity

[stoic jacinth]

I'm not that good at maths to understand that unfortunately 😔

[torn escarp]

mu is the mobius function, and it encodes inclusion-exclusion for doing number theory stuff, look into mobius inversion or the dirichlet convolution if you're interested

[fervent crest]

How is it related?

[torn escarp]

oh these are two questions by the same person, I just skimmed the first part about phi and saw talk about inclusion-exclusion and just assumed they were doing this

[fervent crest]

I meant like

I don’t quite see why that’s inclusion and exclusion

[wind parcel]

i am quite lost on this one

would I wanna do something like adding a+u=b and a+y=b?

[light flicker]

What does a being a unit mean?

[wind parcel]

[a][x]=[1]

or is it just $[a]/=[0]$

[light flicker]

The first one, the second is equivalent if n is prime

So can you use this in some way?

Maybe think about how you would solve ax=b if they're all rational numbers and a is not 0

[wind parcel]

well you would just divide by a and get b/a=x

so could i multiply like a^-1 to both sides?

So then would something like d$ax_1=b=ax_2$ then $x_1=a^-1ax_1=a^-1ax_2=x_2$

[sterile pumice]

cRaZyNiChOlAs12

[light flicker]

Right

[wind parcel]

sweet

gracias

[wind parcel]

alrighty i have got another one cause once again i am stuck oof

so why does ar-b=kn like where does that even come from

so is that just saying ar= b mod n

[leaden swan]

x has to be [r] for some r

[wind parcel]

so ax= b mod n as well?

[leaden swan]

Yes

Well, it's more like ar=b for all r in x=[r]

[wind parcel]

so im guessing that i need it get it down to something along the lines of b=dk

[leaden swan]

yes

You use that if a=b and if r divides a,r divides b

[wind parcel]

where does that come in to play? how does a=b and why does r divide a

[leaden swan]

Ok,I didn't mean a and b as in this question.

So,You have ar=b mod n,rewrite this removing the mod

ar=b+kn for some integer k

[wind parcel]

ar-b=kn or ar=kn+b

yea

[leaden swan]

Move the kn to the left hand side

Now d divides (ar-kn)

[wind parcel]

wait how does d divide (ar-kn) since (ar-kn)=b

[leaden swan]

d=gcd(a,n)

[wind parcel]

oh lord

lol

and that just means d=au+nv but instead its kn and ar

goootch

so the proof would go along the lines of. Since ar=b mod n that means ar-kn=b and since d=(a,n) it takes the form of d=ar-nk=b that means d|b

[warped helm]

Hi 🙂 this is from a number theory exercise sheet, but I'm really not sure where to start/ what theorems to use or even what subtopic of number theory this comes under

sorry I just realised I cut out the question

[light flicker]

Weird, someone asked this exact same question a couple weeks ago

Also there's a hint below

[warped helm]

oh really? Would it be in this channel then?

[light flicker]

here

[warped helm]

Thank you- yes we actually go to the same university so that would explain it hahaha

[light flicker]

Ah, yeah that makes sense

[warped helm]

Just wondering what it means for the legendre symbol to be congruent like this

is this saying that the value is a^(p-1)/2

[light flicker]

I mean, the legendre symbol is either 1 or -1?

So it's just regular congruence of numbers?

[warped helm]

yeah or 0

ahh I see

thank you

[light flicker]

yeah but hcf(a,p) = 1 means the legendre symbol can't be 0 here but you're right

[warped helm]

Thank you very much 🙂

[shrewd mural]

oh um wuts the difference between root and logarithm? so if i have sqrt(4) and log2(4), wouldnt they give me the same results?

[unborn bison]

This isn’t discrete math, the principal sqrt and the log2 intersect at x=4 but that doesn’t make them the same. The log2 is the inverse of the function 2^x while the principal squareroot is function that returns the positive squareroot.

If you plot the functions in desmos

I will se that sqrt will outgrow log2

[shrewd mural]

ah

i think

i get it

[unborn bison]

after x=30 sqrt outgrows significantly

[shrewd mural]

so besides graphing, what makes them different? cuz i think i can still do 10√10 log10(10) and get the same result, (10 in 10√10 is not coefficient)

[unborn bison]

Well what do you get for x=33?

[shrewd mural]

whats the base

[unborn bison]

Try 10

[shrewd mural]

alr

[unborn bison]

Log10(33) is not equal to 10th sqrt(33)

Just because they share some intersections doesnt make them the same functions

[shrewd mural]

so for root i get 1.41.... and logarithm i get 1.51...

wait but how is this explained?

[shrewd mural]

do they only share one?

[unborn bison]

I don’t know

[shrewd mural]

u mean the difference thing?

but how do i determine when to use each one, considering they are different?

[unborn bison]

This isn’t really number theory m8, ask in #precalculus or something

[shrewd mural]

oh i thought its NT, alr lemme ask there

[unborn bison]

This is a question about what functions are, if you aren’t familiar with domains and codomains then I immediately assume you are in precalculus or algebra.

[shrewd mural]

im in geometry hehe

[torn escarp]

wrong channel try #calculus

[lament dove]

sorry

[left sigil]

@odd imp try setting $x=a+b\sqrt{2}$ and $y=c+d\sqrt{2}$, and then compute $x+y=(a+b\sqrt{2})+(c+d\sqrt{2})$, $xy=(a+b\sqrt{2})(c+d\sqrt{2})$ and $1/x=1/(a+b\sqrt{2}$.

[sterile pumice]

Bannanachair Monarch

[ebon dagger]

someone solve this

this is anime math problem

[leaden swan]

Should be (1+n)^p