elementary-number-theory

[craggy solstice]

he wasnt talkint to you

@prime pike leave

[prime pike]

k

[cobalt sparrow]

@craggy solstice Can you please help ?

[craggy solstice]

go back to chill

lol

@cobalt sparrow galois and number theory did

[sacred junco]

it's not that hard to see

are you familiar with the formula for phi(n)

[cobalt sparrow]

n(1-1/p1)(1-1/p2)..........(1-1/on) ?

[sacred junco]

yes

[craggy solstice]

yes

p_n btw

[cobalt sparrow]

Yea sorry

[sacred junco]

you could rewrite it as
$$\varphi(n) = n \cdot \left(\frac{p_1 - 1}{p_1}\right) \cdots \left(\frac{p_k - 1}{p_k}\right)$$

[sterile pumice]

EvilRobotOverlord:

[sacred junco]

now notice

when p1 is 2

you have 1/2 in that bracket

if it's any prime other than 2, you have an even number in the numerator

so well you can consider the case when n has a prime factor other than 2

phi(n) has to be a prime raised to 2016

okay so let's say that the prime p isn't 2

let's say it's some prime m. notice that if you want no prime other than m in phi(n), that means the power of every prime other than m in n is at most 1

does this make sense to you?

[cobalt sparrow]

Yes

[sacred junco]

okay good

now if you examine this closely, you see that each term over there has an even numerator (unless the prime is 2)

since we assumed that the prime p isn't 2, that means all those 2s have to cancel off

somehow

but there can be at most 1 two in the denominator

right?

[cobalt sparrow]

Yes . So by contradiction , there's only one solution

[sacred junco]

yeah

the 2 in the denominator occurs only when 2 is a factor of n

and if it is a factor of n, it has to get cancelled off from n in that expression

the single 2 in the denominator can't cancel off both the 2 in the n and the 2s in the other primes

[cobalt sparrow]

So we can have only 2 as a prime .

[sacred junco]

yup

[cobalt sparrow]

Like

[sacred junco]

yes

[cobalt sparrow]

@sacred junco thanks dude

[sacred junco]

np

[silent lantern]

@cobalt sparrow do you know the formula for the phi function

nvm he already explained

mb

[open cliff]

Is this true

All common multiples of a, b are of the form $k \cdot lcm(a, b); k \in \mathbb{Z}$

[sterile pumice]

ratsella:

[light flicker]

What do you think?

[open cliff]

Yes

I have been trying to prove it though

[light flicker]

What have you tried

[open cliff]

I tried a proof by contradiction

I said

Let $\ell = lcm(a, b)$. Let there be $\lambda = as = bt$ and $\lambda \nmid lcm(a, b)$. Then for some $\omega \in \mathbb{Z}$, $\omega \ell < \lambda < (\omega + 1) \ell$

[sterile pumice]

ratsella:

[open cliff]

But when I plugged back in $\lambda = as$

[sterile pumice]

ratsella:

[open cliff]

It seems like such an s exists

I guess i could try using $\ell = ak_1$ for the lower bound and $\ell = bk_2$ for the upper bound

[sterile pumice]

ratsella:

[light flicker]

Yeah I don't think contradiction is the best way here

Just doing it directly should work

[silent lantern]

there is an alternative way to do it by contradictino

suppose that not all common multiples of a,b are of the form k * lcm(a, b)

then for some consecutive integers i, i+1, there must exist i * lcm(a, b)< j *a * b < (i+1)*lcm(a, b)

@open cliff thats how i would do it by contradiction

@light flicker actually doing it by contradiction this way is kinda a 2 line proof

[light flicker]

what's the rest of the proof

[silent lantern]

@light flicker oh right you just subtract i* lcm(ab) from all 3 sides to get 0< jab - i lcm(a, b)<lcm(a, b)

this implies that there exists some k which is a multiple of ab such that 0<k< lcm(a, b)

contradiction

[light flicker]

which is a multiple of both a and b

Yeah that works nicely

[silent lantern]

hence 2 step solution

lol

[winter ingot]

why did he substitute m*k for m' (m prime) here

[versed storm]

The line above says m' = mk

[winter ingot]

oops

[candid heart]

anyone here?

[light flicker]

[light flicker]

32/5 is not a valid number mod 29

Because you don't know that 5b equal 32

Sure

Still makes no sense

You're still not seeing what's wrong with going from the fourth line to the fifth

Because you don't know why it's wrong

No, you can figure it out

Think carefully

Depends what you mean by not unique

You should probably understand what it means for two numbers to be equal mod 29

Kind of

[silent lantern]

@light flicker @supple furnace remember that problem about quadratics with rational roots we were talking about? found another solution

[supple furnace]

Yes, this is very similar to the construction I gave before

[light flicker]

I worry that tree3 judges everything I say in here

But do you guys know anything at all about complex analysis

Or just complex contour integrals

[simple mason]

@light flicker I came here to hear the rambling,and maybe to ask questions about the ramblings

[sacred junco]

same

[light flicker]

okay how much do you know about complex contour integrals

I mean, I know sto knows

[winter bear]

only residue theorem

[light flicker]

That's it

@sacred junco @empty nymph listen

[empty nymph]

omg fine

[light flicker]

Okay so

Why is Zeta function important

Or at least, why is zeta function so important in number theory

The first, kinda dumb answer you get

Is the Euler product

[simple mason]

tell us what is the zeta function in your own words first

[empty nymph]

i dont even know what the zeta function actually is

something something extend dirichlet series?

[light flicker]

zeta function is literally

$\sum_{n = 1}^\infty \frac{1}{n^s}$ for $\Re s > 1$

[sterile pumice]

Zopherus:

[winter bear]

i mean u just extend by func eqn for Re<0 , and use the alterneting for betweer 0 and 1

[empty nymph]

k

[sacred junco]

yes i have see that

[light flicker]

Oky anyways

The Euler product is that

[empty nymph]

pls put down the gun

i have hw

[light flicker]

$\sum_{n = 1}^\infty \frac{1}{n^s} = \prod_{p\ prime} \frac{1}{1 - p^{-s}}$

[empty nymph]

nice

[winter bear]

pp

[sterile pumice]

Zopherus:

[empty nymph]

-pp

[light flicker]

And this formula isn't really too hard to verify

Just by using the fundamental theorem of arithmetic

[winter bear]

yeah seen it b4

its nice

[empty nymph]

should we clap now

[light flicker]

No I'm not even close to done

Anyways, the euler product isn't super useful

And it doesn't really show at all why we care about the zeroes of the Zeta function

Like why is the Riemann hypothesis so important

And one answer is that

So the prime number theorem says that

if $\pi(x) = #$ of primes less than x

