elementary-number-theory

[alpine jasper]

p=xy
N(p)=N(x)N(y)
p^2 = (a^2+b^2)(c^2+d^2)
if either (a^2+b^2) or (c^2+d^2) is p^2 or 1, we're done
so assume p = (a^2+b^2)

[light flicker]

And again, there's an assumption of the problem that you haven't used yet

[alpine jasper]

reading is hard

let me see what i'm missing

alright, since a^2 and b^2 are both either 0 or 1 mod 4
a^2 + b^2 is either 0,1, or 2 mod 4

i don't think this is what you have in mind when you said

assumption of the problem that you haven't used yet

[light flicker]

nope

can you type out your problem for me

[alpine jasper]

.. jesus

p is congruent to 3 mod 4

so a^2 + b^2 is 3 mod 4

which can't happen

this HAS to be it

[light flicker]

it is

[alpine jasper]

well, thanks for carrying my ass all the way through this

[light flicker]

np

[alpine jasper]

much appreciated

[dreamy rain]

anyone know any good books on elementary number theory and its application in cryptography

or something similar like lecture notes

[sacred junco]

Koblitz NT

[alpine jasper]

i'm stuck on the second part

help

if f(x) is a multiple of y, then n | f(x) and we're done

[sacred junco]

But I guess you have to argue that such x exists

[alpine jasper]

that's exactly where i'm stuck

how do i show that?

[sacred junco]

hmmm not sure if correct, but I guess if youre given f(x) s.t. its congruent to 0 (p_i), then obviously its congruent to 0(\prod p_i) = 0(n)? So assuming there exists such x then it will be solution to the first thing

[dreamy rain]

thank u for ur suggestion, have u been through the book personally? @sacred junco

[sacred junco]

for first 15 pages and I didnt quite like it because it didnt fit my course

[dreamy rain]

ah right, was it easy enough to get into though

[sacred junco]

I think so, there was more cryptography than nt in there, I think you should just check out the pdf somewhere and see for yourself.

Although Im not sure, I didnt read much of it, nor I remember the content table

[alpine jasper]

f(x) s.t. its congruent to 0 (p_i), then obviously its congruent to 0(\prod p_i) = 0(n)
can you explain the "obviously" part? because that's the whole direction

wait

umm

right but isn't that the forward direction

f(x) s.t. its congruent to 0 (p_i)
the given is that there exists f(x) = 0 (p_i) for each i, so like...
f(x_1) = 0 (p_1)
f(x_2) = 0 (p_2)
... so on?

[sacred junco]

knowing f(x)=0(p_i) then if f(x) = a*(p_1)*(p_2)*...*(p_i) will be congruent to all

[alpine jasper]

knowing f(x)=0(p_i)
i'm not sure i can assume that

[sacred junco]

its congruency

[alpine jasper]

unless i'm reading the question worng

again

[sacred junco]

f(x) congruent to 0(p_i)

then f(x) is of the form as wrote above

[alpine jasper]

hmm

i think the question doesn't want me to assume that there exist a single x that f(x) = 0(p_i)

[sacred junco]

$f(x) \cong 0(p_i) \to f(x) = a \cdot p_i$

[sterile pumice]

Godel:

[sacred junco]

for all p_i

thats what we assume right?

[alpine jasper]

no..?

[sacred junco]

well p_i^alpha

[alpine jasper]

it says there exist x for each individual p_i

the second implication

<== direction

[sacred junco]

No, there exists f(x) such taht its congruent to 0 to all p_i ^a_i

if those f(x) were different they would be called f_i(x) I think

[alpine jasper]

f(x)≡0(p_i) has a solution for i= 1,2,···,t

i don't know man

has a solution for those individual i's, not all at once

otherwise it'll just say f(x) = 0(n)

which is the thing that i want to prove

[sacred junco]

I think

Would you agree?

[alpine jasper]

i don't, i think x's need not be the same

[sacred junco]

hmm let me think, you might be right and I just misunderstood the question

[alpine jasper]

it's due in 30 mins

[fervent crest]

What's the most efficient way to calculate the solution for a system of congruence?

Using chinese remainder theorem

I'm asking computational wise

[sleek cove]

am i supposed to use induction here? i dont know how to start

[light flicker]

When is a number not relatively prime to p?

[sleek cove]

when its not pk

gcd not 1

[light flicker]

in other words, its a multiple of p

[sleek cove]

yes

[light flicker]

so how many multiples of p do you have from 0 to p^2 -1

[sleek cove]

p

but i dont know how to like rigorously get that

[light flicker]

you can just list them

it's 0, p, 2p, ..., p(p-1)

[sleek cove]

oh...

ok thx

[winter bear]

oh yeah this is a problem from ireland rosen

what did you try

[limber charm]

Tbh I don’t know what to do but this looks like Wilson’s theorem and it also looks like a previous problem where I applied a theorem that said x^2=-1(mod p) if and only if p is prime such that p=1(mod 4)

[winter bear]

well it does have to do with wilsons, yeah

try writing out the factorial(expanding that is) with the square

[limber charm]

I’m not sure if I expanded correctly

[winter bear]

oh wait i read that as [(p-1)/2]!^2 lol

umm gimme a sec to solve this

[limber charm]

Oh lol

[winter bear]

yeah ok i see it

continuing this should prove it

try playing around with this for a while

[inner anchor]

Cant you get rid of the twos somewhat easily?

[winter bear]

yep

[limber charm]

How?

[winter bear]

so we have a 4^(-1) factor in each right

how many of those do we have

[limber charm]

There’s one in every part of the factorial expansion

[winter bear]

yeah, so how many total

[limber charm]

P-1

[winter bear]

not quite

how many terms are we multiplying

how many terms in n! for example

[limber charm]

n?

[winter bear]

ja

[limber charm]

Ok then the number of terms we’re multiplying is ((p-1)/2)^2

[winter bear]

yep

so if we take out a 4^{-1} from each

what is the total thing we aare taking out

[limber charm]

The number of terms times 4^(-1)?

[winter bear]

no

remember we are taking a 4^(-1) out from each

progress @limber charm ?

[limber charm]

My iPad just died, sorry

On my phone now

And idk, I thought it was what I said

[winter bear]

oh well you are multiplying 4^(-1) by itself that many times

so its 4^(-1) to that power

whats this power

[limber charm]

The number of terms?

[winter bear]

$4^{-(p-1)^2/2}$

[sterile pumice]

JohnDoeSmith:

[winter bear]

yeah

so what does this equal

[limber charm]

This?

[winter bear]

hmm its not exactly that

[limber charm]

Oh the ((p-1)^2)! looks like I wrote it as part of the exponent but I didn’t mean it like that

[winter bear]

oh its still not exactly that

$4^{-(p-1)^2/2} (p-1)^2 [(p-1)^2-4] [(p-1)^2-8]\dots$

