elementary-number-theory

[stuck lintel]

i didnt read the full conversation but isnt that literally bezouts identity

[native zenith]

thats my hypothesis

[north pagoda]

if you've ever seen the word "divides" before

[native zenith]

well a | b if b is a multiple of 'a'

[north pagoda]

yes.

[light flicker]

anyone can write on brilliant lmao

[native zenith]

lets say, m | n iff m is a multiple of n*

[stuck lintel]

also elementary number theory is accessible to even middle schoolers lol

[native zenith]

thats true

[north pagoda]

lets say, m | n iff m is a multiple of n*

other way around

[light flicker]

And if you actually look at what we did

[vast dove]

does brilliant pay you for writing??

[native zenith]

oops

[light flicker]

it was just one step

to do the necessary part

[native zenith]

well i wouldnt leave it out if i wrote it

[sacred junco]

sure hope brilliant pays their authors, it's a paid platform

[native zenith]

im not reading anymore brilliant.org , done with this

[light flicker]

You could've figured that out on your own honestly

[native zenith]

they could have said (leave steps for reader)

[light flicker]

It was just one step

That's what's implied

[native zenith]

oh really

[stuck lintel]

also you should try reading an actual book on number theory

[light flicker]

And people who are familiar with proofs understand this

[native zenith]

oh ok ill keep that in mind for the future

proof steps are implied. why even bother proving

just say 'bah the steps are implied'

[light flicker]

Like I said

[sacred junco]

the trivial ones are

[north pagoda]

educational resources often include these sorts of things to make sure the reader actually understands what's going on

[light flicker]

"Yes there are a lot of logical gaps here, but they are logical gaps that you could fill in if you understood what they were saying
And that's why people leave logical gaps, so the reader can check that they're understanding what's happening in the proof"

[native zenith]

right zopherus , but as i said this is targeted to under-undergrads.

[north pagoda]

👀

[native zenith]

if it's a college number theory book i couldnt care less. but this is targeted to high schoolers

[light flicker]

and high schoolers could have figured that out

@stuck lintel is a high schooler

[north pagoda]

so should high schoolers have their hand held in every step of anything ever?

[light flicker]

The point isn't the age, it's the familarity with these ideas

[native zenith]

"We already know that this condition is a necessary condition" but no we don't you have to prove that

[north pagoda]

when solving 3x + 5 = 2x - 9, do you expect a high school textbook to go

[light flicker]

You seemed to struggle with the idea of substitution, and that's not really the level they're writing for

[north pagoda]

3x + 5 = 2x - 9
3x + 5 + 9 = 2x
3x + 5 + 9 - 2x = 0
3x - 2x + 5 + 9 = 0
(3-2)x + (5+9) = 0
1x + 14 = 0
x + 14 = 0

[sacred junco]

bruh isn't it obvious, d divides a and b, d divides ax, d divides by, so d divides ax + by

[north pagoda]

like no high school textbook is gonna write

all thsoe steps

[native zenith]

yes its obvious now

[north pagoda]

because they expect the reader to be familiar

[native zenith]

but thats the point of a proof, to make reasoning transparent

[north pagoda]

and if the reader isnt familiar, that suggests the reader needs to spend more time to figure it out themself

[native zenith]

its not bezouts identity, technically

[north pagoda]

because otherwise they cant truly understand

[native zenith]

perhaps blame it on the reader

[light flicker]

It would be transparent, if you had the experience needed

Also

https://brilliant.org/wiki/linear-diophantine-equations-one-equation/

[sacred junco]

if it's too transparent you fall asleep reading the proof

[light flicker]

This is the previous article

where they prove it

[native zenith]

yes but brilliant says they are beginner friendly. oh well

[light flicker]

And that's why here, they say "we already know that"

[native zenith]

prove what

bezouts identity

do i have to mind read now?

[light flicker]

prove the necessary conditio

[north pagoda]

from zophs link

[native zenith]

more mind reading, yikes

[stoic bear]

mind reading what?

[native zenith]

yes we were proving that

[light flicker]

That's why they say "we already know that"

[sacred junco]

is there a way to prove bezouts identity other than "bah use euclids algorithm"

[native zenith]

i dont know what 'it' refers to

[light flicker]

Because they proved it in the previous article

[native zenith]

we are not proving bezouts identity,

nice, more confusing

[sacred junco]

well im sure there is but is there a nice and short one

[native zenith]

more confusion*

[stoic bear]

about what

[native zenith]

bezouts identity can be proved using well ordering blah blah

[stoic bear]

You are arguing about the word 'it'?

[native zenith]

no, i wasnt sure what 'it' referred to

[north pagoda]

like ok heres the thing

every article ever is gonna have prereqs

if you open up a calculus textbook

to page 200

[light flicker]

They prove the necessary condition

In this article

[north pagoda]

and start complaining that you dont know what dy/dx means

youre not gonna get any sympathy

same thing applies to online resources

[native zenith]

thats true. but heck this is not a necessary condition.

when someone says, X is a necessary condition, and it isnt, thats a lie. you can derive it, but thats not the same thing

[light flicker]

What the actual fuck

Okay I'm drinking bye

[native zenith]

it can be easily derived

[stoic bear]

[light flicker]

You shouldn't do math honestly

[north pagoda]

...

[native zenith]

what part of necessary condition doesnt make sense?

[sacred junco]

what are you intending to say by "necessary condition"

[north pagoda]

do you know what a "necessary condition" means

[light flicker]

You really can't think logically

[native zenith]

i think so

[stoic bear]

zoph, phd in crankery

[vast dove]

zoph

[native zenith]

i dont care if you give up. thats your choice

[north pagoda]

A is a necessary condition for B, if B => A

[vast dove]

dont drink too much

[light flicker]

you should give up to

[north pagoda]

you need to actually prove that B => A

to know that its a necessary condition

[native zenith]

yep

[sacred junco]

or neg A => neg B

[north pagoda]

(or prove an equivalent statement, like notA => notB)

[native zenith]

did you actually read the article?

[sacred junco]

get sniped

[native zenith]

https://brilliant.org/wiki/bezouts-identity/

[north pagoda]

yes; did you read the article before it?

[native zenith]

yeah i was just referring to the part where it says ' this is a necessary condition' it is not

what does that have to do with anything?

yeah i will, thanks

[north pagoda]

what do you mean "it is not"

[light flicker]

@sacred junco no I'm telling this guy to give up math

[native zenith]

because bezouts identity doesnt say that

[sacred junco]

salty zoph

[vast dove]

fuck

[north pagoda]

[native zenith]

no thats not the article

[north pagoda]

thats from the previous article

like when you're saying "k*gcd(a,b) can be expressed as ax + by is not a necessary condition"

[native zenith]

nobody is expecting hand holding. i think you missed the point i was making. its ok.

[north pagoda]

you're implying that there's a counterexample