[sterile pumice]

Zopherus:

[empty nymph]

just say prime counting function

[light flicker]

Idk I wasn't sure if you knew what this is

The prime number theorem says that

[empty nymph]

[winter bear]

x/ln(x) thingy

right

[light flicker]

$\lim_{x \to \infty} \frac{\pi(x)}{\left(\frac{x}{\ln(x)}\right)} = 1$

[sacred junco]

@sacred junco let the mans speak

[empty nymph]

it means the real part i think

[sacred junco]

its real part

[empty nymph]

yay

my french grade just went up

by nearly a full point

[light flicker]

Okay

[empty nymph]

its like .2 away from 96

[winter bear]

let him speak

[empty nymph]

the entire class failed the test so the teacher is giving corrections lel

an 82

[sacred junco]

this isnt chill

[light flicker]

So

[empty nymph]

i got a 102 on the first test

[light flicker]

Uh

[empty nymph]

it was b a d

[light flicker]

Can I talk about the zeta function

[empty nymph]

idk can u

[winter bear]

yeah

sloth stop distracting, or ill kill u

[light flicker]

Okay

[winter bear]

now show me zeta zoph

[light flicker]

So

Just talk about this shit in #chill wtf

[sacred junco]

i loveo u ll

[light flicker]

Anyways the point is that

[empty nymph]

loveo u ll

[sterile pumice]

Zopherus:

[empty nymph]

prime counting function

[light flicker]

The prime number theorem says that $\pi(x) \approx \frac{x}{\ln(x)}$

[sacred junco]

where does the zets fkition come in that limit

[sterile pumice]

Zopherus:

[light flicker]

But doesn't say anything about the error

[empty nymph]

of primes less than x

[winter bear]

number of primes less than equal x

[sacred junco]

cus pi is acool number

[empty nymph]

less than equals

[light flicker]

E.g., can we bound the difference $\pi(x) - \frac{x}{\ln(x)}$ by some function of x

[sterile pumice]

Zopherus:

[torn escarp]

cause it's greek letter p and p is first letter of prime @sacred junco

[light flicker]

E.g., can we say that $\pi(x) - \frac{x}{\ln(x)} = O(1/x)$ or something

[sacred junco]

@sacred junco hes getting to that silly

[sterile pumice]

Zopherus:

[torn escarp]

@sacred junco quiet

[empty nymph]

wot is big O

[sacred junco]

@empty nymph asymptotically like

[empty nymph]

whut

[sacred junco]

like grows like that function

at infinity

[empty nymph]

o ok

does this apply to horizontal asymptotes too?

[sacred junco]

it applies to your mom

let zopj speak

[empty nymph]

zoph is dead

[light flicker]

I'm here

[empty nymph]

same thing

[sacred junco]

with the zta fuktion of course

@sacred junco "baby rudin"? Or a different book?

[light flicker]

It gets complicated here

So there's this other function that John will know

[winter bear]

whats with the side convos

[light flicker]

The von Margoldt function

[winter bear]

yep

[light flicker]

how do I spell this

[winter bear]

$\Lambda(n)$

[sterile pumice]

JohnDoeSmith:

Wolfram Alpha doesn't understand your query!
Perhaps try rephrasing your question?
Display results online and refine query

Requested by Archsys#2547

[light flicker]

$\Lambda(n) = \log p$ if $n = p^k$ for some integer $k$, and $0$ otherwise

[sterile pumice]

Zopherus:

[light flicker]

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

[empty nymph]

is p prime?

or any p

[light flicker]

p is prime sorry

[sacred junco]

prime+

[empty nymph]

FFFF

[winter bear]

smh its nt

[light flicker]

Anyways

[winter bear]

p means prime

[light flicker]

So if you consider

[sacred junco]

e

[empty nymph]

its natural log

[sacred junco]

doesnt matter

[light flicker]

$\sum_{n = 1}^\infty \frac{\Lambda(n)}{n^{-s}}$

it's e

[sterile pumice]

Zopherus:

[winter bear]

erm

n^s

[sacred junco]

archsys stfu already

[winter bear]

umm deravitive of prime zeta right?

[light flicker]

okay let me check some facts

[winter bear]

actually no nvm im dumb

[light flicker]

Oh yeah sorry

