I'm gonna keep doing problems until i can do mods in my sleeeeeeep
#elementary-number-theory
lean halo
odd nexus
cool so get off discord and try to go through the problems
lean halo
I do problems WHILE on discord
odd nexus
that doesn’t seem good
lean halo
lol i've been studying for the past 10 hours straight
I only use discord when i need help w something lol
I don't understand the part where they're canceling a from ka = ja (mod m)
they say it's to prove there are no duplicates but isn't it contradicting itself
I understand the part where in order to divide stuff a and the list of all positive integers must be relatively prime to m for it to work
but the only thing i don't understand is the part where they're trying to prove there are no duplicates in the set by trying to cancel a from ka = ja (mod m)
I don't understand what they meaaaan
the same problem extends into the ri * a = rj * a (mod m) -----> ri = rj (mod m)
how does canceling the a basically prove there are no duplicates in the set
odd nexus
@lean halo so pretend we cancel a from everything to get {1,2,3,...,m-1}
obviously there are no duplicates in this set modulo m right
so then if gcd(a,m)=1
there are no duplicates in {a,2a,3a,...,(m-1)a}
sterile pumiceBOT
Shipreck:
lean halo
@odd nexus I can understand cancelling a from the set as a whole but i specifically don't understand why they're cancelling a from a single congruence between two elements in the set
odd nexus
@lean halo read the given proof of fermat's little theorem there
in that proof when they write, ka == ja mod p , k and j are arbitrary
to prove that no pair in {a, 2a, ..., (p-1)a} is congruent to each other mod p
lean halo
Isn't ka and ja two elements in the set
So by canceling a they're essentially proving two elements in the set are the same and thus duplicates?
Like say k = 2 and j = 3. So 2a == 3a mod p
(a,p) = 1 so 2 == 3 mod p thus the two elements are the same?????
odd nexus
which is a contradiction
so yeah there's no duplicates
@lean halo
since obviously, there's no duplicates in {1,2,..., p-1} mod p
lean halo
Huh Now I'm even more confused
Are they contradicting themselves to prove there ARE duplicates or NO duplicates
Or are they proving there ARE duplicates to prove there AREN'T any duplicates?
odd nexus
(we're talking about the fermat proof here)
we want to prove that no two of {a,2a, ..., (p-1)a} are congruent to each other mod p
now suppose for sake of contradiction that there exists some two elements there that ARE congruent mod p
call these two elements ka and ja
so we know ka == ja (mod p)
since gcd(a,p)=1 we can simplify this to k == j (mod p)
but this is a contradiction since no two of {1,2, ..., p-1} are congruent mod p
hence no two of {a, 2a, ..., (p-1)a} are congruent to each other mod p
does that make sense
lean halo
Huh isn't that kind proof kind of stupid tho
I mean like
"The set has no duplicates, so If we make this hypothetical statement let's see if it's true or not
But oh no
This contradicts the statement we're TESTING to be true
But we said it's impossible for the set to have duplicates anyway so who even cares lol
Thus the set has no duplicates
FIN
Does my problem make sense lol
@odd nexus
odd nexus
im not very good at this philosophy/logic kinda stuff
but in maths things are either true or false
so proof by contradiction is just eliminating one of those options
like here, we're supposing it false
but that cant happen
so it has to be true
lean halo
Lol is this even important or am I wasting my time on a trivial issue lol
odd nexus
probably both
lean halo
I'll just take their word for it lol
Dammit all these problems are proofs lool it's taking me foreverrr
And I SUCK at writing proofs
odd nexus
you dont have to write them that formally
you dont even need to write the solution down
lean halo
ok but i have one question tho
given i'm under a time constraint and i'm studying first and foremost to pass the amc 12 so I can study more afterwards
@odd nexus would It be safe to skip super advanced level proof questions and return to them later because they might not be so beneficial NOW
odd nexus
for like the third time (sorry, i genuinely dont know) im probably not the person to ask
id recommend you ask in #competition-math or AOPS, im extremely unfamiliar with amc 12
minor pike
sacred junco
It isn't
stuck lintel
Context or
sacred junco
Discrete logarithm problem
log h base g maps from group of units mod p to Z/(p-1)Z
Is the quotient just the group of integers mod p-1?
proper urchin
what's the best way to show that n consecutive integers contains a multiple of n?
in particular when n = 3, but that's doable with the division algorithm and by exhausting cases, so how could it work in general
brittle patrol
You can use division with residues
if $A$ is the set of $n$ consecutive integers then for any $i, j\in A$ we have $|i-j|<n$ so they can't give the same residue when divided by n
sterile pumiceBOT
Gonzo17:
brittle patrol
which means there's n different residues
fathom flax
ew modulus
brittle patrol
Wtf who goes ew when they see modulus
muted girder
|ew|
fathom flax
cuz its hard to understand and i cant find a lot of courses of it online
wide shuttle
Any y'all do infinite products?
$\prod_{p\in\mathbb{P}}^{\infty}{p^{p^{-x}}} = \sum_{n=1}^{\infty}{\frac{1}{n^x}}$ for x>1, is this true?
sterile pumiceBOT
Yeat:
tawny tinsel
So say I do a triangle number and it 2 with 4 iterations equals 20, right? How do I do that in reverse?
Like, how would I look at a product of, say, 120 that had 7 iterations, and find out what the first number was?
wooden creek
if x is a multiple of 2, then x=2(mod2) which will get : x=0(mod 2), right?
sacred junco
yes
wooden creek
thanks
wild zinc
yes
edgy apex
what is it ?
static sparrow
you're saying a is this and that but you didn't prove it existed at all
wild zinc
well the main problem is that you haven't actually shown anything in it
I'm not sure you're understanding the question correctly^
edgy apex
i felt that uneasy regarding the thing, but i wanted to know what is it.
wild zinc
I'll rephrase the question and hopefully that will clear it up?
edgy apex
well i already saw the solution
i wanted to know what was wrong with what i have done......preparing for the IMO on your own isn't very easy you see.
wild zinc
the question is to pick a fixed natural number a, for example, a = 4, such that n^4 + a is never prime for any natural n
for example a = 4 here doesn't work, because setting n = 1, we get n^4 + a = 5, which is prime
edgy apex
yea i understood that perfectly.
i plugged in some numbers here and there
got my hands dirty and well.....it seems that i still have a long way to go hehe.
thanks alot !
pliant cobalt
Let p be an odd prime number. Prove that the product of the quadratic residues modulo p is congruent to 1 modulo p if and only if p = 3 (mod 4).
I know to use Wilson's, but stuck from there.
sturdy dirge
$p^2\equiv1\pmod{4}\iff p\equiv3\pmod{4}$ ?
sterile pumiceBOT
sturdy dirge
With p prime.
fathom flax
wow
abstract sinew
@sturdy dirge that can't be true. the square of any prime (except for 2) is congruent to 1 mod 4
sturdy dirge
That's a question.
sacred junco
why is it a question
p is just 1 or 3 mod 4, so squaring it will leave 1 or 9, which is 1
sturdy dirge
I transcript it only.
sacred junco
oh lol i see
abstract sinew
wait, so who is the question from then?
sturdy dirge
From @pliant cobalt .
sturdy dirge
$7\equiv3\pmod{4}$ and $7^2\equiv1\pmod{4}$.
sterile pumiceBOT
lean halo
can someone please explain the logic of this question for me it won't go through my head
i don't think i'm reading the q correctly
can't you have one integer repeat 2008 and the unique one 10 times
or am i high
so the minimum is 2 distinct values wtf
which is clearly wrong
stuck lintel
The mode is the number which repeats the most
lean halo
so all other numbers repeat less
so u need x numbers repeating 9 times cuz that's the minimum
*max
that only gets u to 2007 tho so one must repeat once
so the answer must be 223 + 1 +1 = 225
lol i forgot what a mode was XD
could someone explain better solution 5
i want to know how to solve this one using number theory instead
sacred junco
there are only $3$ digits in ternary; $0,1,2$. if you have $8$ digits, then you can make any ternary number from $0$ to $22222222_3$
sacred junco
now it is easy to see that the distribution is symmetric
because there are just as many ternary numbers from 0 to 11111111 as there are from 11111111 to 22222222
therefore half of them will be positive, and then 0
so 3280 + 1 = 3281
@lean halo
lean halo
is ternary just a fancy word for mod 3
lean halo
OOOOOOO
sacred junco
lol
lean halo
lol this explanation is the most intuitive to me lol
at first i thought amc 12 tests were difficult af
but after realizing the solutions they don't seem that hard at all
lean halo
so (1-3^7)/(1-3)
sacred junco
1-3^8
sacred junco
let us say
$S_n = ar^0 + ar^1 + ar^2 + \cdots + ar^{n-1}$
there are n terms, as the coefficient of r ranges from 0 to n-1
lean halo
hm gimmie a sec
sacred junco
wait
sterile pumiceBOT
Oxide:
lean halo
the nth term is a*r^(n-1)
sacred junco
yeah
sacred junco
n-1 = 7
lean halo
n = 8
sacred junco
good
lean halo
is that a general rule i must remember
when summing a geo seq always use n - 1 to find n then use the formula and voila
sacred junco
i suppose yes
but you can derive it
$$S_n = ar^0 + ar^1 + ar^2 + \cdots + ar^{n-1}$$
$$r S_n = ar^1 + ar^2 + \cdots + ar^{n-1} + ar^{n}$$
$$(1-r)S_n = a - ar^n = a(1-r^n)$$
$$S_n = \frac{a(1-r^n)}{1-r}$$
sterile pumiceBOT
Oxide:
lean halo
telescoping?
sacred junco
yeah
lean halo
how do ppl find the time to derive stuff during a test lol
lean halo
oh ic
lol it feels nice finally understanding a problem you've been confused about for a while ha
sacred junco
indeed
fathom flax
;-;
lunar quiver
This is the elementary proof to the twin prime conjecture
gilded tinsel
no its not
sacred junco
fake
sacred junco
more like just getting a math degree
leaden peak
this guy's been putting cranky proofs and papers in the server for a bit
sacred junco
Again, if you have results worth publishing, don't put them on viXra. Convince a PhD program and you'll get in.
sonic mirage
I'm having trouble coming up with a more straightforward proof to show:
for the euler-totient function
I found the smallest integer x = 35.
Right now I have a proof by cases:
sacred junco
proof by cases 0-34 LOL
sonic mirage
oh no LMFAO
okay so
I use the property that phi(x) = phi(a)phi(b)
so I have 4 cases of factors of 24
(1, 24) , (2, 12), (4, 6), and (8, 3)
and then I eliminate the other cases to show that phi(a) and phi(b) have to equal 4 or 6 respectively
so phi(5)*phi(7) = phi(35)
shrewd marsh
Just consider the divisors of 24 such that if you add one to the divisor you get a prime
sonic mirage
but I'm pretty sure I can do this in a more simpler way
hmmm how would I back that up?
why look for something d + 1 --> prime?
We haven't entirely finished going through all equivalent formulas + theorem's of the phi funct
lean halo
Could someone please help me understand the first solution
I don't understand why c -1 must be a perfect square at all
i think i get why c -1 and k both have 9 solutions
lean halo
<@&286206848099549185>
lean halo
huh thanks
main spire
How can I find all positive integers m such that gcd(m, 2×(n)!+1)=1 for all positive integers n?
I know that 1 and any power of 2 is an answer (as 2×(n)!+1 is odd) but are there any others?
sacred junco
m being even will work. primes will also work most primes will work
brittle patrol
Well the solution is fully determined by the prime solutions
Since ab is a solution iff a and b are solutions
brazen prawn
Generally factorials and divisibility are pretty hard so there approaches to this are very limited. By Wilson we know (p-1)! = -1 (mod p) thus (p-3)!*(-1)(-2) = -1 (mod p) so (p-3)! = -1/2 (mod p) i.e 2(p-3)! +1 = 0 (mod p). Therefore for p>=3 there is an integer n which makes that expression divisible by p. That means the answer is all powers of 2 only
noble jay
did you just write a non integer fraction in Z/nZ
brazen prawn
No, it's Z/pZ 😛
noble jay
the fact that you wrote all that text makes confuses me. are you being sarcastic or no
brittle patrol
What no this is a perfectly valid solution
1/2 means the inverse of 2 modulo p
Since we're investigating prime p
noble jay
yeah sorry but this step is unnecessary and is completely false
saying (p-3)! = -1/2 mod p is the same as saying : in Z/pZ class of (p-3)! = class of (-1/2)
that's contradicting the definition of the ring
@brittle patrol
noble jay
@brazen prawn you didn't introduce any p, wilsons theorem is for primes only, the question states for all n, and i don't get how, from your reasoning,, you deduced that powers of 2 are the only solutions
brittle patrol
Well first of all (as I said earlier) the thesis can be checked for primes only
noble jay
why is that
brazen prawn
Ok so
noble jay
the question clearly states for all integers n, you said
ab is solution iff a and b are solutions
brittle patrol
Yeah, which means we can factorize it into prime numbers
noble jay
we're trying to find m here
n is a fixed integer
noble jay
m is the unknown
brazen prawn
Yeah, we are trying to find m
Suppose a prime p is not a solution, as in, there's an integer n such that p|2n!+1. Then m=pk is not a solution either for any integer k, because the gcd, for that same n, will be divisible by p, and thus is >1
brittle patrol
btw the 1/2 is kinda notation abuse indeed
but if you just replace it with what it's supposed to mean (the inverse of 2 mod p) everything works out
or if you don't want inverses this would prolly be cleaner
$2(p-3)!+1=(-1)(-2)(p-3)!+1\equiv(p-1)(p-2)(p-3)!+1=(p-1)!+1\equiv 0$ (mod p)
sterile pumiceBOT
Gonzo17:
noble jay
@brazen prawn so what you're saying is:
we have gcd(m,2n!+1) =1 then if we consider the prime factorization of
m=some product of p's
then gcd(product of p's, 2n!+1)=1
if you take any p from that product
you get gcd(p,2n!+1) =1
brazen prawn
Yeah!
inland fiber
hello
main spire
(OP here)
Thanks a lot for the solution!
brittle patrol
No logs, can be transcendental
Actually $\ln n$ is transcendental for all $n>1$, $n\in\mathbb{N}$
sterile pumiceBOT
Gonzo17:
brittle patrol
Generally it's very hard to prove that a number is transcendental
Powers of the form $a^b$ are transcendental where $a, b>0$ are algebraic, $b$ is irrational and $a\ne 0, 1$
sterile pumiceBOT
Gonzo17:
tiny cypress
,help
sterile pumiceBOT
A brief description and guide on how to use me was sent to your DMs! Please use ,list to see a list of all my commands, and ,help cmd to get detailed help on a command!
proper urchin
are there infinitely many primes of the form n!+1?
or perhaps the product of the first n primes + 1
stuck lintel
yap
tidal pebble
i solved riemann's hypothesis and found the exact formula to calculate how many prime numbers there are
so for example
if you enter x as 2 it displays f(x) = 1
and if you enter x as 3 it displays f(x) = 2
and if you enter x as 5 it displays f(x) = 3
and x as 7 displays f(x) = 4
and if you enter for example x = 6 it displays f(x) = 3.5
but if you just look at the whole number (or always round down)
then that is how many prime numbers there are
so 3 prime numbers can be found when looking at 6
2, 3, and 5
etc
and i also found out that division by 0 is equal to 0 in all cases
so like
100 + (100/0) = 100
because it's saying 100 + 0 = 100
100 = 100
tidal pebble
and also with the calculation on how many prime numbers there are it can be used to very quickly figure out where the next prime number is located at
sacred junco
seems false
division by zero is 0
claims solution to riemann hypothesis
What does it say for x=100?
leaden peak
i solved riemann's hypothesis and found the exact formula to calculate how many prime numbers there are
um... no you didnt
gilded quest
leaden peak
im drowning in the salt
but seriously this is the second crank I've seen on this server
the other was also on the nt channel iirc
the other guy claimed to solve twin prime i think
and he also claimed to have found a simpler solution to fermats last
do we get many cranks on this server?
versed storm
sonic mirage
hmmmmm so I just took my nt exam, and I couldn't finish 3 proofs ):. I got super close for two of them, and then the third one sorta ran out of time. This one is bugging me:
so first we're given that $$ h = \frac{\vert ab \vert}{(a, b)}$$ ( which is least common multiple)
and then we're asked to prove
sterile pumiceBOT
dk:
sonic mirage
prove if $$a \vert m \mbox{ and } b \vert m, \mbox { then } h \vert m$$
sterile pumiceBOT
dk:
sonic mirage
I was able to show that
sterile pumiceBOT
dk:
sonic mirage
but not h | m : /
Any general idea?
I can write out/pm my attempted solution if you guys can extrapolate something from it 
There's another student in my class here but I think it's fine to share since I'm pretty sure everyone took the exam
brittle patrol
Try dividing m by h with remainder and prove the remainder has to be 0
sonic mirage
hmmm okie lemme try playing around it with it
vast vessel
hm³
gilded tinsel
:hmmmm:
noble jay
@sonic mirage you've probably already figured it out by know but here's a neat trick in case you don't know it yet
so the question is basically to prove that gcd*lcm=|ab|
from that you can directly deduce that h=lcm
so anyway let d = gcd and m = lcm
let a' and b' in Z such that a=a'd and b=b'd. factoring by d gives us
(^)md = lcm(a,b)xgcd(a,b)= d^2xlcm(a',b')xgcd(a',b') = d^2lcm(a',b')
---now by definiton we know that lcm(a',b') divides ab since its its the smallest multiple. and on the other hand since (a',b')=1, a' divides lcm and b' divides lcm so a'b' divides lcm(a',b')---
so we've just proved that lcm(a',b') =a'b'
.going back to (^) we find
md = d^2(a'b') =(da')(db') = ab
so h=m
sacred junco
Anyone here into Math olympiad? ?
stuck lintel
yeah #competition-math
ebon kettle
f(x) = ax2 + bx + c is a non-constant polynomial
assume a b c are integers, and prove that there are infinitely many integers n such that f(n) is composite
how do you do this problem?
sturdy dirge
Hint: assume there are a finite number.
sacred junco
Rephrase:no non constant polynomial can have only prime values
sturdy dirge
Almost.
sonic mirage
@noble jay Sorry for not seeing it earlier but holy shit
tbh I would have never been able to manipulate what I knew to get that
it took me some time to digest too oof
those are some trippy manipulations 
I need more proof practice & need to nail my fundamentals so I get the hang of finding those tricks 
it's likely there were other solutions as well fooey
sacred junco
Hey, I've been interested in the Duodecimal counting system and what implications it could have. Let me know of anyone else is interested in this topic.
rugged copper
Hi! Does anyone knows good materials about the theme full reptend prime?
sweet apex
Does saying that a/b is in lowest terms mean the same thing as saying "a/b such that a and b are coprime"?
sweet apex
Is anyone familiar with why casting out nines works
leaden peak
Yes to your first question
For your second question, what do you know about modular arithmetic @sweet apex
tame raven
Is this channel (math area) for prime numbers?
Btw I had a math teacher who didnt know about casting out nine, somehow I thought riemmann’s hypothesis could be solved using that lol
sweet apex
@leaden peak I’m familiar with congruencies and stuff
leaden peak
Ok
Think about a given number
You can represent it as the sum of each digit multiplied by a given number of 10
So 5673 is 10^3 * 5 + 10^2 * 6 + 10 * 7 + 10^0 *3
But what is any power of 10 mod 9?
patent yoke
Question:
Let x and y be real numbers. For the purposes of this problem, we define x -> y to mean “there is some nonnegative real number h such that y=x+h.” Using this definition, prove that if x and y are nonnegative real numbers and x->y, then x^2->y^2
patent yoke
How would i begin to proof that ;-;
sharp pagoda
y=x+h
y²=x²+2xh+h²
y²=x²+k where k=2xh+h² is nonnegative real number
leaden peak
yup
stuck lintel
do you need help or?
slender moth
@sacred junco take powers of 2 and reduce mod 11. The first time you get 1 will be the 10th power
sacred junco
Fermat big poop 😤
stark vapor
Is there a formula for the proportion of primite roots mod p ??? where p is prime
actually, nvm I think I figured it out
wild zinc
phi(p-1)/(p-1)
that's assuming you want the proportion excluding 0
if you want the proportion including 0, it's phi(p-1)/p
stark vapor
yeah, that's what I got, trick was to spot (Z/pZ)* is cyclic so it has a generator "a"
then it's just a question of knowing when (a^i) has order p-1
which is exactly when gcd(i, p - 1) = 1 for each i
so phi(p-1)
^w^
low jolt
Let $m=dx$ and $n=dy$, where $d=\gcd(m,n)$, clearly $\gcd(x^5-y^5,xy)=1$
sterile pumiceBOT
Rumoden:
sterile pumiceBOT
Rumoden:
stuck lintel
$ \text{first realize that x and y are coprime} \ \gcd(x^5 - y^5 , xy) = 1 \iff \gcd(x-y, xy) = 1 \text{ and } \\gcd(x^4 + xy^3 + x^2y^2 + xy^3 + y^4, xy) = 1 \ \text{we will first prove that } \gcd(x, x-y) \text{ and } \gcd(y, x-y) = 1 \ \gcd(x, x-y) = \gcd(x, -y) = 1 \text{ and use the same reasoning for } \gcd(y, x-y) \ \text{next, we prove } \gcd(xy, x^4 + xy^3 + x^2y^2 + xy^3 + y^4) = 1 \ \gcd(xy, x^4 + xy^3 + x^2y^2 + xy^3 + y^4) = \gcd(xy, x^4 + y^4) \ \text{since } \gcd(x, x^4 + y^4) \text{ and } \gcd(y, x^4 + y^4) = 1, \gcd(xy, x^4 + y^4) = 1 \text{ and we're done} $
oh jeez idk how this bot works
oh well just ignore the formatting 😂
sterile pumiceBOT
Plum:
stuck lintel
@low jolt
low jolt
Thankzz!
odd nexus
@stuck lintel god putting \text everywhere looks painful
just use ,tex to start as if it was a normal document and use $s to enter/exit mathmode as needed like
,tex first realise that $x$ and $y$ are coprime so that [\gcd (x^5-y^5,xy)=1\iff \gcd (x-y,xy)=1] so then .... $\gcd (xy,x^4+y^4)=1$ and we're done.
sterile pumiceBOT
stuck lintel
That helps, thanks
sacred junco
is this not just ref alpha?
😮
it's ref 3alpha
oh god
<@&286206848099549185>
sacred junco
😎
unique lion
sacred junco
but yes
unique lion
Sorry
sacred junco
part 1 i showed that that rot ref rot is just ref 3 alpha
so basically
ref 3alpha = ref alpha when alpha=npi
so ref 3npi = ref npi ????
@unique lion does this devil maths make sense to you 😮
sacred junco
so we have polar coordinates (r,theta)
sacred junco
ref a (r,theta) = (r, alpha - theta)
rot a (r,theta) = (r, alpha + theta)
unique lion
What is alpha
sacred junco
they're transformations of (r,theta)
alpha is just any angle
to translate the coordinates, not transform lol
unique lion
sec
unique lion
@sacred junco oh ok
Got it
So you must have a property pertaining to the periodicity of theta right
unique lion
Angles
Ok I know I can solve this but I need to read up on accepted axioms
Sec
Oof
When are two points equal?
@sacred junco
sacred junco
when their coordinates are the same i guess
r is the length from the origin (0,0)
theta is the angle made anticlockwise with the positive x axis
unique lion
Yes ik
sacred junco
so yeah
sacred junco
2 points must be equal when r=r and theta= 2npi + theta where n is an integer
sacred junco
I have 4 minutes to write the proof 😎
unique lion
Wait why only 4
unique lion
Lol
unique lion
Haha
noble jay
@sacred junco i have no idea how this relates to number theory but the way i would do it, is define rot and ref as complex functions based on what you have given
so basically for complex z rot a maps z to z*exp(ialpha)
same thing with ref a and then it's just algebra from there
stuck lintel
@noble jay oh yeah where do you get your number theory problems from?
tame raven
plush narwhal
Anyone got any good resources on modular arithmetic? Especially proofs involving standard mod stuff, Fermat's little theorem, eulers totient function and Wilson's theorem
noble jay
@plush narwhal mit ocw. look up theory of numbers
it has everything you can think of
also don't just read the proofs of theorems like that otherwise you would be memorizing them just to forget them after a while, try to think about them first if you got nothing ask for a hint. just don't look up the complete solution
plush narwhal
@noble jay Cheers. Do you have any tips for those weird proof questions?
stuck lintel
Examples?
noble jay
exactly. plug in some numbers maybe you'll see a pattern of some sort.
also usually in elementary nt most problems come down to some basic group theory properties and stuff like that
nova void
noble jay
@nova void https://en.m.wikipedia.org/wiki/Hackenbush
sacred junco
Hi how do i prove that the euler's totient function is multiplicative?
Without matrix.or rings or that stuff
sacred junco
<@&286206848099549185>
stark vapor
@sacred junco https://forthright48.com/2015/09/euler-totient-or-phi-function.html This seems like the most intuitive way not using Ring theory, although I'm curious why you wanna prove it without Rings? 
... actually, I might not have answered your question xD just read the "without matrices" part, and this method uses an n by m table
gilded tinsel
theres one that uses dirichlet products
tho i guess it is a non elementary proof
if you want an elementary proof then
$\phi(n)=n\prod_{p|n} \left(1-\frac{1}{p}\right)$
and you can prove this by induction
but wait actually, this proof uses the mobius function...
fathom sierra
sturdy dirge
Some parenthesis are missing.
sterile pumiceBOT
rockpaperscissors:
gilded tinsel
i just realized ive never seen an elementary proof of euler’s totient being multiplicative
sturdy dirge
It's multiplicative for coprime numbers.
gilded tinsel
well that is what multiplicative means...
gilded tinsel
ok but ill assume what i said above is true without proof
$\phi(nm)=nm\prod_{p|nm} \left(1-\frac{1}{p}\right)$
sterile pumiceBOT
rockpaperscissors:
gilded tinsel
where n and m are coprime
sturdy dirge
Split the product since p divides n or m not both.
gilded tinsel
by euclid’s lemma, if p|nm then p|n or p|m
sturdy dirge
Yes.
noble jay
i've seen a simple proof before by considering the set A(n) = {k ∈ [|0, n − 1|], k ∧ n = 1}.
and then the function
f : A(mn) → A(m) × A(n)
x → (r, s)
where r and s are respectively the rests of the division of x by m and n
if you prove that f is bijective you're done
gilded tinsel
$\phi(nm)=\left(n\prod_{p|n} \left(1-\frac{1}{p}\right)\right) \left(m\prod_{p|m}\left(1-\frac{1}{p}\right)\right)$
sterile pumiceBOT
rockpaperscissors:
sturdy dirge
Perfect.
gilded tinsel
oh yeah that is a nice proof dusty
noble jay
because two sets that are finite and have a bijection between them have the same cardinal
so card(A(mn))=card(A(n))xcard(A(n)) thus phi(mn)=phi(n)phi(m)
sacred junco
Ok that caused brew up a conversation lol
noble jay
@gilded tinsel rereading what you wrote. unless you've proven that phi(n) = n times that product without using it's multiplicity, then it seems to me that you've just used the result to prove the question. so i don't agree with you assuming that it's true
noble jay
how would you prove that equality
gilded tinsel
which i wouldnt regard as elementary
noble jay
can you write down the main idea?
gilded tinsel
yeah
noble jay
i'm not very familiar with the mobius function so i'm curious
gilded tinsel
so you can do this by induction
sacred junco
i need help with functions
gilded tinsel
the idea is that if you expand the product you get
sacred junco
nvm
gilded tinsel
$\sum_{d|n} \frac{\mu(d)}{d}$
sterile pumiceBOT
rockpaperscissors:
sterile pumiceBOT
rockpaperscissors:
gilded tinsel
so from this the product form follows
but now we have to prove this
thankfully you can do this in an elementary way
do you know any basic resutls on the mobius function?
gilded tinsel
expand the product
you’ll get $1-\sum \frac{1}{p_i}+\sum \frac{1}{p_i p_j}-\cdots + \frac{(-1)^m}{p_i p_j\cdots p_m}$
sterile pumiceBOT
rockpaperscissors:
gilded tinsel
m is the number of distinct prime divisirs of n
compare this with $\sum_{d|n} \frac{\mu(d)}{d}$
sterile pumiceBOT
rockpaperscissors:
gilded tinsel
theyre the same. Do you see why?
gilded tinsel
its a nice exercise to prove $\phi(n)=\sum_{d|n} \mu(d)\frac{n}{d}$
sterile pumiceBOT
rockpaperscissors:
gilded tinsel
it doesnt require any other esoteric function
just some summation trickery
and this result $\sum_{d|n} \mu(n)=\left[\frac{1}{n}\right]$
sterile pumiceBOT
rockpaperscissors:
gilded tinsel
(which you could also prove)
sacred junco
How does mod work exactly
swift shard
Let's say you're working in a mod 4 algebra.
Take a number. Divide it by 4, and keep the remainder. All numbers with that remainder are "the same number" as long as mod 4 is concerned
For example
1 ≡ 5 ≡ 9 ≡ 13 (mod 4)
Because all of those numbers leave remainder 1 after division by 4. So we say they are "equivalent" which is what ≡ means
sacred junco
The remainder is always positive but the quotient can be negative?
fossil latch
I'm trying to learn a bit about lattices re: cryptography applications and in some introductory coursework I found (https://homepages.cwi.nl/~dadush/teaching/lattices-2018/) there's reference to the volume of a set - which I think means the Lebesgue measure. Is that something I should have an intimate understanding of to continue pursuing lattices or is "Lebesgue measure is sort of analogous to 3d volume" good enough? Not very familiar with measure theory and I don't want to waste time going down the wrong rabbit hole
sacred junco
@swift shard thanks. Btw u know of any good sites for anyone getting into number theory
fossil latch
<@&286206848099549185>
granite pebble
where's the reference to volume?
i see one in the first lecture that talks about volume in R^n
fossil latch
that's what I'm referring to
sacred junco
@gilded tinsel would actually like an elementary proof if possible
Cant we just like do the prime factorisation for each no
Then show the product's totient=totient of 1st no.*......*totient of nth no
gilded tinsel
well i dont think that’s any easier to prove
i dunno i cant think of any elementary proof
though dusty’s idea may work
well actually i just realised
$\phi(n)=n\prod_{p|n} \left(1-\frac{1}{p}\right)$
sterile pumiceBOT
rockpaperscissors:
gilded tinsel
going back to that
it can be interpreted as saying
$\prod_{p|n} \left(1-\frac{1}{p}\right)$ of the n integers from one to n is coprime to n
sterile pumiceBOT
rockpaperscissors:
gilded tinsel
so maybe some sort of proabilitic argument may work using inclusion exclusion
ahh wait the bijection in dusty’s proof is basically chinese remainder theorem
limber crow
So lemme get this straight - a residue class over a is just the equivalence class over the equivalence relation xRy : x =y mod a, right?
limber crow
OK lol
My professor just switched gears from equivalence relations to residue classes and wanted to make sure I wasn't crazy
sacred junco
What does it mean for a sequence to be o(1/n)? and O(1/n)?
I'm reading something which says if a_n is o(1/n) then that is the same as n*a_n -> 0, but then what would it the equivalence be for the Big O?
Also for little o, shouldnt it mean that a_n < 1/n (for large n)? In that case shouldnt it be that n*a_n< 1 ?
Because in that case, big O would give , a_n =< 1/n, so n*a_n =< 1
static sparrow
$a_n=O(b_n)$ means there exists a sequence $(c_n)$ defined for $n$ in a neighbourhood of infinity that's bounded and such that for all $n$ in said neighbourhood, $a_n=b_nc_n$
sterile pumiceBOT
Tuong:
static sparrow
or, with less words, $\left(\frac{a_n}{b_n}\right)_{\in\bbN}$ is bounded
sterile pumiceBOT
Tuong:
static sparrow
but that sequence (an/bn) isn't always well defined as bn could be 0 for some n, so a better def requires not to divide by bn at all
sacred junco
Oh and a_n/b_n is bounded if the limit n->inf of (a_n/b_n) = 0
oh nvm
but given that b_n = 1/n
then i can do t hat right?
im trying to understand tauber's theorem, and it uses o(1/n) as a requirenment for a_n
static sparrow
then a_n=O(1/n) just means (na_n) bounded
static sparrow
yea
sacred junco
ah ok
cool
and so thats why it said that its the same as n*a_n -> 0
because that implies that the sequence converges
oh wait
no
or
static sparrow
that's for little o?
static sparrow
if you have little o, then you also have big O
sacred junco
static sparrow
indeed
sacred junco
so it fails the requirenment for a_n=o(1/n) (little o)
and how do i show th at it also fails/passes big O?
so in that case is a_n = O(1/n)?
sacred junco
hmm, but a_n/b_n where b_n = 1/n gives
n*1/n = 1
and {1} isnt bounded
ogh wait
im stupid
ok
i got it
=]
i brain derped
i kept thinking that the sequence {1} is a sum..
soryr
so yea thank you ❤
static sparrow
You're welcome ( ^_^)
stuck lintel
^_^
stark vapor
Let U_n be the group of units mod n
Let Q_n = { [a] in U_n : a is a quadratic residue mod n }
A step in my lecture notes says, for f > 3, If [a] is in Q_2^f then [a] is in Q_8
Why is this true?
OHHHH, I got it
Can use the "identity" (or backwards inclusion xD whatever it's called) ring homomorphism f: Z_2^f -> Z_8 to show:
If [x]^2 = [a]
then f([x])^2 = f([a])
sacred junco
Let gcd(m,n)=1;A={x|0<=x<=(n-1) and x is prime to m} and B ={x|0<=x<=(n-1) and x is prime to n}.If C={na+mb|a€A and b€B} then prove that C assumes all the values x,0<=x<=mn-1,x is prime to mn,read modulo mn
@cobalt birch i need specifically your help here
U teach complex things very simply
<@&286206848099549185>
fast monolith
Does somebody know a page with a list of number theory stuff? idk (I'm at a number theory problem rn and I have no idea what i should even try)
stuck lintel
what’s the problem
sacred junco
@vast vessel trust me it just looks long lol..its elementary number theory
gilded tinsel
@sacred junco is B supposed to be all x from 0 to m-1 that are coprime to n instead?
woulda tried to helped sooner but was busy sry
fast monolith
@stuck lintel I want to solve it myself. Give me time till 5th March after the 5th i'm posting it (It's a competition problem)
noble jay
@fast monolith we won't spoil if you share it
fast monolith
K we can do that
In the decimal representation of 2sqrt = 1.4142... Isabelle finds a sequence of k consecutive zeros, where k is a positive integer. Proof: The first zero of this sequence is at the k-th position after the decimal point at the earliest.
.
Translated with DeepL so yeah tell me if something is wrong
fast monolith
a little hint maybe
it would already help me if you would tell me where i could find anything related to this
jolly comet
so if there's a sequence of a bunch of zeroes in a real number
that means you can write it as some rational + some tiny error
you don't need zeroes to do this, but specifically when there's k zeroes at position, i don't know, pick a letter, p,
the error is very tiny compared to the rest of the number
the situation is going to look like $\sqrt2 = \frac{a}{10^p} + \epsilon$ for $\epsilon < \frac{1}{10^{p+k}}$ (i might have off-by-oned some of the exponents here, sue me)
sterile pumiceBOT
tubular:
jolly comet
that'd mean a/10^p is a pretty darn good rational approximation to sqrt2, wouldn't it?
fast monolith
ok gonna try this
@jolly comet 15 mins over and I have no idea what you were trying to tell me with this
do you just wanted to show me another way of presenting 2sqrt?
jolly comet
rational approximations are one of the basic topics of number theory
fast monolith
k
jolly comet
there's a lot written about them, especially with respect to irrational numbers like sqrt2
if you aren't currently savvy it's time to do some research and get savvy
fast monolith
alright
jolly comet
remember: if they gave this to you as a problem that means it has a solution
if they said "prove or disprove" it would be a different story, but they said "prove"
jolly comet
some positive integer
fast monolith
but then it's not sqrt2
jolly comet
$\sqrt2 = \frac{a}{10^p} + \epsilon$
sterile pumiceBOT
tubular:
jolly comet
a is a positive integer
p is a positive integer
epsilon is a real at most 10^-p
if you have k zeroes in sqrt 2 starting at position p, you can make epsilon smaller by k factors of ten
a/10^p is meant to be a rational approximation
sacred junco
@rockpaperscissors#4131 its not a problem but i still havent solved it
And uh B can have any x corresponding the the values of the set phi(m)
@gilded tinsel
gilded tinsel
and for A its all values corresponding to phi(n) right?
gilded tinsel
first thing prove that na+mb is coprime to mn
hint: suppose a prime divides both mn and na+mb and then use euclid’s lemma
sacred junco
Yeah no thats sorted
If p|mn then it divides either m or n
So if its divides it needs to divide b
And b will be from the set of phi (n) numbers
Oh no wait
@gilded tinsel i hit a wall
Lolaoalolao
Uh (na+mb)/mn=a/m+b/n and gcd (a,m)=1
And gcd (b,n)=1
So they both must be coprime
gilded tinsel
p|mn implies p|m or p|n
if p|m then na+mb=na (mod p) or if p|n then na+mb=mb (mod p)
in the first case if p|n this contradicts gcd(m,n)=1 so p|a
but this means that gcd(m,a)=p which is again a contradiction
similarly for the second case
hence na+mb and mn are coprime
@sacred junco
now onto the second part of the problem
we need to prove that no two elements of C are have the same residue mod mn
recall what it means for two numbers s and t to have the same residue mod k
$k|s-t$
sterile pumiceBOT
rockpaperscissors:
gilded tinsel
so take two distinct elements of C, assume their difference is divisible by mn and derive a contradiction
as a hint: the contradiction will have something to do with the maximum size of the sets A and B
sacred junco
@gilded tinsel i didnt jse congruences but my proof also works right?..im just confirming if it is correct
Also I have literally no clue how to do this
But as far as i see it its not possible for mn to divide a number less than itself..
So the difference must be less than mn-1
So like a number cant divide a no. Smaller than itself right?
gilded tinsel
well yes but thats not relevant here
whats relevant is the residue classes
also i dont understand how ur first proof works
sacred junco
Ok ..uh the book doesnt cover anything like residue classes so uh..i mean it mightve covered it but it didnt use the exact word
Please walk me through that once
And also my proof just shows what yours does...but not in mod arithmetic rather plain division
I just checked haha
@gilded tinsel
Wait
gilded tinsel
?
sacred junco
U basically mean to show that each element corresponds to the set ={1,2,3,....,mn-1} right?
Like if i take a_i from the set C and x_i from the set c i just need to show x_i is not congruent to a_i to mod mn
gilded tinsel
yes
sacred junco
Oh dude there was a direct theorem for this i cant remember
Aaaaa
Ahh got it
No this doesnt work here
Let me try ill ping u if i cant do it in a reasonable time
Ahh yeah i got it
My internet sucks image isnt being sent
@gilded tinsel there
Also if the pings are irritating let me know
gilded tinsel
yeah thats right
youre one was a bit quicker than mine actually
you should throw the extra caveat that c_1 doesnt equal c_2
from there, do you know how to finish the proof?
sacred junco
I mean im never sure what to do tbh
Im still confused because we proved that it C will hit only the values in the set{1,2,3,...,mn-1},whats the guarantee it WILL hit each of them?
gilded tinsel
yeah this is the last part
the number of elements less than mn and coprime to it is phi(mn)
sacred junco
Yeah
sacred junco
Hmmhm
gilded tinsel
a has how many options?
sacred junco
Phi(m)
gilded tinsel
and b?
sacred junco
Phi(n)
gilded tinsel
so how many altogether
sacred junco
Oh so phi(m) times phi(n)
sacred junco
Actually thats the follow up question
I need to prove that phi is mulitplicative using this question
gilded tinsel
hmm
sacred junco
But hey we know
We have phi(m) times phi(n) choices forC
And we also know we have phi(mn) choices for C by the facts given in the question
So phi (mn)=phi(m)*phi(n)
Done i guess
gilded tinsel
well no
thats circular
cuz to finish the proof i need the multiplicativity of phi which we havent proved
sacred junco
Ok so uh we prove this question by multiplicativity and then prove multiplicativity by this question?
gilded tinsel
thats what you tried to do
so if you want to prove phi is miltiplicative by this question
sacred junco
Yeah exactly
gilded tinsel
then we need to find another way
sacred junco
Oh man
sacred junco
Ahh too bad
gilded tinsel
ill try working on it tho
sacred junco
Best of luck man!
gilded tinsel
sum big thonkering to do
sacred junco
Haha yeah
gilded tinsel
thx
stark vapor
english was really fun tbh xD
anyway, I can't start that conversation here, not number theory
stark vapor
Let p be an odd prime. Show that x^4 + 1 ≡ 0 mod p has a solution iff x^8 ≡ 1 mod p
because "=>" obvious, and "<=" we have [x]∈ U_p (the cyclic group of units), and cyclic groups of even order have a unique element of order 2 (in this case it's [-1]) so x^4 ≡ -1 mod p
Now x^k ≡ 1 mod p iff the order of [x] divides k
this follows from the remainder theorem as k = q(order of [x]) + r where r = 0 or 0 < r < (order of [x]), then x^k = x^(q(order of [x]) + r) = x^r ≡ 1 mod p, which can only happen if r = 0
Finally using fermats little theorem, x^(p-1) ≡ 1 mod p, so the order of [x] which is 8 divides p-1, hence p - 1 ≡ 0 mod 8, hence p ≡ 1 mod 8```
(edit: only showed x^4 ≡ -1 mod p implies p ≡ 1 mod 8 )
vast dove
Oh I forgot it's In This channel lol
stark vapor
I could have put it in advanced number theory
sacred junco
@stark vapor but what is x, again?
stark vapor
should probably state x is an integers xD
stark vapor
what about it?
sacred junco
Then x^4 == -1 can't be like this
Thus x is restricted or it is like there exists x or sth
jolly comet
if x = p then x^4 and x^8 are 0 mod p
stark vapor
give example 
jolly comet
so (x^4 = -1 mod p) and (x^8 = 1 mod p) are both false
sacred junco
Counterexample of (<=) case
Oof the original problem isn't here
This was a solution for this problem - sasha said this.
question 1 (2 marks): show for p an odd prime, x^4 + 1 ≡ 0 mod p, iff, p ≡ 1 mod 8
stark vapor
oh derp
sacred junco
What is x here
It has given no qualifiers, no whatsoever
stark vapor
there
fixed
xD I was wondering what you guys were saying, but yeah I didn't state it correctly
sacred junco
Ah, so existence. I see
So p = 1 (mod 8) then you just simply take the primal root g
And x = g^(p-1/8)
Maybe it's just enough to say, multiplicative group of Z_p is isomorphic to additive group of Z_(p-1)
Then only need to state that |-1| = 2
stark vapor
Dun like number theory
limber crow
I'm trying that in the set {1^2, 2^2, ..., m^2}, there are two elements that are congruent modulo m (for m > 2)
any hints?
oh nvm I'm just stupid
m | (m-1)^2 - 1, I forgot that (-1)^2 = 1
gilded tinsel
@sacred junco i figure if you can prove that phi(m)*phi(n)>=phi(mn) this woukd imply theyre equal
also i bombed my english test
sacred junco
Rip
Also i can at best prove they are equal using what i did before
But tbh lets just assume it in fact is multiplicative..this book is whack af
odd nexus
@sacred junco want a proof that phi's multiplicative ?
this is a proof that our teacher showed us and i later saw it in a book as well
sacred junco
Yeah the matrix proof
I guess then let's take it that it is multiplicative
@gilded tinsel what next?
Phi(m)*phi(n)=phi(mn)
gilded tinsel
there are phi(mm) elements of C
there are phi(mn) numbers less than mn and coprime to mm
all the elements of C are in different residue classes mm and all elements of C are coprime with mn
meager merlin
if exact form of prime counting function exists, doesn't that means that pi(x) - pi(x-1) is 0 for non-prime and 1 for prime
quick furnace
yes it does
vast vessel
"if exact form of prime counting function exists"
what
"pi(x) - pi(x-1) is 0 for non-prime and 1 for prime"
by definition this is true?
quick furnace
maybe they meant that if pi(x) were expressible in closed form then so would the indicator function of the set of primes?
stiff rivet
but there is a closed form expression of prime counting function
This works for example
Well, maybe it depends on how you define "closed form"
But it's computable in a finite number of steps
stiff rivet
Because I just gave you one?
unique vaultBOT
stiff rivet
Unless you don't allow rounding and factorial in your closed form expression
vast vessel
more so that there is not a fixed amount of operations
stiff rivet
It's just multiplication
noble elm
Factorial is closed form bb
sacred junco
Factorial sequence was a closed form?
what natural sequence isn't a close form then
Every elements of natural sequence takes finite time to evaluate
vast vessel
sacred junco
@vast vessel whi
surreal shuttle
Can someone explain past Let b_l = last b_i != 1 (mod n)...
In particular I don't understand the line after that
sacred junco
@surreal shuttle it is mixing english with equation lol
surreal shuttle
Yeah but I still don't get what my professor is trying to say
sacred junco
Ah that
@surreal shuttle that is trivial though?
Do you get what he means by 'last b_i such that b_i != 1 (mod n)' ?
surreal shuttle
Mmm no I don't
sacred junco
Hm yeah
surreal shuttle
I guess that would be k-1?
sacred junco
Do you get what b_i is then?
surreal shuttle
Oh
surreal shuttle
So k-1 = i = l?
surreal shuttle
Just kind of by how it's defined if b_k = b_k-1 ^2 = 1, then it would just make sense that l = k-1
I guess I don't have a good reason besides that
surreal shuttle
Yeah
sacred junco
Then do you know how sequence b is defined?
surreal shuttle
squaring the previous term?
sacred junco
Ye but do you know what you mean when you say 'the previous term'
sacred junco
Let's suppose wr have a nontrivial relation a^r = 1 (mod n)
Do you know what this means?
Also do you know what r even means?
surreal shuttle
r is even?