yes but I don't think that I recognize you from those servers
#elementary-number-theory
supple garden
Oh concept?
raven stag
I have the feel I've seen you on non-math related servers
but we don't have any mutual non math related servers
raven stag
I quit and enter servers all the time
lol me too
supple garden
Not me then lol
supple garden
Here if you can help me with this problem lol
supple garden
What is the higher bound for gcd(n, floor(n * rt 2))
raven stag
Hey how would you prove an upper bound for gcd(n,floor(n rt 2))
@supple garden
problem repost
supple garden
Floor of n root 2 basically
supple garden
Yes
raven stag
ok so, you can simplify a bit that with the fact that floor function of x is equal to x - f(x) where f(x) is it's fractional part
so
supple garden
That would be more tricky tho
raven stag
you get gcd(n, n - floor(n*f(sqrt(2))) )
supple garden
Ok
supple garden
We can but it's more tricky then
raven stag
more hints?
supple garden
Since you are moving away from natural numbers to irrational numbers
raven stag
tell me what you've thought about the problem
raven stag
Since you are moving away from natural numbers to irrational numbers
yes, but remember the floor function
also
you wanna proof an upper bound
supple garden
Hop on the voice chat so we don't have to spam this instead plus a lot easier to discuss
If you can ofc
raven stag
lol I don't have my head phones
supple garden
I am not super loud anyhow
Otherwise i tried to use bezouts theorem
And pells equations
raven stag
lol but my speakers are really bad
supple garden
Because of Markov constants
supple garden
Yea
raven stag
yeah and the sqrt and so
mmm
but
floor function
you can easyly prove an upper bound with my first manipulation
supple garden
Sorry not Pell's equation but rational approximation to irrational numbers
raven stag
you could make more manipulations and get a lower upper bound
raven stag
and you can get pell equations from some infinite fractions
well
you're not searching for an exact value
try to think about the definition of floor functions
and what you can do with that in order to make your problem easier
Ig
where does your problem come from?
supple garden
Concepts and problems
raven stag
https://en.m.wikipedia.org/wiki/Markov_constant
@static sapphire
lol bro@supple garden try writing out little cases of n in order to get oriented
stop trying to kill the problem with obscure methods
where are you from btw your accent !
lmao
it's so cool
raven stag
Concepts and problems
oh the nt book?
did you see markov constant there?
you're worikng with a gcd and floor functions!
lmfao
@supple garden
lol why are you asking for help ?
oh
okay
lmao
sacred junco
can anyone help me with the Pythagorean Theorem i wasnt paying attention in class
raven stag
search it on youtube
sacred junco
ok thx
raven stag
there's plenty of stuff
@supple garden @supple garden
@supple garden @supple garden
lmfao
raven stag
what's up?
supple garden
Sorry my wifi keeps going in and out
Ok yea I could not see the mentions since on phone discord
I am super sorry
raven stag
oh the nt book?
.
supple garden
Yea just say it in chat
raven stag
what?
supple garden
I am thinking of Markov constant becuz of rational approximations and inequalities
raven stag
mute ned and the other guy
talk now if you want
yeah I heard what you said
bruh the thing is
it's an olympiad problem
you're supoused to use elementary methods
lmao
supple garden
Yea its just that it could help me get intuition
raven stag
special case of bull shit theorem is all I hear, go solve it with out looking out on the internet obscure analytic methods
bruh
section 3.4!
supple garden
It's not obscure lol
supple garden
Yea
raven stag
lol bro<@!378718247912079360> try writing out little cases of n in order to get ...
also this
@supple garden
supple garden
Yea I am trying to
regal dust
I'm trying to write a program that outputs a vector of all of the primes up to a certain number, and the way I want to check if a number, say n, is prime is to check if n is divisible by any of the primes in my vector up to sqrt(n). I could just start from the beginning of the vector and stop checking once the square of the prime exceeds n, but I want to be able to tell, from n, what is the largest index in my vector I need to check
for example, if I wanted to check if 100 was prime, I would have to check up to 3 (indexing from 0), since 2,3,5,7 are the only primes less than or equal to sqrt(100)
so here's my real question: what's up with the sequence "index of the largest prime less than or equal to the square root of n"? Does it have a name? Is it on the oeis? Does anyone care about it?
raven stag
pi(n) is the number of primes up to n, so the "index of the largest prime less than or equal to square root of n" would be pi(sqrt(n)). Also I think that you could optimise your program by using a sieve, there are several sieves, but the sieve of erathostenes's algo has an O(sqrt(n)) time complexity, cuz like, finding primes through divison up to a certain number is actually really slow if you don't optimise it and n is somewhat big.@regal dust
raven stag
<@715280568761450619> ayyy we got it
congrats, no need to ping tho lmao
raven stag
not meant to be mean but like, I thought I had stated that I don't give a f lmfao
you pinged my in the first place lmao
anyways, congrats
lol
which methods did you use
supple garden
I mean you seemed fairly invested in the problem
It was a lot of bounding and some epsilon delta proofs
supple garden
Wait what did you delete
raven stag
like
raven stag
I mean you seemed fairly invested in the problem
lol cuz I asked you a ton of non related questions after you pinged me and burried down your question
raven stag
It was a lot of bounding and some epsilon delta proofs
what was your bound?
supple garden
2 root 2
raven stag
lmfaoooooooooo
supple garden
The same bound we were supposed to
supple garden
It's a little bit complicated but we squared both sides
Since it preserves gcd inequality
Lot easier to deal with
supple garden
Yea we didn't use anything obscure lol
supple garden
Wdym
supple garden
Wait no tho
supple garden
That's not true
supple garden
The second part is proving that statement that the best bound is root 8
No I literally proved it we can better gcd
raven stag
what
supple garden
Is 2 rt 2
supple garden
No try it no cap
raven stag
what is the lowest number less than or equal to root 8?
I mean the integer
lol
sorry
supple garden
Come to voice easier to discuss
supple garden
Oh ok alright
raven stag
what I wanna show you is that you can gain lots of info by trying out small n's
as I told you
supple garden
I see what you mean
raven stag
lol
supple garden
But the problem behaves very differently for infinitely large n
raven stag
no, it doesn't, what was your upper bound again?
raven stag
wtf is danka?
supple garden
Thank you in german
supple garden
No lol
raven stag
why do you care lol
supple garden
Idk just curious
raven stag
11 th, what about you?
supple garden
Same 11th
raven stag
enjoy it then lmao
supple garden
I will
raven stag
I spent a lot of time learning your language
supple garden
My language?
raven stag
where are you from lmao
supple garden
Canada
supple garden
Ok
supple garden
🤔
raven stag
I'm not an american
supple garden
I never qualified for AIME lol
raven stag
no
supple garden
Did amc once in grade 9 or smth
raven stag
I started doing math olys 4 months ago
raven stag
also there's no section 3.4 in concepts and problems
wtf
you're so north american
like
supple garden
Practice problems 3.4
supple garden
Ok
raven stag
I will only say that english ain't my native language
raven stag
lmao your statistical reasoning ain't working
supple garden
Rip
supple garden
Cya later alligator
raven stag
lmao
regal dust
pi(n) is the number of primes up to n, so the "index of the largest prime less t...
Thank you, this is a great answer! I'm familiar with the prime counting function (as in I've heard of it before, too bad I wasn't able to take number theory in my undergrad), so I definitely shouldn't have been looking for a "nice" expression for the sequence in question. I'm a bit mad at myself that I thought there would be a "nice" expression
stiff estuary
one thing they don't always mention when they teach primepi is if primepi is the ceil or the floor
also, they don't always teach this https://en.wikipedia.org/wiki/Legendre's_constant
they teach n/logn without legendre's constant. with the constant it gets way better
it is still a mystery today how legendre did this. obviously he is finding the minimum error but we don't know what algorithm he used to do this on paper in a lifetime.
this is in my opinion on the level of crazy accurate approximations that ramanujan made for the perimeter of an elipse
🧐
high forge
I don't know if this is the right channel for this, but:
Wouldn't this just be a horizontal line? I can't really imagine any other function which has no max or min
I'm not quite sure if there is a way to reach a similar thing by utilizing the fact that the function is continuous on the rationals
sleek cove
if f is constant, that constant is both the max and min
an example of a function that has neither a max nor min is f: (0,1) -> R, f(x) = x. obviously you have to get a bit more creative than this since your domain is strictly rationals on a closed interval
but this should give an idea
wait
high forge
Huh, so as long as the ends of the interval are irrational numbers for the function that should work?
I guess it seems strange to me because I thought it was that a function that's continuous has to have a maximum and minimum value
sleek cove
do you have the definition for max and min?
they are different than supremum and infimum
high forge
Ahh that was a misunderstanding I had then
So for f: (0,1) -> R, f(x) = x, it has no max or min because the max/min values for the function on that interval are technically not part of the set due to the interval being open?
sleek cove
this is the formal definitoon
when you refer to max/min in your above statement, you are really talking about supremum and infimum
which is not correct
cN you see that for any M you pick to be the maximum of f, that there exists another point c, such that M<c<1?
high forge
Yeah, that makes sense; there is an infinite number of values approaching 1 so there is no particular maximum value
sleek cove
yup
high forge
I was imagining for my original problem it would be easier to just find a function on the rationals that approaches some infinity at 1 and 3
Actually wait no
Since it's a closed interval I can't do that
sleek cove
why not
high forge
I thought approaches to infinity had to be open :o
since 1 and 3 would be asymptotes and it never really reaches those values
sleek cove
forgot the problem lol
too late
this might take more thinking that i originally thought
high forge
It's kind of tricky
Not even considering the rationals part of it which is also kind of strange to me, I'd imagine the set of all rational numbers would be discontinuous in terms of functions
sleek cove
hm i cant think of anything. i can look harder tomorrow but im sure someone else can figure it out b4
high forge
No worries, thanks for clearing up the maximum/minimum thing haha
stiff estuary
I am not understanding this "and attains neither a maximum nor a minimum value on K"
does that mean >1 union ❤️
can't disable heart emoji
@sleek cove you might get better answers if you repost it in #advanced-analysis. this question is about real analysis.
sleek cove
this is not my question...:
vital relic
I don't know if this is the right channel for this, but:
You need a function that is continuous on the rationals, but discontinuous on the reals; perhaps 1 / (x-sqrt(2))
high forge
Makes sense! I was thinking something which has a maximum/minimum at some multiple of pi
lost falcon
it is still a mystery today how legendre did this. obviously he is finding the m...
wow, this is really interesting. do you have any sources on this topic that you really like?
stiff estuary
@stiff estuary https://mathoverflow.net/questions/273315/legendres-constant
people arguing if legendre's constant is 1 or some real number. they argue if he got it by guessing or calculating it. one thing we know is that he was working with euler on this problem. the story is that euler came up with the idea, then a week later, legendre came back with the precise value 1.08366 but no explanation how he did it.
stiff estuary
@lost falcon
obsidian slate
is this number theory?
stuck lintel
yes
obsidian slate
i guess does anyone have any idea how to do it
tested up to m=10, the only one i could find was m=2, n=4
with mods i figured out that m and n have to be even
apart from that not much else
sage fern
number theory is all mods
what did you take the mod of
and whatever it was try taking the mod of the other things
obsidian slate
ok so i rewrote it as 3^m + 7 = 0 mod 4
sage fern
ok...
obsidian slate
and then 3^m mod 4 is either 1 or 3, it's 1 when m is even, so m is even
and i did something similar with 2^n - 7 = 0 mod 3
torn escarp
mod 7 forces m to be even
obsidian slate
oops
yeah, figured n and m both had to be even
sooo i guess this would be saying
(mod 6)
m=2, n=4
m=4, n=2
m=0, n=0
torn escarp
how did you figure n was even?
torn escarp
gotcha
obsidian slate
i feel like theres something else im supposed to use because
i feel like the only solution might be m=2, n=4
https://math.stackexchange.com/questions/2995163/find-all-integer-solutions-m-n-such-that-3m-7n-2
i was googling around and found this
but idrk how to apply it (or if it even works in this case)
ima take a break ill be back in a bit
torn escarp
rewriting it 9^a+7=4^b we can see 0=4^b mod 8, making b>=2, not super exciting
torn escarp
looking at 9^a+7=4^b mod 5 gets us 2 = (-1)^b + (-1)^(a+1) mod 5, so b is even and a is odd
sage fern
ooh
torn escarp
err my labelling of variables is messed up there is no c lol
that lets us write 9*81^s+7=16^t lol
getting scarier
looking mod 7 forces t to be odd... rewriting...
9*81^s +7 = 16*256^k
I feel like I'm going to end up infinitely going here, but now there are fixed coefficients on the exponential terms so maybe it actually dies... 😬 somehow...
sage fern
3^m has residues 1 and 3 mod 8, as 3^2a = 1 mod 8
so n = 3k or 3k+1
as (1, 3) - 1 = (0, 1, 2, 4), clearly only (0, 1) will work
wait am i a fool
i am
2^n can't be 1 mod 8
except for n = 0
so n = 3k+1? what am i doing
okay from the top
(-1)^m - 1 = 0 or 2 mod 4
1 = (-1)^n mod 3
so yeah n is even
and m is also even
mod 8
3^m - 1 = 0, 2, 4
3^m = 1 when m is even
so 2^n = 0 mod 8
n = 3k
but that's false
oh wait i see
for all n >= 3, 3^m - 1 = 0 mod 8
i'm a fool
so yeah m = 2a, n = 2b
9^a + 7 = 4^b
(-1)^a + 2 = (-1)^b mod 5
a is odd, b is even
m = 4c+2, n = 4d
9*81^c + 7 = 16^d
2*(4^c) = 2^d mod 7
4^c = 2^(d-1)
2^2e = 2^(d-1)
2e = d-1 mod 7
sage fern
my work is useful and original, but what's useful isn't original and what's original isn't useful
2*(4^c) = 2^d mod 7
2^(2c+1) = 2^d mod 7
d = 2c + 1 + 6n?
by FLT? i'm bad at maths, idk if i'm making things up
okay let's go back i found something weird
m = 4c+2, n = 4d
but 0, 3 is a solution??
obsidian slate
ok im not done like figuring out the whole thing above yet but
the 0 part probably isn't included in the pattern
like
it's not consistent
for instant idk mod 6
3^0 is 1 mod 6, the rest is 3 mod 6
ok im kinda lost on the last bit
obsidian slate
3^m - 1 = 0, 2, 4
ok from here
i think mod 8, 4 isn't actually possible cuz 3^m is only 1 or 3 mod 8
but anyways 3^m =1 mod 8 when m is even (which it always is)
2^n = 0 mod 8 is always true
sage fern
2^n = 0 mod 8 only if n >=3
obsidian slate
oh yeah
obsidian slate
m = 4c+2, n = 4d
ok i think u lost me a bit here
ohh nvm wait i still got it
ok that is obtained using the fact that a is odd and b is even
obsidian slate
2*(4^c) = 2^d mod 7
from 16^d to 2^d, are you just allowed to take away 14 like that? or am i being dense
oh yeah im being dense nvm
sage fern
been there
obsidian slate
d = 2c + 1 + 6n?
hrm not sure where this came from
hm
man i might just leave this unsolved for now lol
sage fern
me neither
supple furnace
You were almost there. If m=0, n is obviously 3. Now if m>0, mod 3 implies n is even. As n>2, mod 4 implies m is even as well. This means that that m=2a and n=2b, so 2^(2b)-3^(2a)=7. Factoring gives (2^b-3^a)(2^b+3^a)=7. This means that 2^b-3^a=1 and 2^b+3^a=7, giving 2^b=4 and 3^a=3. This means m=2 and n=4.
sage fern
paaaain
damnit, difference of two bloody squares
that's a really clever one, i'll have to try and remember that
supple garden
I hope this one is better
Being uploaded rn
Its not sending rip
@leaden swan
Is there anything else I could do?
Are there 2011 positive integers a_1 <a_2 ......<a _2011 such that gcd(a_i,a_j) = a_i-a_j for 1<=i<j<=2011
polar pine
this isnt even a picture you just uploaded a memory
sterile pumiceBOT
bacon prince
sacred junco
don't bother
bleak matrix
How to prove
Let p be a prime number and n an integer with 1≤n≤p-1. Show that the binomial coefficient (p,n) is divisible by p
Can anyone help me?
Even a hint?
sleek cove
r?
bleak matrix
Oh, yeah sorry
sleek cove
oh well, just write out the formula
leaden swan
Note power of p in a/b is power of p in a - power of p in b
And write that down
(by power of p in a,I mean greatest integer k such that p^k divides a)
sleek cove
just use that binom coeff is always an int
sleek cove
no, that the coefficient will be
bleak matrix
Is proving the gcd of (p,n) and p will also work?
sleek cove
sure
bleak matrix
Oh, it's easy
I found it
You just need to represent the p! and n!(p-n)! Differently to show that p is a multiple of (p,n) thanks
stiff rivet
variables?
you generally compute the gcd using the extended euclidean algorithm
(or use the prime factorization)
native ore
what is that?
stiff rivet
actually you only need the regular euclidean algorithm
its repeated application of euclidean division
native ore
my first language isn't english so i may not know that
but ok i will search the web
thx anyways
stiff rivet
ye, there should be videos on that
alternative is to compute prime factorization
and choose the minimum of the exponents on each prime
(that is slower)
the lcm is then computed by $\frac{m\cdot n}{(m, n)}$
sterile pumiceBOT
Lochverstärker
stiff rivet
or alternatively the maximum of the exponents in the prime factorizations
native ore
ok thanks 😄
bleak matrix
Will this hold for: $2^{2a-1}+2^{2a+1}+3^{2a+1}=p$, where p is prime and a=1,2,3,4,...
sterile pumiceBOT
QQWWWWWEEE
sacred junco
can somebody help guide me in the right direction for this problem?
leaden swan
Strong Induction
Assume that relation is true for all k<=n, show that implies it holds for k=n+1
sacred junco
sleek cove
where r the +
whole sigil
there should be a day dedicated to mourning how awfully prime factorizations interact with addition
supple garden
Prove the existence of a bijection from Z to Z such that | f(n)-f(n-1)| for all integers n is an element of a set D which has gcd 1
sage fern
identity
supple garden
Wdym?
sage fern
f(n) = n
sage fern
the set D = {1}
leaden swan
there should be a day dedicated to mourning how awfully prime factorizations int...
Like a day for collatz conjecture?
sterile pumiceBOT
AnalyticContinuation
sacred junco
I start by assuming that it's rational
so the sum is the quotient of two integers
but I'm not sure how to proceed
prefer hints/guidance over a straight answer
why did you delete that message @leaden swan
sacred junco
ok np
sleek cove
you could try moving one of the sqrts and then squaring
sacred junco
oh yeah i think that works
bleak matrix
Is there a website that dedicated to number theory problems?
sacred junco
you mean a website with challenging number theory problems?
verbal cedar
i have a problem and i think it is related to number theory. if not i can delete it.
suppose im given only 3 coefficients of a cubic polynomial
$$t^3-St^2+?t-P=0$$
where $S$ and $P$ are integers
if i know there are integer solutions/roots to this cubic $x,y,z$ then i have the equations
$$x+y+z=S$$
$$xyz=P$$
my question: if i find a particular integer solution to this system by inspection, $x_0,y_0,z_0$, then are there any cases where its possible they are not in fact also the roots of the polynomial? in other words, can there be multiple integer solutions to that system of equations that aren't just rearranging the order of $x,y,z$? if so, does that only happen under specific circumstances/certain combinations of P and S?
sterile pumiceBOT
nix
verbal cedar
as an example:
x+y+z=4
xyz=2
an obvious solution is 1,1,2
is it possible that's the wrong solution?
sage fern
there might be additional constraints from the ?
you need all the coefficients
i'm like 85% sure
wait
integer, hmmmmm
i don't know number theory
alright let's just consider a degenerate case and leave it at that bc i don't have much time
consider S = P = 0
then you could have roots 0, k, -k for any k, right?
verbal cedar
ah
very true
if P=0 then that does make things much more difficult
we know for sure that one of them will be zero
lets say z=0
then we get x+y=S
which definitely has infintiely many integer solutions
sage fern
in the general case this is a very complex question, i think
verbal cedar
ill attempt to investigate the case where P is not zero on my own and see if i can make any observations
torn escarp
this is a fun question
verbal cedar
i suppose if |P| is prime then that would be a very easy case. x=P and y,z=+-1 to be determined easily by S
fervent crest
There exists an l with 1< l < m such that l | m
fervent crest
Not necessarily
I feel like it doesn't really have a universal meaning
It's rather just a pause
Don't quote me on that though
dusky glacier
i see
stoic bear
. means nothing in particular, whoever is probably correct that it is just a pause
verbal cedar
as an update to my question from earlier, i found a counterexample:
2,5,9 and 3,3,10 have the same sum and product
and if theres one counterexample, then i imagine there are infinitely many.
so my question then becomes: how can i find/generate sets of (lets say just 3) integers which have the same sum and product?
verbal cedar
thats true. i should have mentioned i was focusing on nonzero integers because of just that
thats my b
dusty dragon
This might be a relevant read
Extending to integers: https://math.stackexchange.com/questions/929564/solve-the-equation-abc-abc-for-a-b-c-in-mathbbz
verbal cedar
hmmm well its not as much the numbers have a sum equal to the product as it is two sets of three integers which both have the same sum and the same product (ex. 3,3,10 & 2,5,9)
though that is extremely interesting
supple furnace
Sorry, your question got buried. Here's an inductive construction. Start with just $(1)$ (which satisfies the now empty condition). Given a working $(a_1,...,a_n)$, we get a $(b_1,...,b_{n+1})$ by setting $b_1=lcm(a_1,...,a_n), b_i=b_1+a_{i-1}$ for $2 \leq i \leq n+1$. Indeed, for $i>j>1$, the Euclidean algorithm and the inductive hypothesis imply that $\gcd(b_i,b_j)=\gcd(a_{i-1}-a_{j-1},b_j)=\gcd(\gcd(a_{i-1},a_{j-1}),b_j)$. However, $\gcd(a_{i-1},a_{j-1})$ divides $a_{j-1}$ and hence $b_1$, meaning it divides $b_j$. This means that $\gcd(b_i,b_j)=\gcd(a_{i-1},a_{j-1})=a_{i-1}-a_{j-1}=b_i-b_j$, as desired. Now we check the case of $i>j=1$. Here, the Euclidean algorithm gives that $\gcd(b_i,b_1)=gcd(a_{i-1},b_1)=a_{i-1}=b_i-b_1$ because $a_{i-1}$ divides $b_1$ by construction. This completes the proof.
sterile pumiceBOT
Zheng He
dusky glacier
could someone explain this proof please
does he just replace x with q for the least non negative element
ok i see
torn escarp
as an update to my question from earlier, i found a counterexample:
2,5,9 and 3,...
ah nice
verbal cedar
oh yeah totally! in that case, if we find a large solution we can likely reduce it to a lowest form. so if we can figure out how to generate small solutions then that will still give us a whole family of solutions
i suspect it would be easier to generate P and S such that there are multiple solutions to
x+y+z=S
xyz=P
over the integers than it is to find 6 integers that happen to satisfy the conditions
so is there something special about 90 that would allow two factorizations into 3 integers to have the same sum? does 16 have any special connections to 90 that would suggest it can be decomposed into two different sums of 3 integers which have the same product?
verbal cedar
i tried finding solutions of the form
(s,s,tr)
(s^2,t,r)
got a quadratic that led me to a formula for some solutions
(1+n,1+n,2n^2+2)
((1+n)^2,1+n^2,2)
where n is any integer
torn escarp
I might have gotten a slightly more general version than that, idk
$s=1 \pm (r-1)m$ and $t = m^2 (r-1)-1$
sterile pumiceBOT
merowo (◡‿◡✿)
torn escarp
here, r, m are integers that determine s,t
but they are free to be anything, I didn't actually check this yet though lol probably should do that
verbal cedar
still for (s,s,tr) (s^2,t,r) right?
torn escarp
yeah
torn escarp
one sec let me type it up
verbal cedar
torn escarp
$$s+s+tr = s^2+t+r$$
$$s^2 - 2s +t+r-tr$$
$$s = -1 \pm \sqrt{1 - t-r+tr}$$
Now we must have this is a perfect square, $1 - t-r+tr = n^2$, then solve for $t$,
$$t(r-1)= n^2 -1+r $$
$$t = \frac{n^2}{r-1} -1 $$
For this to be an integer, $n=(r-1)m$
$$t = m^2(r-1) -1 $$
sterile pumiceBOT
merowo (◡‿◡✿)
torn escarp
Oh, and then plugging back for s, $$s = -1 \pm n = -1 \pm m(r-1)$$
sterile pumiceBOT
merowo (◡‿◡✿)
torn escarp
like I said, I didn't actually check it, but I don't think I did anything to worry about
verbal cedar
hot damn thats sexy
torn escarp
I'm assuming it collapses back down to what you got, at least I was just trying to rederive what you got haha
deciding to focus on a specific form like that was a good idea
verbal cedar
i solved for r and then just said t=2 so that t-1 would always be an integer lol
setting n to have a t-1 factor is definitely much smarter
ty :3
i wonder if there are more forms that would work 🤔
torn escarp
yeah that's exactly my next question too
like do we technically contain other kinds of forms this way, or trying to think
like for instance we know multiples gets more solutions, stuff like that
in some sense before that it seemed like it'd be a hard problem to try to parametrize cause it's like finding integer points on this weird intersection of two surfaces S=x+y+z and P=xyz
but I'm more hopeful now
I just tried checking it by plugging it back in, but something doesn't seem right, it forces a kind of condition
$m=\pm \frac{1}{2}$
sterile pumiceBOT
merowo (◡‿◡✿)
sterile pumiceBOT
merowo (◡‿◡✿)
torn escarp
maybe I just made some mistake, not sure
in principle I see no reason for there to be a problem here
I guess except when r-1=0 we do have a kind of division by 0 hmm
verbal cedar
oh maybe i found a mistake
torn escarp
I put -1 instead of +1 for s
verbal cedar
**merowo (◡‿◡✿)**
shouldnt it be s=+1+-sqrt(...)?
torn escarp
yeah
verbal cedar
ye
torn escarp
but that doesn't solve the whole problem
it still forces the condition that r=1 on me
I'm getting -2r+2 which should be 0
maybe there's some issue with 1-t-r+tr>=0 for it to be a square that is somehow breaking something
this is equivalent to (t-1)(r-1)>=0 or (1-t)(1-r)>=0 so either they're both bigger than or equal to 1 or both less than or equal to1
not a big deal there, hmm
verbal cedar
$(m(r-1)+1,m(r-1)+1,r(m^2(r-1)+1))$
$((m(r-1)+1)^2,m^2(r-1)+1,r)$
sterile pumiceBOT
nix
sterile pumiceBOT
nix
verbal cedar
im not getting and inconsistencies
torn escarp
ah ok it's working I messed up again with a sign error lol
sacred junco
can someone help with algebra 2
torn escarp
cool perfect
verbal cedar
itd be great if we could show that any solution must be of that form. but that sounds like a very difficult task (if its even possible).
torn escarp
I dunno yet, but that'd be cool if we could
I'm kind of tempted to try to find other forms maybe that work too first, or at least fail at it
something interesting I'm noticing is
$x_k = m^k(r-1)+1$ is the form of all the r,s,t for k=0,1,2
sterile pumiceBOT
merowo (◡‿◡✿)
torn escarp
$x_0=r$, $x_1 = s$ and $x_2=t$
sterile pumiceBOT
merowo (◡‿◡✿)
torn escarp
I think this is more than a coincidence
maybe $x_k=m^k(r-a)+a$ is what we should try
sterile pumiceBOT
merowo (◡‿◡✿)
torn escarp
maybe changing $a$ has an effect on the factorization $sstr = s^2tr$, I guess in this general form it's now $$(x_0x_1)x_2x_2 = x_0x_1x_2^2$$ not sure where this will get us but it feels natural
sterile pumiceBOT
merowo (◡‿◡✿)
torn escarp
and the sum that goes with this is now $$x_0x_1+x_2+x_2 = x_0+x_1+x_2^2$$
sterile pumiceBOT
merowo (◡‿◡✿)
torn escarp
hoping that by writing this out something magically pops out that would make it clear why these terms have the m^k terms on them as they do
or something
like a kind of geometric series that's been manipulated
verbal cedar
wouldnt it be $(x_0x_2)\cdot x_1\cdot x_1=x_0\cdot x_2\cdot x_1^2$?
sterile pumiceBOT
nix
torn escarp
yeah you're right I'm just letting all the details fall through the cracks today lol
sterile pumiceBOT
nix
verbal cedar
$x_n=m(x_{n-1}-1)+1$
sterile pumiceBOT
nix
torn escarp
oh interesting idea
are you thinking this generalizes to arbitrary products and sums this way?
I'm gonna believe $x_{n+1} = m(x_n-a)+a$ and imagine a=1 is a special case or something lol
sterile pumiceBOT
merowo (◡‿◡✿)
iron matrix
hello
I'm not sure if this is the right channel to talk about this, but my friend and I are curious if we can multiply and store very large number by finding their common base and then sum their log together
theorically, if we can find their common base, it should be possible right?
torn escarp
I think $x\oplus y := m (x+y-a)+a$ is an associative, commutative binary operation
sterile pumiceBOT
merowo (◡‿◡✿)
torn escarp
maybe I'm misremembering
@iron matrix what do you mean by common base? you should be able to use any base
iron matrix
well let's say, we only able to store integers
iron matrix
hmm let me rephrase that
say we have a list of numbers of form
$b^{e1}$, $b^{e2}$, $b^{e3}$, etc
sterile pumiceBOT
Artemis
iron matrix
we want to find what b is regardless of what ei might be
we dont know either b nor ei
we only know what they are as regular numbers
torn escarp
and you know they are all powers of some b, you just don't know what that b is
iron matrix
yes
iron matrix
Im not gonna be able to sleep until I solve this please help lmao
torn escarp
I mean sure, that's how it works, if you have the same base yeah
$$\log_b(b^x*b^y) = \log_b(b^x) + \log_b(b^y)$$
sterile pumiceBOT
merowo (◡‿◡✿)
torn escarp
so you're adding x+y really
it's just like, the inside out version of exponent rules
iron matrix
i wonder if finding common base b from two integer is an NP problem
iron matrix
well the fact that I'm stuck
NP stands for nondeterministic polynomial time, which means the problems' solution can be verified in polynomial time, but not the solution itself
torn escarp
it's probably faster to just pick base e, and use the approximation to guess the solution
iron matrix
the problem is, computer sucks at floating points, so we can't surely check if the log is an integer as it's prone to errors
you can read about P vs NP in https://news.mit.edu/2009/explainer-pnp if you're interested
iron matrix
it does when you care about precision, because computers actually do compress floating points due to it's physical limitation
check out IEEE-754
there's also another method to store floating points in computers caled Unums if you're interested
torn escarp
well if you have the ability to store the huge number in the first place
you have the ability to store its logarithm to sufficient accuracy
trim pollen
can anyone help me with this set of exercises? if you're free ofc
would actually be super appreciated
swift shard
@trim pollen
Have any in particular you want to talk about?
raven stag
yo friends
anyone has ever read the disquisitione arithmeticae by gauss?
the last chapter seems dope
any thoughts?
can send a pdf copy if you want
halcyon cedar
How can I prove $$x^p + p -1 \geq px $$ for $p>1, x>0$.
sterile pumiceBOT
All functions are smooth
halcyon cedar
Fixed!
supple furnace
This is equivalent to Bernoulli’s inequality
halcyon cedar
I proved it by showing that the function f(x) = x^p -px +p -1 has a derivative ≥ 0 whenever p >1 and x >0 and f(x) ≥ 0 when x = 0 and p =1. Thus we have that f is monotonous and since initially it was ≥0, it remains as such. That works right?
lusty hornet
yeah, I also thought that way to do it
supple furnace
Not quite. The derivative is negative for 0<x<1 (you can think of it bottoming out at x=1), but the derivative argument works with a minor edit.
halcyon cedar
But if we assume alongside that p>1 then it doesn't come out negative, no?
supple furnace
The derivative of f(x) wrt x is px^(p-1)-p. If p>1 and 0<x<1, then x^(p-1) is also between 0 and 1 and hence the derivative is negative.
@halcyon cedar
halcyon cedar
oh right.... my brain isnt working ):
languid cradle
is this a good place to ask about co-prime numbers? Is it proven that you can generate all the co primes by starting with (2,1), (3,1) and looking at all the children of these coordinates via looking at (2m-n, m), (2m +n, m), (m +2n, n). for (m>n). The wiki page seemed unclear on this. So the children of (2,1) would be (3,2), (5,2), (4,1). And those numbers would have 3 more children: (3,2) would have (5,3), (11,5), (7,2)...ect
pearl jolt
sleek cove
pudding
languid cradle
thanks
reason i bring it up is because i was drawing a bunch of nxn integer lattices with edges drawn to each other vertex, and noticed that if the coordinates are co prime then the edges do not intersect any vertices, was trying to give a recursive formula for edge count when increasing the size of the lattice
trail inlet
can anyone confirm that $p_{n+1} \leq 2p_n$ where it's the nth prime
sterile pumiceBOT
xdres
sacred junco
I was thinking about a PNT argument, since for N big enough (N+1)log(N+1) < 2NlogN
but idk how to deal with it being just an approximation, but probably one can complete this argument?
lusty hornet
@trail inlet see Bertrand's postulate https://en.wikipedia.org/wiki/Bertrand's_postulate#Better_results
trail inlet
cheers yeah that's perfect
warm flicker
how would you solve for an integer x such that
$x^{a}\equiv b(modc)$ for integers a b c
sterile pumiceBOT
Xpert104
sage fern
so for the example you had, x^11 === 2 (mod 79)
then x^22 = 4, x^33 = 8, etc.
get the power to a number close to 79, then smash it with FLT
?
sage fern
ok so what does FLT actually say
warm flicker
For all prime numbers p and integers a not divisible by p, we have a^(p-1) = 1 (mod p)
sage fern
ok
so x^78 === 1
so how do you get to x^77
so what does that look like
x^78 == 1 (mod 79) so x^77 == x^-1 (mod 79)
but x^77 == 49 (mod 79)
so x^-1 == 49 (mod 79)
and then you can take it from there
torn escarp
another way you can try, which is probably not any better but worth a shot, is look at what you can multiply the exponent by mod p-1 to make 1, so solve 11y=1 mod 78 then you have
$$(x^{11})^y = 2^y \mod 79$$
$$x = 2^y \mod 79$$
if it turns out y is small, then you're lucky
sterile pumiceBOT
Merosity
warm flicker
bezouts lemma gets you sx^(-1) - 79t = 1
sage fern
so bezout's will give you s right
?
well no
wait
bezout's should give you ax + by = d
so consider that x * x^-1 = 49^-1 * 49 = 1
urgh
i'm making a hash of this
basically you want 49s + 79t = 1
then taking modulo 79, 49s == 1
s = 49^-1 = x
as x^-1 = 49?
ok
so 50*49 == 1 (mod 79)
which i can believe
yes?
x == 50 == 49^-1
torn escarp
because what I describe is in the exponent, it's because of fermat's little theorem
sage fern
no
it's based off whatever mod you're using
so ax == b (mod c)
x^-1 == 49 (mod 79)
x * x^-1 == 1 (mod 79)
x * x^-1 + 79c = 1
49x + 79c = 1
coolio
sacred junco
find rationals x and y such that x^2 + xsqrt(2)=12y-5+(y^2+2)sqrt(2), please help me with an idea.
i think this equation dont have sol. in Q
vestal blaze
Since 1 and sqrt(2) are linearly independent over Q your equation is equivalent to the system x^2=12y-5, x=y^2+2
raven stag
anyone has read the disquisitione arithmeticae by gauss?
anyone knows where to find the last chapter?
what do you think about such book?
sacred junco
Since 1 and sqrt(2) are linearly independent over Q your equation is equivalent ...
thanks!
but when i solve the system i don t obtain sol in Q
ashen kraken
I was reading about whether negative numbers are prime
I ran into this sentence, and I didn't really understand it.
I was wondering if someone could please explain
thanks!
plain fable
since 1 divides everything, and -1 divides 1, -1 divides everything. Thus, if a divides a number, we know that -a also divides it, since from before we saw -1 divides everything
stoic inlet
So there are no negative prime numbers except -1? Is that right?
leaden swan
So there are no negative prime numbers except -1? Is that right?
From a ring theoretic perspective, given a prime p,-p is also prime,since they generate the same ideal.
Which is well a prime ideal
sacred junco
So there are no negative prime numbers except -1? Is that right?
1 and -1 aren't primes
sleek cove
? dont be a hater
true herald
@sacred junco you're in a lot of math servers
trim pollen
Assume that n = 987654321. Apply the appropriate algorithm that was
told in the lecture to determine the greatest common divisor of 106n+ 30 and
74n + 21.
Can anyone help with this?
lusty hornet
Apply the appropriate algorithm that was told in the lecture, where was your attention during the lec
@trim pollen basically what you need to use here is this gcd(a , b) = gcd( a, b-a) = gcd( a-b , b) : which is the property of gcd
this will simplify until you can directly say what is the gcd
sacred junco
if sqrt(2x+y) and sqrt(3y+x) are simultaneous perfect squares, prove x and y are congruent to 0 mod 5
where x and y are positive integers
help me pls
lusty hornet
if you take sqrt(2x+y) and sqrt(3y+x) as perfect squares, then automatically (2x+y) and (3y+x) are perfect squares
what is 2(3y+x) - (2x+y) mod 5 ? @sacred junco
following that you can show x is a multiple of 5 too
sacred junco
no, i mean sqrt(2x+y) is a k, k positive integer, 2x+y=k^2
sacred junco
following that you can show x is a multiple of 5 too
thanks
quick roost
I've got a proof that i can't seem to find. c|gcd(a1,a2,a3,...an) only if you can write c as a lineair combination of a1,a2,a3,...,an
does anyone have any tips regarding this?
leaden swan
That's not true
It should be gcd(a1,a2...an) divides c
You can show gcd(a1,a2) can be written as a linear combination of a1,a2 using euclidean algorithm
And extend that result to gcd(a1,a2...an) by induction
So,if gcd(a1,a2...an) divides c you get c can be written as a linear combination of a1,a2...an
wise oyster
isnt the step of expanding the terms of $\sigma$ a bit sketchy since there are infinitely many summed terms in each multiplied term?
sterile pumiceBOT
Little Narwhal
wise oyster
damn how do you do capital greek letters in latex
wise oyster
You can show gcd(a1,a2) can be written as a linear combination of a1,a2 using eu...
either that or just apply bezout's lemma
lusty hornet
there is a simpler way of proving this also which does not use divergent series , harmonic sum etc.
what seems confusing to you here though? Looks good to me, no mistake, this seems more to be a full solution than a sketch
that 1 / (1 - 1/ p_i) < inf , that is a bit weird way of writing, rather you should write it like say 1 / (1 - 1/ p_i) = a_i where a_i is a finite positive number, so a_1. a_2 . ..... a m is finite, as a finite product of finite numbers is finite. Picking out combinations, nothing wrong with it, but you can still write it a bit more rigorously. And then an ending explanation a bit more elaborate. Your proof will be complete , will look like a proof
rare cobalt
Y=X+(-1)^X
I'm probably a bit dumb, but I can't isolate x
wise oyster
Aight thanks @lusty hornet i only ask because i havent done much analysis and so im not familiar with how to rigorously approach issues of convergence and divergence of limits. Ive read things about how grouping terms in infinite series isnt always okay though I dont know why so I was just checking to make sure. Also im aware of euclid's proof for infinitely many primes but this proof was also there and I just wanted to make sure they werent omitting details
hearty current
Does there exists a formula for distance modulus calculations? Such that given a function: f(x) := x (mod 16) we can determine the real distance between two integers for example: Distance(1, 15) == 2 where f(x) := x (mod 16)?
abstract flax
Why is distance(1,15) 2?
hearty current
Because 15 + 2 (mod 16) == 1 (mod 16)
So the distance between 15 and 1 would be 2.
abstract flax
Okay, you basically want the shortest distance between representatives from two equivalence classes?
sage fern
is it just min(|a-b|, |a+b-16|)?
hearty current
Yes exactly, the shortest distance.
abstract flax
is it just min(|a-b|, |a+b-16|)?
Do you mean min(|a-b|, |a-b-16|)?
sage fern
nnno
hearty current
is it just min(|a-b|, |a+b-16|)?
This would give min(14, 0)
abstract flax
Yeah
sage fern
ok, probably then
abstract flax
Let 0<=x<=y<=15. Then it's either y-x or it is x+16-y
sage fern
it helps to visualise it as a ring
clock arithmetic
instinctively i knew it would be the minimum of two things because you can get to it going either way round
hearty current
Assuming we know the natural direction of the operation I guess it'd burn down to ´a - b + 16´
lusty hornet
@wise oyster there are only 2 things there in that proof sketch , which you need to understand a bit of analysis , one is that harmonic series diverges, and the second is the comparison test that was used to show at the end that there are infinitely many primes. But there is an extremely simple way to do this as well, without using any analysis, just by contradiction and a bit of elementary number theory , here fundamental theorem of arithmetic
wise oyster
That's fine i know the comparison test and ive proven that the harmonic series diverges before
hearty current
it helps to visualise it as a ring
Using the same argument surely I could determine if an integer a is larger than b given a window size using min(|a - b + 16i|) where 16i denote the window size?
sage fern
in practice you only need i = 0 or i = 1
i don't understand what you mean by larger in this context
hearty current
Given a window size c = 4 and the integers a = 1 , b = 15 where f(x) := x (mod 16), and we let the series naturally converge in the positive direction, then a > b == true.
Namely, I am implementing a reliable protocol in udp, so here I would assume we could apply the same logic, calculating the distance and double checking that it is within our window size.
Do you understand?
hearty current
Alright so, a = 1 would be larger than b = 15 if f(x) := x (mod 16) because we can reach f(1) starting at f(15 + x) where x <= our window size.
Whereas b > a if a = 1 and b = 3
sage fern
yes i see
it breaks what's left of the natural ordering on the integers, but whatever you're doing works
hearty current
Thus; given z := min(|a - b + 16i|) if z > c (our windowsize) then b > a otherwise a > b, correct?
sage fern
i mean if you're now redefining > like that sure
it's a different relation, i think
is it even a relation? it's strange, it depends on the window size
i guess each window would be a different relation
sometimes neither number would be related over the other, sometimes both
hearty current
It's the result because the modular space is bigger than the sought for window size, and for good (yet technical) reasons.
So my modular space is mod 16 in this example, and my window size is 4. So I want to reduce the space to 4 from 16, yet keep the upper space available.
If that makes sense?
lusty hornet
the point is what is being proved here
although it is obvious, but this is a proof, so you will write it in a convincing and formal manner , and this blackboard proof is fine
sacred junco
although it is obvious, but this is a proof, so you will write it in a convincin...
wdym
i don't see a difference btw. the 2
sleek cove
how does writing b as ak prove a|c
sacred junco
c = akl
a divides rs -> so it divides ls @sleek cove
sleek cove
so do you not get why they make kl= k'
sleek cove
the definition of m divides n is if
n = mx, for x an integer
sacred junco
ik
sleek cove
where does that come from
sacred junco
integers create integers
sacred junco
c = bl
b, l are either both or neither is
check both and you see that all are
oh nvm
wise oyster
im having trouble trying to prove that if gcd(a,b,c) = 1 then gcd((a-1)(b-1), c) = 1. Any hints? Is this even true? I have good reasons to believe that it is
twin summit
$gcd(7,5,2)$
sterile pumiceBOT
usernamephobic
wise oyster
hm fair
Then I dont understand how, once having proved the lemma at the bottom, the proof can be completed. Im not sure how gcd(a1,a2,a3) = 1 is a sufficient condition together with the veracity of the lemma to show that g(g(a1,a2) + 1, a3) exists as well... here g(a,b) refers to the frobenius number, the largest N that cannot be expressed as a non negative integer linear combination of a and b
the proof of the lemma is clear and I understand the inductive argument, but nowhere does it show that g(g(a1,a2) + 1, a3) exists and I struggle to show it myself
because if you take the case 7,5,2, then g(g(7,5), 2) is g(24,2) which doesnt exist since no odd number can be expressed as a linear combination of 24 and 2. Yet 7,5, and 2 are coprime??
lusty hornet
ok, I see
wise oyster
and i know that the image does not say this but considering we are proving the lemma for relatively prime pairs i thought it mightve been the way to go
but it obviously isnt
thing is i cant figure out the correct approach
lusty hornet
could you give me the link of the page
wise oyster
sure
gimme a sec
havent given it much more thought since i posted the question but any help would be greatly appreciated
lusty hornet
firstly are you sure that g(5,7) =24 ?
how about 23
@wise oyster
also, I repeat it is assumed that g(g(a1,a2) + 1, a3) exists
wise oyster
yes g(5,7) is 23, i meant to write above that g(g(5,7) + 1,2) was g(24,2). As for the assumption part, if what you are saying is true then I dont understand how the proof works... The "inductive argument" escapes me
lusty hornet
the proof is written a bit loosely there, and it is shown only for n=3, I read it 2 times to understand it and not fully proved
lusty hornet
and it is not a good proof frankly speaking for proving that theorem
not presented well
wise oyster
yeah...
do you know of a better proof, or of a way to take the same approach but present it better?
lusty hornet
I don't know of a proof which is at the same level as this, others you need to study some group theory
there are other ways but you need grasp over some concepts to prove it
no wonder they didn't do it on brilliant and just showed a simple case of n=3
wise oyster
darn
thought it would be a nice extension after seeing linear diophantine equations in 2 variables to see what happens for more variables but oh well
at least now I know of the existence of the chicken mcnugget theorem
abstract flax
Hmm, nonnegative integer linear combination? So if you show its true for any two numbers in a1,..., an, why can't you just make the other coefficients always zero? @wise oyster
wise oyster
because that wont show anything about a maximum non attainable value?
we want to prove that there is a maximal non attainable value
oh wait
abstract flax
If you say g(a1, a2) exists and is N. Then for M > N, M = a1x + a2y for some x and y, so M = a1x + a2y + a3(0) +...+an(0)
wise oyster
i see what you're saying
abstract flax
I don't follow the proof either though
wise oyster
wait but no that isnt enough
because we know g(a1,a2) exists if a1 and a2 are coprime
but a1 and a2 are not necessarily coprime if all of a1,a2,a3,a4,...,an are coprime
but we want to show that if gcd(a1,a2,...,an) = 1 then g(a1,a2,...,an) exists
here we would only be showing that if gcd(a1,a2) = 1 then g(a1,a2,...,an) exists
so it's a bit of a weaker statement
but a fair point