$\sum_{n = 1}^\infty \frac{\Lambda(n)}{n^s} = - \frac{\zeta'(s)}{\zeta(s)}$

[sacred junco]

two $ at the start

[light flicker]

Oh yeah whoops, anyways you hve this

[winter bear]

n^s

not n^(-s)

[sterile pumice]

Zopherus:

[light flicker]

yep

[winter bear]

right

cause lambda*1 = ln(n)

[light flicker]

Yeah

Okay now the idea is that

we can estimate this

[empty nymph]

so $\frac{\zeta'(s)}{\zeta(s)}$ bounds the error?

[sterile pumice]

hegel:

[sacred junco]

why does estimating help bind the error?

^

[light flicker]

Okay, well equivalently, the prime number theorem says that

[empty nymph]

that seems kinda odd tho cause then dont the zeroes of the zeta function cause ur error to blow up?

[light flicker]

$\lim_{x \to \infty} \frac{\sum_{n \leq x} \Lambda(n)}{x} = 1$

[empty nymph]

lmao

zoph

\infty

[winter bear]

hmm

[sterile pumice]

Zopherus:

[light flicker]

my latex skills are trolling me today

Here, the idea is that we can use something called Perron's formula

And the statement is going to say that

[simple mason]

what kind of problems can the zeta function help us solve ?

[sacred junco]

binding the error for number of primes

[empty nymph]

if thats true then

[light flicker]

$\sum_{n = 1}^\infty \Lambda(n) = -\frac{1}{2\pi i} \int_{\sigma -iT}^{\sigma+iT} \frac{\zeta'(s)}{\zeta(s)} \cdot \frac{x^s}{s} ds + O(\frac{x\log^2(x)}{T})$

[empty nymph]

wat

[light flicker]

with $\sigma, T \in \mathbb{R}$, $\sigma > 1$

[sterile pumice]

Zopherus:

[winter bear]

whats x

[sterile pumice]

Zopherus:

[sacred junco]

doesnt matter

thats just telling you the error

its of that order

[winter bear]

oh ok

[light flicker]

Sorry, $\sigma =1 + 1/\log(x)$

[sterile pumice]

Zopherus:

[light flicker]

Or, at least, we pick a sigma and get this x

Anyways the point is that now

[sacred junco]

so the integral representation works for each sigma?

[light flicker]

We have a complex integral of the zeta function

sigma > 1

[sacred junco]

ya

[winter bear]

ok am i missing something

[sacred junco]

the difference is then 1/x

[winter bear]

cause like

lhs diverges?

[light flicker]

Yeah it should say up to T

Anyways the point is that

[winter bear]

ok that makes more sense

[light flicker]

We have a complex integral now that we want to bound

And so we can use residue theorem

But we want to avoid the zeroes of the Zeta function

Since otherwise we'd pick up those residues and our estimate would be off

[sacred junco]

ya

[light flicker]

But of course, we don't know where the zeroes of the Zeta function are

So we can't shift our contour too far to the left

There are some zero free regions that we do know

And this allows us to get bounds such as

$\pi(x) = \frac{x}{\log x} + O\left(\frac{x}{\log^2 x}\right)$

[sterile pumice]

Zopherus:

[light flicker]

But knowing that the Riemann hypothesis is true would allow us to have bounds such as

[empty nymph]

wow thats my favorite bound

love that bound

[winter bear]

i mean hes prolly typing up some big bounds

lol

[light flicker]

No sorry I'm looking it up, forgot what exactly it was

[empty nymph]

hahaha

[light flicker]

I think it's just $O(\sqrt{x})$

[sterile pumice]

Zopherus:

[light flicker]

but don't quote me on that

Jk that's just worse

[winter bear]

rip

[light flicker]

Yeah I don't remember it

[empty nymph]

oof

we still accept u

[light flicker]

The point is that the Riemann hypothesis allows us to get a better bound because of contour integrals

[empty nymph]

probably

[light flicker]

And how we can shift them

[winter bear]

yeah thats nice

so main use of RH is contour integrals and nice contours for zeta?

[light flicker]

One of the uses

Yes

[simple mason]

I would like to see this solve a permutable prime problem

[light flicker]

Uh what?

[simple mason]

A permutable prime is a number which remains prime on every rearrangement (permutation) of the digits. For example, 337 is a permutable because each of 337, 373 and 733 are prime.

[light flicker]

Uh okay?

[simple mason]

it seems like a good way to put the zeta function into a practical example

[light flicker]

I mean

1. I doubt the zeta function can be used for that

2. people don't really care about those types of problems

Problems that depend on something arbitrary, in this case, the choice of the base 10 representation of the number, aren't really super deep

And also, I don't think the prime number theorem is really not-practical

It tells you how many primes there are less than some number, or in another way

It tells you approximately what the nth prime is

[cobalt sparrow]

How do I compute phi(phi(n^n)) where n isn't a prime ?

[torn escarp]

phi is multiplicative, so you break it up into the powers of primes and evaluate those and multiply the results

I don't think there's some nice formula

[supple furnace]

It’s quite messy in general, however

phi(n^n)=n^(n-1)phi(n) is the best trick I can think of here, and it doesn’t really help

[cobalt sparrow]

The problem is to phi(phi(2019^2019))

[torn escarp]

you should have just asked that

[supple furnace]

That makes things better

Use the trick I mentioned above

[cobalt sparrow]

Can you explain how you came to that ? I am studying from Burton I don't see it anywhere neither could I think of it :/

[torn escarp]

do you know how to evaluate the phi function normally?

phi(p^a) = p^{a-1}(p-1)

[supple furnace]

Think about the formula for phi(k)/k

[torn escarp]

understand that, that's all it is

[cobalt sparrow]

But @torn escarp in your case , p should be a prime

2019 isn't a prime

[torn escarp]

p is prime a is an exponent

[supple furnace]

phi(k)/k=prod p|k (1-1/p), so phi(n^n)/n^n=phi(n)/n

[cobalt sparrow]

@supple furnace no I didn't know of this

[supple furnace]

You’ve never seen the formula for phi in terms of prime factorization?

[cobalt sparrow]

Can you recommend me a good book to understand elementary number theory ? I am using Burton , and I am lost .

@supple furnace I have seen the phi(n)=prod {k=1 to n }n(1-1/pk)

[supple furnace]

That’s all I’m using above

[cobalt sparrow]

Oh yes

I thought you were using Gauss's theorem on phi functions

My bad

[supple furnace]

phi(phi(2019^2019))=
phi(2019^2018(1344))=
phi(3^2019)phi(2^6)phi(7)
phi(673^2018)=(2)(3^2018)(2^5)(6)(673^2017)(2^5)(3)(7)=(2^12)(3^2020)(7)(673^2017).

[silent lantern]

@cobalt sparrow there are quite a lot of good number theory online books online for Olympiads

Most range to a pretty complex level

Problems from elementary number theory is quite a good run through

[cobalt sparrow]

By serpinski ? @silent lantern

[silent lantern]

https://artofproblemsolving.com/wiki/index.php/Olympiad_books#Number_Theory

@cobalt sparrow the number theory section

Most of them can be found online in some form

[cobalt sparrow]

@silent lantern thanks man

[astral fiber]

]

how do we know this

where p is a prime number

and a is a natural number

sorry it should say p^a

[supple furnace]

Need more context

[astral fiber]

@supple furnace

[light flicker]

The full sentence should be

There are p^(a-1) multiples of p less than or equal to p^a

Since that's what you're concerned with when you're trying to calculate phi(n)

@astral fiber

[astral fiber]

okay but how do we know that

[light flicker]

Think about it

[astral fiber]

i hvae thought about it for a while and still dont get it thats why im asking

😭

[light flicker]

You can figure it out

Substitute some actual numbers

How many multiples of 2 are there less than or equal to 2^5

[astral fiber]

i know that its true intuitively

but i dont know how to prove it

[light flicker]

Do some math

Try the example

[sacred junco]

examples don’t constitute proof but it’s worth trying a few to see what works/what doesn’t.

[silent lantern]

@astral fiber right i think u're overcomplicating things

consider an integer 100, how many multiples of 10 are there ≤ 100

just 10

for the same reason, given an integer n= ab, how many multiples of b are ≤n

it would be a multiples

[supple furnace]

@light flicker

[light flicker]

spoiler pls

I haven't thought about it yet

[supple furnace]

Oops

Sorry

Who dmed it

[quartz gate]

How to factor x^2 + x + 2 in Z5[x]

[swift shard]

Check for zeroes, you only have 5 options

[quartz gate]

there are none

so it cant

but why cant i do this

[swift shard]

Not factorable

[quartz gate]

x^2 -4x +2

is that different?

[swift shard]

Shouldn't be

Is there a zero of that? Lol

[quartz gate]

then x^2 - 4x + 12 is also the same?

which is (x-6)(x+2) , but apparently not, and so i am confused

@swift shard am i stupid or like what is wrong ;-:

[swift shard]

No it's not? Check your factoring

[quartz gate]

waitttttttttttttttttt im actually dumb

[swift shard]

Either way I don't doubt you could actually get a factorable polynomial this way

[quartz gate]

okok

ty sir

[swift shard]

But like you said, there's no zeroes so the polynomial is irreducible over Z5[x]

[light flicker]

For any 13 integers, there are seven of them that sum up to a multiple of 7

My friend gave me this, haven't thought about it much

[silent lantern]

i think mod 91 and some pigeonhole is th best way

[rugged loom]

Anyone know anything about Mobius inversion theorem

[light flicker]

Yes

[supple furnace]

@light flicker the above problem is a special case of Erdos Ginzburg Ziv

[light flicker]

Yeah, my friends told me about Cauchy Davenport after they gave me this question

[rugged loom]

god bless

been trying to wrap my head around how to do this question

any hints on how to approach

I've tried expanding the f(x) summation and also tried apply the mobius inversion theorem to g(x) but couldnt get too far both times

[rugged loom]

<@&286206848099549185> pls halp thank u!

[rugged loom]

now that i look closer i dont think i can apply the mobius inversion theorem

since the sum is from 1 to x and not over the divisors of x

[sacred junco]

Prove that if 2xy+y^2-1|x^2 then 2x|y^2-1

[supple furnace]

@rugged loom When we sum up the gs, we’re effectively summing up terms in the form f(x/(ab)). Now add in the Mobius function. Fixing ab=n, we see that mobius(a)f(x/n) appears iff a|n, and the term associated with the sum of f(x/n) terms is f(x/n)(sum a|n mobius(a)). These terms evaluate to, by Mobius inversion for example, f(x/n)e(n), which is 0 unless n=1. Hence we get just f(x).

[rugged loom]

thanks

[rugged loom]

btw did u mean f(x)(sum a|n mobius(a)) instead of f(x/n)?

actually nvm

[upbeat wren]

Nothing important. Quick a quick theorem for thought:

Show for each odd n > 2, there are infinitely many relatively prime integers a,b,c > 2 where a^2 + b^n = c^2.

Enjoy!

Just* a quick theorem ...

[silent lantern]

^can just solve it directly

[upbeat wren]

It can be solved with some very low level tools / thoughts if that is what you mean?

[silent lantern]

just factorise

b^n=(c+a)(c-a)

so c+a=b^j and c-a=b^ n-j

and that is a generating algorithm

for infinite sets

im assuming j>n-j here

in other words, pick n, fix b (get some a and c)

fix another b, get corresponding a and c

[upbeat wren]

Ah. I had ... Let b be any odd > 2 as also is b^n. Every odd is a difference of consecutive squares so. c^2 - a^2 suffices.

[silent lantern]

hmm fair enough

[upbeat wren]

There are many proofs I'm guessing.

[silent lantern]

probably

whenever i see perfect power = difference of powers, i always jump to factorisation

(excluding fermat's last theorem) but yes

[upbeat wren]

it's been an honor to provide a bit of mathy entertainment but it's 5am here. I must go. Thanks, @silent lantern

[proud drift]

@sacred junco I attempted that problem with someone else, and he came up with the proof. I can send it to you if you want.

[sacred junco]

Thank you

Please do

[proud drift]

I can rewrite it if needed

[sacred junco]

@proud drift Why is y^2-1=2xk

You begin with the statement that its 2xl

Afterwards it changes into 2xk

[proud drift]

You can ignore 2xl. That was part of my first attempt

[sacred junco]

Ahh so why is it equal to 2xk?

[proud drift]

Y^2-1=2xk because that is the way one would rewrite 2x|y^2-1

k in this case is some integer

[sacred junco]

Yeah

But it isn't the same k
(y^2-1+2xy)k=x^2
and k2x=y^2-1 are not equivalent

You cannot have such a statement

At the very least it's wrong

[proud drift]

@sacred junco Are the x and y integers? I forgot to ask this.

[silent lantern]

ofc they r

else u can find inf solutions

[proud drift]

Okay. I will take some time to figure it out this week, and I will ping you if I think I have a solution.

@sacred junco

[unkempt nova]

continuing from #math-discussion, i have next to no idea what i'm doing when it comes to the euclidean algorithm

my lecturers have been really unhelpful

[light flicker]

Well, what do you understand and what are you confused about

[unkempt nova]

I kinda understand what it's trying to accomplish

I have no idea how to apply it

The thing I'm currently trying to do is find the modular inverse of a number

apparently I have to use the euclidean algorithm for that

[light flicker]

Well okay, explain to me what it's trying to accomplish

[unkempt nova]

Finding the greatest common divisor of two numbers?

[light flicker]

Yep

There's a related idea called Bezout's lemma

Do you know what this says?

[unkempt nova]

Can't say I've heard of it

[light flicker]

It basically says that

if you take two integers a,b

then you can find two other integers x,y such that ax + by = gcd(a,b)

Like take a = 8 and b = 18

then gcd(8,18) = 2

and so the lemma tells us that we can find integers x and y so that

8x + 18y = 2

[unkempt nova]

yeah, and you use the algorithm to solve that equation?

[light flicker]

Right

This statement, bezout's lemma

Just tells us that x,y exist, but don't tell us actually how to get them

we get them through the use of the euclidean algorithm

[unkempt nova]

right

so how would I use that to solve an equation? when i see someone do it it just feels like they pull numbers out of nowhere

[light flicker]

I mean, first understand how the euclidean algorithm works

Then try to think about how you could get these coefficients x,y out of the algorithm

[silent lantern]

@unkempt nova ok quick refresher: what is the condition for a multiplicative inverse to exist

|| a has a modular inverse mod m, IFF gcd(a, m)=1||

[unkempt nova]

in the context of a modulus?

[silent lantern]

yes

[unkempt nova]

that there's a number a^-1 such that a*a^-1 = 1?

[silent lantern]

thats the definition of a multiplicative inverse

yes

question, does 2 have a multiplicative inverse mod 10

no right?

does 7 have a multiplicative inverse mod 10?

[unkempt nova]

i think so

cause their gcd is 1 right?

[silent lantern]

hint (7*3=21=1 mod 10)

exactly

so integer a has a mulitplicative inverse mod m IFF gcd(a, m)=1

[light flicker]

Yeah idk this explanation is bad. Giving no motivation for why that fact is true is

kinda

[silent lantern]

yeah well im tryna get to the final answer lOL

Then, think about what this means regarding bezout's lemma, in this case: gcd(a, m)=1, so by bezout's lemma, there exists ax + my=1

since my=0 mod (m), so ax=1 (mod m)

[light flicker]

I mean, you have all the time in the world, there's no rush

[unkempt nova]

okay, so I want to solve ax+my=1 using the algorithm?

[silent lantern]

yes

[unkempt nova]

now the big question is
what the HECK am i doing

[silent lantern]

so what do you think the euclidean algorithm is

/ do you have any examples you could work off?

[unkempt nova]

an algorithm for solving that equation?

not really

all I really have on hand is this affine cipher exercise i gotta do

[silent lantern]

ok

[unkempt nova]

i'm trying to find the inverse of 5 mod 26

i got
26 = 5*5 + 1
1 = 26-5*5

[swift shard]

So you want some numbers x,y such that
5x + 26y = 1

[silent lantern]

so 1= 26 + (26-5)*5

and 1=26 + 21*5

[swift shard]

Very nice, Lacer has it in no time

[silent lantern]

i think that may have been more confusing to say

[unkempt nova]

i am so confused, i'm sorry

[silent lantern]

ok so quickrun through of theory

So Euclidean algorithm is about integer division

and remainders

We know that if $a, b \in \mathbb{N}$, we can write $\frac{a}{b}= q + \frac{r}{b}$, where r is some remainder and q is the quotient

[sterile pumice]

LacerNoMore:

[silent lantern]

this is just basic integer division

Now, we can multiply both sides of the equation by $b$ to obtain $a=qb + r$

[sterile pumice]

LacerNoMore:

[silent lantern]

We really do know that this last equation is possible: starting with (b * 0), then (b * 1)etc. we may subtract increasing multiples of b from a until what remains is a non-negative number less than b

this is synonymous with saying a=a-b=a-2b=a-3b...=a-nb (mod b) for all integers n

The euclidean algorithm takes this concept of integer division, and helps us find the gcd of (a, b) by a repeated application of the above division algorithm

so if i wanted to find the gcd(15, 10), I would do:

15=(10)(1) + 5

10=5(2) + 0

but we are done here because the next iteration gives 5=0 + 5

so the gcd would be 5

similarly, to find the gcd of (5, 26), i would do:

26=5*5 + 1

5=1*5 + 0

so the gcd would be 1 in this case

but due to ways in which multiplication and addition in mods are done in the same manner as integer, we can do 26=5*5 + 1

1 (mod 26) =26 (mod 26) - 5*5 (mod 26)

1 = 26 + (26-5)(5) (mod 26)

I have essentially added 26*5 to both sides mod 25 which doesnt change the value of either side, but allows us to turn the -5 into a 21, which will be the inverse of 5

@unkempt nova sorry for the wall of text

[astral fiber]

]]

any clues?

[unkempt nova]

i'm a little confused about how you get -5 from that

[silent lantern]

@unkempt nova oh right -5=21 mod 26 ?

[unkempt nova]

like, i understand it's from 26-5*5

[silent lantern]

right from our algirthm, we had 26 + (-5)*5 = 1

if that makes it clearer

and so we reduce it mod 26, which gives 0 + (-5)(5)=1 mod 26

but -5 is just 21 mod 6

[unkempt nova]

so because it's all mod 26, 26 just becomes 0?

[silent lantern]

yes

thats the idea

sorry for the long-winded explanation

[unkempt nova]

right, that helps a fair bit

thank you

[silent lantern]

@astral fiber ok so m|(a-b) and n|(a-b)

agree?

can you see how this implies that mn|(a-b) and so a=b (mod mn)

think about if p|x and q|x, then pq|x where p, q are primes

[astral fiber]

ahhh thanks

[unkempt nova]

so for an affine cipher i have an enciphering key of [5,7] and i found the deciphering key to be [21, 9]

does that sound right?

so i've got x≡21(y-7) mod 26

but that isn't the same as x≡21y+9 mod 26?

do i need to simplify it?

7y+3 mod 26?

[swift shard]

How does an affine cypher work? Sounds cool. What's the source?

[unkempt nova]

It's something I have to learn for my applied maths class

it's boring

Basically, assign each letter in the alphabet a number

then the cipher is ax+b mod 26 where x is the letter

[swift shard]

Oh IC. [a,b] = [5,7] in this case?

So you start with the letters
a = 1, b = 2, c = 3, d = 4...?

[unkempt nova]

Yeah

No, a is 0

[swift shard]

Oop yeah that makes sense

[unkempt nova]

but yeah, that's how it goes

[swift shard]

So you have
5x + 7 = y (mod 26)

[unkempt nova]

mhm

[swift shard]

5x = y - 7 (mod 26)
5x = 105y + 45 (mod 26)

That part trip you up?

[unkempt nova]

so i've got y = 21(x-7) = 21x+9

what the

[swift shard]

I can explain it in pieces
y = 105y (mod 26)

Simply because 1 = 105 (mod 26)

I can replace that 1 with a 105 anywhere I see it

[proud drift]

@sacred junco Hello! I need to know if the statement you want the proof for was from a textbook?

[sacred junco]

No

[proud drift]

Is the statement a claim you devised yourself?

@sacred junco

[craggy solstice]

.

[wind gulch]

How can I prove that sqrt(a^2 + 1) is not an integer when a is a positive integer?

[woeful trellis]

Hmm, try a proof by contradiction?

Let a be any natural number and let there exist a natural number b such that b^2 = a^2 + 1

[wind gulch]

Thanks

[wind gulch]

Im stuck. Do I have to work with prime factorization?

[woeful trellis]

Well okay.

b^2 -a^2 = 1

(b-a)(b+a) = 1. Since b is a natural number & a is a natural number, what can be said about the two factors?

[wind gulch]

Also a natural number?

Thus its not equal to one unless both factors are one

[woeful trellis]

Well, if a is a positive integer, then it's a natural number, with the possibility of it being 0.

Well, (1)(1) = (-1)(-1) = 1

So both factors have to be 1 or -1

Right?

[wind gulch]

Yes

[woeful trellis]

Then what can be said further about a & b?

[wind gulch]

If both are natural then they can be only be 1 but b^2-a^2=1 with a and b being 1 means that 0=1

[woeful trellis]

a + b = 1

b -a = 1

Hence, 2b = 2 & b = 1. Hence, a = 0. Hence, you have derived specific values of a& b where it's true. Since, you assumed that a was an arbitrary number, it means that any attempt at deriving a & b (generally) such that the conditions you want hold is going to yield a very specific solution.

In other words, there are no other solutions.

[wind gulch]

How do I get to
2b = 2?

[woeful trellis]

They're linear equations. Add them.

[wind gulch]

Oh I get it now

Damn. Thanks

[woeful trellis]

🙂

[wind gulch]

Is there an easy way to prove that the square root of 2 ^ x + 1 where x is a natural number is not an integer?

[woeful trellis]

No. Let x =3

[wind gulch]

Is there a number that can replace 2 so that it won’t work?

[light flicker]

1

[wind gulch]

will there be a solution for every number except 1?

[woeful trellis]

Huh? Okay, you have to phrase your statement in a better way. What exactly is it that you're asking?

[wind gulch]

is there a number for a in sqrt(a^x+1) where for every x (natural number) the solution is not an integer? a =! 1

[light flicker]

There are plenty of others

Use the fact that you just proved

[wind gulch]

something along these lines?

[sacred junco]

does anyone know a good book on really basis number theory

like dividing stuff and modular arithmatic

and gcd and lcm, euclidean algorithm

[stuck lintel]

104 number theory problems by titu andreescu is pretty nice

[jade latch]

lmfao

titu andreescu

[sacred junco]

thanks 🙂

[upbeat wren]

Throwing out another problem if anyone is interested. Let c be exactly one googol. Let a,b both be positive whole numbers where ac and c/b are perfect cubes. What is the LEAST number of cubes from c/b to ac inclusive?

[light flicker]

Uh, is this even doable? Like it's easy to figure out what a and b should be, but to count the number of cubes in that interval?

[upbeat wren]

It's not bad,I think?

ac once found should be easy to take the cube root of?

[light flicker]

oh I'm dumb, of course

[upbeat wren]

No. I'm dumb. And I hehe.

But seriously I often make up problems with mistakes. It happens.

[stuck lintel]

What’s wrong with titu andreescu ?_?

[versed storm]

He has a cold

[rugged loom]

not really understanding this proof for why there are no such integers such that ϕ(n)=n/4

[light flicker]

What are you confused about

[sacred junco]

how can i prove (c)?

the book says that these are basic properties

from the definition

i dont think any of these are basic besides the first one

[stoic bear]

2nd is simple

Think about it like this

If we take out the gcd, then the residue factors are coprime/have gcd = 1

[sacred junco]

what is residue?

[stoic bear]

Leftover, kinda bad wording there

Try an example

Like 27 and 18 are m and n

gcd is 3^2

27 = 9 x 3 and 18 = 9 x 2

3 and 2 are coprime

[sacred junco]

i see that but how would i prove it in general?

i used contradiction but i think its too complicated

[stoic bear]

Nope, contradiction is the proper way to go

[sacred junco]

oh

[stoic bear]

Basically, if m' and n' are NOT coprime, then you could've taken out another factor in m and n

[sacred junco]

is (c) also by contradiction?

[supple furnace]

This is roughly equivalent to Bezout’s Theorem

This is where unique factorization becomes so powerful by the way. You basically have to get to unique factorization to prove this result.

[stoic bear]

Really nice how the simple things that people take for granted as "obvious" can be so powerful

[sacred junco]

how do i prove this?

s' = m/s and t' = m/t
gcd(s', t') = gcd(m/s, m/t)

because we are taking numbers out of the lcm they will share no other divisors so it must be 1?

does this work? it is kind of informal

[sacred junco]

what is wrong with my proof

of

if n in Z and m | s, then lcm(m,n) | s

say lcm(m,n) = e. Then m = ek for some integer k. Since m | s, ek | s so e | s

but this isnt true so my proof must be wrong right?

wait

i think im confusing gcd and lcm

[serene socket]

Let me look

What are you proving

if n in Z and m | s, then lcm(m,n) | s
is false taken at face value

[sacred junco]

nvm

i was confusing lcm with gcd

[sacred junco]

im stuck on this

say e = lcm(m,n)

then m | e and n | e

but i dont know how to connect e and s

[serene socket]

Hint: $e$ is the \emph{least} common multiple of $m$ and $n$

[sterile pumice]

Icy001:

[sacred junco]

hmm

im not sure how to use that

[quartz gate]

T/F Quick one: Only [1]

<@&286206848099549185>

@sacred junco the lcm of m and n is divisible by both m and n

[serene socket]

You could just test each element of $\bZ_6$ manually

[sterile pumice]

Icy001:

[sacred junco]

i have s = mm' and s = nn' as m|s and n|s
since m|e and n|e, e=mm'' and e=nn''
so m=e/m'' then s=e/m'' m' so e|s

but i think this is wrong because i didnt even use the n

[serene socket]

$\frac e{m''}m'$ isn't necessarily divisible by $e$

[swift shard]

m (mod n) has a multiplicative inverse if m and n are coprime

[sterile pumice]

Icy001:

[sacred junco]

oh

[serene socket]

I have a simple proof which is definitely not what your professor expects

I'll give it and then you see how you can modify it

[sacred junco]

okay

[serene socket]

We have $e\leq s$ since $e$ is the least common multiple of $m$ and $n$ while $s$ is a common multiple of $s$ and $n$. Now if $e\nmid s$, then $\gcd(e,s)$ has the following properties:
\begin{itemize}
\item $\gcd(e,s)<e$ and $\gcd(e,s)<s$
\item $m\mid \gcd(e,s)$ and $n\mid \gcd(e,s)$
\end{itemize}
Hence $\gcd(e,s)$ is a common multiple of $m$ and $n$ which is smaller than $e$, contradicting the minimality of $e$

[sterile pumice]

Icy001:

[sacred junco]

is there a direct proof? this is kind of confusing

[serene socket]

Yes I was about to say

Let $e'=\gcd(e,s)$. Then $m\mid e'$ and $n\mid e'$, so $e'\geq \operatorname{lcm}(m,n)=e$. The only way this is possible is if $e'=e$, hence $e\mid s$.

[sterile pumice]

Icy001:

[swift shard]

Oh my bad icy I didn't realize you were proving it

Isry

[serene socket]

I'm confused, what'd you do?

[swift shard]

I spoiled it without proof

Oh wait no nvm

[sacred junco]

why is e' >= lcm(m,n)?

[serene socket]

by minimality of the lcm

and the fact that e' is a cm

(common multiple)

[sacred junco]

oh i see

[serene socket]

basically I used the definition $\text{lcm}(m,n):=\min{x\in\bN:m\mid x\text{ and }n\mid x}$

[sterile pumice]

Icy001:

[sacred junco]

im confused about the e'=e part

[serene socket]

So $e'$ was $\gcd(e,s)$. And we have $e'\geq e$, in other words, $\gcd(e,s)\geq e$. How can the greatest common divisor of a two numbers be greater than or equal to one of the numbers?

[sterile pumice]

Icy001:

[sacred junco]

ohh i see

[quartz gate]

how do i get the remainder of 8^(9^7) divided by 11

<@&286206848099549185> can you give me the first step?

[shadow steeple]

might help:
https://en.wikipedia.org/wiki/Modular_exponentiation

[serene socket]

First step is to determine the order of 8 in $(\bZ/11\bZ)^\times$

[sterile pumice]

Icy001:

[serene socket]

This language isn't elementary so I'll say it another way; Determine $\min{n\in\bZ^+\colon 8^n\equiv 1\pmod{11}}$

[sterile pumice]

Icy001:

[quartz gate]

kinda still confused

[rugged loom]

could someone pls help me understand how to get the even part for this, the odd was sort of straightforward but having trouble with the even

[quartz gate]

is n = 10 by Fermat's little theorem @serene socket

[supple furnace]

@serene socket a more intuitive approach is the following: let s be the lcm (minimal) and let r be another multiple not divisible by s. Then k=r mod s is nonzero and less than s. Since m,n|k, we’re done.

[serene socket]

$r\mod s$ when they haven't gone over modular arithmetic yet

[sterile pumice]

Icy001:

[supple furnace]

Call it the remainder then

[serene socket]

The fact that there exists a representative of the equivalence class of r mod s that's between 1 and s-1 is surely not covered at this point though

[quartz gate]

i am very very very confused

why does 8^n = 1 mod 11 appear

[serene socket]

It's because the remainders of $8^n$ when divided by 11 form a periodic sequence

[sterile pumice]

Icy001:

[serene socket]

and the period is the first positive integer $n$ for which $8^n$ has a remainder of 1

[sterile pumice]

Icy001:

[supple furnace]

I mean the proof uses nothing fancy

[quartz gate]

the period

why is it the first and not the second?

[serene socket]

Division with remainder is fancy from the point of view of a grounds-up number theory class

like

[supple furnace]

Most of the stuff at this point is well ordering

[serene socket]

That's how you ultimately relate the two notions of gcd

And I think he's just working with one of them for now

[supple furnace]

The first nontrivial result is Bezout

Which is fancy well-ordering (ideals)

But yeah, I shouldn’t be assuming too much I guess

The result r|a,b implies r|gcd(a,b) is an interesting corollary

[quartz gate]

im sorry...

uh

how do i start?

[serene socket]

If you count the first as 0, then you can call the period the second

[supple furnace]

@rugged loom Partition the sum into sub-sums by the largest odd divisor. Then you just have to show that totient(2^rk)-totient(2^(r-1)k)-...-totient(k)=0 (n is assumed to be at least 1), but totient is multiplicative and k is odd, so this simplifies to (2^(r-1)-...-1)totient(k)=0.

[serene socket]

Ok you don't need to find the period @quartz gate

It turns out the period is the maximum it can be anyway, which is 10

[quartz gate]

ok

i d k what u mean, but okay

[serene socket]

You know that $8^{10}\equiv 1\pmod {11}$ by Fermat's not last theorem

[sterile pumice]

Icy001:

[quartz gate]

yeah

yes ik that

[serene socket]

Therefore, $8^{10a+b}\equiv 8^b\pmod{11}$ for any $a,b\in\bN$

[sterile pumice]

Icy001:

[supple furnace]

@serene socket wait have you seen the well-ordering proof for Bezout? It’s pretty nice

[quartz gate]

why is that

[serene socket]

Well, it follows from the previous fact

I won't spoil it

[quartz gate]

oh ok i get it now, the a is just 1^a, and the b is 8^b

[serene socket]

All proofs use well-ordering and the non-trivial aspect is that $\bZ$ is a Euclidean domain isn't it?

[sterile pumice]

Icy001:

[supple furnace]

Yes

But that’s fine here

Also, there is a way to revamp things for proving the general fact for gcd ideals in Bezout Domains.

[serene socket]

Well I can say this is the first time I've heard of a Bezout domain

[rugged loom]

@supple furnace thanks for the response but kind of confused, why 2^n and not something like 2^n/k

[supple furnace]

Well all the numbers that have largest odd divisor k are in the form 2^nk

[rugged loom]

oh ic

n isnt the original n from the question i assume lol

[supple furnace]

Yeah bad notation

But solution works

[rugged loom]

tru tru, had to check back and confirm but ye it works, thanks for the help

i would defo not be able to come up with that on a test tho

also having trouble with this if anyone could chip in would appreciate it

[serene socket]

v = ?

[rugged loom]

total number of positive divisors

so v(6) = 4 (1,2,3,6)

[serene socket]

Oo

Ok here's a big hint

[rugged loom]

my approach for these questions were just to split them up into the prime factors and work from there but not sure that works here

[serene socket]

Make an injective map that sends a divisor of $n$ to a divisor of $2^n - 1$

[sterile pumice]

Icy001:

[serene socket]

you have to figure out what the map is

[rugged loom]

hmm ic, i'll try that out

[quartz gate]

if ax = b (mod m)
and the gcd(a,m) = 1
then there is only one solution of x, right?

[serene socket]

yes (mod m)

[rugged loom]

is there some propert of 2^n - 1 i can utilize to get an idea of what the divisors would look like

[serene socket]

Try to factor it in more than one way

[quartz gate]

x^ 10 can become x^3 when dealing with mod 7

?

[stuck lintel]

no

what does FLT say?

[quartz gate]

x^(p-1) = 1 mod p

[stuck lintel]

okay so, in this case what's p-1?

[quartz gate]

6

[stuck lintel]

so x^6 = 1

[quartz gate]

oh

so x^10 can become x^4

[stuck lintel]

ye

[quartz gate]

because x^6 is 1

ohhhhhhhhh okokok

then

x^26 can become

uh

x^2

because 6*4 = 24

so we have 40x^2 + x + 1 = 0 mod 7

then i can sub in 0 to 6, and check if 0

0 is false, 1 is true, 2 is true, 3 is true, 4 is ... is there a faster way of doing this

@stuck lintel

[supple furnace]

@rugged loom there is

Use x-1|x^r-1

[rugged loom]

in this case x = 2 no, does that help much

[supple furnace]

You let x be a power of two

I don’t want to spoil the whole thing

[rugged loom]

o

[supple furnace]

Progress?

[rugged loom]

not really

[supple furnace]

Plug in x=2^d

What do you get

[rugged loom]

2^d - 1| 2^dr-1 ?

[supple furnace]

Yes

Now what do you want r to be

[rugged loom]

n/d?

[supple furnace]

Yes

So if d|n, 2^d-1|2^n-1

This gives the injection
d->2^d-1

[rugged loom]

ahhhh

so for every factor of n, theres a divisor for 2^n-1

end of proof?

[supple furnace]

Yes

Since it’s an injection, we get one divisor of 2^n-1 for each divisor of n.

Hence v(2^n-1)>=v(n)

You can prove much better bounds using cyclotomic polynomials (totient function comes up here).

[rugged loom]

ahhhh i see, makes sense i guess, its been long since ive seen a proof using injections but gotta make sure to take note of the method

thanks guys

[supple furnace]

Keep posting if you need help

[rugged loom]

💯

[sacred junco]

i think this is really basic but im not sure how to actually prove it

prove that s | lcm(ns, nt)

wait it this right?

s | ns and ns | lcm(ns,nt) so by transitivity s | lcm(ns,nt)?

[rugged loom]

seems correct to me

[sacred junco]

thanks 🙂

[rugged loom]

how would i use the chinese remainder theorem to solve c)