[sterile pumice]

JohnDoeSmith:

[winter bear]

is what it is right

[limber charm]

How?

[winter bear]

basically take out a 1/4 from each factor

in the expansion

anyhow first evaluate $4^{-(p-1)^2/4}$

[limber charm]

1/2^(p-1)!

I really wish I knew how to use that bot, it’d be helpful

[winter bear]

just put your things between $

also oops i made a bit of an error

[sterile pumice]

JohnDoeSmith:

[winter bear]

yeah sorry, there are [(p-1)/2]^2 = (p-1)^2/4

but same principle will apply

[limber charm]

Ok then it’s 1/(4^(p-1)^(2)!/4

[winter bear]

theres no !,but yeah

now can you simplify this

[limber charm]

Oh yeah no !

Isn’t it 1/(sqrt(2)^(p-1)^2)

[winter bear]

well sqrt(2) isnt nice in mod

[limber charm]

Ok then I’ll leave it in the exponent

[winter bear]

$2^{-(p-1)\times (p-1)/2}$

[sterile pumice]

JohnDoeSmith:

[winter bear]

its this right

what theorem can you use for modular arithmetic

that simplifies this

[limber charm]

I’m not sure

Are you talking about the thing we factored out or the whole thing?

[winter bear]

$a^{p-1} \pmod{p}$

[sterile pumice]

JohnDoeSmith:

[winter bear]

whats this in general

[limber charm]

I haven’t seen this theorem before

If this is the theorem

[winter bear]

fermats little theorem?

umm idk if this can be done without that

[limber charm]

Oh wait nvm I’ve seen fermat’s little theorem

[winter bear]

alright by fermats little, what is the thing we had

[sleek cove]

t is the residue classes of Z_n right

nvm im blind

[spark kindle]

hello is anyone here

[stoic bear]

[upbeat wren]

I have a general question about some Number Theory. I know about rings like Z[sqrt(n)] and that some of those rings have/don't have (I don't remember exactly here) zero divisors or unique factorization. Is this question difficult: Does a^3 + b^3 = c^3 have nontrivial solutions in say Z[root(105)]? Or for Z[root(n)] in general?

[light flicker]

This seems hard

[sacred junco]

👍🟥

[prisma flame]

What's the difference between a Cayley table and a group/multiplication table?

[quick furnace]

cayley tables are multiplication tables just with a fancy name

[sacred junco]

Well, you can also de addition in a Cayley table

So in that case, its not a multiplication table

[neat crow]

Very fancy name, indeed.

[civic marsh]

@upbeat wren try to research and work it out for yourself. You probably already know that numbers in general Z[alpha], alpha in R can be described with the fundamental pair of periods.

[light flicker]

Fundamental pair of periods? I've heard this term in relation to complex elliptic curves, but I'm not sure if that's what you're referring to here? @civic marsh

[granite quiver]

I'm having problem with (b), i have done some search on the internet and i found out that n! - 1 is prime for some n, which makes me confuse because i don't know how to answer the question.

[inner anchor]

apparently these are called factorial primes

it isnt known if there are an infinite number of them, so I would answer that n!-1 can be prime or composite

[granite quiver]

Ok thanks. I want to ask that is there anyway to know whether a number is a prime or not ?

At problem a i can prove that 119 is not divisible by any prime which is lower than sqrt(119) but i have no idea with problem c

Oh my mistake 119 is divisible by 7

[silver solar]

(c) is almost a Mersenne number

[granite quiver]

But how do we know whether it is a prime or not ?

[silver solar]

||https://math.stackexchange.com/questions/140804/if-2n1-is-prime-why-must-n-be-a-power-of-2||

This helped me, so it should be able to help you

[granite quiver]

Thanks a lot !

[granite quiver]

But i also have a question, it just say that if 2^n + 1 is prime then n must be a power of 2, but it doesn't mean that if n is a power of 2 then 2^n + 1 is prime. Similarly for Mersenne prime, 2^n - 1 is a prime then n is a prime number, however, if n is a prime 2^n - 1 may not be a prime

For instance, 2^11 - 1 is not a prime number although 11 is a prime number

So how do we know 2^35 - 1 is a prime number or not

[neat crow]

You could look at Fermat's little theorem

Oh wait, no, I'm dumb

It's only for primes

[granite quiver]

I'm so confused =((

[neat crow]

I know.

I'm going to show you.

$2^{35}-1=(2^5)^7-1=32^7-1^7$ is divisible by 31

[sterile pumice]

WWM resident:

[neat crow]

Therefore it is not prime.

You can check by yourself that $a-b\mid a^n-b^n$

[sterile pumice]

WWM resident:

[granite quiver]

Okay i got it

Tks a lot

[neat crow]

I'm glad I could get it right on time

[granite quiver]

But what about 2^n + 1

[neat crow]

Unless that special rule indicated above, I don't think there is a special rule. Maybe except that 2^(an odd number)+1 is not prime

[granite quiver]

Okay, tks a lot !

[neat crow]

Hence the theorem, by the way.

[granite quiver]

Is there any documents or books that explain these topics ? I'm reading Discrete Math by Kenneth but it seems like the book doesn't explain these topics a lot.

[neat crow]

Sorry, I'm not good at giving away titles of books, as I don't have enough.

[granite quiver]