so either you phrased your point wrong

or youre fundamentally misunderstanding

what "necessary condition" means

[native zenith]

i am "proving ax + by = z has solutions iff z is a multiple of gcd(a,b)" at least thats what is purported to be happening. the author uses N and then changes his mind

[north pagoda]

the author... doesnt change their mind, N represents the entire set

[native zenith]

i meant doesnt use the letter N anymore*

anyways my issue was the statement that i circled.

anyways im not pursuing number theory. dont worry. i cant mind read at this level.

[empty nymph]

its pretty clear what it is saying

just read

[north pagoda]

youre gonna be pretty offput by math in general if you cant fill in 1 line of proof

[native zenith]

it kind of is

[empty nymph]

[stoic bear]

"mind read"

[vast dove]

DAMN ZOPH

i think zoph drunk

[empty nymph]

yes, he shall join the field of true intellectuals

[light flicker]

Ok I drank too much

[empty nymph]

foundations

[light flicker]

Continuous logic time

[stoic bear]

what it is just a little bit of thought

Just follow the proof, and it becomes quite obvious

[native zenith]

well the article says clearly itsi a necessary condition

[vast dove]

he said a typical thing jan would say

[empty nymph]

[native zenith]

where is the link to the previous article

[empty nymph]

why fuck zoph

[exotic raptor]

ok I drank too much

operator algebra time

[stoic bear]

anyways, hi sloth

[empty nymph]

hai

[stoic bear]

this crank is entertaining

[light flicker]

Lmao

[stoic bear]

[light flicker]

Got u good

[empty nymph]

i dont understand what he's even mad abt

Just Read It

[stoic bear]

that he cannot fill in one step of a proof from what I gather

[native zenith]

wait the statement is

[light flicker]

hegels literally in middle school and understands this

[vast dove]

hegel is in highschool

[stoic bear]

no kindergarden

[vast dove]

zoph dont text while drunk

[light flicker]

hegel is 12

[native zenith]

" there exist solutions x,y,z to ax + by = z iff gcd(a,b) | z "

[light flicker]

im taking the amc later

when I get home

[native zenith]

which is equivalent to saying, z is a multiple of gcd(a,b)

[stoic bear]

[light flicker]

maybe ill beat poc

pco

poco

[stoic bear]

Ping all of your kids and tell us your score @light flicker

you probably can

[light flicker]

144 I estimate

[stoic bear]

I suck at comp-math

[north pagoda]

yes, there exist solutions x,y,z iff z = k*gcd(a,b)

for some k

[native zenith]

so what is the necssary condition here

in this statement

[empty nymph]

thunk

[exotic raptor]

[native zenith]

if gcd(a,b) | z then there exist solutions to ax + by = z

[vast dove]

this is essentially saying Z is a PID

[sacred junco]

hey i just gave the thing a better reading and like the proof does seem kinda weird tbh
they seem to say "you can express the GCD like this" and then say "question => GCD fact and GCD fact is true so GCD fact => question"

[north pagoda]

"Let d=gcd(a,b). We show that any integer of the form kd, where k is an integer, can be expressed as ax+b for integers x and y"

this is the necessary condition

[exotic raptor]

@vast dove I'm sure he'll truly see the light as a result of this

[north pagoda]

ie "the thing that is always true"

wtf why is copy-pasting off brilliant so dumb

again, A is a "necessary condition" for B if B => A

[empty nymph]

this is why u take screencap

[native zenith]

A iff B , the necessary is B →A, correct?

[sacred junco]

they don't seem to have shown that only integers of the form kd can be expressed

[stoic bear]

screencap?

[north pagoda]

A is a "sufficient condition" for B if A => B

[native zenith]

right jelly, this article is full of logical gaps

[north pagoda]

jelly

they do

thats what the next 2 sentences are about

[native zenith]

oh

[north pagoda]

all the stuff after "so to show that it is sufficient"

[empty nymph]

[north pagoda]

gimme a sec

[native zenith]

let A = "there exist integral solutions x,y,z to ax+by = z" and B = z is a multiple of gcd(a,b)

[empty nymph]

reading is hard jan

[stoic bear]

imagine reading jan

[sacred junco]

well i am aware of bezout's lemma but their wording makes it seem this way imo

[empty nymph]

[north pagoda]

$\begin{tabular}{|c|c|c|}
\hline
$A$ is a necessary condition for $B$ & $B \implies A$ & \
$A$ is a sufficeint condition for $B$ & $A \implies B$ & \
$A$ is an equivalent condition to $B$ & $A \iff B$ & alternatively: $A \implies B$ and $B \implies A$\
\hline
\end{tabular}

[exotic raptor]

ok uh

what actually occurred here

[native zenith]

i dont think we even proved the statement

[sterile pumice]

Namington:
Compile Error! Click the reaction for details. (You may edit your message)

[north pagoda]

no clue where my error is but w/e its readable

[vast dove]

you gotta use \

[native zenith]

all we showed is that gcd(a,b) divides z, which is obvious by the definition of gcd(a,b)

[vast dove]

\

\ \

[north pagoda]

i used \s

discord escapes them

as you just found out

but texit reads it fine

[native zenith]

where did we prove 'if there exist solutions x,y,z " then gcd(a,b) | z " ?

[vast dove]

hm

[empty nymph]

pls,,,

[native zenith]

this proof purports to prove both if and only if

[exotic raptor]

missing $?

[north pagoda]

oh shit lightning

you right

thanks

[vast dove]

i feel like i could teach way easier in person

[sacred junco]

imo they should have maybe changed their wording a bit, d divides every integer of the form ax + by instead of exists x' and y' such that d = ax' + by'

the latter seems like a useless fact

[north pagoda]

what?

[sacred junco]

rip my logic

[exotic raptor]

[native zenith]

do you agree that

[light flicker]

Bezouts identity says the second thing

[native zenith]

let A = "there exist integral solutions x,y,z to ax+by = z" and B = " z is a multiple of gcd(a,b)"

[light flicker]

That's literally what bezouts identity is

[sacred junco]

sorry didn't mean to add a bezout there

im dumb i should go and eat something

[exotic raptor]

yes

[native zenith]

bezouts identity says that gcd(a,b) is an integral linear combination of 'a' and 'b'

i.e. there exist integers x,y such that ax + by = gcd(a,b)

also we can let both a,b, be nonzero

gcd(0,0) is a mindf$ck

[north pagoda]

yes

[native zenith]

some books define gcd(0,0) = 0 others leave it undefined

in the partial ordering of divisibility 0 is greatest

[sacred junco]

frick convention

[native zenith]

because you could leave it as undefined

its not a natural convention like 0! = 1

what is the largest number that divides 0 and 0 , there is no largest integer

n | 0 for any n.

[stoic bear]

what does this matter pertaining to the current conversation

[native zenith]

i was answering jan

it has nothing to do with it

[stoic bear]