so far i split it into 3 equations, 46mod3, mod 5 and mod 7

then i have x^2=1mod3
x^2=1mod5
x^2=4mod7

how do i apply CRT from here

[serene socket]

How do you usually apply CRT and how is it different with 3 primes

[rugged loom]

3 primes i guess we expect 2 or no incongruent quadratic residues for each prime

nah thats not what u mean im guessing

i mean from that point in the CRT, regularly we would find M1, M2, and M3, and then do M1=1mod3, M2=1mod5, M3=1mod7 to find x1,x2,x3

and then use those to get the final answer as
x=M1x1b1+M2x2b2+M3x3b3mod M

not sure what changes with quadratic residues though

[serene socket]

Nothing should change

[rugged loom]

felt like i went in a circle tho, the final x i obtained was 151mod105 which is the same as 46mod105

[light flicker]

That shouldn't be one of your answers though

46 squared is not 46 mod 105

[rugged loom]

how do i get the residues from this process

[serene socket]

how did you obtain 151 exactly

[rugged loom]

this number M1x1b1+M2x2b2+M3x3b3

[serene socket]

what's M1, x1, and b1?

[rugged loom]

in this case, M1 is 35, x1 is 2, b1 is 1, M2 is 21, x2 is 1, b2 is 1, M3 is 15, x3 is 1, b3 is 4

