i often forget rules for basic exponents
#elementary-number-theory
hexed atlas
Practice makes perfect, they are annoying to remember at first
fossil cape
(5^n)(5^v) = 5^(n+v) right?
hexed atlas
Yep
fossil cape
wait how do i factor exponents
wait nvm
wtf
are you allowed to have fraction exponents
in this case
full summit
@swift shard
swift shard
@full summit Looks good to me
swift shard
Do you have an example?
full summit
(42)(43(45)(41)belong to the subgroup A5
swift shard
A5 is the group of all even permutations on 5 elements
Looking that up because I forgot, lol
"An even permutation is a permutation obtainable from an even number of two-element swaps"
full summit
what if it were odd permutations?
swift shard
Fairly certain yours is even, as it is written with 4 transpositions
vast plank
Hey guys, I'm struggling to prove that
$$p_n \sim n\log(n)$$
using the PNT
stoic basinBOT
stoic basinBOT
vast plank
But I'm not sure where to go from there
Not sure if I know enough analysis to know what to do
sacred junco
Isn't what you're trying to prove the statement of the PNT itself?
vast vessel
I presume they are trying to show that $$\pi(n)\sim\frac n{\log(n)}\Rightarrow p_n\sim n\log(n)$$
stoic basinBOT
vast plank
The PNT is $$\pi(x) \sim \frac{x}{\log(x)}$$
stoic basinBOT
vast vessel
you probably need some upper bound on p_n
hm okay
=tex \pi(x)\sim\frac x{\log(x)}\ll\frac x{\sqrt x}=\sqrt x
=tex n\ll\sqrt{p_n}
=tex p_n\gg n^2
=tex p_n\sim n\log(p_n)\sim n\log(n\log(p_n))\gg n\log(n\log(n^2))\sim n\log(n)
wait no
nope ignore that 
wait
oof
inequalities are all backwards
@vast plank ignore the above and begin reading here
=tex \pi(x)\sim\frac x{\log(x)}\gg\frac x{\sqrt x}=\sqrt x
stoic basinBOT
vast vessel
=tex n\gg\sqrt{p_n}
stoic basinBOT
vast vessel
=tex p_n\ll n^2
stoic basinBOT
vast vessel
=tex \begin{align*}p_n&\sim n\log(p_n)\&\sim n\log(n\log(p_n))\&\ll n\log(n\log(n^2))\&\sim n\log(n)\end{align*}
stoic basinBOT
vast vessel
=tex p_n\gg n\Rightarrow p_n\sim n\log(p_n)\gg n\log(n)
stoic basinBOT
vast plank
@vast vessel sorry had to take a call, will read through in a min
vast vessel
t!remindme reading in 1 minutes
unique vaultBOT
⏰ | Got it! I'll remind you in 1 minute!
vast vessel
vast plank
aaa sorry that took so long
@vast vessel thanks very much for the help
I think that makes sense, I'm not completely familiar with the
=tex \gg
stoic basinBOT
vast vessel
🤷 idk if it's standard notation tbh
vast plank
I feel like my school should have made analysis a prerequisite for this num thy. module I'm taking
vast plank
like f(n) = o(g(n)) then, or am I barking completely up the wrong tree?
vast vessel
@vast plank it's just inequalities, like log(n) < √(n)
vast plank
oh fair, sorry
neon comet
im stuck
how does this mean that https://i.imgur.com/uM2qnVo.png
So the complement to A_1 = everything thats not in the union
thats all i got
neon comet
<@&286206848099549185>
neon comet
hello
neon comet
no man im only in highscool
hexed atlas
It says that $(A \cup B)^c = A^c \cap B^c$
sterile pumiceBOT
Puerøsola:
hexed atlas
So the elements which aren't in the union, are the elements which aren't in A and aren't in B
Does that make sense?
I can prove it if you want
neon comet
Yes that is what i got
hexed atlas
The proof might be confusing though if ou aren't familiar with logic
neon comet
this is all new to me
hexed atlas
Ah ok
neon comet
Can i tell you what i got
hexed atlas
Ok
neon comet
and you can tell me where im retarded
hexed atlas
Haha go ahead
neon comet
so this side https://i.imgur.com/mh3UnnP.png
im udnerstanding:
everything thats outside the sets
and other side
the compliment of all intersections
so basically
in a diagram
first pic = all area around the sets
and then im stuck
neon comet
looking through
yeah
yeah i guess its the series that scared me cause i never seen it before
i only done with max 3 sets
hexed atlas
The same thing holds for any finite number of sets
Although we now have to use some form of logic to prove it
neon comet
What with this series i have i was thinking: maybe some A's intersect and some dont
hexed atlas
Induction is an easy way if you have done that
neon comet
i have not
hexed atlas
Let's do it in words then
neon comet
i know bit of electromagnetic induction but i feel that wont be helpfull here lmao
hexed atlas
So $x\in \bigg(A_1 \cup A_2 \cup \dots \cup A_n\bigg)^c$ means that $x$ is not in $A_1 \cup A_2 \cup \dots \cup A_n$, right?
sterile pumiceBOT
Puerøsola:
neon comet
yeah in a diagram this would be all x not in any of the sets
neon comet
ye
hexed atlas
So that means
That $x$ is not in $A_1$, $x$ is not in $A_2$, $x$ is not in $A_3$, ..., and $x$ is not in $A_n$
sterile pumiceBOT
Puerøsola:
hexed atlas
Because x is not in the collection of everything from every set, it can't be in any of the sets
neon comet
yeah " x is not in any of the sets" which means its in the complmentary of the sets?
sterile pumiceBOT
Puerøsola:
hexed atlas
So, what we said above can be written\
$$x\in (A_1)^c, x\in (A_2)^c, \dots, x\in (A_n)^c$$
sterile pumiceBOT
Puerøsola:
stoic basinBOT
neon comet
let me process this
hexed atlas
Sure :)
neon comet
x is an element thats not in A1, A2, A3, is what im reading
hexed atlas
Yes, x is something which is not in any of the sets, which means x is in the complement of each set
hexed atlas
Ok
Now, if x lives in set A and x lives in set B, in general, x lives in the intersection of A and B
That's the definition of intersection, $A\cap B$ is the collection of all elements in both $A$ and $B$
sterile pumiceBOT
Puerøsola:
hexed atlas
This is in general
neon comet
yes
hexed atlas
So, x must be in the intersection of all those complement sets
Since that intersection is exactly those things which live in every one of the sets
neon comet
is that the "proof"?
neon comet
i dont think it will be needed i just need to process all steps
and get the whole picture
hexed atlas
Sure
neon comet
ok 😃
hexed atlas
We start with
$$x \in \Bigg(\bigcup_{i=1}^{n} A_i\Bigg)^c = \big( A_1 \cup A_2 \cup A_3 \cup \dots \cup A_n\big)^c$$
so this is the same as saying that $x$ is not in that union, i.e.
$$x \not \in (A_1 \cup A_2 \cup A_3 \cup \dots \cup A_n).$$
Since $x$ is not in the collection of every element from every set, $x$ can't be an element of any of the sets. That is,
$$x\not \in A_1, x\not \in A_2 , \dots, x\not \in A_n.$$
That is,
$$x \in (A_1)^c, x\in (A_2)^c, \dots , x\in (A_n)^c.$$
So $x$ is in every one of these complement sets. That means exactly that $x$ is in the intersection of them all!
$$x \in (A_1)^c \cap (A_2)^c \cap \dots \cap (A_n)^c.$$
Writing this more compactly, we have
$$x \in \bigcap_{i=1}^n (A_i)^c.$$
Which is what we wanted.
stoic basinBOT
sterile pumiceBOT
Puerøsola:
neon comet
holy fuck
hexed atlas
❓
neon comet
just alot 😃
neon comet
thanks again man im sure all these helps can help me understand
neon comet
@hexed atlas areu still around?
sterile shadow
not sure if this belongs here, but how do I prove it by induction? dont know why it breaks when I try to do it
sacred junco
It's obvious that each sqrt(k) < sqrt(n), but that's not enough obviously
sterile shadow
ACtually I think I found my problem
jsut want to ask if taht legal
if
I take that it is true for n
sacred junco
And I had the inequality backwards. Problem: asking me for help :)
sterile shadow
hah
but
is my thinking good: if for n it is true then right side will be 2(n+1) sqrt(n+1) +1 + R(N) (right side for n) - (2n* sqrtn +1)
sacred junco
Something like that, yes.
sterile shadow
Cause I want to compare both sides, since Left side for n+1 is L(n) + 3 times the root
Ok thanks, I hope you got what I meant 😄
sacred junco
You're looking for the difference between n and n+1 on both sides. If you can show the inequality holds for the difference, it holds for the sum. Of course, you need an initial case for the induction too
On the left, it's 3sqrt(n+1) on the right, it's 2(n+1)sqrt(n+1)+1 - (2n(sqrt(n)+1)
Which is pretty much what i think you said :)
sterile shadow
gotcha, thanks again
heady raven
number a cant be represented as a ratio of two prime numbers
how can we find two prime numbers p and q that gives us a minimum of (p/q - a)?
and is there a minimum at all?
wide shuttle
hm
a can't be b/c, where b,c are primne
but, b,c have to be coprime
so...
the 'a' could be (14/15)
Maybe there is no minimum
hm
(14x+n)/(15x+m), as x -> infinity, there will always be some numbers n,m that make (14x+n), (14x+m) prime.
sacred junco
a^3 - a = a (a^2-1) = a (a+1) (a-1) one of which must be a multiple of 3
gaunt rose
Why must one be a multiple of 3
wide shuttle
out of 3 consecutive numbers, 1 of them is a multiple of 3
if a isnt, then them ultiply is either a+1 or a+2
gaunt rose
Ahh ok
I get it
But i still dont get how a^3 is equal to a mod 3 when for example a = 2
2^3 = 8
2 mod 3 = 2
wide shuttle
8 = 2+6 -> 2
wide shuttle
maybe the mod3 is applied to both sides?
proven topaz
@stuck lintel op
proven topaz
never knew mods went on both sides O.o
mellow nimbus
that's fermat's little theorem
if z is not a multiple of a prime p, then p divides z^p - z
which can also be written as z^(p-1) = 1 mod p
it's a theorem of elementary number theory which is incidentally the base concept behind many encryption algorithms
rain thicket
Ooh, that colour scheme is really nice.
Do you have the code lying around @heady raven ?
gaunt rose
Let a, b, and m be integers, and m ≥ 2. Prove that
ab ≡ [ (a mod m) · (b mod m) ] (mod m).
static sparrow
use euclidean division stuff I guess
half fable
what have you tried
half fable
what's the definition of a mod m
you can start doing most problems by unpacking the definitions
and understanding what each term means
gaunt rose
mod gives the remainder
half fable
a = (a mod m) + km for some k
gaunt rose
Ok
I understand better with examples so if you can do this step by step with me that would be appreciated
So ok i assume b = (b mod m) + km as well
static sparrow
Euclidean division is that algorithm you were taught very young to compute divisions,
the very process of finding q and r such that a = bq + r with r in [0,b-1]
gaunt rose
(a mod m) · (b mod m) + (a mod m) · km + (b mod m) km + k^2m^2
half fable
yes
half fable
no
gaunt rose
lol
gaunt rose
xD
gaunt rose
jm
half fable
you see my point?
gaunt rose
I need to factor out mod m instead?
gaunt rose
(a mod m + km) * (b mod m + jm)
Ok wait
(a mod m) · (b mod m) + (a mod m) · jm + (b mod m) km + k^2m^2
(a mod m )* (b mod m) + m( (a mod m) j + (b mod m) k + k^2m)
half fable
what
gaunt rose
Oh no
half fable
no
gaunt rose
Can you write it for me
Cause the mod m is confusing me
This is what i got factoring m
(a mod m )* (b mod m) + m( (a mod m) j + (b mod m) k + k^2m)
half fable
you wrote it fine
half fable
ab = (a mod m )* (b mod m) + m( (a mod m) j + (b mod m) k + k^2m)
what is this equal to mod m
gaunt rose
But its ab (mod m)
Im pretty sure ab ≡ [ (a mod m) · (b mod m) ] (mod m).
is equal to
ab (mod m) = ((a mod m) · (b mod m) ) (mod m)
Basically the mod m is on both sides
fathom sierra
the notation they use is hella confusing with their (mod m)s everywhere
half fable
yeah those two are equivalent
gaunt rose
I know man
But to answer your question fruit, i have no idea what happens if you mod m the right side
Lets try it and see what happens
(Meaning you show me what it is lol)
fathom sierra
Show that if $$\begin{cases}a\equiv b \pmod{m}\a'\equiv b' \pmod{m}\end{cases}$$ then $$aa'\equiv bb' \pmod{m}$$
tbh that's how i'd write the problem statement
sterile pumiceBOT
emeric75:
fathom sierra
m( (a mod m) j + (b mod m) k + k^2m) is divisible by m, so m( (a mod m) j + (b mod m) k + k^2m) == 0 (mod m)
gaunt rose
Oh and then (a mod m) (b mod m) 0mod m = (a mod m) (b mod m) mod m? ?
Why does the 0 leave
fathom sierra
that's a property of congruences also
if $\begin{cases}a\equiv b \pmod{m}\a'\equiv b' \pmod{m}\end{cases}$ then $a+a'\equiv b+b' \pmod{m}$
sterile pumiceBOT
emeric75:
gaunt rose
Ahh cause fruit told me to use km for a and jm for b
Look
Thats where im at
But if i mod m both sides at the end
It will be messed up no?
Did i mess something up?
fathom sierra
~~gotta take a shower ~~
gaunt rose
Damn
😦
My last question for my assignment then im done lol
I just wanna get it over with
And i gotta go bring it to school too 😭
@half fable
Can you check it for me please?
Wait
0 mod m = 0 right?
So at the end itll be (a mod m) (b mod m) + 0
And then mod m both sides and voila?
I see you @swift shard
Dont be shy 😝
swift shard
I'll throw out a quick proof. Let
a = a' (mod m)
b = b' (mod m)
Then
a = a' + km
b = b' + km
ab = (a' + km)(b' + km)
= a'b' + a'km + b'km + k²m²
= a'b' + (a'k + b'k + k²m)m
Since a'k + b'k + k²m is an integer:
ab = a'b' (mod m)
swift shard
Note the (mod m) at the end is like a note. "This line uses mod m arithmetic"
So be careful where you have and don't have it. Also, using it in the line is awkward, lel
gaunt rose
And then you would mod m both sides?
@swift shard
WAit did you mean to say
a' = a (mod m)
Cause that would make more sense
Damn i hate when ppl disappear
<@&286206848099549185>
Anybody please
I just wanna finish this
gaunt rose
Lol rlly?
I thought when you said a = a' + km
Youre essentially saying a = (a mod m) + km
Which would mean a' = a mod m
swift shard
No. So note the non-existance of (mod m)
a = a' (mod m)
Is, by definition
a = a' + km (regular, non-modulo integers)
Any line that doesn't have (mod m) on it is a line that's working in the regular integers
gaunt rose
Ah ok
swift shard
Feel free to ask anything if it doesn't make sense, that's how you learn!
gaunt rose
Yeah
Thanks
My bad for stressing you out
Its just cause my assignment is due today and i gotta go bring it
swift shard
I'm not stressed. I get it, I learned these once too
gaunt rose
Thanks again
swift shard
@gaunt rose
I derped. My proof is making a mistake. It's not a proof-breaking mistake, but it's a derp.
a = a' + jm
b = b' + km
Where j isn't necessarily equal to k
fathom sierra
@swift shard we have the same modulo taste hehe 
swift shard
I liked your suggestion it was good
mellow nimbus
I'm kinda confused as to why you use mod as an operator rather than to express a relationship
and it seems to be confusing you too when you don't get why "it's only on one side"
fathom sierra
mod as an operator ewwww
totally agree with you on this point
the problem was stated originally using it as an operator, then i couldn't stand it so i rewrote the problem statement :/
sturdy dirge
Double post.
fathom sierra
(shitty internet)
mellow nimbus
Yeah I just mean that perhaps he should learn to use mod "properly"
fathom sierra
maybe the book he/she's using should use it properly also lel
mellow nimbus
Fair enough
"mod gives the remainder" is true but makes it seem more complicated than it actually is
Which brings me to a 'fun' problem
leaden peak
When mod is used as an operator it's usually expressed the way it is in this problem right? If it's all written out properly, it's being expressed as a relation
swift shard
It's bad form, imo, to express mod as an operator, unless you're actually using it as an operator like in programming.
mellow nimbus
@leaden peak in this problem we're looking at remainder classes mod 3. That is, every element being congruent to k mod 3
And that's done because it forms a nice structure with respect to some operations
leaden peak
Hmm
What's the full problem in English, if possible?
Oh I see
So we just have to determine the remainder class of that really long number
Is k 2?
frank knot
Asumme c and e arbitrary and N=2^(8*k), k any integer > 0
I have to show that
c*(s^e) mod N
is a discrete uniform distribution in Z_n.
s is choosen completely randomly
I began with saying that we can assume s<N, as for all s>=N we can choose s'=s mod N and know that c*(s^e) = c*(s'^e) mod N
This is argued in the context of RSA, meaning c=m^e so I could write c*(s^e) mod N = (m^e)*(s^e) = (m*s)^e mod N
I do further know that N must be the product of two prime number p and q (RSA) and e must have been chosen such that gcd(e,phi(N)) = gcd(e,(p-1)*(q-1)) = 1
I sadly cannot post the original task as it is not in english
It also makes no sense that N must be the multiplication of two prime numbers if it is of form 2^(8*k)
frank knot
I talked with one if my tutors and he specified the assumption I could make. I summarized the 'new' question in this
https://math.stackexchange.com/questions/3009106/why-is-c-cdot-se-mod-256k-a-uniform-distribution-on-mathbbz-256k-f post
upbeat wren
hmm s', c, e are all arbitrary and from 0 to N - 1 ... just making sure?
upbeat wren
so for all a, ac is uniformly distributed, no?
(all integers a technically)
oh oops
For any invertible c in mod N, if a is uniformly distributed in mod N so is ac in mod N.
That's what I meant.
sound ok?
frank knot
So ac is uniformly distributed? Why exactly?
upbeat wren
um for any invertible c ... c, 2c, 3c, 4c, ... Nc spans all residues of (mod N) if N = 2^n
assume it doesn't for distinct a, b for 0 <= a, b < N, ac = bc (mod N) and a = b (mod N) and a - b = kN and b - a is divisible by N but 0 <= a, b < N so WLOG b >= a and 0 <= b - a < N. b = a. not distinct and contradiction. (there is probably a much slicker proof of this)
so assuming a is uniformly distributed, ac spans all residues and is also uniformly distributed.
for finite {a}
frank knot
I get the contradiction I think. You did not use c invertible and N=2^n did you?
upbeat wren
the invertible is used to go from ac = bc (mod N) to a = b (mod N)
Yaah, N = 2^n may not be necessary. (still pondering that)
frank knot
There were subtasks were I needed that so it MIGHT not be necessary
upbeat wren
oh. yeah for your specific example N = 2^n will help.
or at least not hurt
if c is invertible in mod N, does that mean there is a distinct And invertible z such that z^e = c? If so ..
(z^e)(s^e) = (zs)^e (mod N)
looks kinda nice
frank knot
I can solve it, if I can assume the existence of a d such that s^e^d=s. I am not sure, if I can as so much of the rsa context is not true, so I will ask my tutor once more.
The idea then: (c*s^e)^d mod N = c^d*s mod N = k^d mod N, if k=c*s^e
c^d is invertible, if c invertible. Take the inverse of c, let that be c' and then: c^d * c'^d = (c*c')^d = 1^d =1 mod N
s is uniformly distributed in [0,...,N] and c^d invertible so s*c^d = k^d mod N uniformly distributed
k^d must be smaller than N so 1<=k^d<N is uniformly distributed and as k has to be smaller than N as well and the same k cannot yield different k^d, k must be uniformly distributed on [1,...,N]
((I'm on mobile rn hope the format and phrasing will be alright))
frank knot
I can assume that the d exists, so I think my proof should be valid
frank knot
Thank you very much vincent. Your proof of ac uniformly distributed helped a lot!
upbeat wren
you are quite welcome.
unreal rapids
(i know it's pretty trivial - don't beat me) could someone please help me getting an idea about solving this kind of problems: decide whether there exist integers a,b such that a,b>1, a+b-1 is a prime and (a^2+b^2-1)/(a+b-1) is an integer
stuck lintel
Okay this should work I think?
$\frac{a^2 + (b-1)(b+1)}{a+b-1}$. Let c=b-1. $\frac{a^2 + c(c+2)}{a+c} = \frac{2c(c+1)}{a+c} - a + c$. Since -a+c is an integer we only care about making $\frac{2c(c+1)}{a+c}$ an integer. Notice that since $a>1, \frac{c+1}{a+c} < 1$ and therefore $\frac{2c}{a+c}$ must be an integer. Since $\frac{2c}{a+c} < \frac{2a + 2c}{a+c} = 2$, $\frac{2c}{a+c}$ must equal 1. This implies a=c. However since a+c is a prime greater than 2, a and c must have different parities, a contradiction, and hence there exist no (a,b)
sterile pumiceBOT
Plum:
stuck lintel
@unreal rapids
stuck lintel
thanks i just hope i didnt make a mistake somewhere
unreal rapids
but shouldn't it be 'a-c' instead of '-a+c' in the second line?
it doesn't really change the result, just saying
stuck lintel
oh yeah i think youre right my bad
mellow nimbus
@leaden peak whoops. yeah, k was 2 lol
sacred junco
Prove that if positive integers a, b, c, d satisfy the equation a^2+b^2+c^2+d^2=2018! they are bigger 10^250.
neon comet
alright guys i spent all day learning about modular arithmetic and i understood the basics of it and before i google it i wanted to ask you guys what one can actually use it for? preferable with basic example
I also had a look at Diophantine equations and i do see how that is useful for certain calculations
but just normal modulo i get no natural understanding of where one can apply that knowledge
short surge
"what can one use modular arithmetic for"
Encryption xd, basically all of your bank details wouldn't be safe if it weren't for the modulus boy
other applications i'm not really aware of, i've been trying to look myself as well
I've used modular arithmetic to prove no square can have a remainder of 2 if it's divided by 4 for example
the proof of fermat's last theorem uses modular arithmetic iirc
@neon comet
pbs infinity has a couple of cool vids that involve modular arithmetic
I'd say it's a powerful tool for partitioning the number line and thus proving things
stuck lintel
Mods are useful because they let you be lazy and not divide
sacred junco
yeah I guess if you want to get remainders
it is sometimes nice to cyclically access arrays
humble wraith
i need help with a diophantine equation
i need to prove that a^2 - 2 b^2 = 1 has infinitely many integer solutions
i know empirically that the ratio of successive values for b converge to sqrt(34)
oh shit
i don't actually know anything about diophantine equations because this problem showed up in a ring theory class
where i have to show that Z[sqrt(2)] has infinitely many units
i decided to just invoke the fact that Lagrange has proved this already
leaden peak
@mellow nimbus heh thanks for the confirmation
mellow nimbus
@neon comet RSA is a thing because of Fermat's little theorem
Not all forms of encryption rely on mod arithmetics tho, e.g. ECDSA relying on elliptic curves
leaden peak
well, nowadays we might consider elliptic curves kinda mod arithmetics, thanks to developments in that field...overall, cryptography and number theory are deeply linked
mellow nimbus
yeah but what makes ecdsa secure is fundamentally different from what makes rsa secure
charred oar
Can someone help give a somewhat mathematical explanation on why is it that when you reverse a number its common multiple stays the same?
e.g 24 is a multiple of 3 and reversed (42) is also a multiple of 3
smoky knoll
that is not generally true
23 is a prime number, 32 is not
what you might be thinking about is the rule for divisibility by 3
where if the sum of its digits id divisible by 3 then it itself is
rearranging the digits will not change their sum
take a number abcd
@charred oar that's the most intuitive explanation of why the 3 digit rule works
and that should explain why you can rearrange the digits in cases where the number is divisible by 3
sacred junco
incidentally that also shows that it works for 9 as well
sacred junco
i_p(m) is called the p-adic valuation of m
the first sum is not quite legendre's formula
the valuation is additive, the last one is kummer's lemma
which says the power of p on the binomial coefficient n choose j is equal to the number of times you have to carry when you add j to n-j in base p
or at least I think that's it, in disguised form, actually no it's simpler than that
it comes from showing that i_p(ab) = i_p(a)+i_p(b) and simply writing the binomial coefficient as a product of factorials
it is basically a logarithm
damn both of those summations are not even interesting results
they're like the first steps towards getting interesting results
which are not too far away
$i_p(n!) = \frac{n-s_p(n)}{p-1}$
sterile pumiceBOT
Empty Axes:
sacred junco
s_p(n) is the sum of digits of n in base p
smoky knoll
alright, that gives me some good leads to start unpacking everything, thanks
sacred junco
yeah definitely try to prove i_p(m) is additive, also the first summation is kind of, uhh, common sense
I don't mean that in a condescending way haha I just mean like try to think of i_p(n!) as being what's the power of p on n! and think about how n! is a product of consecutive numbers
smoky knoll
that part makes sense
unreal rapids
Could please someone help me with this: i have to decide whether there exist different primes $p_1, p_2, ..., p_n (n>=2)$ such that $\sum_{i=1}^{n} \frac{1}{p_i}$ is an integer
sterile pumiceBOT
asj 🦌:
sacred junco
what happens when you multiply an integer by an integer? you get another integer. What if you multiply this "integer" by a product of all the primes except for one of them?
that's how I would answer it
unreal rapids
oh my, how haven't I realized that
sounds trivial
thank you anyway @sacred junco ❤
sacred junco
it's sorta a common trick, like in proving the rational roots theorem I think
unreal rapids
yeah i gotta learn those, 'cause I'm preparing for competitions now
not the highest level, but you know, gotta start with something
sacred junco
fun fun
yeah if you have more problems I like playing around with that kind of stuff
I'm not the best I would just say I got lucky on that last one haha
unreal rapids
Okay: another one that is probably trivial but somehow i can't do it (well, i have actually done it, but in an unsatisfactory way); Find all positive integer values of n that satisfy the following equation: $2^n+33=k^2, k \in \mathbb{Z}$
sterile pumiceBOT
asj 🦌:
sacred junco
not sure but did you try to evaluate it mod 4
hmm
I'm pretty sure the power of 2 and 32 being a power of 2 is part of a nice solution
squares and mod powers of 2 tend to be kinda funny
like all odd x are x^2=1 mod 8 idk if that's true for higher powers of 2
idk is this what you were thinking about or not
unreal rapids
but shouldn't it mean that x is always congruent to 1 mod 8?
+-1
or do i misinterpret it
sacred junco
not necessarily, so like 3^2=1 mod 8
but 3 is not 1 or -1 mod 8
7 is -1 mod 8 though
5 is another counter example here
so I guess the question you want to know the answer to is, when can you look at this thing being unique like you're wanting it to behave, like a field
that's when you're dealing with mod p arithmetic for p prime
otherwise you end up with a ring, don't worry so much about the jargon, just probably good to know it exists at least
you don't get clean inverses mod n unless n is a prime
to say it intuitively
unreal rapids
Oh it is actually true for any odd integer: let's say $x^2\equiv 1 (mod 8)$, then $(2k+1)^2\equiv 1 (mod 8)$ which is equivalent to $4(k^2+k)\equiv 0 (mod 8)$. And it is always true, because in the first case, when k=2n+1 (odd), it takes form of $8(2n^2+3n+1)\equiv 0 (mod 8)$, which is obviously true, or in the second case, when k=2n (even), then it takes form of $8(2n^2+n)\equiv 0 (mod 8)$ which is true as well.
sterile pumiceBOT
asj 🦌:
sacred junco
wait back up, if someone says x^2=1 mod 8 that does not mean that x=1 mod 8 or x=-1 mod 8, that's all I meant by my last comment
and gave the example x=3 as a counter example, since 3 is not 1 or -1 mod 8
but 3^2 = 9 = 1 mod 8
unreal rapids
yeah ok, just wanted to make sure $x^2\equiv 1 (mod 8)$ is always true
sterile pumiceBOT
asj 🦌:
unreal rapids
ofc for odd x
sacred junco
ahh ok I see
I don't see any super nice way to solve this problem
I'm just imagining looking at cases and breaking it down haha
unreal rapids
uhh, checked that with the mod, all it gives is that n must be greater than 3
sacred junco
yeah, I don't think that trick is going to help in this case, but it's quick and easy check to try out
when n>4 if you reduce mod 32 you end up with 1=k^2 mod 32 which means k=1+8m
unreal rapids
well, i've found that 4 works
but that doesn't give us much
ughh this question kills me
sterile pumiceBOT
Empty Axes:
sterile pumiceBOT
Empty Axes:
sacred junco
maybe plug in k=2a+1 to simplify a bit cause we know k is odd
I think k+1 and k-1 is divisible by 8
because one is 0 mod 4 and the other is 2 mod 4
$2^2 (2^m+1) = \frac{(k+1)(k-1)}{2^3}$
sterile pumiceBOT
Empty Axes:
sacred junco
just nice to think the right side is an integer for sure, idk lol
maybe now is the time to plug in k=1+16a
that simplifies to
$2^m+1 = (8a+1)*a$
sterile pumiceBOT
Empty Axes:
sacred junco
lol I suppose this implies a is odd
yikes
just seems like a never ending stairway to hell to keep wandering this path
unreal rapids
something is not right with the mod
or it is
idk
the mod tells us that $16|k^2-1$ if $n>3$ and $32|k^2-1$ if $n>4$
sterile pumiceBOT
asj 🦌:
smoky knoll
@unreal rapids you can prove that any number above 33^2 does not have this property
so then you'd only need to check 2^1 up to 2^10
proving that is relatively straightforward, but ping me if you have any questions
then it;s easy to check all values below that and then you get finitely many answers
unreal rapids
well, i am a bit confused now
smoky knoll
you can use the fact that you know the minimum distance between 2 square numbers at any given point
and you also know the minimum distance between 2 powers of 2
after 33^2, all square numbers must have a difference of at least 33 between them, so it is impossible for (any square) + 33 to itself be square
you now know that any power of 2 which is also a square does not fulfill this property, and you can use that to check the powers of 2 in between squares
@unreal rapids does that make more sense?
unreal rapids
but 2^n is not necessarily a square
unreal rapids
well, actually i've done it like this: $k^2-2^{n}=33$ which is equivalent to $(k+2^{\frac{n}{2}})(k-2^{\frac{n}{2}})=33$ from which i deduced $n\in [4,8]$
sterile pumiceBOT
asj 🦌:
smoky knoll
That works too
neon comet
<@&286206848099549185>
jovial totem
Nope, looks fine to me.
neon comet
for real?
jovial totem
and hence you conclude that since it true for n=p, and n=p+1, it is true for any number in the domain too
neon comet
yeah i will add some supportive text
jovial totem
oof, i'm a sidekick now thx pur 😄
neon comet
but the wording has to be in swedish hence why i did not include it for you guys
jovial totem
the math is sound, go ahead
hexed atlas
xD
jovial totem
I'm so jealous your name is in blue and mine is in green
I like blue so much
dang it
hexed atlas
Haha
neon comet
the scum of the server
jovial totem
lol
neon comet
who asks annoying questions
hexed atlas
Nah, all the rest of us exist to serve the white :)
jovial totem
yep ❤
hexed atlas
💜
hexed atlas
Oh wow that looks awesome
sacred junco
^
stray gale
Is this a theoretical number?
sacred junco
Hello everybody
Have some issues with Fermat theorem
3 Is prime
And 4 is Natural number
So with fermat 4^3 = 4 Modulo 3, Not ?
a^(p-1) = 1 (mod p)
4^2 = 16 = 1 (mod 3)
You're using the a^p = a (mod p) format?
Yup
Oh
And
1 Mod 3
Is equivalent to 4 Mod 3
@sacred junco Thank you ! 😛
Always glad to drop random strings into a channel
x)
sacred junco
I've done the basis step, proving that it holds true for n = 1
then began the inductive step by setting n = k
but then idk what to do for where n = k + 1
this question is very different to the proof by induction we've done before
coral burrow
<@&286206848099549185>
coral burrow
i had a thought
@sacred junco
since you know that that sum in the middle up to k is less than 2sqrt(k), all you have to prove to prove that the RHS is true for k+1 is show that 1/sqrt(k+1) is less than 2sqrt(k+1)-2sqrt(k)
sacred junco
why less than and not greater than? @coral burrow
coral burrow
i didnt really think about the LHS but you can probably do something similar lol
or are you asking why i said to show that 1/sqrt(k+1) is less than 2sqrt(k+1)-2sqrt(k)
sacred junco
yeah the latter
coral burrow
the sum up to k+1 is
$1+\frac{1}{\sqrt(2)}+\ldots+\frac{1}{\sqrt(k)}+\frac{1}{\sqrt(k+1)}$
sterile pumiceBOT
fishcat:
coral burrow
$1+\frac{1}{\sqrt(2)}+\ldots+\frac{1}{\sqrt(k)}<2\sqrt(k)$
sterile pumiceBOT
fishcat:
coral burrow
we want to show $a+\frac{1}{\sqrt(k+1)} < 2\sqrt(k+1)$ where a is some number less than $2\sqrt(k)$
sterile pumiceBOT
fishcat:
sterile pumiceBOT
fishcat:
coral burrow
and the most that a can be is 2\sqrt(k)
technically, an arbitrarily small amount under it
$\frac{1}{\sqrt(k+1)} < 2\sqrt(k+1)-2\sqrt(k)$
sterile pumiceBOT
fishcat:
sacred junco
kk thank you
vast vessel
@sacred junco not really a numbre theory question and I can prove it using telescoping if you want
coral burrow
@vast vessel he asked what category to put it in, i saw an induction question recently asked in here so I suggested this channel
hexed atlas
@vast vessel You want CRT method?
hexed atlas
Lmao
Ok
So I'll do it in the two congruence case
Say you have a system of congruences
,$ \amod{x}{a_1}{m_1}\
\amod{x}{a_2}{m_2}
With $m_1$ and $m_2$ coprime
stuck lintel
vast vessel
you and ur things
hexed atlas
Lol
sterile pumiceBOT
Puerøsola:
hexed atlas
Oh oops
sterile pumiceBOT
Puerøsola:
vast vessel
👌
hexed atlas
The CRT will give us $\amod{x}{m_1m_2}$
sterile pumiceBOT
Puerøsola:
hexed atlas
Urghh, can't type in bed lol
First you have to find the partial mods
In this case they are $$M_1 = m_2, \qquad M_2 = m_1$$
sterile pumiceBOT
Puerøsola:
vast vessel
stuck lintel
.-.
vast vessel
very enlightening
hexed atlas
Which isn't very enlightening, but in general we have $$M_i = m_1m_2 \dots m_{i-1} m_{i+1} \dots$$
sterile pumiceBOT
Puerøsola:
hexed atlas
Don't steal my words before I post them :P
vast vessel
hexed atlas
The next step is to find the inverses of $M_i$ modulo $m_i$
sterile pumiceBOT
Puerøsola:
hexed atlas
Do you know modulo inverses?
vast vessel
When multiplied by it, the result is 1 (mod m)
stuck lintel
i learned it in a different way
vast vessel
stuck lintel
but im still listening along to learn this new method :O
stuck lintel
language >.<
vast vessel
Lmfao they patched that
hexed atlas
vast vessel
Lemme see if I can find it
hexed atlas
❓
stoic basinBOT
hexed atlas
Oh right
stuck lintel
I learned it where if you have $$x \equiv a_1 \pmod{p_1}$$ $$x \equiv a_2 \pmod{p_2}$$ then you find two numbers $N_1$ and $N_2$ where $N_1 \equiv a_1 \pmod{p_1}$, $N_1 \equiv 0 \pmod{p_2}$ and $N_2 \equiv a_2 \pmod{p_2}$ , $N_2 \equiv 0 \pmod{p_1}$ and the result is $$x \equiv N_1 + N_2 \pmod{p_1 p_2}$$
sterile pumiceBOT
Plum:
stuck lintel
hopefully didnt type anything wrong 
vast vessel
well I think I see what we're gonna do here
hexed atlas
You sure the result is right? 🤔
stuck lintel
one sec let me just make sure
hexed atlas
Oh wait nvm
vast vessel
Let m^(-1) be the inverse modulo whatevs
hexed atlas
I think that works
hexed atlas
Yep that works
stuck lintel
and same thing for if there's 3, 4, etc. congruence relations, then you just do N_3, N_4, etc.
i think it's somewhat easier than finding the inverse? but idk
hexed atlas
$N_1 = a_1 M_1 y_1$ where $y_1$ is the inverse of $M_1$ mod $m_i$
sterile pumiceBOT
Puerøsola:
hexed atlas
I think
stuck lintel
too many variables ._. head hurts
stuck lintel
peacefulness ensues
👀
oh yeah i was going to ask if there was any method to do it if they werent coprime
or maybe there would be more than one least residue then? im not sure
hexed atlas
vast vessel
$$x=c_1m_2^{(-1)}m_2+b_1m_1+a_1=c_2m_1^{(-1)}m_1+b_2m_2+a_2$$
sterile pumiceBOT
Simple_Art:
vast vessel
Should we do this?
stuck lintel
🤢
hexed atlas
Well, to finish the previous method,\
Find the inverses $y_i$ of the partial moduli $M_i$ modulo $m_i$.\
Then CRT states that
[
\amod{x}{a_1M_1y_1 + a_2 M_2 y_2}{m_1m_2}
]
sterile pumiceBOT
Puerøsola:
hexed atlas
I'm not sure what a b and c are in what you wrote
hexed atlas
it's possible to do CRT with non-pairwise coprime but it's really messy
sterile pumiceBOT
Simple_Art:
hexed atlas
Yes
vast vessel
vast vessel
It's more numbre theory so 🤢
stuck lintel
numbre theory > big nombr theory
stuck lintel
what does non elementary number theory have? 😦
hexed atlas
It looks very very different
stuck lintel
fresh pelican
Can someone here explain to me how p-adic expansions work?
fresh pelican
Ok, I'll ask there then sorry 😂
hexed atlas
Haha doesn't make much difference but we might as well use the channel xD
vast vessel
hexed atlas
But it uses some analytic stuff 🤔
vast vessel
fresh pelican
I don't know, p-adic numbers comes up in number theory but also in abstract algebra I think
hexed atlas
Hmm
fresh pelican
Ok, thanks SA
hexed atlas
They are built from integers
vast vessel
hexed atlas
And they use primes
vast vessel
fresh pelican
Reeeeach
vast vessel
Reeeeeaching my banhammer?
hexed atlas
I'm fairly sure certain bits of them are defined up to congruence as well
So they seem appropriate enough ☺
vast vessel
hexed atlas
It stared back at me
vast vessel
hexed atlas
We've mutually decided that we aren't for each other
stuck lintel
lmao
hexed atlas
👀
vast vessel
I can prove e^x is irrational for rational |x|<=1
need to prove it for larger x for a challenge problem
stuck lintel
why is ur clock ahead
vast vessel
see the second line of words
stuck lintel
hexed atlas
LOL
vast vessel
I like how slime appears twice
vast vessel
hexed atlas
How do you get so many suggestions 🤔
hexed atlas
I have a voice button there
hexed atlas
hexed atlas
What UI?
vast vessel
slender sedge
Could someone explain to me the equality in the solution?
what does d exactly represent here
vast vessel
@slender sedge d = any natural numbre
slender sedge
Thank you
I really don't understand how he got the form d^k + (p - d)^k
and factorised out p
I think i figured out how d^k + (p - d)^k works
but not clue how the author factorised out p
sturdy dirge
Hint: Expand d^k + (p - d)^k.
coral burrow
oWo what's this
sacred junco
i have been spelling number wrong the whole time
faint whale
it's spelt nahmber
stuck lintel
NOMBR
swift shard
Numbre
remote sinew
番
umbral locust
Hello, is this the correct channel to ask about linear programming questions (minimizing or maximizing a function subject to equality and/ or inequality constraints)?
outer brook
umbral locust
thanks
upbeat wren
lol any zero plus any other zero is still zero 😃
(and any zero multiplying with his/her wife/husband? Still makes a zero.)
That's a family of zeroes just because either parent is zero and no one is adopted 😃
F*** off
Anyway, I need to help the poor be non-zero. And find someone who doesn't want to have kids so I can continue my life's work of helping. 😃 jk. A lot of people suck (as I have learned in SoCal) and I wouldn't want to inadvertently help ANY of them which pretty much means I should be the opposite of helpful.
Good Night.
raven kite
Lol what ?
muted girder
i agree
quiet sequoia
Can anyone help me with groups?
Every left inverse should be right inverse
But how do i proof this?
past summit
Are you allowed to assume the identity commutes?
past summit
I'm not sure but I think you could say:
g=ge=g(g^-1g) =(gg^-1)g
So g = (gg^-1)g
So gg^-1 = e = g^-1g
I remember there was a way to explicitly show that gg^-1 = g^-1g but I tried doing it and it's a lot more difficult than I first thought
I remember it involving g^-1 and (g^-1)^-1) and showing it was equal to g but that seems long @quiet sequoia
stark vapor
Proof:
eg = ge = g (by the def of identity)
(gg^-1)g = g(gg^-1) (using e = gg^-1 where g^-1 is the right inverse)
g(g^-1 g) = g(gg^-1) (by associativity)
g^-1 g = gg^-1 (by cancellation lemma)
so g^-1 is also the left inverse
Hmm.. actually that might be circular logic xD lemma look at the proof for the cancellation lemma
past summit
Yeah who knew this was so difficult to prove
past summit
I suppose you could say g^-1g = gg^-1
proof: trivial
stark vapor
What I wrote works
leaden peak
Ok, in general
With groups proofs of uniqueness
What you want to do is set up two different possibilities and then show that they have to be equal to each other
So lets have a right inverse called r and a left inverse called l on some element g with identity e
gr = lg = e
Take gr = lg
Pre multiply by l
lgr = llg
Use associativity
lg = e, so lgr = er = r
and llg = le = l
thus l = r and our right and left inverses must be the same
past summit
This is much nicer ^
leaden peak
Hopefully that makes sense, looking back now I did not set that up very clearly
leaden peak
Yeah now re reading yours I realised we ended up doing the same thing
stark vapor
your notation was more clear tbh
leaden peak
Its just how i was taught to do groups proofs
Set them up as different then prove they are the same, it typically makes it look much more clear
Same concept for proof of unique identity
stark vapor
That's more.. suppose two distinct e & e', then show they're the same for contradiction
as with most uniqueness proofs
leaden peak
Well yeah, but again its the suppose they are distinct => they are actually not distinct
stark vapor
for the left and right inverses, you don't really need to suppose they're distinct initially
but it's all semantics
leaden peak
You don't, which is why your proof works, but I just prefer the distinct approach because I feel like its clearer
hazy hawk
Solve for integers xy(x+y)=2222..22(a number consisting of 2018 twos)
hazy hawk
<@&286206848099549185>
unique lion
@hazy hawk x, y and x + y must be factors of this number
And clearly, this number has a factor of 9 (2018*2 = 4032—satisfies the divisibility test of 9)
It also has a factor of 2
hazy hawk
Okay
hazy hawk
It's kinda tough, I've been sitting on it for some time
sterile pumiceBOT
inubakari:
hazy hawk
2018*2=4036 tho
lunar quiver
x and y has to be even
xy(x+y)=2a2b(2a+2b)= 8ab(a+b)
check if 222.222 is divisable by 8
brittle patrol
lunar quiver
x and y are not both even because 222...222 is not divisable by 8