i meant gcd(0, 0) in the first place

[native zenith]

yes it has to do with the claim

we don't allow a and b to be zero

[vast dove]

The word "greatest" in "Greatest Common Divisor" does not refer to being largest in the usual ordering of the natural numbers, but to being largest in the partial order of divisibility on the natural numbers, where we consider a to be larger than b only when b divides evenly into a. Most of the time, these two orderings agree whenever the second is defined. However, while, under the usual order, 0 is the smallest natural number, under the divisibility order, 0 is the greatest natural number, because every number divides 0.

-stackexchange

[native zenith]

so do we agree that A = "there exist integral solutions x,y,z to ax+by = z" and B = "z is a multiple of gcd(a,b)", and we want to prove A iff B

actually different books define gcd(0,0) differently

anyways, we want to prove A iff B

have we done that?

[empty nymph]

i like that it isnt sourced from a specific user on stackexchange but just the website as a whole

[vast dove]

yes

[native zenith]

i dont see the proof

[vast dove]

stackexhange is a hivemind

[whole chasm]

All of stackexchange collaborated on that definition

Accepting it is a prerequisite to making your account

[native zenith]

A = "there exist integral solutions x,y,z to ax+by = z" and B = "z is a multiple of gcd(a,b)." We want to prove A iff B. Proof: there exist integral solution x,y,z to ax + by = z. if z is not a multiple of gcd(a,b)... you can do a proof by contradiction

[vast dove]

@empty nymph why are you still here

[sacred junco]

just to suffer

[native zenith]

assume there exist integer solutions x,y,z to ax + by = z.

nothing in the way im proving it corresponds to this brilliant.org article

[light flicker]

One part is proven which they write

The other we did

[sacred junco]

smd noone caught my meme

[north pagoda]

yes, there are usually multiple ways to prove things

[native zenith]

man i already forgot it

[north pagoda]

and at an elementary level, proofs by contradiction are usually just "rephrasings" of direct proofs

[native zenith]

this scroll chat is a mindf###

[swift shard]

Stack exchange is a gauntlet

[sacred junco]

it killed iron man

[native zenith]

am i even typing in the right place?

i got an invite , idk

[sacred junco]

imagine being killed by a glove

[native zenith]

i clicked elementary number theory

[north pagoda]

this channel is fine, yes

[swift shard]

It's the new #chill

[native zenith]

what about the converse. if gcd(a,b) | z , then how does that prove there exist integers x,y such that ax + by = z

how do you edit your pfp

[solemn raft]

Let n = p1^k1…pm^km. I'm trying to show φ(n) = n(1-1/p1)…(1-pm). I thought I had a slick proof of this by interpreting φ(n)/n as the probability that a randomly chosen integer k between 1 and n is coprime to n, but I realized that this relies on the events "k is not divisible by p" and "k is not divisible by q" being independent. Is this true? Is there an easy way to see that?

[sacred junco]

that's what the second part of the proof is for

that's why they use bezouts lemma

[solemn raft]

I know I can just use multiplicativity but this seemed cooler

[north pagoda]

gcd(a,b) | z so write z = k*gcd(a,b)

and from bezouts we know

[native zenith]

ok

[north pagoda]

gcd(a,b) = ax + by

for some x, y

so multiply by k

k*gcd(a,b) = axk + byk

[light flicker]

I'm not sure those events are multiplicative

[solemn raft]

Are independent?

[north pagoda]

and hence

k*gcd(a,b) = a(xk) + b(yk)

[light flicker]

Yes that

[north pagoda]

and of course, xk and yk are integers

[solemn raft]

Yeah, it seemed suss

[north pagoda]

completing the proof.

[native zenith]

so the new integers are x' = xk, and y' = yk

[north pagoda]

sure

then k*gcd(a,b) = z = ax' + by'

[solemn raft]