[serene socket]

I mean what they stand for

what is their purpose

[rugged loom]

oh there for computing the unique solution modulo M for the system of equations

[serene socket]

Yes and what is M1, what is x1, and what is b1

what are their roles

Alright let me help you here

[rugged loom]

ye lol im lost

[serene socket]

CRT is the theorem that the canonical map $\phi\colon \bZ/(pqr\bZ)\to (\bZ/p\bZ)\times(\bZ/q\bZ)\times(\bZ/r\bZ)$ is a ring isomorphism, where $p,q,r$ are distinct primes in our case

[sterile pumice]

Icy001:

[serene socket]

$\phi$ being defined as $x\mapsto (x\mod p,x\mod q,x\mod r)$

[sterile pumice]

Icy001:

[serene socket]

The inverse of this map $\phi$ is what you want to construct, and it requires manually computing $\phi^{-1}$ of some basis of $(\bZ/p\bZ)\times(\bZ/q\bZ)\times(\bZ/r\bZ)$. Usually the basis chosen is $(1,0,0),(0,1,0),(0,0,1)$. So define $x_1:=\phi^{-1}(1,0,0),x_2:=\phi^{-1}(0,1,0),x_3:=\phi^{-1}(0,0,1)$

[sterile pumice]

Icy001:

[serene socket]