=(( okay tks

[upbeat wren]

|| Let k be odd and greater than 1, 2^(k) + 1 is not prime. (in fact it's divisible by 3).

1. Any multiple of 3 greater than 3 is not prime as it is divisible by 3.

2. If k is odd and greater than 1, 2^(k) + 1 is divisible by 3.

Proof: Mod 3 ... 2 = -1 and so 2^(odd) + 1 = -1^(odd) + 1 = -1 + 1 = 0.

Note also that 2^(k) > 3 for k > 1. ||

[granite quiver]

"Mod 3 ... 2 = -1 and so 2^(odd) + 1 = -1^(odd) + 1 = -1 + 1 = 0."
I don't understand this one, can you please explain it to me ?

[swift shard]

All in mod 3, for an odd k:
2^k + 1
= (-1)^k + 1
= -1 + 1
= 0
@granite quiver

[granite quiver]

Okay i get it now, tks a lot !

[alpine jasper]

i've been stuck on this proofs for a while now, i read many many stuff on google, my note, and textbook

and i just don't fucking get it

can someone guide me through everything (inclusive) from and for k>=2 please

<@&681259820611141654>

i think you can come up with a system of linear cong. where the solution is m

idk much, sorry

[light flicker]

Publius, you should just look at the part of Ireland Rosen where they go through these things

[alpine jasper]

i did

[light flicker]

Chapter 5? I think it is?

[alpine jasper]

in fact, i'm staring at it rn

and i still don't get it

[light flicker]

It's probably easier to ask questions about that then

[alpine jasper]

does the red line assumen is either p^a or 2p^a?

since n=2 and 4 is proven already

this sentence makes think that it was assumed to be p^a only?

[light flicker]

In the first picture

They're assuming that it's not of the form p^a or 2p^a

And then going on to show that it's not cyclic

[alpine jasper]

oh...

reading is hard

i thought euler phi function is always even? why does that matter here

unit of Z/2mZ X Z/2nZ has two order two element because they're both "even" right?

i guess i gotta hope this is not one of my exam question in 30 mins

maybe i should just recite this proof

[light flicker]

Them being even implies that the groups have an element of order 2

Euler phi(m_1) is the order of

U(Z/m_1Z)

And so the order of this group is even and so it has an element of order 2

[granite quiver]

I'm wandering what is the value of the division 1 by 4 in Z9 ? Is it existed ? Because the division 1 by 4 is a fraction, therefore (1/4) mod 9 can not be an integer, however, every element in Z9 is positive integer and lower than 9.

[light flicker]

The way to define division is

That 4^-1 is the number such that 4 times 4^-1 = 1

And you can extend this idea to Z9

Since 4 times 7 is 1 mod 9

[granite quiver]

This is similar to modular multiplicative inverse right ?

[light flicker]

It's exactly that

[broken igloo]

So using (-8085) * (37797)^-1 instead?

yeah seems about right

except that 37793 != 1 (mod 65536)

what did you get?

yeah

of course 37793 and 1 are not the same mod 65536

seems about right

so the inverse is 7213

so A = 9935

what did you do?

I got B = 33885

It's -B = 42101

@acoustic plinth

hmm wait that's a bit weird

(375552931)%65536 is actually 31651

[worldly tree]

If I am given two polynomials f(x) and g(x) , what is the difference between doing polynomial long division and doing FFT style division?

[stoic bear]

FFT?

[worldly tree]

Fast Fourier Transform

So convert the f(x) and g(x) into evaluation form, IIUC

@stoic bear Is this the right place to ask this?

[stoic bear]

idk anything about FFT

If in doubt about which channel to ask, I would go to one of the 10 #❓how-to-get-help channels at the bottom

[worldly tree]

Alright thank you

[willow crest]

Hi I'm trying to understand Euclid's algorithm, I'm reading the explanation of why it works from a study guide but unfortunately I am not following (I feel like it's something stupid I just don see)

The explanation goes as follows

The HCF of the pair 207, 60 is the same as the HCF of the pair 60, 27. To
see why this is so, recall the first equation:

207 = 3 × 60 + 27. (this is the equation they are referring to)

If 207 and 60 are both divisible by an integer n, then 3 × 60 is also
divisible by n. This implies that 207 − 3 × 60 is divisible by n. So 27,
which is equal to 207 − 3 × 60, is divisible by n as well. Therefore any
factor of both 207 and 60 is alsoafactor of both 60 and 27. Using the
same kind of argument you can see that any factor of both 60 and 27 is
also a factor of both 207 and 60. It follows that the HCF of 207 and 60 is
equal to the HCF of 60 and 27.

[worldly tree]

Is there a quick way to do polynomial division, if you know the divisor is a factor?

[willow crest]

I specifically get lost when it says "If 207 and 60 are both divisible by an integer n, then 3 × 60 is also
divisible by n. This implies that 207 − 3 × 60 is divisible by n. So 27,
which is equal to 207 − 3 × 60, is divisible by n as well."

@worldly tree If the divisor is factored into monomials then you can use ruffini

[worldly tree]

@willow crest So if the divisor is a linear equation, I can use Ruffini ?

Here are some rules for GCD: https://www.cut-the-knot.org/arithmetic/GcdLcmProperties.shtml

I think the main one is that GCD(P M, PN) = P * GCD(M,N)

In your equation:

207 = 3 × 60 + 27

You know that if a number is divisible by 207, then it must also be divisible by 180 and 27

@willow crest

If I were to put this part into my own words "If 207 and 60 are both divisible by an integer n, then 3 × 60 is also
divisible by n. This implies that 207 − 3 × 60 is divisible by n. So 27,
which is equal to 207 − 3 × 60, is divisible by n as well."

If 207 = 3 X 60 + 27

Then if you know that 207 and 60 are divisible by n. Then this means that 27 is forced to be divisible by n

Whatever this number n is both divides 207,60 and 27.

So GCD(207, 60) = GCD(60, 27) = n

@willow crest Am I making any sense?

Although we have not proved n is the GCD though, but that was the intuition

[willow crest]

@worldly tree sorry I'm not following you, I'm feeling kind of dumb today. I'm getting overwhelmed with all the symbols and I get lost in the process of trying to understand what I'm reading

@worldly tree btw regarding the polynomial division I think using synthetic division in your case is the fastest way

why can we conclude that "This implies that 207 − 3 × 60 is divisible by n"? (which I know is the remainder)

[sacred junco]

That's because you end the algorithm when there is no remainder.

For a proof, you can reason backwards.

I did this in Python. I hope it's correct:

In [18]: a,b=24,15

In [19]: a,b=b,a%b;a,b
Out[19]: (15, 9)

In [20]: a,b=b,a%b;a,b
Out[20]: (9, 6)

In [21]: a,b=b,a%b;a,b
Out[21]: (6, 3)

In [22]: a,b=b,a%b;a,b
Out[22]: (3, 0)```

In the end, b is zero, and the greatest divisor is 3.

But if you know that the step n left no divisor, then you can also reason back to step n-1.

And so forth. Up until step 0, so you know it also divides the original numbers.

Just watch the algorithm in action and I think you will realize intuitively.

[willow crest]

I know how the algorithm works (applying it blindly), I understand that I have to stop when the remainder is 0, but I don't understand the specific explanation they're giving me there about why it works

[sacred junco]

Because you can reason divsibility backwards (1) and because it always gets smaller (2). (1) and (2) together are the reason for Euclid's GCD working.

[light flicker]

Maybe one explanation is that if some number d divides both a and b

Then it also divides a-b

And it also divides a - 2b and a - nb for any integer n

So that's why doing the division doesn't change the gcd

[sacred junco]

You know that a_n = b_n-1 * k from the last step, because in the last step, the remainder b is zero.

You can, inductively, reason your way up the chain and see that therefor the last a_n will also divide all previous steps.

By induction, this means that it divides both the original a and b.

[worldly tree]

@willow crest sorry missed your message; so if a number n divides 207 and 60 then it must also divide 27. If I explained this part well.

Then you can rephrase it in the way you wrote it This implies that 207 − 3 × 60 which is 27

If n divides 207 and 3 x 60, then it is forced to divide 27 which is 207- 3 X 60

As its been put above; another way to look at is:

If n divides a and b, then n is a factor of a and b .

So a = nk and b = nm , where n and m are integers.

If we look at a-b, we see that a-b = nk - nm = n(k-m) , so n also divides a-b.

We can go one step further and so a-xb = nk - xnm = n(k-xm)

So n divides a minus any multiple of b

[sacred junco]

(60, 27)
(27, 6)
(6, 3)
(3, 0)```

(thought the steps might help, not meant as explanation)

[worldly tree]

We know that n | a and n |b implies that n | a-b and n | a-kb for any k

using your example:

If we know that a number divides 207 and 60, then this number will also divide 207-k60

In your example k is 3. So this means that n must also divide 207 - 3 X 60 which is 27

So from this we know that n divides (207, 60,27, 207-k60)

We may as well use 60 and 27 to find n

[willow crest]

@worldly tree although I still don't see it put together (i'll need some time to analyze this) your explanation really helped me. thank you very much

[worldly tree]

No problem. So it's missing a part which I mentioned above. (Proving that n is indeed the GCD) there is a proof of it in a book. But If you assume this, then it should make a bit more sense

I will reformat what I was saying below this line, so it flows better for you

[sacred junco]

I think you can demonstrate one key insight in this example:

The last line tells you 6 = k3. But since 27 mod 6 has remainder 3, you know 27 = k3 + 3 = m*3. So 27 also has to be divisible by 3.

And so forth, up the chain.

You can take any portion of the tail end of this sequence and it will be a "sub-case" of GCD. Reasoning your way backwards is actually a lot simpler than forward in this case.

https://en.wikipedia.org/wiki/Euclidean_algorithm#Proof_of_validity

[worldly tree]

First we show that if n | a and n | b, then n | a-b

If n divides a and b, then n is a factor of a and b .

We can rewrite a and b like so:

• a = nk where k is an integer

• b = nm , where m is an integer.

Now lets look at a-b:

a-b = nk - nm = n(k-m)

This means that n is factor of a-b , if it is a factor of a and b. In other words, if n | a and n | b, then n | a-b

---

We can actually go further and say that if n | a and n | b , then n | xa - yb for all integers x and y. (Lemma 1)

_ How does this help with your question?_

First recall that n | a means that n is a factor of a. You want the GCD/GCF, which means the greatest common factor. So (Lemma 1) applies here. we will not show that n is the GCD/GCF, let's just assume it. Remember two numbers can have more than one factor!

_ Okay so how do we use what we now know to find the GCD/GCF in a simpler way?_

• We have 207 = 3 X 60 - 27

• We know that n divides 207 and 60. (Lemma 1) tells us that n also divides 207 - 3 X 60 = 27 . This means that n also divides 27.

• So n divides both 60 and 27.

_ Who cares if n divides 60 and 27?_

Remember we are trying to find n and instead of looking for the GCD(207, 60) we can now use GCD(60, 27) because they both equal n!

We can keep applying the same argument again, by writing 60 = m27 + r. Until r =0

Hope that helps a bit

[sacred junco]

does this work as a proof?

since a has order k modulo p it follows that a^k=1

so (aA)^k=a^kA^k=1A^k=1

so with A^K=1 i claim that A has order k

[light flicker]

what's $\bar{a}$?

[sterile pumice]

Zopherus:

[sacred junco]

or do I also need to show that this k is the smallest k?

a bar is inverse which i refer to as A

$(a\bar a)^k = a^k\bar a^k = 1 \cdot \bar a^k = 1 \mod p$

[sterile pumice]

Slate:

[light flicker]

yeah this shows that A^k = 1 as you want

but yeah, you need to show its the smallest

[sacred junco]

i think it being the smallest follows from it being an inverse?

because the inverse is unique mod p

so if k isnt the smallest and theres a smaller x which satisfies the given properties, then that x is also an inverse

but that should be a contradiction since inverses are unique up to modulo

[light flicker]

I don't see how x is also an inverse

x and k are the powers

[sacred junco]

i mean a^x is an inverse

[light flicker]

a^x is 1

[sacred junco]

actually no you're right

[light flicker]

or well, A^x is 1

[torn escarp]

assume there is a x<k, then do the same argument but switch a and A around @sacred junco

[sacred junco]

I figured it out doing just that @torn escarp thanks!

[torn escarp]

cool

[sacred junco]

n = pq with p and q distinct primes and i need to show the following congruence

$m^{1+f(n)r}=m^{1+f(pq)r}=m^{1+f(p)f(q)r}=m^{1+(p-1)(q-1)r} \mod (pq)$

[sterile pumice]

Slate:

[sacred junco]

$(mm^{(p-1)r})^{q-1} \mod (q)=m$ due to fermat

[sterile pumice]

Slate:

[sacred junco]

$(mm^{(q-1)r})^{p-1} \mod (p)=m$ also due to fermat

[sterile pumice]

Slate:

[sacred junco]

i cant guess where to take this to from here, did i start off in the right direction?

i could use chinese remainder theorem since i know mod p and mod q and combine it to mod pq but I don't think i'm ending up with m as the answer

and i dont know what the inverses would be if i tried using CRT

[light flicker]

That's all you need

If a = b (mod p) and a = b (mod q) then you have that a = b (mod pq)

[sacred junco]

🤦 i'm forgetting the basics

thanks @light flicker

[dreamy rain]

If a = b (mod p) and a = b (mod q) then you have that a = b (mod pq)

how would u go about proving that?

i cant seem to do it

@light flicker

[light flicker]

you have that pk = ql right?

[dreamy rain]

yeah

[light flicker]

think about this

and the fact that p isn't q

[dreamy rain]

alright, gimme 5min

[light flicker]

I'm timing

[dreamy rain]

lol

[light flicker]

get off discord

your time's ticking

[dreamy rain]

cant do it still, frick. i figured that pk and ql have the same prime decomporisation or whatever its called, so that might mean p/q is an integer

but yeah i dont have anything else

[light flicker]

p | ql

take 5 more minutes

[dreamy rain]

aight

hmmm, i think if p| ql and if q | pk, then p | q and l | k

intuitively, but i cant prove it

[light flicker]

can p | q happen?

both are primes, and they're not equal to one another

[dreamy rain]

if q > p

hm

nah that cant happen then

p and q arent necessarily primes though? u didnt set that condition in ur statement “If a = b (mod p) and a = b (mod q) then you have that a = b (mod pq)”?

u could have this for example

[light flicker]

ah sorry

it was part of the conversation

"n = pq with p and q distinct primes"

[dreamy rain]

ohhh, i didnt fully read it lol

oopsie

[light flicker]

should've realized that was what you were confused about

[dreamy rain]

i shall try again :P

yeah i still dont get it

do u have any other clues, doubt theres any more at this point

had a look online and its chinese remained theorem which is a popular one i think, but dont wanna spoil it lol

[light flicker]

well, now you realize that p | q can't happen right?

[dreamy rain]

ye

[light flicker]

but p | ql

[dreamy rain]

yh

[light flicker]

an important fact about primes is that if p | ab, then either p | a or p | b

[dreamy rain]

yeah that makes sense

hm

[light flicker]

so you know that p | l

[dreamy rain]

yh

[light flicker]

yeah, just write l = pn for some integer n

and you get that ql = pqn

and so a - b = pqn

[dreamy rain]

oooooooo

that works out nicely

epic

cheers

just to make sure, have i written the correct explanations for this?

[light flicker]

yep yep

You're right that this is just a special case of chinese remainder theorem

but you don't need to know about that to do this

[dreamy rain]

idk what chinese remainder theorem is lol

ill have a look later today i think

[light flicker]

This is kind of the basic idea behind it

but CRT is much stronger and general

[dreamy rain]

i see

yeah this seems like a very specific case, what i proved

[light flicker]

Basically, it allows you to split any modulus up into prime power moduli

and working with prime power modulus is almost always a lot easier

[dreamy rain]

as in if u split up the modulus into its primes, u can replace the modulus with a power of its prime and the modular equation would still hold?

or have i got that wronf

[light flicker]

Yeah not quite

How it's usually taught kind of

is like giving some example like

In a classroom, the teacher tries to form groups of 3, but two people are left over

Then the teacher tries to form groups of 5, but 3 people are left over

but then the teacher tries to form groups of 7 and no one is left over

What is the smallest number of students that the teacher could have?

[dreamy rain]

oooo, thats an interesting problem

[light flicker]

ha

maybe I won't spoil it then, you can think about it

[dreamy rain]

ya

[light flicker]

I'm sleeping soon though so you might not get a response til I wake up

[dreamy rain]

yeah thats fine

[light flicker]

This is kind of the opposite of what I was describing

this problem is more about how to combine small modulus into a single larger one

and the nice thing about CRT is that it allows you to go both ways, and both ways are often useful

[dreamy rain]

i see

yeah i didnt really get anywhere

28 and 63 are the only numbers that satisfy the bottom 2 equations, but it doesnt solve the top one, it would be silly to continue listing multiplies of 7 above 10

[light flicker]

so you know that x = 3k + 2

[dreamy rain]

yh

[light flicker]

plug that into your second equation

[light flicker]

or think about it as 3k - 1 = 0 (mod 5)

now can you solve for k?

[dreamy rain]

21?

wait

7

lol

[light flicker]

you should get a solution that only depends on the mod 5 value of k

[dreamy rain]

idk if im being an idiot, or does this work

u should be able to multiply both sides by 5 since 5 is essentially coprime to the modulus which is also 5

idk

[light flicker]

what is 15k (mod 5)?

[dreamy rain]

also u can sleep if ur tired

[light flicker]

and is 5 coprime to 5?

don't feel bad lmao, I'm still working on stuff

[dreamy rain]

ah oke

the definition of coprime is that 2 numbers have hcf of 1

5 and 5 have hcf of 5

so not cprime

lol

[light flicker]

yep

[dreamy rain]

i is idiot

[light flicker]

well

[dreamy rain]

ok

[light flicker]

you get that 15k = 0 (mod 5)

which is true I guess

not very helpful

[dreamy rain]

indeed

[light flicker]

This is related to what we were kind of talking about though

for prime modulus, all numbers have a multiplicative inverse

so there's some number you can multiply both sides by

so you just get k on the left side

[dreamy rain]

so k = 2?

or the smallest value of k would be 2

hm if k was 2, x would equal to 8, which isnt divisible by 7

[upbeat wren]

Cheap solution:

Brute force.

k = 2 (mod 3)
k = 3 (mod 5)

Use the remainder plus multiples of the larger number: 3, 8, 13, 18 ...

k = 8 mod 15

k = 0 mod 7

Brute force two: 8, 23, 38, 53, 68, 83, 98.

[light flicker]

@dreamy rain I woke up if you're here

[dreamy rain]

ye lets continue from my last message

[light flicker]

Yeah, the smallest (positive) value of k would be 2, but all solutions are 2 (mod 5)

[dreamy rain]

so how are we meant to find the value of k which satisfies these equations

its def not 2

cus subbing in 2 into the first equation, ud get x =8

[light flicker]

Well the important thing is that x = 8 satisfies the first two equations right

And we've only dealt with the first two equations so far

[dreamy rain]

oh yh

[light flicker]

So you kind of do the same thing again

We found that k = 2 + 5n

If we substitute this back in for x, we get that x = 8 + 15n

[dreamy rain]

ah yup

ill see if i can do it from here, ty

is the answer 98?

@light flicker

ill write up the method neatly gimme a min lel

its not really that much working out, i just made sure i wrote every detail in case i didnt remember if i ever come back to this

but yeah, how does this link to chinese remainder theorem

we have started with small moduli of 3,5 and 7 and ended up with a modular equation of a bigger moduli of 15

and 15 relates to 2 of those original moduli in that 3*5=15

idk where im going with this hm

[light flicker]

Yeah that's the idea

And then we combined 15 and 7 into a bigger modulus

105 which is 15*7

We had a system of equations mod 3,5,7 and we were able to combine them into a single equation mod 105

[dreamy rain]

ahhhhhh

wow thats cool

[light flicker]

yeah

and we can go the other way

split up a single equation mod 105 into three equations mod 3,5,7

[sacred junco]

can anyone explain how exponents work in modular arithmetic

like a = b (mod m)

then what can you say about a^n = b^n (mod m) or something

[light flicker]

a^n = b^n (mod m)?

is true?

What else are you asking?

[sacred junco]

no i mean

idk what i'm even asking

i just don't know how modular arithmetic works at all

like

[light flicker]

All rules of addition and multiplication really remain the same

[sacred junco]

yeah but why i suppose?

the proofs on wikipedia are very confusing

i feel like they're made for experts who have read 20 books on it already

[light flicker]

well first you have to settle on what it means for a = b (mod m)

[sullen rune]

look at anything besides wikipedia kthx

[light flicker]

also true, wikipedia isn't really meant for you to learn something new rigorously from

[sacred junco]

a = b (mod m) means that a/m and b/m have the same remainder

where the remainder is an integer

[light flicker]

Yeah it's just that there are a lot of problems with this

Or at least, a lot of work you have to do

Like, what does remainder mean?

[sacred junco]

remainder can be denoted as r, where 0 <= r < m, otherwise it would no longer be a remainder since it goes into m at least once.

and we have

a = m * k + r, where k is some integer that we're multiplying to get a

[light flicker]

How do you know that remainder is unique?

How do you know there's only one such r?

How do you know there's any such r at all?

[sacred junco]

because deg(m) > deg(r) by the remainder theorem

[light flicker]

Uh what remainder theorem?

And deg? These are just numbers

[sacred junco]

idk i only know the polynomial remainder theorem lol

[light flicker]

Yeah idk, the point is that you have to be rigorous in these things

But maybe the better definition is that

a = b (mod m) if and only if m divides a - b

[sacred junco]

don't you get that from my "definition" though?

like

a/m = integer

b/m = integer

a/m - b/m = integer - integer = integer?

[torn escarp]

didn't read previous stuff but generically a/m, b/m are not integers

it's (a-b)/m that is an integer

[sacred junco]

sorry i'm very dumb

[light flicker]

Even if you think about remainders

You have to deal with all the stuff I mentioned

[sacred junco]

i suppose what i wanted to say is

a/m has a integer remainder

b/m has a integer remainder

so (a-b)/m has to have an integer remainder

?

[light flicker]

Again, you have to deal with all the remainder stuff I mentioned

How do you know the remainder is unique and it even exists

And it's not about (a-b)/m having integer remainder, you want this to have 0 remainder

[sacred junco]

you got any videos or something like that

i could educate myself with

[light flicker]

Pick up a book

Maybe something like aops number theory

Or Silverman's introduction to number theory

[sacred junco]

@light flicker which one did you read? or both or

[light flicker]

I've only read the first one

But the second ones probably more what you want

[sacred junco]

@light flicker why is that?

[light flicker]

Aops is more meant for competitive math

And doesn't go over things super rigorously

[olive remnant]

$a^2 \equiv 1 ($ mod $n)$ What are the solutions for a?

[sterile pumice]

yohst:

[light flicker]

What have you tried?

[olive remnant]

Well I know $a^2 \equiv 1 ($ mod $p)$ if $p$ is a prime

[sterile pumice]

yohst:

[olive remnant]

ooop

not what i meant

like a plus or minus one

makes a^2 equiv 1 mod p

so i know thats like one solution

and i know that its just like what numbers are their own inverses between 1 and n-1 inclusive

[light flicker]

Yeah

if you know chinese remainder theorem, that'd help here

[olive remnant]

i only know how to use it to compute like systems of congruences(? i think they are called)

ill look into it some more

[light flicker]

Yeah, that's kind of one direction of CRT

[olive remnant]

thank u

for the hint

[sacred junco]

im stuck on (b)

Compute phi(n)

[sterile pumice]

Slate:

[sacred junco]

I understand that the final number i obtain must be converted back to a string using the A <-> 01 conversion scheme, but this doesn't seem to be a correct answer

one sec

90113200805230112182119```

thats the step calculating m?

yeah

c^d mod n

hmm

let me double check again

yeah it's 90113200805230112182119

then just add a 0 in front

how do u get that answer though i got the same number again

(2795798886831045888222263^1567443108794230900121825)%3711589008744437349643567

oh lafmaoafma

^ is xor

omg...

i forgot

what did you use to calculate it? wolfram?

python

is powmod

that much faster

than plainly typing it out?

mine is taking long

what are you doing?

(2795798886831045888222263**1567443108794230900121825)%3711589008744437349643567

yeah don't do that

it's going to multiply 279.... by itself 1567... times

I'm not exaggerating when I say it will take millenia to compute that

cool

thanks @sacred junco

np :DDDD

[sacred junco]

suppose p doesnt divide a. prove that p doesnt divide a^k

i feel like there should be a straightforward proof for this utilizing the fact that p is a prime

i have something of a mess now

since a p doesnt divide a i can write $a=px+r$ and so $a^k=(px+r)^k$

[sterile pumice]

Slate:

[sacred junco]

then i use the expansion formula to show that mod p u get a nonzero remainder

[light flicker]

that works fine

[sacred junco]

it does but its more general than it needs to be i feel like

i dont use anywhere the fact that p is a prime

and i still havent wrapped my head around primitive roots and orders and i think that this is related to those

[light flicker]

you have used the fact that p is prime

[sacred junco]

where did i use it?

[light flicker]

think through each of your steps

[sacred junco]

hey, I was studying polynomial rings when I encountered eisentein's criterion. The proof was given by contradiction. I wanted to know if there is a proof without using contradiction?

I tried searching on Google, but couldn't find any

[torn escarp]

instead of showing a contradiction with f=gh, you can instead say when you factor f into g and h, one of them is always a degree 0 polynomial, which is effectively the same but avoiding a contradiction.

[sacred junco]

oh okay

thanks!!

[sacred junco]

How do I calculate what multiples of 9 end in some number

[light flicker]

just look for a pattern

[sacred junco]

but wouldn't I miss some numbers then

like considering 9 * 7 = 63
then 3 * x = y3

[light flicker]

what

[sacred junco]

I mean wouldn't I miss some numbers if I only considered 7 and numbers that end in 1

[light flicker]

what

[sacred junco]

like 11 or 21

63*11 = 693

so 9 * 77

[light flicker]

all multiples of 9 are 9 times something

figure out what that something has to be

[sacred junco]

if you mean 3 then that doesn't help

[light flicker]

well 9 * 7 works

and the last digit of a product of two numbers, only depends on their last digits

7 is the only one-digit number that works

[sacred junco]

yeah so 9 * 7 * any number that ends in 1

[light flicker]

this misses a lot of things

[sacred junco]

yeah

[light flicker]

again, all multiples of 9 are 9 times something

and the last digit of 9 times x, is just 9 times the last digit of x

[sacred junco]

so you're telling me that only numbers that ends in 1 or 7 work?

[light flicker]

why would numbers that end in 1 work?

9 * 1 does not end in 3

[sacred junco]

nvm, I forgot that 9 * 7 * any number that ends in 1 just means 9 * a number that ends in 7

[light flicker]

kinda

but not all numbers that end in 7 can be written as 7 * a number that ends in 1

[sacred junco]

I guess

[light flicker]

anyways, you should see that all numbers that end in 7 work

[sacred junco]

Can someone explain why: Given some linear Diophantene equation $ax+by=c$ and two solutions $(x_0, y_0)$ and $(x,y)$, why $a(x-x_0)+b(y-y_0)=0$?

[sterile pumice]

Tarski:

[light flicker]

Expand out that left hand side

What do you get

[sacred junco]

$ax - ax_0 + by -by_0$

[sterile pumice]

Tarski:

[light flicker]

Okay, do you see any familiar things

[sacred junco]

Not really, but I'm guessing the next step is to change the way we group them?

[light flicker]

Yeah that might be helpful

[sacred junco]

or do we use some fact about the $gcd(x,x_0)$

[sterile pumice]

Tarski:

[light flicker]

Nope

[sacred junco]

okay let's try $ax + by -(ax_0 + by_0)$

[light flicker]

You should also think about what you know about x,y and x_0,y_0

[sterile pumice]

Tarski:

[sacred junco]

@light flicker is it true that $gcd(x,y) = gcd(x_0, y_0)$?

[sterile pumice]

Tarski:

[sacred junco]

I think that must be true

[light flicker]

Why would that be true

Look

You're just ignoring information

How were x,y and x_0,y_0 defined

[sacred junco]

oh I'm forgetting about our initial equation

that could be useful

@light flicker $gcd(a,b) = c$

[sterile pumice]

Tarski:

[light flicker]

How do you know that?

And besides, it's not relevant

There's something a lot simpler that you just seem to be ignoring

What does it mean for x_0,y_0 to be a solution to ax+by = c?

[sacred junco]

oh

so it is c - c

wow

@light flicker thanks, I'm pretty slow when it comes to number theory, I need more practice

[light flicker]

There wasn't even any number theory here

[sacred junco]

yeah this is just part of a larger problem

[light flicker]

And it's not true that gcd(x,y) = c

[sacred junco]

I'm trying to find a general expression for every integer solution in terms of x_0 and y_0

[light flicker]

For example if you have like x= 1 and y=1 then the gcd is 1 but

You can take like 5*1 + 3*1 = 8

And c would be 8

So that's not the gcd

[sacred junco]

It should be $gcd(a,b) | c$

[sterile pumice]

Tarski:

[light flicker]

That would be true yeah

[sacred junco]

okay, I need more practise

[light flicker]

Also $\gcd$

[sterile pumice]

Zopherus:

[sacred junco]

thanks

[light flicker]

And $\mid$

[sterile pumice]

Zopherus:

[sacred junco]

Okay suppose $\gcd(a,b) = d$ then $\gcd(a/d,b/d) = 1$, how can this be demonstrated?

[sterile pumice]

Tarski:

[light flicker]

Use your definitions

What does gcd mean

[sacred junco]

The largest integer $d$ s.th. $d \mid a$ and $d \mid b$

[sterile pumice]

Tarski:

[light flicker]

Okay so you want to show that no number greater than 1 divides both a/d and b/d

[sacred junco]

use a contradiction?

[light flicker]

yes

[sacred junco]

oh well if there was such a divisor then we can multiply that by d and we get a bigger common divisor of a and b right?

[light flicker]

yes

[sacred junco]

I'm way too tired to be doing this

thanks @light flicker

[light flicker]

anytime

[bronze crag]

Is quadratic reciprocity elementary number theory?

[stuck lintel]

ye

[bronze crag]

Like including proofs and stuff

Not just applications

[inner anchor]

just post the question

[bronze crag]

I don’t have a question

I was just wondering

Whether it’s considered elementary number theory

[inner anchor]

does it really matter

[bronze crag]

Idk

[inner anchor]

ive seen it in elementary number theory textbooks so thats what i would go by

[bronze crag]

Just like if I have a question about it

Cuz it’s something I’m interested in

[inner anchor]

in my very non-expert opinion it would be elementary number theory and i doubt it matters really

[bronze crag]

Ok

[native zenith]

I am using a polynomial calculator to find the gcd of two polynomials. For some reason the calculator (and wolframalpha) get x^2+x+2 as the gcd. But it says "the last nonzero remainder is " ...

Isn't the last nonzero remainder 4x^2+4x+8, not x^2+x+2?

Here is the link for the calculator https://mathsci2.appstate.edu/~cookwj/sage/algebra/Euclidean_algorithm-poly.html?fbclid=IwAR1oIyKaC8F9MTA5p7K1bh57ifwkHBlhSlP5ae095Fv2_kONvNLbduzuSGU

[light flicker]

It's kind of because it's just a constant times one anotjer

4 times one is the other

[native zenith]

yes i noticed that

4(x^2+x+2)

[light flicker]

Idk exactly what they mean

But they probably simplify if they can

[native zenith]

wolfram also got the same answer

https://www.wolframalpha.com/input/?i=gcd(x^5%2Bx^4%2B2*x^3-x^2-x-2%2Cx^4%2B2*x^3%2B5*x^2%2B4*x%2B4)

i dont know what you mean by simplify

do we simplify when we use regular integers, gcd(4,8) = 4 ?

[light flicker]

1/4 is not an integer

But it's an element of Q[x]

[native zenith]

the ring was Q[x]

or can you elaborate on that , simplify

not saying youre wrong , im stumped :/

[light flicker]

Do you know what ideals are

[native zenith]

i know examples of ideals, nZ

i would have to look at the definition to be certain

so it looks like they are simplifying. but im not sure why, or is it allowed.

[light flicker]

The ideal generated by (x^2 + x + 2) and (4x^2 + 4x + 8) are the same

[native zenith]

yes that makes sense

[light flicker]

Maybe another reasoning that doesn't appeal to ideals is that

If f divides g, then kf divides g for any rational number k

And f,g are elements of Q[x] here

[native zenith]

so with respect to Q[x], x^2+x+2 and 4x^2+4x+8 are equivalent?

[light flicker]

Yes in some sense

[native zenith]

or k*(x^2+x+2) , to generalize

[light flicker]

Changing an element by a unit doesn't change it

When you think about factorization

You normally just work up to units

[native zenith]

interesting

so we can't really analogize here from regular integers, like in gcd(4,8)

well maybe you can

[light flicker]

Well, the analogous idea is that 4 is equivalent to -4

[native zenith]

ah

[light flicker]

Or that sign doesn't matter when factorizing

[native zenith]

right

so it wouldnt be wrong to say the gcd is 4x^2+4x+8

or maybe it's preferred to use the principal ideal

thanks. i was just surprised when i saw the calculator work. clearly they are using a different 'nonzero remainder'

but not really different it turns out

[light flicker]

@native zenith no it wouldn't be wrong

Either works

[dreamy rain]

could someone give me a clue for part b

ive spotted a pattern

but idk if it can simplified or anything

i do have the answer, but dont quite wanna check yet

[inner anchor]

showing that the nth triangular number is equal to $\frac{n(n+1)}{2}$ should allow you to verify your pattern

[sterile pumice]

Pappa:

[fair dagger]

You may consider relationship between n(n+1)/2 and odd square (2n-1)²

Since you cannot use "previous triangle number" in your answer as you haven't proof if M is a triangle number or not

[dreamy rain]

the nth triangle number is just the sum to n terms, and its a common result that it equals n(n+1)/2, but ye i could derive it

and yea ill mess around with that

thank u guys

[dreamy rain]

i have no idea what i can do with this

i think its time for me to give up and check the answer lol :(

[inner anchor]

$\frac{n(n+1)}{2} + \frac{(n+1)(n+2)}{2} = ?$

[sterile pumice]

Pappa:

[sacred junco]

@dreamy rain you can solve it combinatorially

[dreamy rain]

not quite sure what combinatorially means lel

[inner anchor]

did you get it?

[dreamy rain]

nop

i solved the equation u got, and got (n+1)^2 if i recall correctly

[swift shard]

The sum of two consecutive triangular numbers is a square number. But the question is talking about odd squares

[dreamy rain]

i looked at the answer as well, but it doesnt give an explanation to how they got to it

yeahh

[swift shard]

Have a picture of the answer?

[dreamy rain]

ye

really curious to how someone would obtain this result

[swift shard]

Oh you just rearrange the result in a

[dreamy rain]

yeah

but how did they get part a

[swift shard]

But how can we be sure that works? Hrm

[dreamy rain]

part c gives a solid proof that it works

[swift shard]

"if and only if" nvm, it will clearly work

[dreamy rain]

do u know how they got the answer?

for part a

part b is just the inverse argument p sure

[native zenith]

woops, didnt mean to say prime ideal.

There is a theorem we can use.

[dreamy rain]

ooooo

what is said theorem

[sacred junco]

Hey, I have a small doubt about integral domains
Let there be 2 elements a and b of a commutative ring R with identity.
a and b are associate if there exists c such that b = ac.
And a divides b if there exists d such that b = ad.
So aren't these things basically the same?
Also, if d is a unit, then won't there exist d^(-1) such that b*d(-1) = a?
Wouldn't that mean that b also divides a?

[light flicker]

first, it's associate, not associative

and the definition of associate requires c to be a unit

so they're not the same

a,b being associate implies that a divides b and b divides a

and the reverse is true, if a divides b and b divides a, then a,b are associate

but just having that a divides b doesn't let you say that a, b are associate

[sacred junco]

oh okay, thanks a lot!!

that made it all clear!

also is your dp from tower of god?

[light flicker]

YES

its androssi

my favorite

[sacred junco]

Yup, I know her

cool

you know her real name isn't androssi?

[light flicker]

what do you mean?

like endrossi spelling wise or

oh wait, yeah I know what you're talking about

its just an alias

i wonder why

[sacred junco]

Hey, I have a small doubt

Is is always the case that <1> generates the integral domain?

[light flicker]

the ideal <1>?

[sacred junco]

yes

[light flicker]

yes

[sacred junco]

and that's not the case with rings (with identity) in general?

[light flicker]

uh, depends what you mean by ring

is it still commutative?

[sacred junco]

I'd like to know in either case

cause a lot of proofs in my book assume it in some cases, and there isn't anywhere explicitly written out

[light flicker]

then is the ideal <1> a two-sided ideal?

[sacred junco]

yes

[light flicker]

then yeah

its true for both cases

its true for all rings

[sacred junco]

oh okay thanks

I'll try to work on proof of that

[light flicker]

it really just follows straight from the definition

also you don't even need it to be a two-sided ideal now that I think about it

either sided is enough

[sacred junco]

yeah, maybe that's why the book didn't mention it

But I am having a bit trouble seeing it

[light flicker]

well, list out what ideals must satisfy

[sacred junco]

So I'll need to prove for myself, thanks a lot anyway!

oh okay got it, lol now it seems obvious that you mentioned

<1> has to have all 1*r in it

for any r in R

it will always be in commutative ring with identity

thanks again!!!

[light flicker]

yeah

[alpine jasper]

i don't understand what does the "dth powers form a subgroup" mean exactly

what's dth power?

[light flicker]

the set ${x^d \mid x \in G}$

[sterile pumice]

Zopherus:

[alpine jasper]

oh

i see

ty

[bronze crag]

${x^d \mid x \in G}$

[sterile pumice]

Duck5929:

[sacred junco]

\{

\{

[fervent crest]

So (a,b) denotes the gcd of a and b, what denotes the lcm?

[light flicker]

a \cap b

[light flicker]

@fervent crest

[fervent crest]

🤔 ok

is it standard?

[light flicker]

"standard"

I mean, you should understand that one of the big reasons that (a,b) is even used is because its the ideal generated by (a,b) in ring theory

and that (a,b) = (gcd(a,b))

in other words, the ideals are the same

[fervent crest]

Ok

I see

[light flicker]

and the correspondence ideal operation for lcm would be intersection

as in (a) \cap (b) = (\lcm(a,b))

[fervent crest]

Oh

That makes sense

But is it standard

👀

[light flicker]

probably not

[a,b] is probably more standard lmao

[fervent crest]

Lol

[last breach]

turning on ur answer

Legit best book ever: https://www.isinj.com/mt-usamo/250 Problems in Elementary Number Theory - Sierpinski (1970).pdf

[light flicker]

that's cool

https://www.math.muni.cz/~bulik/vyuka/pen-20070711.pdf

There's also this

[fervent crest]

I think A23 is pretty interesting

[stoic bear]

Both problem collections are pretty neat

[sacred junco]

I hace a really small doubt: In a ring of polynomials, an irreducible polynomial p(x) is one which can't be written as :
p(x) = f(x) * g(x)

But defination of irreducible only requires that f(x) and g(x) are not units. But there are no units in polynomials except for constant 1 and -1, so it is safe to assume that irreducible polynomials simply can't written as product of 2 polynomials?

[light flicker]

okay first, it depends on your ring if there are more units

what are the units of R[x] where R is the real numbers?

[sacred junco]

everything except 0

[light flicker]

really? what's the inverse of x then

[sacred junco]

1/x

[light flicker]

is that an element of R[x]?

[sacred junco]

oh okay sorry, only 1 and -1

I mistook for only R

[light flicker]

are those the only ones?

is 2 a unit?

[sacred junco]

ah, yes

all constants ones except 0 are?

[light flicker]

yes

In general, the units of R[x] for a ring R are just the constants which are units of R

[sacred junco]

oh okay, my question was incomplete, sorry😅

I should have said irreducible polynomials with degree greater than 1 can't be reduced in polynomials with degree greater than 1

but I see know

they can't be reduced

thanks!

[light flicker]

no wait

If you consider the ring Z[x] where Z are the integers

then the polynomial 2x is not irreducible

[sacred junco]

2x = (2) (x)

where 2 is a unit?

[light flicker]

is 2 a unit in Z?

[sacred junco]

no

[light flicker]

so then 2x is reducible

[sacred junco]

I see

thanks!

[alpine jasper]

i'm having trouble to show the order = (p-1)/d part, i tried to do the three examples first thinking that the first (p-1)/d will be unique but that was not the case

i have also tried writing out U(Z/pZ) by its generator
let a be a primitive root of p, then
U(Z/pZ)={a, a^2, ... , a^(p-1)}
rise to dth power
{a^d, a^(2d), ..., a^(d(p-1))}

idk how to precede from that tho...

@light flicker help me papa

[light flicker]

you haven't really used fact about d dividing p-1 yet

write p - 1 = dk

[alpine jasper]

hmm ok let me try that

${a^{\frac{p-1}{k}},a^{2\frac{p-1}{k}},a^{3\frac{p-1}{k}},\ldots,a^{(p-1)\frac{p-1}{k}}}$