But the argument that φ(n)/n = the probability that a random integer k is coprime to n = (1-1/p1)…(1-1/pm) is so nice :(

[north pagoda]

and because you can do this for any z, a, b

[solemn raft]

Guess I'll just be boring about it

[north pagoda]

(satisfying the criteria)

we're done

[native zenith]

so that is the converse i think

[north pagoda]

yes

[native zenith]

wait, we didnt prove the first part, the only if part

A = "there exist integral solutions x,y,z to ax+by = z" and B = "z is a multiple of gcd(a,b)", and we want to prove A iff B. Lets prove A only if B.

is this part trivial?

[north pagoda]

thats... what we just proved

we proved that B => A

[native zenith]

no we proved that if z is a multiple of gcd(a,b) , there exist

[sacred junco]

@solemn raft they aren't mutually exclusive but you're in the right track

[native zenith]

right, B →A. can we prove A →B

[north pagoda]

are you getting "if" and "only if" backwards

[native zenith]

nope.

[north pagoda]

wait FUCK

[sacred junco]

consider what you're doing by multiplying by (1 - 1/p)

[north pagoda]

sorry

im tired

youre right

lmaoo

[native zenith]

no worries

[north pagoda]

anyway yeah we can show the only if direction

[native zenith]

i feel like these "elementary proofs" are like a wall to the more interesting fruits of number theory

yeah...

[solemn raft]

@sacred junco I'm not sure what you mean? I didn't say that they were mutually exclusive

[sacred junco]

yoneda, you can think about it as starting with a large list of numbers below n and then filtering out the ones divisible by the factors

[solemn raft]

Sure

[stoic bear]

Well, math is usually foundational

You need to know the basics to do the more complex stuff

[sacred junco]

and there's a straightforward logic to see that the ones you filter out have a nice ratio of the other primes

well you start with the list from 1 to n - 1

[swift shard]

Getting proofs right is definitely a wall for many

[sacred junco]

you take a prime that divides n - 1

say, p1

[solemn raft]

Divides n?

[sacred junco]

woops yes

sorry

[north pagoda]

assume there exist integers x, y, z such that ax + by = z
suppose that z is not a multiple of gcd(a,b); then z / gcd(a,b) is not an integer

but we know gcd(a,b) divides a and b so considder

(ax)/gcd(a,b) + (by)/gcd(a,b) = z/gcd(a,b)

left hand side is all integers, but right hand side is not an integer; contradiction

[sacred junco]

anyways so exactly n/p1 of the numbers from 1, ..., n - 1 have the common factor of p1 with n

[north pagoda]

this is the proof id probably think of immediately night

[solemn raft]

Yeah

[sacred junco]

so now consider what you're removing when you're "filtering"

[native zenith]

ah i was thinking along the same lines, by contradiction

[sacred junco]

you're removing p1, 2 p1, 3 p1, ..., k p1

[solemn raft]

Oh, are you saying that if I remove p1's multiples and then p2's, I'll remove the multiples of p1 p2?

[sacred junco]

where n = k p1

[solemn raft]

And theres n/(p1 p2) of those?

[sacred junco]

well by removing multiples of p1 first you're already removing multiples of p1 p2

[solemn raft]

Right, I'm saying that's what would be overcounted

[sacred junco]

but the thing is, what you're left with is also divisible by p2

as in

initially from 1 to n-1, 1/p2 of them were divisible by p2

but once you remove the multiples of p1, still 1/p2 of the remaining list is divisible by p2

[native zenith]

im still so confused by this article https://brilliant.org/wiki/bezouts-identity/

[solemn raft]

Ah, now I see

[native zenith]

how do you step from articles embedding

how to prevent

[solemn raft]

So this is proving independence since we show P(divis by p2|divis by p1) = P(divis by p2)

[sacred junco]

it's not that obvious to see this, but you can argue using the fact that exactly 1/p2 of p1, 2 p1, 3 p1, ..., k p1 is divisible by p2

[solemn raft]

That makes sense

Right?

[sacred junco]

for a list of numbers whose size is a multiple of p1 * p2, yes

[solemn raft]

Okay, I think I can go from here

I mean, I need to argue that as you keep removing stuff this is still true

[sacred junco]

gl

[solemn raft]

But it makes sense

I think it's probably easier just to prove multiplicativity and look at what it does to the prime powers

But I'm happy to understand why it works

[sacred junco]

btw the actual proof involves using a large table of numbers and modular arithmetic

[solemn raft]

?

[sacred junco]

instead of a 1D list, they use a 2D grid

[solemn raft]

Actual proof of what?

[sacred junco]

phi(n)'s formula

maybe looking up residue classes can help you on your proof

[solemn raft]

I know what residue classes are lol

[sacred junco]

ah then you should be good ig

[solemn raft]

My proof that φ(nm) = φ(n) φ(m) is that Aut(G×H) ≈ Aut(G)×Aut(H) when G, H have coprime order

Apply this to Z/nZ and Z/mZ and take orders

[sacred junco]

lol idk ring theory or whatever that is

reminds me that i gotta read some algebra lol

[solemn raft]

Algebra is good

[sacred junco]

indeed

[native zenith]

I think thats a good proof

and it scored 0 on mathstackexchange. sad

i gave it a thumbs up or whatever

[solemn raft]

oh wait I can just use the chinese remainder theorem, lol

[supple furnace]

Yes

[solemn raft]

I am very very bad at number theory

[native zenith]

hey guys im back

is the professor around

I rewrote the proof to the collorary of Barzini's identity, using set theory.

[quick furnace]

i would not call this a "set theory proof"

[craggy solstice]

barzini?

[quick furnace]

any more than any proof of the equality of two sets by a two-way inclusion argument could be described as such

[native zenith]

huh?

[quick furnace]

two-way inclusion arguments are used, like, everywhere

[native zenith]

yeah thats set theory

set theoretic proof

[quick furnace]

calling your proof set-theoretic just because it uses one is...

meh

[native zenith]

look up the word set theory

[quick furnace]

i know what set theory is thank you very much

[native zenith]

definition of a set , we can start there

[quick furnace]

don't take me for more ignorant than i already am

[light flicker]

Everything uses set theory

[native zenith]

thats a stupid critique

[light flicker]

The proof on brilliant used set theory

[quick furnace]

i've seen and used plenty of arguments of the kind you present

[light flicker]

just not explicitly

[native zenith]

zopherus aha!

[quick furnace]

i'm not criticizing your proof itself. content-wise, it seems fine.

[native zenith]

it kind of led me to that thinking

[light flicker]

You don't have to talk about sets to use set theory

[native zenith]

jesus christ, the proof is wrong because i said set theory

[quick furnace]

NO, I DIDN'T SAY YOUR PROOF WAS WRONG.

[native zenith]

its pedantic, fair enough

[quick furnace]

the thing i'm objecting to is your LABELING of the proof as "set-theoretic" as if that somehow makes it special. which it doesn't.

[native zenith]

huh?

[quick furnace]

by that metric basically any proof out there except the most basic ones would be set-theoretic.

[native zenith]

that not my intention, why are you trying to mind read me like that

[light flicker]

yeah, none of us said your proof was wrong what

[quick furnace]

i'm not trying to mind-read you.

[native zenith]

yes you are

[quick furnace]

no i'm not.

[native zenith]

the thing i'm objecting to is your LABELING of the proof as "set-theoretic" as if that somehow makes it special. which it doesn't.

that was not my intention

i was trying to emphasize that it uses sets. because sets are cool, ok?

sue me

i think they are called sets, let me double check that

[quick furnace]

...okay, fine, it uses sets because you reframed the proof of an iff statement as the proof that two certain sets are equal.

yes they're called sets.

[native zenith]

i didnt say the proof is special at all, how do you get that

[quick furnace]

it came across as such.

[native zenith]

ok hmm

i was just making everything explicit, as opposed to hidden 'you should know this by now' statements. i know you math people love those.

[quick furnace]

-.-

[native zenith]

there are many number theoretic proofs that can be recast as set proofs

[quick furnace]

i mean... ok but maybe don't be as condescending

anything can be recast as a set proof. it depends on the target audience whether or not that's necessary.

[native zenith]

i dont know about that. i think that statement is a bit extreme

[quick furnace]

an "if this then that" proof can be recast as "this set is a subset of that set"

if one so desires

[native zenith]

but like you said it depends on your audience. i mean sometimes using sets would be more natural

or maybe easier to follow (shock, gasp)

i guess im in the dumb audience

i wrote that proof because this proof is driving me crazy

im trying to match this proof with the proof i wrote, which is clearer

mine's lengthier , i know

so the first sentence is saying ( B \subseteq A )

[winter bear]

theres really nothing wrong with that proof? the "necessary condition part" is p obvious i think, and if someone doesnt see it immediately, they can always work it out themselves. authors dont need to feel in every little details

infact i will go ahead and say its better if they dont

so that readers can learn by filling in the details

[native zenith]

i know, that leads to frustration for stupid people like me

some readers will give up though

its true some can learn by filling in details, but others wont. its tricky decision

[winter bear]

its not like he is skipping a difficult step

[native zenith]

ideally you dont want students to give up

[winter bear]

like, obv since $d|a$ and $d|b$, then $d|ax+by=N$

[sterile pumice]

JohnDoeSmith:

[winter bear]

and the statement is given, i think almost everyone would be able to figure this out after some time to think

[native zenith]

yeah but thats not what he said

[winter bear]

that is what he said

[native zenith]

nope

did you read what he wrote?

[winter bear]

yes he said that it is a necessary condition

[native zenith]

well what is the necessary condition?

[winter bear]

i.e $N=ax+by\implies d|N$

[sterile pumice]

JohnDoeSmith:

[native zenith]

how can a condition be both necessary and sufficient

the same condition

[winter bear]

...

[native zenith]

sometimes seems off , idk

[winter bear]

ok i think you are a bit unfamiliar with proof notation

but thats fine

[native zenith]

not really , uh oh here we go again

if you read this sentence carefully he says 'this condition' which is

any integer of the form kd

[winter bear]

so when we say A is a nessacary condition for B, we mean that $B \implies A$
when we say A is sufficient for B, then $B\implies A$
if its both, then its $A\iff B$

[sterile pumice]

JohnDoeSmith:

[native zenith]

thats a necessary condition for ax + by. then he said this condition is sufficient.

ok

ah this english

wait

[winter bear]

he said the necessary part is obvious and didnt include it

he proved the sufficient part

[native zenith]

can you write out the necessary condition, sorry

[winter bear]

with bezouts

[native zenith]

what was the sufficient part , lets label the parts

[winter bear]

ok so $d|N$ is $A$ lets say, and $N=ax+by$ for some x,y is $B$

[native zenith]

A = " z = ax + by for some integers x,y " and B =" z= kd , where d = gcd(a,b) "

[winter bear]

or that

we'll use yours

[native zenith]

i didnt mean to stop you

thanks

i mean to mess up your work

[winter bear]

ok so when he says necessary, he means B is necessary for A to be true, i.e $A\implies B$

[sterile pumice]

JohnDoeSmith:

[winter bear]

also think about what the word necessary means

if B is necessary for A, that means if B were false A couldnt happen right

[native zenith]

right

[winter bear]

you should recognize this as the contrapositive of A implies B

[native zenith]

ok but the author says "this condition is a necessary condition" , so i got confused which condition

[winter bear]

i mean that is fair, but theres only 2 ways it could go

so its not too hard to figure out which way he meant

[native zenith]

"Let d=gcd⁡(a,b). We show that any integer of the form kd, where k is an integer, can be expressed as ax+by for integers x and y. We already know that this condition is a necessary condition"

right there are only two ways, i agree

also the placement of the parentheses is misleading

[winter bear]

i mean these are nitpicky at the end of the day, everyone has a different writing style and different styles they read better

like i personally like explicitly labelling left and right implications

at the end of the day you need to learn to be comfortable with all the common styles

cause you will encounter a whole lot more of these

[native zenith]

yes

ok i think the brilliant.org writer is saying z = kd is a necessary condition for z = ax + by

[winter bear]

mhm

[native zenith]

then z = kd is a sufficient condition for z = ax + by

[winter bear]

yep

[stuck lintel]

All this discussion over bezout’s identity... ._.

[sleek cove]

holy shit

i shouldnt have read through that argument...lol

[native zenith]

barzini's identity

[native zenith]

Is it ok to define gcd(0,0) = 0, for the edge case ax + by = c when a=b=c=0. Then it is still true that c = k*gcd(a,b) since k * 0 = 0.

c is still a multiple of gcd(a,b)

[silver solar]

I think this is about more than Bézout's identity... It's about how to write good mathematics

And how it should be interpreted

[sacred junco]

Yes, similarly, gcd(0,n)=n for all natural numbers, extending to zero

[quick furnace]

gcd(a,b) is the unique nonnegative generator of the ideal generated by a and b in Z

[sacred junco]

assuming Z is pid

[night isle]

hello

could anyone help please?

[light flicker]

What have you tried

[night isle]

is this right?

[kindred estuary]

No

[silver solar]

$\lfloor mx\rfloor\ne m\lfloor x\rfloor$ in general

[sterile pumice]

Rijinaru:

[night isle]

so uh?

[torn escarp]

idk, looks like someone took a binomial expansion, fiddled around with it to arrange it into some kind of inequality, then they took the floor of it to make this seemingly random thing and now you just have to pray extra hard to guess the same stuff to try to undo the magic backdoor good luck

[light flicker]

Yeah this seems like a comp math style question

[supple furnace]

Handle 2,3,4 individually. If n isn’t prime, then it’s enough to show that v_2((n-1)!)>v_2(n(n+1)) . In this case, it’s clear that only one of n,n+1 is even and that for n>4, 2(ceiling(n/2)|(n-1)! with even quotient because ceiling(n/2) is odd for n=5,6 and because there are at least three evens in (n-1)! for n>6 when multiplied out, including 2 and ceiling(n/2) (if it happens to be even).
It suffices to show the result for odd primes. Using Wilson’s Theorem and CRT, one gets (n-1)!=-n-1 mod n(n+1). Then it’s enough to show that ((n-1)!+n+1)/(n(n+1)) is odd. But since n>4, the first result and the parity of n imply v_2((n-1)!+n+1)=v_2(n+1)=
v_2(n(n+1)), showing that the integer is odd.

[sacred junco]

would induction work somehow btw?

[torn escarp]

try it, see how far you can get

[cunning stump]

Does anyone else hate it when the professor says "It's easy to see that..." and "from here, solution is trivial" etc? 😛

it ain't easy to see! show us! t_t

[stoic bear]

Trying to work out the "missing" step can often be pretty illuminating

and also, it usually is pretty simple; if you need help, just ask later, or a friend

[native zenith]

Quote " Does anyone else hate it when the professor says 'its easy to see that' " yes thats my pet peeve. Sometimes its obvious, sometimes it takes a bit of work to 'see that'. Also the teacher may derive the 'obvious step' in a different way than you did, whilst you took a circuitous route.

[torn escarp]

I love to hate it so good

[native zenith]

I think math gives enjoyment to people who enjoy problem solving. Though i would qualify that "enjoying problem solving" is a necessary but not sufficient condition to enjoy math. There are people who enjoy solving crossword problems or chess puzzles and yet don't enjoy math much.

[torn escarp]

why did you edit the message I replied to? cringe

[quick furnace]

cringe bruh

very not poggers

[sleek cove]

not an epic gamer moment

[native zenith]

How can you be sure that you have found the correct gcd, without using Euclid's algorithm.

Using just the definition of gcd. For example I claim that gcd(18,24) = 6 , and I want to show this is true using only the definition of gcd.

It is true that 6|18 and 6 |24 . Then the definition says, if there is another common divisor of 18 and 24, then it will divide 6.

[sacred junco]

No. I get what you’re trying to say, but it isn’t true the way you word it 2 | 8 and 2 | 12, but gcd(8,12)=4 and 4 does not divide 2

[dusky pecan]

how do i solve 11x^2 congruent modulo 13 to 7

[sacred junco]

11x^2 = 7 mod 13

ak = b mod c

a/k = b/k mod c/gcd(c,k)

[dusky pecan]

what?

could you elaborate

[sacred junco]

Actually, this won’t work, my bad

[light flicker]

There's really no better method here than just guessing and checking

[dusky pecan]

yea i can use my computer (maple) for the guessing and checking part

but first i gotta get it to the form x^2 = some number b

[light flicker]

I mean, you can do it by hand, there are only 13 possibilities

[dusky pecan]

so like, remove the coefficient of x^2

[light flicker]

Ah, so you're meant to do it in maple

[dusky pecan]

yup

[light flicker]

So what you're looking for is a number n so that 11n = 1 (mod 13)

since then you can multiply both sides by n to reduce down the equation like you want

[dusky pecan]

hang on im thinking

how does multiplying both sides by n 'reduce down' the equation though

like, u'd get 11n^2 = n (mod 13)

[light flicker]

ah not multiplying that equation

multiplying 11x^2 = 7 (mod 13) by n

[dusky pecan]

that'd get me (11n) x^2 = 7 n (mod 13)

i still dont see how its gotten to the form x^2 = a

[light flicker]

How did we choose n?

What's special about n

[dusky pecan]

n is s.t. 11 n = 1 mod 13

[light flicker]

so what happens to the equation

[dusky pecan]

ya i think i know what ur saying

(11n) x^2 = 7 n (mod 13)
would become x^2 = 7n (mod 13) ?

what law is that?

[light flicker]

don't think there's really a name for it

just that mod is a nice operation with respect to multiplication

if a = b (mod p) and c = d (mod p), then ac = bd (mod p)

[dusky pecan]

how are you using that law? what is the a,b,c,d in this case?

[light flicker]

Think about it for a bit, see if you can spot it

[dusky pecan]

hmm..

[light flicker]

It's not super obvious

Focus just on the left hand side though

What you're trying to show is that (11n) x^2 = x^2 (mod 13)

[dusky pecan]

yea so i can start with 11n = 1, multiply both sides by x^2 to get (11n) x^2 = x^2

thats a different law tho (multiplication by scalar)

yea and because congruency is transitive it proves that (11n) x^2 = 7n (mod 13) => x^2 = 7n (mod 13)

cool, thanks so much!

[light flicker]

That's basically what happening here yeah

[sacred junco]

i need to write a single congruence that encapsulates the following 2

x = 3 mod 7 and x = 3 mod 5

i wrote x = 3 mod 35, is that correct?

[light flicker]

yes

[sacred junco]

im writing out numbers and coming up with it @light flicker , is there a general way to do it?

[light flicker]

This is called the Chinese Remainder Theorem

[sacred junco]

oh okay thanks, ill look into it

chinese remainder theorem seems to give the remainder

it doesn't tell us under what mod

actually it does, i looked up bad resource

[light flicker]

Do you mean getting 35 from 5 and 7?

[sacred junco]

yea i meant that

mod is always the product right?

[light flicker]

depends

The chinese remainder theorem does tell you this

It'll be the product if all of the things you started with are pairwise coprime

[sacred junco]

got it

for x is odd and x is divisible by 7 its trivially 7x=1 mod 2 right?

just trying to verify that my solution is correct

[light flicker]

x being divisible by 7 doesn't matter here

odd times odd is odd

[sacred junco]

so x=7 mod 2?

why wouldnt 7x=1 mod 2 work

it says the left side is divisible by 7 and its odd since its 1 mod 2

[light flicker]

what do you mean why wouldnt it work

[sacred junco]

x=7 mod 14

is the answer right

hmm

i think i got it, thanks @light flicker

i skipped CRT in my book

ill read it up, but really the easiest way i found to solve these problems is

by listing first few numbers

in this case it is

7 21 35 49 63 77 91

and then it is easy to see that we are doing x = 7 mod 14

every number is incremented by 14 and it starts by 7

i think CRT might be tangent to this

[light flicker]

I mean, this is exactly the problem that CRT allows you to solve

Doing your method isn't really viable if you are trying to combine four or more equations

or if the numbers are big

[sacred junco]

yeah just gotta do the readings

we didnt go through it in lectures

by the way whats the difference between elementary number theory and advanced number theory here?

aside the obvious lol

from what point does it stop being elementary and starts being advanced?

[light flicker]

I mean, its not a super clear line

Maybe what I'd say is that

When you start using higher math ideas like analysis or algebra to do number theory, it becomes advanced number theory

[sleek cove]

actually it becomes advanced when it stops being intermediate

[glass dawn]

How is 2^(-1) = (p + 1)/2 (mod p) where p is a prime number

[torn escarp]

multiply both sides by 2

[glass dawn]

I can only get 2^(-1) = 2^(p - 2) (mod p) using Fermat's little theorem

thanks 🙂

got it

[torn escarp]

cool

you're welcome

[sleek cove]

uh so im having some trouble proving a corollary that theres an infinite number of primes that are in the form 3q+2, q in Z

im not sure where to go after i get 6k+5, k in N

ive tried using gcd(6k, 5)=1 but not really sure

i feel like im missing smth obv

[winter bear]

Familiar with euclids proof of infinite primes?

Try tweaking that to work here

[sleek cove]

the one with assuming a largest p, then show contradiction with p|1?

[winter bear]

The one with p1*...pn+1 asduming largest prime

[sleek cove]

yeah ok

will do

this one right, just notation is diff

[winter bear]

Yeah. But tweak it ofc

[sleek cove]

alright, thx

[solemn agate]

when do we use divison algorithm?

[torn escarp]

when you wanna divide

[limber charm]

Can someone help me solve the following proof?

If a divides bc, then a divides c so long as gcd(a,b)=1

[light flicker]

What have you tried

[limber charm]

I’m gonna be honest, the only things I know from the given information is that a times an integer x = bc and a times an integer y =c and that a and b are relatively prime

Kinda struggling in this number theory class. The prof thinks we’ve taken Real Analysis so rip

[native zenith]

Since gcd(a,b) = 1 , Bezout's theorem guarantees the existence of integers x,y such that ax + by = 1

Multiply through by c. acx + bcy = c. Since a | acx and a | bcy , then a divides their sum. Thus a | acd + bcy , which implies a | c.

[limber charm]

Oh, okay, I was going through my notes and found something about Bezout’s Identity

[native zenith]

nice ;o

[limber charm]

States that ax+by=gcd(a,b) is an instance of his identity

Can I use this all the time or only when a and b are relatively prime

[native zenith]

You can use that all the time, there always exist integer solutions
to the equation ax + by =c when c is a multiple of gcd(a,b) .

More explicitly, given integers a,b not both zero,
the equation ax + by = k*gcd(a,b) always has an integer solution x,y for any integer k.

In particular we can use this with k=1 and gcd(a,b) = 1.

a,b don't necessarily have to be prime, only in the case the right side is equal to 1.

But if you are given gcd(a,b) = 1, then you can go backwards and say there exists integers x,y to the equation ax + by = 1.

[limber charm]

Thank you, I’m writing the proof for this now

This was very helpful

[native zenith]

Sure.

[limber charm]

Prove that gcd(a,a+2)=1 if a is odd and gcd(a,a+2)=2 if a is even.

In the first case, gcd(2n+1,2n+3)=1

Is there a way to apply Bezout’s theorem again?

Or is this something else?

[light flicker]

Just use some properties of gcd

[limber charm]

Not sure which ones

If gcd(a,b)=d, then d is the largest number such that d divides a and d divides b

[light flicker]

gcd(a, b) = gcd(a , b - a)

[limber charm]

Could I use the one I stated above to prove the second case?

[light flicker]

That's just the definition

That's not any property

I mean, you can, but you'll basically end up using the property I stated

[limber charm]

Cause in case 2 I could say let a=2n, so if a/d=2n/2, then d divides a?

I’m not even sure what I’m saying lmao

[light flicker]

yeah that doesn't make sense

[limber charm]

How could I use the property you listed to prove it?

[light flicker]

Try it

[limber charm]

Ok, I’ll try it

Like this?

Probably should have said gcd(a,a+2) in the last line, my bad

[light flicker]

yes

You should probably understand/prove why this property is true

[limber charm]

It would probably have been useful if my professor actually taught us this property :/

I didn’t know this existed

[light flicker]

There are other ways to do this problem

Directly from the definition, but

[limber charm]

I have to prove this property is true?

(In order for my proof to be valid?)

[light flicker]

That's how proofs work?

You can't just use something if you don't know if its true or not

[limber charm]

Well how do I prove it?

[light flicker]

Use the definition of gcd

[limber charm]

Is it because of the division algorithm?

[light flicker]

That's one way to do it

[limber charm]

So I need to establish a>b and then apply the division algorithm to a and b?

Or actually in this case, b>a*

[light flicker]

Either way, I mean gcd(a,b) = gcd(b,a)

so it doesn't really matter which one is bigger

[limber charm]

Could I also say that since d divides a and d divides b, then d divides their sum and their difference?

And that because of that, gcd(a,b)=gcd(a,b-a)?

? @light flicker

[limber charm]

Can anyone answer this?^

Just need confirmation so I can write the proof correctly.

[stoic bear]

Why must d divide the sum or difference?

[limber charm]

Isn’t that the definition according to the Euclidean algorithm?

[winter bear]

you dont really need euclidean algorithim to prove this

well u really dont

cause this is the euclidean algo lol

but basically proof the following:

well just show that gcd(a,b) is the biggest common divisor of a,b-a

||try showing bigger factor will lead to contradiction||

[pallid totem]

I understand most of what is on my homework conceptually, but we have not covered proofs or anything. Are there ways of going about this aside from formal proofs?

[torn escarp]

you can draw a venn diagram with A and B to see their intersection informally

[pallid totem]

Ok, so

something like that?

[torn escarp]

I'd probably draw the right thing on top of it in a different color maybe

https://prnt.sc/qypgd1

at least this makes it kind of obvious the section is A when you take the union of A with A intersect B

[pallid totem]

Yeah. I am mainly just unsure of what is really expected of me, which I know you can't definitively know. But thank you.

[torn escarp]

I'm not in your class I can't answer that, but it can't hurt to do a little doodle like this as a sanity check or help you plan out your more formal proof

[pallid totem]

Yeah, I have been losing my mind over these. Not because I don't understand it, like I knew that A U (A n B) = A, but the venn diagrams do not feel adequate and we have no covered proofs. I don't know. Thanks again.

[torn escarp]

no covered proofs? hmm well good luck, you're welcome

[pallid totem]

have not*

[limber charm]

If gcd(a,b)=d and k>0 is an integer, prove a formula for gcd(ka,kb).

In this problem, would scaling the gcd of a and b result in scaling d?

As in, gcd(ka,kb)=kd?

[light flicker]

prove it

[limber charm]

How can I prove it?

Writing the gcd as a linear combination and scaling it?

So using Bezout’s identity and then scaling it is proof of gcd(a,b)=d being scalable

[light flicker]

Not really

[limber charm]

I have no idea what to do then

[sacred junco]

Yes, the distributive property can be proved by Bezout @limber charm

d = na + zb for n, z in Z <=> dx | ax, bx and so dx = nax + zbx <=> dx = gcd(bx, ax)

[limber charm]

Awesome, that’s what I ended up doing

Thank you

[river socket]

Hi, so im not one of those calculus 3 person (in fact im a high school student), but this have been going through my mind lately. So the inverse operation of addition is subtraction and the derivative is a integral, vice versa. So I have two questions. 1. whats the inverse of modulo? and 2. can I solve this algebraically?

https://cdn.discordapp.com/attachments/496785853180543027/676603617158889472/Capture5.PNG

assume "??" is a variable like x

[stoic bear]

mod doesn't have an inverse

If you think about it 12 mod 5 and 7 mod 5 are equal

[hidden trellis]

That sounds like a nonsense question

[vast dove]

@river socket yes

The inverse of 3 mod 5 is 2 because 3*2 = 1

[stuck lintel]

i think he's trying to say modular multiplicative inverse

[formal carbon]

i need help

[vast dove]

Gtfo

[river socket]

yes, but how would I solve it algebraically?

[formal carbon]

[river socket]

hory shet dud use pemdas

or gems something

[stuck lintel]

@formal carbon doesnt belong in this channel, you can use one of the questions channels or #prealg-and-algebra

@river socket so when you try to find the multiplicative inverse of something, theres a few steps

[vast dove]

What do you mean algebraically?

[river socket]

like (3 *x)MOD 5 = 1

solve for x

[stuck lintel]

let's say you're trying to find the inverse, x, of a such that ax = 1 (mod m). Then the inverse exists iff gcd(a,m)=1. if it does exist, then you can find x using the euclidean algorithm

[river socket]

okay the Euclidean Algorithm is something like a=bq+r

i think

[vast dove]

Oh right

[stuck lintel]

yeah specifically you want to solve the linear diophantine equation ax - my = 1

[vast dove]

gcd(a,m) = 1 => xa +ym = =1 for some integers x, y.

Then mod m, we get xa =1

You can actually apply the Euclidean Algorithm, as @stuck lintel said, to find what x and y are

[river socket]

i see

thank you. it makes a lot of sense

[formal carbon]

@stuck lintel wait till i pull out my calculus worksheet

[worldly tree]

Apart from having an inverse, is there a property that elements in a finite field have that zero does not have?

MB like an equation that holds for all elements except zero

[winter bear]

i mean not anything really useful but like

if the order of the field is q

then $x^{q-1}=1$ for all non zero element

[sterile pumice]

JohnDoeSmith:

[winter bear]

if you really want an eqn not for zero lol

[worldly tree]

Is this FLT ?

[winter bear]

this is lagrange

[worldly tree]

oh, looks like fermats little theorem

Thank you

[winter bear]

btw finite fields usually write $x^q=x$

[sterile pumice]

JohnDoeSmith:

[winter bear]

cause all elements including 0 satisfy it

[hidden trellis]

Interesting property

[sacred junco]

5x≡18 (mod 63),7x≡5 (mod 8)

how can i solve these two congruences into one with chinese remainder theorem?

i cant reduce the first equation by finding inverse

because inverse 5 mod 63 doesnt exist

therefore i cant bring these two in the standard form to apply chinese remainder theorem

[light flicker]

Yes it does exist

[sacred junco]

i pasted wrong

it should have been

15x≡18 (mod 63),7x≡5 (mod 8)

inverse 15 mod 63 doesnt exist

their gcd is 3

[light flicker]

I mean, just divide that first equation by 3

I.e. 15x = 18 (mod 63) if and only if 5x = 6 (mod 21)

[sacred junco]

oh yeah

now i can find inverse of 5 and 21

its 17

thanks zopherus

[light flicker]

Np

You should confirm what I said is actually true

And probably prove the general idea

[sacred junco]

💡

[sacred junco]

for tonights last problem i need to prove that theres no m that makes Phi(m)=14

ive tried doing this algebraically

disproving m*Prod(1-1/p) = 14

this doesn't really simplify it though

i've also had an idea to break it up in two using multiplicativity Phi(a)Phi(b)=2*7

id appreciate a hint in right direction, spent an hour thinking about it to no avail

I think you could also say that theres no such m that makes Phi(m)=7

[torn escarp]

multiplicativity means that you can pretty easily see the smallest value it will take

[hidden trellis]

Well then, isn't it practically proved?

[torn escarp]

for a given prime

[hidden trellis]

There is no m for Phi(m) = 7

[sacred junco]

how do you know that?

[hidden trellis]

Wait wasn't it you who said so

But ye, 7 is prime and 7+1 = 8.. so

It's not gonna be in region of phi

[sacred junco]

i suggested but i wasnt surei

im not sure how to go about proving no m satisfies phi(m)=7

where does 7+1 come from in your argument?

[torn escarp]

you're over thinking it

once you know that for a prime p it's at least p-1 then you don't have to check primes that are very large, then brute force check

[hidden trellis]

You can't at least decompose 7 further right

[sacred junco]

yeah 7 cant be decomposed further

[hidden trellis]

Phi(p^k) = p^(k-1) * (p-1)

There is no such prime p and number k here

Which should be obvious after some try

[sacred junco]

its p^k-p^(k-1) right

Phi(p^k) = p^k-p^(k-1)

yea thats what you wrote

damn its still not clicking to me

[hidden trellis]

Well, put that 7 = p^(k-1) * (p-1)

Now think of factorization of 7

[sacred junco]

well theres none, only 1 and 7

i see why theres no such p and k that satisfy that

but i miss the transitioning step to that

i also know that Phi(p^k) = p^(k-1) * (p-1)

[hidden trellis]

Transitioning step? Wdym

[sacred junco]

but why is the next step writing 7 = p^(k-1) * (p-1)

[hidden trellis]

Well you wanted to know if there is m satisfying phi(m) = 7

[sacred junco]

yea and how do we know if

[hidden trellis]

Since 7 is prime it can't be further decomposed

[sacred junco]

m = p ^k

Phi(p^k) = p^(k-1) * (p-1) works only for m=p^k

[hidden trellis]

If m = ab where a and b are coprime

Phi(m) = Phi(a) Phi(b)

So such a and b couldn't exist

[sacred junco]

oh

so since 7=1*7

Phi(7)=Phi(1)Phi(7)

[hidden trellis]

Wait when did you put 7 inside

I meant no such a, b where Phi(a) Phi(b) = 7

[sacred junco]

my bad

and whats the reason

for saying that?

[dawn warren]

I’ll be honest

Idk what the phi function is

[sacred junco]

eulers totient

i thought u were going to say

[dawn warren]

Oh

[sacred junco]

ill be honest you're dumb

phew

[dawn warren]

Yeah ik Euler totient

[hidden trellis]

I mean 7 is prime

So it's either 1 * 7 or 7 * 1

[sacred junco]

isnt that circular

you are saying that theres no such b that Phi(b)=7

[hidden trellis]

And there's no a > 2 s.t. Phi(a) = 1

[sacred junco]

why does a have to be more than 2?

because m has to be factored righht?

[hidden trellis]

Well, a = 1 doesn't make sense since that means m = b, you get this?

[sacred junco]

i think i got it

[hidden trellis]

Yep, m is factored

[sacred junco]

yea totally

absolutely

i get this

but

what were you saying initially

with Phi(p^k) = p^(k-1) * (p-1)?

i understand this argument

[hidden trellis]

So, when Phi(m) = 7, m can't be factorized into two coprime numbers

Now let's say more than two primes divide m

Considering prime factorizarion of m, (p^k) and (m/p^k) is coprime

It's about prime factorization

Actually this is one of the important theorems in number theory, but I don't recall the fundamental proof for this

[sacred junco]

its okay, thank you, i got through it

[inner anchor]

Isnt phi(n) always even?

except for phi(2)=1

[winter bear]

yep

[inner anchor]

so trivially there exist no n such that phi(n)=7

[hidden trellis]

..I missed that

Now that is an easy way..
..but proof for that?

[inner anchor]

What are you allowed to assume

[hidden trellis]

Maybe up to prime factorization thm

[inner anchor]

If you get to assume that phi is multiplicative and how phi behaves for prime power arguments then its pretty clear

But probably the easiest way is just to look at the size of the multiplicative group of Z/nZ

[hidden trellis]

I mean is it that clear

But ya size of multiplicative group Z/nZ* helps

[inner anchor]

$\varphi(p^{k+1})=p^k(p-1)$ is pretty trivially even

[sterile pumice]

Pappa:

[hidden trellis]

I mean, it's tiring to put prime factorization

Iterating the prime elements

[inner anchor]

what do you mean?

Just let $n=mp^k$ where $(m, k) =1$, p is some prime, and now $\varphi(n) =\varphi(m)\varphi(p^k)$ which is clearly even

[sterile pumice]

Pappa:

[inner anchor]

when n isnt 2

[hidden trellis]

How do you know existence of such m

[inner anchor]

its not too hard to prove that n has a prime factor

because thats all you need

[hidden trellis]

..oh god why I didn't get this immediately

Actually I guess I was thinking of n = 1

.>

[sleek cove]

why is it asking to prove p exactly divides m and n, isnt the proof the same? like is it only relevant for part c?

[light flicker]

I mean, you're not doing each part separately

You need to find m,n so that all three parts are satisfied at the same time

[sleek cove]

oh wait, yeah i read that wrong my b

[sleek cove]

uh so im having a bit of trouble

proving it directly, would contradiction be better in this case, since i cant get a relation ship between all thrree

[light flicker]

no you can explicitly just write down m,n

[sleek cove]

yes, i did that and their ppfs, and establish wlog p = q_1 ^x1 = q_1 ^y1

[light flicker]

uh

im not sure what ppfs means

or how you're using wlog here