The solution would be $\phi^{-1}(a,b,c)=x_1a+x_2b+x_3c$ where you can choose any arbitrary lifts of $a,b,c$ to $\bZ/(pqr\bZ)$

[sterile pumice]

Icy001:

[rugged loom]

i dont fully understand all the concepts but the concept of computing the inverse kind of makes sense i guess

given when i did the CRT outright i just got back to where i started from

[serene socket]

well let's see

$\phi^{-1}(1,0,0)$ is the number $x$ in $\bZ/(pqr\bZ)$ such that x is 1 mod p, 0 mod q, and 0 mod r

[sterile pumice]

Icy001:

[serene socket]

So It should be (inverse of qr mod p) times qr

Ah so that's probably your mistake

You have to take the product of the rest of the primes

instead of just one of them

[rugged loom]

so if my 3 primes are 3,5,7

[serene socket]

the solution to a mod 3, b mod 5, c mod 7 would be

a * (inverse of 35 mod 3) * 35 + b * (inverse of 21 mod 5) * 21 + c * (inverse of 15 mod 7) * 15

rather than

well whatever you did

Hm

in this case, M1 is 35, x1 is 2, b1 is 1, M2 is 21, x2 is 1, b2 is 1, M3 is 15, x3 is 1, b3 is 4

I think you did it right actually

M1 would be the product of the primes, x1 is the inverse of that mod the remaining prime

Your mistake is that you took the squares for the bi rather than the square roots

Hehe...

like your b3 was 4

it should've been +/- 2

and b1 should've been +/-1

and b2 should've been +/-1

[rugged loom]

ahhh ic

so for each combination of those id get a unique solution, for a total of 6 which i should have

[serene socket]

you mean 8

[rugged loom]

8?

[serene socket]

Yes

2 options for each of b1, b2, b3

gives 8 total combinations

[rugged loom]

oh true

ahhh this makes alot more sense now

thanks!

[serene socket]

No problem, even though I re-derived all of CRT while trying to help

[rugged loom]

loooool, it was pretty nice seeing the derivation since we never really did that in class, prof only gave us a proof of the theorem and algorithm

[serene socket]

Did he explain that the xi's are the multiplicative inverse of the Mi's mod the unused prime?

how'd he explain it

[rugged loom]

it was kind of long, but basically he started by obtaining Mi =M/mi (M is the product of all the primes) , then he showed that (Mi,mi) = 1 (since all the mi's are relatively prime) then he claims the equation Mix=1modmi has a solution xi = b1M1x1+...., and he shows this is true cause for example each Mimodm1=0modm1 except for M1xmodm1 which is = 1modm1, subbing into the equation x=bi*1+0+0...modmi for each of em, so satisfies the equations

really bad explanation on my part lol

the proof was kind of informal tho, lots of visuals since its an intro course

[serene socket]

That's pretty accurate

[rugged loom]

ahh ok my prof knows his stuff then lol

last question, if one of my bi's were not perfect squares how would i go about doing this, do i just say theres no quadratic residues?

[serene socket]

Yep

[supple furnace]

Bezout leads to quick proof of CRT

Plus it explains why the formula is what it is

[serene socket]

Hm a simple proof of CRT is to show that $\phi$ is a ring homomorphism, that it's injective and that both sides have the same cardinality

[sterile pumice]

Icy001:

[serene socket]

Like, CRT is just the statement that $\phi$ is a ring isomorphism

[sterile pumice]

Icy001:

[rugged loom]

i have no idea what those mean lol