but i can't grasp how to show it conversely, that any integer a = 3j + 2 cannot also be 6k + 5
#elementary-number-theory
warm glacier
sacred junco
Don’t you just need 1 counterexample
warm glacier
is there any way of going about finding the counterexample without trial and error?
sacred junco
Converse isn’t false in general
Uh
Kind of?
You can make good guesses
It kind of pops up immediately if you use trial and error anyway
Almost immediately
warm glacier
hmm.. so the logic would be something like, 14 = 3 * (4) + 2 and you can't express that in terms of 14 = 6k + 5?
and that's it?
sacred junco
j=2 or j=-1 is simpler
warm glacier
yeah i s'pose so
sacred junco
But yea that is sufficient
8 is congruent 2 mod 6, but all integers of form 6k+5 are congruent 5 mod 6
warm glacier
maybe there's something like finding uniqueness here
sacred junco
If you are familiar with that language
warm glacier
not yet sadly, modular theory comes later
sacred junco
Modular arithmetic*
fervent crest
Like 0*3+2 cannot be expressed in the form of 6k+5
sacred junco
Oh that’s even simpler
warm glacier
yeah /facepalm
thanks, i thought i was supposed to show this algebraically somehow
makes sense logically that converse only needs 1 statement to be false
sacred junco
If you wanted to make a “method” for finding counterexamples, you’d probably be characterizing the counterexamples in some way
Which is more than the problem is asking for
Characterizing as in, finding them all, in a sense
Or describing them, whatever
warm glacier
fair, i have a habit of overcomplicating ideas that are new in number theory so far
but that makes sense
sweet girder
so 6k+5=2j+2 is not true for all combinations of k,j , only some of them, right?
warm glacier
kind of, any integer 6k + 5 is always of the form 3j + 2, but 3j + 2 is not always 6k + 5, that's what it seemed to prove
sweet girder
Im just wondering if we solve the diophantine equation what is the result really saying for the form of the number
I struggle with these convertions too
sacred junco
What Diophantine equation?
sweet girder
6k+5=3j+2 <=> ...<=>j-2k=1, this has solutions j=3+2n , k=1+n , for n integer and if you replace j and k to the first forms you get numbers of form 6n+11 which is 6(n+1)+5 , same form as 6k+5
it could be nonsense
sacred junco
not sure what you are saying lol
sweet girder
me neither, haha , Im wondering what the solution represents
if these 2 forms of numbers are equal
sacred junco
I mean 6k+5=3j+2 is a linear diophantine equation
sweet girder
yes
sacred junco
but what are you asking about it, exactly?
sweet girder
not graphically
warm glacier
that it only holds for certain choices of j, k i'm guessing
and that would be equivalent to the original hypothesis?
sweet girder
I dont know I expected that somehow, the solutions would give us something that we could use to show that we can write 6k+5 as 3j+2 but not vice versa
sacred junco
I mean sure but that's overly complicated
warm glacier
ahh i see
sacred junco
actually I think it will be kind of cute, although unnecessary
the solution pairs (j,k) are given by (-2t-1, t) for arbitrary integer t
so set k to be an arbitrary integer, and there will be a j
but set j to be an arbitrary integer and k might not be
hehe
sweet girder
I think that, ANY 6k+5 can be written as 3j+2 , SOME 3j+2 can be written as 6k+5 (not all, that's why we can use counter example) and the equation gives us the SOME 😛
yes i noticed that too
sacred junco
there is probably an easier way to do this too
but again, this is more along the lines of a characterization of counterexamples, which is not needed
sweet girder
yes, we are not talking about the exercise
sacred junco
actually I don't even think this makes it any easier to exhibit a counterexample...
it's just solving a linear diophantine equation for fun lol
literally doesn't help
warm glacier
i guess it's interesting in the case of how, as in you can show some more meaningful reason as to why it is the case, instead of just saying "ok, i see a value where the division algo breaks the opposite direction"
in other words
i've found earlier that a^2 = 3k, so i'm saying 3(a^2 - k) = 1
but now i'm stuck about how to show it is never a perfect square
sacred junco
modular arithmetic is the easiest way to do this (takes about 1 line)
wait maybe it is harder than I thought
if it was +1 this would be a lot easier
warm glacier
a^2 = 3k + 1 is also true
if that's what you mean
so it could also be 3(a^2 - k) = 2
sacred junco
what do you mean a^2 = 3k + 1 is also true
warm glacier
erm, showing the square of any integer is either the form 3k or 3k + 1
sacred junco
oh oops, it is as easy I thought
but I did not do math correctly
the square of any integer is either the form 3k or 3k + 1 is the key fact you want
warm glacier
i think i'm just missing some basic thing with the div. algo here
warm glacier
that's correct
sacred junco
regardless of choices of a and b, what is the remainder when you divide each side by 3?
well, "regardless of choices" is not the best phrasing
what are the possibilities
warm glacier
so i ended up with 3a^2 - 1 = n^2 = 3k => 3(a^2 - k) = 1
so 1 = 3(0) + 1 is impossible?
warm glacier
which part?
sacred junco
well...
n^2 is doing nothing right now, so are you just examining the lhs?
(this is fine if so)
sacred junco
but are you working with that right now?
warm glacier
and then i substitute n^2 for what i found earlier which is 3k
sacred junco
what are you trying to do rn
warm glacier
i'm trying now to use 3(a^2 - k) = 1 to show somehow that 3a^2 - 1 is never a perf. square
sweet girder
the square of any integer can be written as 3k or 3k+1 (this can be proved easily)
sacred junco
that only gets you so far bne
it doesn't cover everything
3a^2 - 1 = 3k can't even happen
if anything, you should be showing that it can't happen
warm glacier
well exactly
sweet girder
well thats what we wanna show lol
sacred junco
if you can't cite division algorithm or whatever
warm glacier
no, i'm doing precisely that
if 3a^2 - 1 = 3k was possible i should end up with a reasonable form
but i'm just not sure if it's correct to say 1 = 3 * (0) + 1
sacred junco
can you lay out your plan in one message?
warm glacier
because that seems impossible according to the div algo
my plan is to show that 3a^2 - 1 is never a perfect square by equating it to a perf. square and seeing if i get a contradiction somehow
and i substituted the n^2 with 3k, but i could also use 3k + 1
warm glacier
by the div algo 1 = 3 * (0) + 1 is impossible, so that should be enough
but i'm just not exactly sure if i'm misusing it or something
sacred junco
3(a^2 - k) = 1 clearly has no solutions
the lhs is always an integer when divided by 3, the rhs is not
or the lhs leaves 0 remainder upon division by 3, rhs leaves 1
however you want to slice it
warm glacier
yeah, that's what i was thinking
i just wanted to express it in terms of something thematic, which is the div algo
sweet girder
same with 3(a^2-k)=2
sweet girder
a^2-k should be integer since a and k are integers, and there are no integers x such that 3x=2 nor 3x=1
sacred junco
said in the language of modular arithmetic, to excite you to learn how easy it makes things, the entire proof is:
3a^2 - 1 ≡ 2 mod 3, but for any n, n^2 ≡ 0 or 1 mod 3
warm glacier
exactly
warm glacier
i'll believe you when i understand it lol
sweet girder
2020^2019mod11
sweet girder
it s supposed to be done with a pen 😛
sacred junco
aight I may have a solution shortly then
static sapphire
You can look at the factors of 2020 and work out their order mod 11
By Fermat Euler you know a^10=1 mod 11
sweet girder
i tried factorize 2019 but it doesnt going anywhere
static sapphire
You don’t need to factorise 2019
You know anything to the power of 10 is 1 mod 11
sweet girder
yes im checking 2020^10=1mod11 now
sweet girder
checking this approach haha
static sapphire
Yeah so work out 2020^9
Split it into 101^9•4^9•5^9mod 11
Which is still a little excessive
So it’s easier to work out the inverses
Reduce 101 to 2 mod 11
So we’re left with 2^27•5^9
So 2^7•5^9
Inverse of 2 is 6, inverse of 5 is 9
So it’s 6^3•9 mod 11
I think it’s 8
sweet girder
yes it is 8
i still didnt make it but i know it is 8
why did you choose 9 ?
i mean 2020^9
static sapphire
Because mod 10 it doesn’t matter
So 2020^2019=2020^2010 • 2020^9
But 2020^2010=(2020^201)^10=1 mod 11
static sapphire
Yeah
sleek cove
you're welcome
warm glacier
i'm stuck on this. i say d = gcd(a, b) and then b = a + n, so i have d = ax + (a + n)y
but i don't get how to show that d | n
fervent crest
So if d = gcd(a,a+n), then d | a and d | (a+n)
Then use the fact that d will divide the sum and difference (meaning if d | a and d | b then d | (a+b) and d | (a-b) )
warm glacier
you derive that from knowing d | (ax + by)? e.g: if x = 1 and y = 1 then d | (a + b) and if x = 1 and y = -1 then d | (a - b)?
trim gust
think about what being a divisor actually means
fervent crest
Yes
trim gust
that is not the most enlightening way
warm glacier
please enlighten me
fervent crest
lmao that is how to prove it
and since he knows that d | (ax + by) I think he knows the proof already
Well try to use this fact for the problem
fervent crest
gcd(a,a+n)=gcd(a,n)
Well that isn't quite obvious to someone who's trying to show this
warm glacier
i am having trouble translating/understanding the problem properly in terms of known theorems
since this is very new material to me
divisibility isn't altogether intuitive for me yet
trim gust
just as a conceptual background, you are aware of euclidean algorithm?
warm glacier
somewhat yes, you use the div. algo in an iterative manner to end up with the gcd, no?
but for these problems we haven't touched on that yet
trim gust
well think about if something divides a, and also a+n, then that facor must divide n
warm glacier
i suppose that makes sense, yeah
stuck lintel
You could always argue a=dz, a+n=dz', so n = (a+n) - a = d(z'-z) -> n is a multiple of d
trim gust
the easiest way to understand it is through mudulus
but modulo is essentially divisibily relationships anyway
warm glacier
i'd rather not confuse myself more at this point lol
trim gust
like assume n is not a multiple of d, then a+n=0=n(mod d), contradiction
warm glacier
but ok, going back to earlier. so using that if d | a and d | b then d | (a + b) and d | (a - b), using d | (a - b) => d | -n => d | n
so now i've shown at least that gcd(a, a + n) | n, but then i have to show gcd(a, a + 1) = 1.. but isn't that as simple as saying d | 1?
i mean, if d | 1 <=> |d| = 1, right?
warm glacier
oh yeah, that's right
wait so, which part is inaccurate here then? |d| is unnecessary at least
fervent crest
?
trim gust
lol if -1 is a divisor so is 1
and there is no point in saying "if" as it is every integer
also showing consecutive integers are coprime is trivial
fervent crest
Dude can you not
warm glacier
whoever, i assumed you were pointing out an inaccuracy by stating that gcd is always positive
trim gust
Dude can you not
?
fervent crest
Don’t just say the problem is trivial
Yes if you’re familiar with nt it is obvious
But is it obvious to you if you’re just learning it?
trim gust
it is obvious that every prime is greater than 1
warm glacier
oh ok, so Whoever, what am i missing now exactly? i've shown that gcd(a, a + n) | n and since d | n, then d | 1 which means d = +/- 1 therefore gcd(a, a + 1) = 1, right?
fervent crest
Remember we defined d to be gcd(a,a+n), so if n=1 then d=+/- 1 and since d is positive we have d=1
warm glacier
yeah
fervent crest
Mention gcd is positive
trim gust
as i already said, if -1 is a divisor so is 1
warm glacier
ahh, i thought that was implied in the end by my saying gcd(a, a + 1) = 1 (<=> d = 1)
trim gust
and 1>-1
warm glacier
but there was another way to prove this by using factors instead? i guess instead of talking of divisibility, i could say that there exists integers x, y so that dx = a and dy = b = a + n, then dx = dy - n so that d(x - y) = -n. so now again d | n
trim gust
that is exactly what we said earlier
warm glacier
it makes more sense now after using the existing divisibility theorems more "directly" to begin with
it's not obvious for me to flip these things around and finding the right substitutions/patterns
Whoever, thanks for the help, again your teaching intuition is invaluable
fervent crest
warm glacier
no way, that's just a gateway-drug to hard drugs
indigo atlas
i'm having trouble with a specific problem, how do you find two numbers a and b given both their gcd and lcm? I know you can multiply these latter ones out to obtain the product ab but beyond that any algebraic manipulation i do seems to lead to nowhere
trim gust
you cannot do this
fervent crest
Yeah you can't
So for example if gcd(a,b)=6 and lcm(a,b)=36 then a=12,b=18 and a=6,b=36 both work
indigo atlas
but how would you actually find the results instead of just guessing them?
fervent crest
Here's my thought process
trim gust
the point is that u cant discern them given only this information
fervent crest
So if $\gcd(a,b)=p_1^{g_1}\cdots p_n^{g_n}$ and $\operatorname{lcm}(a,b)=p_1^{h_1}\cdots p_n^{h_n}$, $a=p_1^{e_1}\cdots p_n^{e_n}$ and $b=p_1^{f_1}\cdots p_n^{f_n}$, then we know that for each $i$, $g_i=\min(e_i,f_i)$ and $h_i=\max(e_i,f_i)$. This means that for each $i$ there are two possibilities: $e_i=g_i$ and $f_i=h_i$, which corresponds to the case where $e_i\leq f_i$; or $e_i=h_i$ and $f_i=g_i$, which corresponds to the case where $f_i\leq e_i$. So this means that each possibility lead to a different solution for $a,b$, if we are given $\gcd(a,b)$ and $\operatorname{lcm}(a,b)$. Therefore if $n>1$ and $g_i\neq h_i$ then the $a,b$ do not have a unique solution
sterile pumiceBOT
Whoever:
fervent crest
So using this we can explicitly construct an example: n=2, p_1=2, p_2=3, g_1=1, g_2=1, h_1=2, h_2=2
@indigo atlas
Does this make sense?
indigo atlas
yes it does make sense, tho in the textbook it doesn't actually reference the gcd's and lcm's prime factorizations based on the prime factorization of the numbers themselves (the textbook in question is an introduction to the theory of numbers by ivan niven) or atleast from what i've read
yeah i just checked, the subchapter preceding the exercises doesn't even remotely reference prime factorisations
fervent crest
hmm alright
shadow fjord
@sacred junco chode ma
sacred junco
solve this equation , over the positive integers
silent quail
Is there an integer, x, such that exp(exp(x)) is an integer?
stoic bear
I don't believe so
e^x for all x in Z - {0} is irrational
e^0 is the only case where it is an integer, so we want to find e^x = 0, which is impossible
Wait why thonk @fervent crest
stoic bear
e^y is only an integer when y = 0, so y needs to be equal to 0
Let y = e^x, so so e^y = e^(e^x)
e^x is never 0 for any value of x
silent quail
@stoic bear Huh? I do not understand.
fervent crest
What e^{ln(2)} is an integer
sacred junco
is ln(2) an integer
fervent crest
No
But for this part:
e^y is only an integer when y = 0, so y needs to be equal to 0
If you can show that ln(n) is not some integer power of e then you’re done
sacred junco
this problem is too hard for me to think about anyway so I'm out
stoic bear
ah i c now
silent quail
@fervent crest I think your statement is a consequence of Schanuel's conjecture. But it is a conjecture.
fervent crest
Oof
stoic bear
yeah my mistake was just assuming e^x needed to be an integer
fervent crest
I just searched up some stuff and it said that e, exp(e), exp(exp(e)), exp(exp(exp(e))), ... are all algebraically independent
silent quail
@fervent crest can you give me a reference?
silent quail
Right, assuming Schanuel's conjecture. But it is a conjecture.
fervent crest
Damnit
sacred junco
I knew this would be too hard for me
silent quail
Anyway, I guess your reference tells me that it is too hard for me.
fervent crest
Lmao
fervent crest
But on wolframmathworld it says that Schanuel's Conjecture implies that “there is no unexpected exponential-algebraic relations on the integers Z”
What does that even mean
Does this imply that e^{e^n} is never an integer?
silent quail
@fervent crest Yes. The conjecture implies that.
fervent crest
Yeah found an answer
And integer n such that e^{e^n} is an integer, was called a "humdrum" number a couple decades ago. Someone posed the problem at West Coast Number Theory and so this probably ended up in Guy's "Unsolved problems in Number Theory"
Rip
Alright
fervent crest
lmao you’re welcome
fervent crest
silent quail
@nuiton I never studied number theory, but I don't think there is a solution. Look at it mod 5. RHS is 2 or 3 mod 5. y**4 is 1 mod 5. Does that work?
fiery root
Hi guys, I have a trouble grasping the solution to this problem. Please take a look
I followed the same procedure but I picked (5) because I could only identify F(p) as divisible by 36. Can someone clarify how they got 10 as a factor too?
I mean, it fits when I plug in values but I didn't see it happening mathematically via those factors
sleek cove
you could look at it mod 10
rich spindle
it’s much easier if u multiply by x/x cause then u have a product of 5 consecutive integers
sacred junco
Can someone explain the first line in https://math.stackexchange.com/a/1059188 to me?
I do not understand how he got from the sum to the product
cedar badger
Curious: By Bezout's lemma, we know that if we have some a, b such that there exist integer x, y that makes ax + by = 1, then a and b are coprime
Can we say that either a and y are coprime?
Like given a general ab + cd = 1, can we say that a and c are coprime, but so could a and d?
fervent crest
yes
fiery root
@rich spindle Excellent technique! I love this method :)
hearty wadi
https://math.stackexchange.com/a/2214043 Isn't it, that if alpha_i < beta_i <= gamma_i, then we get 2*alpha_i on the right side, and just alpha_i on the left, so gcd(a, b)*gcd(a, c) wouldn't divide gcd(a, bc)?
trim gust
i didnt reallly read the response, but it is simple if u think about it. as they are coprime u arent going to be overcounting so it is literally just the shared factors of (a and b)*(a and c) which is just the gcd of them
hearty wadi
unfortunately it is not that simple for me 🙂
and I just think that 2 * alpha_i is greater than 1 * alpha_i for all i, so i'm stuck
trim gust
you are overthinking this, just consider what it really means to be coprime
hearty wadi
I think of it like this: $$gcd(a,b)*gcd(a,c) = \prod_{i=1}^np_i^{min(\alpha_i,\beta_i)+min(\alpha_i,\gamma_i)}$$
$$gcd(a,bc) = \prod_{i=1}^np_i^{min(\alpha_i,\beta_i+\gamma_i)}$$
$(gcd(a,b)*gcd(a,c))|gcd(a,bc)$ iff $min(\alpha_i,\beta_i)+min(\alpha_i,\gamma_i) \le min(\alpha_i,\beta_i+\gamma_i)$.
If $\alpha_i \lt \beta_i \le \gamma_i$, then $min(\alpha_i,\beta_i)+min(\alpha_i,\gamma_i) = 2\alpha_i$ and $min(\alpha_i,\beta_i+\gamma_i) = \alpha_i, $, so $min(\alpha_i,\beta_i)+min(\alpha_i,\gamma_i) \ge min(\alpha_i,\beta_i+\gamma_i)$.
sterile pumiceBOT
Andrij Rusnak:
sacred junco
\min and \max
trim gust
is what u said logical? you can use the coprime condition so that for every i at least one of B_i or Y_i=0; so for the subset of p_i where p_i divides b, you just get min(ai,bi)=min(ai,bi), and u can do the same thing for the subset which divides c.
hearty wadi
isn't it that $gcd(a,b)gcd(a,c) = \prod_{i=1}^np_i^{min(\alpha_i,\beta_i)+min(\alpha_i,\gammai)}$?
sterile pumiceBOT
Andrij Rusnak:
Compile Error! Click the 
reaction for details. (You may edit your message)
trim gust
yea the top line is right, but is also the same as p^(min(ai,bi)+0)
for when p_i divides b, and other way around when it divides c
hearty wadi
for b*c we get either beta_i or gamma_i, but if alpha_i is smaller than both, then alpha_i is minimum of all three, so for gcd(a,b)*gcd(a,c) we should get alpha_i + alpha_i
in this case then i don't understand how gcd(a,b)*gcd(a,c) can divide gcd(a, bc)
trim gust
it doesnt
it is >=gcd(bc), so divides it in the special case which is what we are doing now
are you doing this for the general case, or the question where b and c are coprime
hearty wadi
where b and c are coprime, like on the link above
trim gust
bruh i have said this quite a lot times now, but as they are coprime either b_i or y_i is 0 for every i, and a_i cant be less than 0
hearty wadi
but I don't see how coprimality of b and c affects it 🙂
since if min(alpha_i, beta_i) = alpha_i and min(alpha_i, beta_i + gamma) = alpha_i, then factors for gcd(a,b)*gcd(a,c) are two times as for the gcd(a, bc)
trim gust
hearty wadi
basically you just say that in this case all those gcd's just = 1?
I don't get it
since b and c are coprime, it's just beta_i + gamma_i = (beta_i or gamma_i)
Can you write a proof of above theorem by factorization? I'll just study through your proof and will understand it eventually 🙂
solemn agate
fervent crest
"A Friendly Introduction to Number Theory" by Silverman is a beginner friendly introduction: you don't need to know anything and it covers all the basic number theory stuff.
"An Introduction to the Theory of Numbers" by Hardy, Wright contained more material and is very concise, but it's a bit more advanced and some familiarity with basic calculus/analysis is required for some chapters. But this book doesn't have exercises.
"A Classical Introduction to Modern Number Theory" by Ireland, Rosen. Very good book, but also to read it you need calculus and some basic abstract algebra
@solemn agate
hearty wadi
can someone explain how it follows readily from prime factorizarion?
fervent crest
@hearty wadi
Let $$m=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_r^{\alpha_r}$$ and $$n=q_1^{\beta_1}q_2^{\beta_2}\cdots q_s^{\beta_s}$$ be the prime factorization of $m,n$ into distinct primes. Since $\gcd(m,n)$ is assumed to be $1$, all the $p$'s are distinct from all the $q$'s. Then let $$a=p_1^{\gamma_1}p_2^{\gamma_2}\cdots p_r^{\gamma_r}q_1^{\eta_1}q_2^{\eta_2}\cdots q_s^{\eta_s}k,$$ where $\gamma_1,\dots,\gamma_r,\eta_1,\dots,\eta_s$ are only required to be nonnegative and $k$ is an integer not divisible by any of the $p$'s and $q$'s. Then $$mn=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_r^{\alpha_r}q_1^{\beta_1}q_2^{\beta_2}\cdots q_s^{\beta_s},$$ and since the $p$'s and the $q$'s are all distinct, we can calculate the gcd as follows: $$\gcd(a,mn)=p_1^{\min(\alpha_1,\gamma_1)}\cdots p_r^{\min(\alpha_r,\gamma_r)}q_1^{\min(\beta_1,\eta_1)}\cdots q_s^{\min(\beta_s,\eta_s)}.$$ Then you can also easily see that $$\gcd(a,m)=p_1^{\min(\alpha_1,\gamma_1)}\cdots p_r^{\min(\alpha_r,\gamma_r)}$$ and $$\gcd(a,n)=q_1^{\min(\beta_1,\eta_1)}\cdots q_s^{\min(\beta_s,\eta_s)},$$ and the result follows
Whoever:
hearty wadi
Thank you very much. I understood my mistake, which was in loss of information in my notation, when I thoughtlessly converted factorization in big Pi notation (which could be correct, if I did it right). Very educative 🙂
hearty wadi
This is how I should have been doing it using product notation.
oak mica
what's a good book for this course, i wanna start learning as soon as possible
sacred junco
"A Friendly Introduction to Number Theory" by Silverman is a beginner friendly introduction: you don't need to know anything and it covers all the basic number theory stuff.
"An Introduction to the Theory of Numbers" by Hardy, Wright contained more material and is very concise, but it's a bit more advanced and some familiarity with basic calculus/analysis is required for some chapters. But this book doesn't have exercises.
"A Classical Introduction to Modern Number Theory" by Ireland, Rosen. Very good book, but also to read it you need calculus and some basic abstract algebra
@oak mica
Message by Whoever
warm glacier
@oak mica Elementary Number Theory, 7th Edition - David M. Burton seems good so far, we're using it for undergrad number theory. It's starting to get a bit old though, so you can't expect much in terms of formatting, pedagogy etc, but being old you can usually find a lot of solutions online when you're stuck
sacred junco
💿
warm glacier
@sacred junco ✌️my man
sacred junco
CD is the symbol of transparency
fallow cargo
I want to find a bijection $ f : S\rightarrow S $ such that for $x \in S$, $\lVert x-f(x) \rVert = 1 $ where for some $A \in \mathbb{N}$ we have $S = {(a, b) : a \in [0, A[; , b \in \mathbb{N}} \subset \mathbb{R}^2$
is there a simple way i can do this computationally? it's not for a math exercise, actually for this art im making
please tag me with your reply!!!
sterile pumiceBOT
Whoever:
sterile pumiceBOT
jn3008:
civic phoenix
anyone using this channel?
fallow cargo
bruh
civic phoenix
ill take that as a yes
fervent crest
I don't feel like there is a bijective function
fallow cargo
maybe i should say b in Z
sterile pumiceBOT
Whoever:
fervent crest
it's bijective
fallow cargo
oh right
i mean i want a random function
i want to generate a lot of these functions randomly
this one is trivial but uninteresting
fervent crest
well there are infinitely many
fallow cargo
yep
i guess i could do it computationally but starting with x = (0, 0) and then just keep adding 1 or -1 to either the first or second by taking mod A from first component checking if it is in the path and then adding it to the path
fervent crest
I guess you can kind of do a snake walk
You can't take mod A
if you take mod A then sometimes it will go from (A-1,0) to (0,0)
then the distance is not 1 anymore
fallow cargo
then i should rephrase my question again x)
i guess the snake thing works for my purposes
thanks for your help @fervent crest 🙂
fervent crest
Lmao I'm sorry
fallow cargo
no i wasn't being sarc
fallow cargo
ok it might take me a few days idk but when I finish my gif ill dm to you (i hope i remember)
fervent crest
alright
fallow cargo
in the meantime feel free to check out my stuff on twitter
^ name here is the username
civic phoenix
How many integers $a$ from 1 to 1000 are there such that $a^{100}-1$ is divisible by 1000?
sterile pumiceBOT
Dualist:
civic phoenix
i tried seperating the congruences to
a^100 mod 125
and
a^100 mod 8
but i don't know what to do next ._.
fallow cargo
ty :3
fervent crest
DUDE
So you were the person who created this
Omg I found this like months ago
and I loved it so much
fallow cargo
yeah hahahaha
glad you like it
this one got around a lot
not much credit given tho
fervent crest
Yeah you can tell since I didn't even know you
fallow cargo
doesnt help that my name isn't very memorable
i dont know why I chose to put numbers in this
i guess i didnt expect to get popular at all, started off as just learning to code
fervent crest
Bro what you're doing is super super good. I'm really interested in these type of animation too, so I learned a bit of those. But the stuff you've done, I don't even know how to start making those
Hang on I'm gonna move to another channel
fervent crest
this is worth fanboying in my opinion
stoic bear
I'm inclined to agree after looking at more stuff
shrewd marsh
Does there exist arbitrarily large gaps between consecutive quadratic residues modulo n?
storm sinew
Came across this formula for finding the number of trailing zeros in a factorial. Does it have a name tho?
storm sinew
oh ighttt ty, yeah i saw legendres formula but thought it was something similar (but different) cause of the infinities
shrewd marsh
<@&286206848099549185>
fervent crest
@shrewd marsh https://arxiv.org/pdf/math/9812046.pdf
I found a paper about that
I haven't really looked at the paper yet
shrewd marsh
Thanks
simple hearth
I did not see this called Legendre's formula until late in my life, I'm curious how many people call it that.
sleek cove
thats how it was called in my nt book
trim gust
im pretty sure its name is well known
void widget
that's what it was taught to me as
I think it goes back to https://en.wikipedia.org/wiki/Legendre_sieve
lofty marsh
What do you mean?
raven stag
so @solemn agate
[1^2 \equiv 1 \pmod{4}]
[2^2 \equiv 0 \pmod{4}]
[3^2 \equiv 1 \pmod{4}]
[4^2 \equiv 0 \pmod{4}]
$\implies a^2 \equiv 1$ or $0 \pmod{4}$
sterile pumiceBOT
jamperezmondragon:
heady aspen
Also, if you check ℤ₄ + 2 = { ... , 6, 10, 14, ... } and ℤ₄ + 3 = { ... , 7, 11, 15, ...}. None of the values in ℤ when squared yield any of these results.
Also, 4k + 2 = 2(2k + 1) which is a product of an odd and even. Squaring is a product of itself. So that crosses out ℤ₄ + 2
vernal widget
is Z4 + 2 correct notation?
wouldnt it be 2 bar in Z4?
oh
you meant 4Z
(be careful, afaik Z4 is the usual notation for Z/4Z or Z/(4))
Z_4 I mean
heady aspen
ℤ₄ + 2 is just coset notation
It’s essentially the same thing. Just stands for integers mod 4
And then add 2
I guess it also depends on the context you use it in, but overall they mean the same thing
I wrote my sets just not in reduced residue form
vernal widget
Z_4 in in general is used for equivalence classes mod4
fervent crest
I think you write 4Z+2
heady aspen
Ohhhhh shit nvm. My bad guys, haven’t done number theory in couple years. Got some terminology mixed
I just realized it ahaha
fervent crest
np
fiery root
A number when divided by 4 leaves a remainder 3, and when divided by 9 leaves a remainder 1 - how would the general representation (like, odd numbers are 2n+1) look like? I have to find the remainder when this number is divided by 36
stoic bear
Google the "Chinese Remainder Theorem"
if you have any further questions/want someone to walk you through it, just ask
I just don't have a lot of time right this moment
@fiery root
also I'm assuming you are familiar with modular arithmetic
fiery root
I am not, but I will take a look - thanks for the hint!
Oh wow that method is EXACTLY suited for these questions
sleek cove
imagine that
trim gust
bruh
fervent crest
I've always wondered why it's called the chinese remainder theorem
Just because the first problem of this kind was stated in that chinese person's book?
孙子算经
sacred junco
maybe it just sounded good
jaunty crater
heyyy
are there infinitely many pairs of consecutive primes that differ by 246
or were they less conclusive than that
fervent crest
That seems like the current progress on the twin prime conjecture without assuming anything
jaunty crater
well I'm just mind farting around wondering about the "difference is <= 246"
as in could it be there are finite of 246 and infinite of 244 or something
fervent crest
that might be the case
or there might be fintely many primes that differ by 246,244,242,...,8,6,4 and infinitely pairs
heady aspen
There’s a YouTube video that goes over the Chinese remainder theorem very well too. It’s probably arithmetically one of the most fun theorems to apply cuz it does work itself out pretty neatly.
sterile pumiceBOT
Weeaboo:
upbeat wren
hmm so let's consider the "integer-ness" of ( 6^a ).
sterile pumiceBOT
Math Fan:
upbeat wren
Still there?
fervent crest
So clearly if n=1 then the log is rational. So we can assume n≥2 and the log equals a/b where a,b>0, like you said. Then 6^a = n^b, so n must has be divisible by 2 and 3 and no other prime factors. Assume n=(2^i)(3^j), then 6^a=(2^(ib))(3^(jb)). By fundamental theorem of arithmetic a=ib and a=jb, so i=j and n=6^i. Therefore the log is rational exactly when n is a power of 6
raven stag
hey guys
I'm currently learning bout quadratic residues and stuff, but like I was wondering and exploring some other residues, like of the nth degree, are there similar laws that apply to higher degree congruences?? could someone wonder with me bout all those things?
fervent crest
There's the cubic reciprocity and quartic reciprocity. There's also higher degree generalizations, but I think you need to know algebraic number theory to understand those
I think cubic reciprocity is in Ireland Rosen's number theory book
raven stag
ohh the one you send me b4??
fervent crest
Yeah
fervent crest
Well you use analysis or you use algebra to study number theory
By algebra I meant abstract algebra
raven stag
ahh
so like algebraic nt is more like a generalization of nt ideas to abstract structures like what we talked bout the other day
isn't it??
how is analytic nt tho
fervent crest
Well for example the prime number theorem
$\lim_{n\to\infty}\frac{\pi(x)}{x/\ln(x)}=1$
sterile pumiceBOT
Whoever:
raven stag
shitttt I've heard bout that
but like that's some crazy shit tho
and you prove that with analysis??
what is more cool, analitic or algebraic nt??
after artin I could learn algebraic nt couldn't I??
fervent crest
This is more analytic number theory
And theoretically yeah after artin you can learn algebraic nt, but I really don't know much about that so
You can probably move to #advanced-number-theory at that time
raven stag
ahhh
but like I should learn it before moving tho
hahah
so like you know more bout analytic nt??
fervent crest
Not much more
fervent crest
Cool is heavily subjective
fervent crest
Well considering I haven't even seen the proof of prime number theorem idk how beautiful the proof is
But here
Here's a video series on analytic number theory
It's quite accessible
As long as you know calculus
fervent crest
Or maybe analysis
raven stag
I have a book by that guy
fervent crest
I can't quite remember
raven stag
on algebraic nt
fervent crest
Nice
raven stag
by the same ram murty
iirc
ok so I ll read artin and some analysis and then those topics
do you know bout higher combinatorics ??
what's that like ??
fervent crest
I don't really enjoy combinatorics that much when I read it so I didn't read more
But I guess you can go read the book "Principles and Techniques in Combinatorics" by Chen Chuan-Chong
That's the book I read and it seemed decent
stoic bear
What kind of combinatorics? The field is very broad
stoic bear
I tried that book whoever; didn't enjoy it particularly
fervent crest
It was accessible and the results were quite cool
But I just don't enjoy combinatorics
raven stag
But I guess you can go read the book "Principles and Techniques in Combinatorics" by Chen Chuan-Chong
@fervent crest ohh I'm reading that, along with vilelkin's (or some soviet dude) Combinatorics and I plan to read concrete mathematics afterwards
but like I'm just wondering how is it like
like higher combi
it's sounds so good
stoic bear
really annoying
raven stag
really annoying
@stoic bear you mean combi??
stoic bear
yeah, combinatorics for me is just too tedious and doesn't interest me that much
I do believe a grasp of the fundamentals is important for other fields; I see combinatorics as the study of counting which is important everywhere in math
raven stag
yeah
but like I'm going through those books for Olympiads and CS
I just dk what's higher combinatorics
but like
"higher combi" sounds like a really cool name
stoic bear
hmmm, I can't think of anyone off the top of my head that does a field of higher combinatorics in this server
fervent crest
frucht was pretty interested in combinatorics
stoic bear
Restating what I said before though; "higher combinatorics" isn't really a specific field; its a very broad term for anything that is not elementary combo
cause you can apply combinatorial techniques virtually everywhere
raven stag
ohhh
stoic bear
raven stag
but like graph theory would be higher combi??
stoic bear
I mean just look at the wikipedia listings as "subfields"
yeah, I could consider a section of graph theory as combinatorics
fervent crest
Um graph theory is not higher combinatorics, it is in fact pretty elementary that you don't really need to know much to learn about them
Then again higher combinatorics is pretty ambiguous like poco said, but I still don't think anyone would consider graph theory as "higher combinatorics."
stoic bear
idk we are just messing with semantics at this point
stoic bear
just keep on learning what you like and worry about what is "higher combinatorics" later
fervent crest
He was like the person who kept spamming combinatorics stuff in the chat
raven stag
ahaahahahah
heady aspen
Myeh, I’m not much of a combinatorics fanatic either. But, pidgeonhole principle does show up in other maths 🤷🏽♂️. And there are some combinatorics applications in probability theory.
trim gust
combi is good
trim gust
algebraic nt>analytic nt
spare garden
Anyone have a good resource for $1^2 + 2^2 + 3^2 + ... + n^2 = n(n+1)(2n+1)/6$ I already looked here https://brilliant.org/wiki/sum-of-n-n2-or-n3/ but I couldn't follow
sterile pumiceBOT
pancakehammer:
tacit wraith
@spare garden I think the mathologer has a video on it
Dang it's an hour long
I enjoyed it though 🤣
sacred junco
there's also plenty of geometrical proofs out there
leaden swan
Show that 0^k+1^k+2^k+3^k...n^k Is a polynomial of degree (k+1)
Then find the polynomial f using values of f(0),f(1)...f(k)
For example, 0+1+2+3...n will be a polynomial P of degree 2. P(0)=0, P(1)=1, P(2)=3
P(x)=$
0 \frac{(x-1)(x-2)}{(2)}+ 1 \frac{x(x-2)}{(-1)} + 3 \frac{x(x-1)}{(2)}$
sterile pumiceBOT
DrunkenDrake:
twin forum
if a=b(mod n) then does that mean a^k=b^k (mod n)?
leaden swan
Yes
twin forum
alright tq
heady aspen
It’s actually a proved proposition if I remember ahaha
trim gust
lol that is like saying is a^k=a^k modn
raven stag
it's actually not that difficult to prove
sacred junco
Let d(n) be the number of divisors of n. For example, 6 has divisors 1, 2, 3, 6 so d(6) = 4.
What proportion of natural numbers have d(n) divisible by 4?
I am thinking it is 1/2, but I can't prove it. I know d(n) is odd for perfect squares only, but the number of perfect squares / n tends to 0 as n goes to infinity. Then d(n) is either 0 or 2 mod 4 100% of the time.
raven stag
d(n) it's only odd for ||perfect even powers of integers||
they could cancel in your aproach, ||but there's actually a formula for d(n)|| iirc
ahhh
like note that ||d(p^n) = n+1 for all p primes and then show that d(ab)=d(a)d(b)||
I would also think bout when d(n) is congruent to 2 mod 4
supple furnace
In the same way that it’s almost always even, it’s almost always divisible by 4. The only exceptions (in addition to the perfect squares) are numbers of the form p^ax^2 with a=1 mod 4. By using a bit of analytic number theory, one can show that the number of such numbers up to x is O(x/log(x)). Ask if you want more details.
In fact, I can show that the number of n<x such that 2^k does not divide d(n) is O(xlog(log(x))^(k-2)/log(x)). In particular, d(n) is divisible by any fixed power of two with probability 1.
sacred junco
Analytic nt
Thanks! I think I have an argument...
$d(n) = (e_1 + 1)(e_2 + 1) + ... + (e_m + 1)$ where the e_i values are the exponents in its prime factorization. For d(n) to not be divisible by 4, we need all but one of these e_i values to be even, which is unlikely as m goes to infinity.
sterile pumiceBOT
doublemintdave:
supple furnace
This is a heuristic (intuitive reason for why it’s true), but proving it rigorously is harder
silver oak
why are there + signs?
cedar badger
Hrm so in my number theory class, the prof asked us if, for gaussian integers z, w, if d = gcd(z, w), then is it true that N(d) = (N(z), N(w))?
I can't seem to think of a counterexample
But I don't think it's necessarily true
cedar badger
Oh
regal aspen
I thought this was elementary 😦
fervent crest
This is elementary number theory though
sacred junco
@supple furnace how do you use analytic nt for that?
for the O(x/log x) stuff i mean
trim gust
algebraic nt >analytic nt
void widget
what's the sound of an analytic ntist drowning? log log log log log log log
trim gust
lol
fervent crest
lol
fervent crest
But I also want to know how tree3 did it
sleek cove
lots of things are O(x/logx) or O(logx/x) so it was a 50/50 guess ez
leaden swan
Why is analytic nt<algebraic nt?
fervent crest
also lexicographic ordering
supple furnace
An upper bound for the number of positive integers of the form pn^2 less than x is sum floor(sqrt(x/p)), which can be upper bounded by sum sqrt(x)/sqrt(p). It’s then enough to analyze sum 1/sqrt(p) over p<x. Via Abel Summation, this is pi(x)/sqrt(x)+1/2 integral t=2 to x pi(t)/t^(3/2) dt. Using PNT, we know pi(x)=x/log(x)+O(x/log^2(x)) and so we end up sqrt(x)/log(x)+1/2 integral t=2 to x 1/(sqrt(t)log(t))+O(1/sqrt(t)log^2(t)) dt. Using integration by parts on the 1/(sqrt(t)log(t)) turns this into sqrt(x)/log(x)+sqrt(x)/log(x)+O(1)+int t=2 to x 1/(sqrt(t)log^2(t)) dt. We now show that the final integral is O(sqrt(x)/log^2(x)). Integrating by parts, we see that int t=2 to x dt/sqrt(t)log^2(t)) is 2sqrt(x)/log^2(x)-C+4 int t=2 to x dt/(sqrt(t)log^3(t)). Picking some constant D, we have that 1/(sqrt(t)log^3(t))<1/D(1/sqrt(t)log^2(t)), and so int t=2 to x dt/(sqrt(t)log^3(t)) is o(int t=2 to x dt/(sqrt(t)log^2(t)). Hence we conclude that that the integral is (1+o(1))sqrt(x)/log^2(x), which is indeed O(sqrt(x)/log^2(x)). In the end, you get sqrt(x)((2sqrt(x)/log(x))+O(sqrt(x)/log^2(x))=2x/log(x)+O(x/log^2(x)) as an upper bound.
leaden swan
Ok,Algebraic nt>analytic nt
simple hearth
but isn't analytic algebraic number theory best of all?
void widget
I actually learned a tiny bit of ANT today
just a bit about the ideal class group and binary quadratic forms
simple hearth
I propose renaming Algebraic Number Theory to Ringy Number Theory so that ANT is unambiguous
void widget
haha
simple hearth
ideal class groups are awesome.
void widget
yeah? they seem very interesting but I am not sure how to do much explicit computation with them
simple hearth
"Use a computer" is a good bet
although in specific cases there are often weird shortcuts
like the connection between cyclotomic class numbers and Bernoulli numbers is nuts
@abstract sinew Is it worth it for me to try to understaht that Class Number / Bernoulli number connection? Just from a point of view of, is it cool enough I'll be happy I did?
abstract sinew
@simple hearth I think the proof of the ribet-herbrand theorem is pretty nice if that's what you're talking about
it kind of made me realize I needed to appreciate modular forms haha
simple hearth
it frankly is modular forms fault for making themselves so difficult to appreciate
dusky glacier
is this the correct channel to ask this ?
(i just want to check my solution)
$\LARGE x(x+y)+(-y)(x+y) \Rightarrow x^2+x(y)+(-y)x-y^2 \ \Rightarrow x^2+x(y+(-y))-y^2 \Rightarrow x^2-y^2$
sterile pumiceBOT
Yes:
sacred junco
what are the implication arrows for?
@dusky glacier I think you want plain equal symbols
this also probably isn't the right channel
dusky glacier
Oh ok
raven stag
What bout p-adic number theory tho?? is it better?? is it good?? interesting??
what can someone do with it?? can I eat it??
fervent crest
Oh boi
Rip Merosity
He was the goto person for p adics because he was really into it
stuck lintel
wait what happened to mero D:
sleek cove
zoph is my waifu
trim gust
sacred junco
how can this solved very simple?
leaden swan
Try am gm
sacred junco
how?
leaden swan
Try to make a sandwich for the term
sacred junco
thanks
leaden swan
I don't think that would work
sacred junco
how can solve this over the positive integers?
leaden swan
I don't know if this is useful,but you can reduce this question to $2(x-y)^2-(x+y)^2=1$
sterile pumiceBOT
DrunkenDrake:
leaden swan
So,you just have to solve $2a^2-b^2=1$
sterile pumiceBOT
DrunkenDrake:
leaden swan
Which is the negative pell's equation
sacred junco
thank you again :))!
sleek cove
np 🙂
raven stag
yeah Ik that, but like why is it called p-adic tho?
it does not seem to have any conections with p-adic bases
it's wired
manic arch
yep, it defines a norm by $\lVert x \rVert_p = p^{-\mathrm{ord}_p (x)}$ where $\mathrm{ord}_p (x)$ is the $p-$adic valuation. A norm (in general) gives you a notion of "magnitude" (like the magnitude of a vector in $\mathbb R^n$ which is the absolute value in $\mathbb R$) or "distance" (such as the euclidean distance). However under the norm $\lVert x \rVert_p$ the "big" numbers (or distances) are those without powers of $p$, or those where $p$ has a negative power. That is very roughly the point of defining the valuation; you can also read any book on p-adic numbers such as Svetlana Katok's or Fernando Gouvêa's. @raven stag
sterile pumiceBOT
bastian.uwu:
red ravine
Hey so i am trying to solve a challenge called "LostKey" here is encrypt.py: https://pastebin.com/UpNf3Pis and output.txt https://pastebin.com/bM9X3znV my initial assumption is that its ECC. but pollard rho is going to be sqrt(2^255( that's too hard for rho. but you can't get them to multiply by n on your input. As you don't know n 🙂 and the curve is none of these: singular/anomalous/super-singular as anomalous is #E(F_p)=p, super-singular is p+1 and the point doubling isn't broken
the use of P.xQ.x in the P==Q case is very odd, probably meant to be slightly confusing, which I guess iis to throw me off a bit of obfuscation in the python P.xQ.x when P=Q is just (P.x)^2
"if P.x == Q.x and P.y == -Q.y:" is normal as that's how you add P and -P so maybe the issue isn't to break the curve? but to do something to the cbc, maybe a padding oracle? but why would you need to break sha1? if you break the ec you have their n. which is their key. they use the n to generate a key to aes-cbc
(I have been using sage and pari/GP and python)
Do you have any hints? Or how I should go about this, as I have seen you are quite familiar with cryptography.
To me it does look like the standard elliptic curve discrete log problem (get n from knowing nG and G); and that assert says n < 2^85 ((assert(n < 38685626227668133590597631)), so if the complexity of solving that is O(sqrt(n)), that shouldn't be too much (sqrt(2^85) = 2^42.5)So this is how I would solve it: 1) identify the elliptic curve (I used linear algebra for this, treating the implementation as a black box), 2) use that to find the group order (pari/gp can do that), and the order of G. 3) mount a generic discrete logarithm attack for the small prime factors of G's order. 4) brute force the rest to find n. (for 4), the upper bound on n is somewhat relevant) (and, somewhere along the way, you may want to fix the bugs in the add() function)
printf "int-e{$flag}" | sha1sum -> d9e14e41e230a1557b025067d706c807ac7cab4e 😉 So Pohlig-Hellman kind of works, well, not all the way; there's a 118 bit prime factor, but it gets you close enough to win I think. pohlig helman helps except for 2915987653003935133321257255080924232005234239344602998871. meant it doesn't help with 2915987653003935133321. sqrt(2915987653003935133321) is not unreasonably big (though for this problem, attacking that factor would be overkill) It would take a while I suppose. Some days of CPU time? It's hard to estimate without actually trying. Do GPUs pay off for this kind of thing, modular arithmetic with unfriendly modulus? n is the secret scalar. So that should narrow down the search space a bit, since the order of the curve is considerably larger. So I think Pollards Kangaroo would help.So if we know that the range of x is a ≤ x≤ b, then we can solve the above problem with the time complexity of O(sqrt(b - a)). 2^85 - 1 is the bound on n
Only problem is I am not sure how to implement this all in sage or pari/GP, if you could help me with that would be appreciated, but I think my maths is correct and I have figured it out! 🙂
Find n mod p, n mod q, n mod r, if the order of the generator is pqr*s; then perhaps you can do Pollard's kangaroo to find s.
sacred junco
10^(n) - 1 congruent to m ( mod 37 ), show m is a perfect square.
This is clearly not true
obtuse monolith
It is true
sacred junco
10^2-1 is congruent to 10^2-1 mod 37 and 99 is not a perfect square
obtuse monolith
99 is a perfect square mod 37
It is 25
We are talking about perfect squares in Z/37Z
obtuse monolith
Then why would you have the mod 37?
sacred junco
Anyways it's just observing that there are only 3 cases
obtuse monolith
Yep
@sacred junco The key is that 10^3 = 1000 = 1 (mod 37)
So you just have to check the cases n=0,1,2
sacred junco
thanks !
sacred junco
solve over the positive integers, a hint pls?
leaden swan
You can just enumerate all the possibilities
sacred junco
2x^2 congruent to 1 ( mod 4 ) , no sol in integers...
leaden swan
Sorry,Thought that z was 2
sacred junco
n^2 is congruent to either 0 or 1 mod 4
maybe also mod 5
only mod 5 and mod 4?
idk sub x=2m+1 and y=2n+1
and how help this ?
idk I'm just suggesting ideas
i triyed, but idk how need to do
sly perch
Hi, I'm working on this problem, and I'm stuck.
Problem:
What I've tried so far:
tender light
Let $n$ be an integer. Show that if ${a_i}^k_{i=1}$ is a pairwise relatively prime family of integers, where each $a_i$ divides $n$, then their product $\prod^k_{i=1} a_i$ also divides $n$.
sterile pumiceBOT
Konoha:
tender light
Given that ${a_i}{i=1}^{k}$ is a family of pairwise relatively primes, which each $a_i$ divides $n$, we have $\gcd(a_i,a_j)=1$ where $i\neq j$ and $1\leq i,j\leq k$. Since $ab,|,n$ if $a,|,n$ and $b,|,n$ with $\gcd(a,b)=1$, and without loss of generality, we can have $a_1a_2,|,n$. Since $a_1k_1+a_3k_2=1$ and $a_2k_3+a_3k_4=1$ where $k_1,k_2,k_3,k_4$ are some integers, we have
\begin{align*}
(a_1k_1+a_3k_2)(a_2k_3+a_3k_4)&=1\
a_1a_2k_1k_3+a_1k_1a_3k_4+a_3k_2a_2k_3+a_3k_2a_3k_4&=1\
a_1a_2(k_1k_3)+a_3(a_1k_1k_4+a_2k_2k_3+a_3k_2k_4)&=1
\end{align*}
This implies $\gcd(a_1a_2, a_3)=1$. Combine this result with $a_1a_2b_1=n$ and $a_3b_2=n$ where $b_1,b_2$ are some integers, we have
\begin{align*}
a_1a_2k_5+a_3k_6&=1\
n(a_1a_2k_5+a_3k_6)&=n\
a_3b_2a_1a_2k_5+a_1a_2b_1a_3k_6&=n\
a_1a_2a_3(b_2k_5+b_1k_6)&=n
\end{align*}
where $k_5,k_6$ are some integers. Hence, $a_1a_2a_3$ divides $n$. Repeating this process until $a_k$, we have $\prod{i=1}^{k}a_i$ divides $n$.
sterile pumiceBOT
Konoha:
tender light
<@&286206848099549185>
sacred junco
Yeah this looks correct. But I don't think you need anything past gcd(a1 a2, A3) = 1
tender light
I don't follow your suggestion
sleek cove
you do a bunch of extra work
sacred junco
Basically it can work by induction. Show that if a1 a2 ... an are relative prime and each divide n, then a1 a2 divides n and gcd(a1 a2, ak) = 1. Then applying this result again to a1 a2, a3, a4,... ,an,then a1 a2 a3 divides n and a1 a2 a3, a4, a5, ..., an are still relatively prime, and repeat to get a1 a2 ... an divides n
But you don't have to actually "apply this result again" because this is just an induction
tender light
i see
upbeat wren
A late response, you show clearly it works for n goes from 1 to 2 and n goes from 2 to 3, but you have to show from n --> n+1 ... You need to be very detailed as to what the deal is with the case for n and why the case for n+1 follows. The current form only talks about a1a2 --> a1a2a3 ... but you need a1a2...an --> a1a2a3...a{n+1}.
supple furnace
@sacred junco I was able to establish that that for fixed z, there are (z+1)/2 solutions for z odd and 0 solutions for z even.
@sly perch This follows quickly from what is known as the LTE lemma
sacred junco
thx
sly perch
@tender light@sleek cove @sacred junco @supple furnace @upbeat wren thanks so much for all of your help. I really appreciate it!
daring ice
Are there any theorems which tell you whether a polynomial which is irreducible over Z will be reducible mod p? Or is the only method to just check values?
tender light
Let $a, b, c$ be positive integers satisfying $\gcd(a, b) = 1$ and $c \geq (a − 1)(b − 1)$. Show that there exist non-negative integers $s, t$ such that $c = as + bt$.
sterile pumiceBOT
Konoha:
tender light
so far, I stop at c=ack1+ack2=a(ck1+bk)+b(ck2-ak). Couldn't figure out how to show ck1+bk and ck2-ak are non-negative
tender light
<@&286206848099549185>
sacred junco
Probably casework from here, k allows u to try to make ck1+bk and ck1-ak simultaneously positive. If ck1 is negative, then k should be big to make ck1+bk positive, but it should also be small so that ck1-ak is positive. So u should choose k minimal so that ck1+bk is positive
tender light
@sacred junco I couldn't figure out the existence of k
sacred junco
@tender light i think you meant this
if gcd (a,b) = 1 (that means a, b are primes), then gcd(a,b) divides c
if it divides c, then it has integer solutions for the diophantine equation
and c is the condition that it makes it ocurrs, i guess
but i guess that c >= (a-1)(b-1) makes it just positive integers
tender light
thank you, I think I get it
sacred junco
@tender light by bezout's lemma gcd(a,b) = 1 implies there exists integers x and y such that ax + by = 1. Multiplying each side by c, you get a(cx)+b(cy) = c. So putting s=cx and t=cy gives the existence you want
tender light
Given $a,b,c$ are positive integers, and since $\gcd(a,b)=1$, there exist integers $k_1,k_2$ satisfy $ak_1+bk_2=1$, and one of $k_1,k_2$ is positive and the other is negative. We assume $k_1>0$ and $k_2<0$. Multiply both sides by $c$, we receive $c=cak_1+cbk_2$. So, integer $ck_1$ is a solution of the previous equality, this implies that for some integers $k$, $ck_1-kb$ satisfy this property as well. Let $k$ be the integer such that $ck_1-kb$ is as small non-negative as possible, then $ck_1-kb<b-1$.
$$c=a(ck_1-bk)+b(ck_2+ak)<a(b-1)+b(ck_2+ak)$$
sterile pumiceBOT
Konoha:
sacred junco
oh heck I didn't notice the non-negative s,t requirement
tender light
that is the tricky part of this problem
tender light
Still, my proof is incomplete
vestal blaze
Assume $ck_2+ak<0$ then $c<a(b-1)+b(ck_2+ak)\leq a(b-1)-b+1-1=(a-1)(b-1)-1$
sterile pumiceBOT
leoli1:
vestal blaze
btw, why do we have $ck_1-kb<b-1$? I can only see $ck_1-kb<b$ from the minimality of $ck_1-kb$
sterile pumiceBOT
leoli1:
vestal blaze
ok, that shouldn't be a problem: we change it to $ck_1-kb\leq b-1$, and then we get $c\leq (a-1)(b-1)-1<(a-1)(b-1)$.
sterile pumiceBOT
leoli1:
azure tulip
A * B mod C = D, How do I find A when given a B, C and D?
leaden swan
What if B doesn't have an inverse?
leaden swan
A may not exist
You divide B and D by a factor k, such that B/k is co prime to C
And repeat the above process
tender light
Let $n$ be an integer. Show that if ${a_i}^k_{i=1}$ is a pairwise relatively prime family of integers, where each $a_i$ divides $n$, then their product $\prod^k_{i=1} a_i$ also divides $n$.
Proof: Given that ${a_i}{i=1}^{k}$ is a pairwise relatively prime family of integers, elements of this family have no common prime divisors. Since each $a_i$ divides $n$, any prime $p$ that divides $a_i$ also divides $n$ and $\nu_p(a_i)\leq\nu_p(n)$ for all $i$. This tells us that
$$n=C\prod{i=1}^{k}p^{\nu_p(a_i)}=C\prod_{i=1}^{k}a_i$$
where $C$ is a product of products that are not any factors among the family. Hence, we can conclude that $\prod_{i=1}^{k}a_i$ divides $n$.
sterile pumiceBOT
Konoha:
tender light
C\prod{i=1}^{k}p^{\nu_p(ai)} is not quite right base on the notation, what is the best way to interpret this
tender light
\nu_p(a_i) is a function that give the exponential power of prime p
hybrid herald
Are there any theorems which tell you whether a polynomial which is irreducible over Z will be reducible mod p? Or is the only method to just check values?
@daring ice as a sort of interesting learning exercise, try taking a few polynomials, see what happens if you want to reduce the mod some numbers, preferably some manageable numbers, then try to find some pattern
maybe you can prove them and even find something new
sacred junco
$$\sum_{n = 1}^{\infty} \frac{x^{n^2}}{ (1 - x)^2 (1 - x^2)^2 \dots (1 - x^n)^2 }$$
So I expanded that out, and plugged some terms in OEIS, and I realized it generated the partition numbers. But does anyone have a proof or explanation of why it does?
sterile pumiceBOT
doublemintdave:
hearty wadi
does anyone have "How to prove it" 3rd edition within a hand's reach?
paper lion
Libgen?
trim gust
yea basically just look there
hearty wadi
no, I need to look up an exercise 7.3.20 from a real thing, to be sure it isn't ruined by imperfect scan
trim gust
you can take a picture of the exercise and someone can say if it doesnt make sense
hearty wadi
yeah, we can try so
hearty wadi
The question was in checking the exercise itself, the last expression differs in both parts of two versions
So I'm not sure yet, what to solve
upbeat wren
So just to make sure ... [a] is the eqivalence class containing a.
Also I'm calling the bottom problem 20Za and 20Zb.
For 20Za ... using the hint (-1)^3 =/= (-1)^8 ... a good possible choice is m = 5, a = 4, a' = 9, b = 3, b' = 8.
4^3 is not congruent to 9^8 mod 5. The former ends in the digit 4 and the latter ends in the digit 1 base 10.
And an example to disprove the statement in 20Zb is just ... a = 9, b = 8, m=5 ... 4^3 mod 5 is not (9^8) mod 5.
Not sure what 20 (top) is saying. I think there may be a typo or two?
hearty wadi
Yeah, it was the actual question. I don't know which to solve. As for not knowing what any of it is saying - it happens all the time when I approach an exercise, even if there are no typos 🙂
Oh, I get it - looks like in the first version the last expressions were just swapped in (a) and (b).
thanks for the help
sacred junco
solve over the positive integers : m^3 - 2012^n = 26
@sacred junco mod 4
m^3 - 2012^n congruent to 2 ( mod 4 ) ?
m^3 - 0 congruent to 2 ( mod 4 )
m^3 congruent to 2 ( mod 4 )
thank you!
trim gust
quite trivial
sacred junco
Hello, can someone help me understand this problem:
I understand the idea is that you test differences and if they are not equal, than two different representations refer to different integers.
But I don't understand what the guy did to solve for the second case
where for some i<m : a_i is not equal to b_i
sacred junco
no one 😦
hybrid herald
hold on
leaden compass
@sacred junco Hint:
Suppose you have something of the form $ak^n = \sum_{i=0}^{n-1} a_ik^i$, so the RHS definitely has degree less than $n$ (any of the $a_i$ can be 0)
leaden compass
(And of course a in {0, k-1})
sacred junco
is there a nice general relation between the product of n integers and the gcd and lcm of combinations of them?? for example n = 2: ab = gcd(a,b)*lcm(a,b)
fervent crest
Apparently there's this: https://math.stackexchange.com/questions/1579/n-ary-version-of-gcda-b-space-lcma-b-ab
sacred junco
oh thanks
faint hare
Not sure if I should ask here or discrete math. Let $s_i$ be the ith element of the multiset containing every integer from 1 to n, n!/n times. I'm trying to determine (constructively) all the ways of arranging the multiset such that either $s_i= s_{i \pm 1 \mod(n!)}$ or for some $c > 1$, and all integers $k$, $s_i = s_{i + ck \mod(n!)}$.
Some examples of permissible orderings in the n=4 case:
111111222222333333444444
112222221133333311444444
122213331444122213331444
111222333444111222333444
112233441122334411223344
112344231123442311234423
123412341234123412341234
sterile pumiceBOT
Obscura:
odd steeple
Hey guys, I'm struggling with cognitive dissonance around my understanding of the Collatz Conjecture. I know that I've made a mistake somewhere, and I know something is wrong - I just can't find it.
Can someone please review my trash and tell me where I screwed up? I'm sure I'm going to be facepalming for weeks after this.
https://www.reddit.com/r/math/comments/j6jbn5/reducing_search_space_in_the_collatz_conjecture/
I use a modular arithmetic approach (I think) to repeatedly divide the set of positive integers into smaller sets.
I then show a method of recording the path that a set of integers follows in order to reduce to a lesser value.
Using this documentation method, I develop a binary tree of possible paths that may be followed.
I introduce a lower bound to the slope of the possible paths at which point a lesser value is reached. (This is the part where I think the most mistakes are present).
I show a method of determining which set of integers follows a path.
I conclude the post by thinking that if a linear lower bound is present, then for every path with a known number of a certain operation ( (3n+1) / 2 ), there is a a calculable length at which the path reaches a lesser integer.
Thus for all paths containing a non-infinite number of the operation (3n+1) / 2 a point at which the path reduces to a lesser value is known.
oak vale
so your collatz proof is basically an elaborate halting problem
odd steeple
I don't think that what I've written could constitute a proof.
I'll look into halting problems, thanks for the tip.
Wiki says that
In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever.
I don't understand how that applies as given an input (path with known number of non-infinite odd operations), the program will finish running quite quickly as the total steps required for path to reach a lesser integer is determined by ceiling ( (number of odd operations in the path) / (slope of the lower bound))
Does the halting problem only pertain to non-infinite inputs?
I guess
For example, one such consequence of the halting problem's undecidability is that there cannot be a general algorithm that decides whether a given statement about natural numbers is true or false.
Clears that up. Thanks. I'll keep reading.
oak vale
I read the reddit post and saw the condition you conjecture (the log(2)/log(3) thing), and that would be the thing to prove if any
odd steeple
Thanks, I appreciate your time.
Do I need to prove an exact value for the lower bound?
Would proof of a lower bound existing and an approximation of its value suffice?
Eg: the value for the lower bound is between the lowest slope of a non-terminating point and the highest slope of a terminating point.
oak vale
if I read your post correctly the important bit would be showing that such a condition that forces the sequence to terminate is satisfied by every sequence
it doesn't matter how strict the condition is so long as it justifies the claim
misty nova
In this article (p. 3), Tait claims, without proof, that, in his formalization of PRA, $0 = 1 \implies \phi$ and $((\phi \implies 0 = 1) \implies 0 = 1) \implies \phi$. Are there proofs of these facts?
sterile pumiceBOT
katia:
odd steeple
The lower bound is the ratio of ( y/x ) where ( 2^x > 3^y ).
Integers moving through the conjecture grow in terms of 3n+1 , and reduce in terms of n/2, thus if the ratio of odd steps (3n+1) to even steps (n/2) is less than the ratio of ( y/x ) where ( 2^x > 3^y ) then the sequence has reached a lesser value.
The tricky part is in determining an exact value. We know that the lower bound is > 0.25 because 2^(4y) > 3^y.
The exact ratio is little bit lower than log(2)/log(3) because
f(x) = 2^p * x + c
Has a value for c that may equal 2^p - 1.
Thanks for the feedback bacono
tender light
How to show there are 14 distinct calendars
fervent crest
Each year can start with each 7 days of the week, and a year can be a leap year or a non-leap year. If two years have the same starting day of the week and they are both leap or non-leap year then the calendars are the same and vice versa. So there are 7*2=14 possibilities
Very interesting problem though
tender light
😮
upbeat wren
A nice related problem is ... come up with a formula to calculate the correct day of the week (from Jan 1, 2001 to Dec, 31, 2999). There are special rules about leap years in years ending in 00.
Er also related but less datey, what is the following sequence mod N? 1, 12, 123, 1234, 12345, 12356 ... ... 123456789101112131415, ...?
bleak matrix
Let $n$,$d$ positive integers and assume $1<d<n$. Show that $n$ can be written in the form $$n=c_{0}+c_{1}d+...+c_{k}d^{k}$$ with $0≤c_{i}<d$, and that these integers $c_{i}$ are uniquely determined.
I
sterile pumiceBOT
Not so spooky user:
bleak matrix
Can anyone help me in this channel?
upbeat wren
assume it has two differnt representations and show they're equal?
you might need induction too.
bleak matrix
I first proved the uniqueness of $n$ using Euclidean-Algorithm as $n=qd+c_{0}$ what i am troubling now, is how will i conclude this finding to show that $n$ can be written on that form
sterile pumiceBOT
Not so spooky user:
bleak matrix
Oh thanks, this can be done with modular
sacred junco
Here mu is mobius function and tau is the number of divisors
Assuming $n$ has $m$ prime factors, I'm getting that the first one is $\frac{1}{m} + \frac{2}{m - 1} + \frac{3}{m - 2} + \dots + m$
sterile pumiceBOT
doublemintdave:
sacred junco
But I'm not sure if that's right, because I think there's supposed to be a Mobius inversion in there somewhere
misty nova
Bump
In this article (p. 3), Tait claims, without proof, that, in his formalization of PRA, $0 = 1 \implies \phi$ and $((\phi \implies 0 = 1) \implies 0 = 1) \implies \phi$. Are there proofs of these facts?
sterile pumiceBOT
katia:
odd steeple
@bacono I'd like to build on our prior discussion with a question around limits. The below code can be used to determine the number of paths through the operations tree described in my reddit post.
#include <cmath> // for std::floor
double LOWER_BOUND = ;
int activePaths(int x, int y) {
if (y > x) { return 0; } // must be under slope of 1
if (x < 0 ) { return 0; } // cannot have negative x
if (x == 0 ) { return 1; } // at origin, 1 active path
double slope = y / x;
if ( slope < LOWER_BOUND ) { return 0; } // Outside of acceptable limits, no active paths
return activePaths(x-1, y) + activePaths(x-y, y-1);
}
int terminatingPaths(int x, int y) {
return activePaths(x - 1, y);
}
int activePathsForP(int p) {
int sum = 0;
int ylimit = std::floor(p * LOWER_BOUND);
for (int y = p; y > ylimit; --y) {
sum += activePaths(p, y);
}
sum -= terminatingPaths(p, ylimit);
}
As p in [ 2^p * x + c ] increases, and integers are further subdivided into sets, the ratio of new paths to terminating paths decreases. As p approaches infinity, would this imply that the rate of growth approaches x^2?
Using the above code, activePathsForP(p) / activePathsForP(p-1) approaches 2 as p approaches infinity. I don't know how to express this using standard mathematical syntax.
The total possible paths and therefore sets of integers is 2^p. The ratio of active paths to possible paths decreases as p increases and would approach 0 if the increase in active paths was not at the same rate as the increase in possible paths.
How does the rate of new paths approaching x^2 interact with the limit of active paths / p^2?
silk vine
Is there a general method to, when it exists, finding the lattice points of a quadratic form?
For example, I was thinking about studying the solutions of this diophantine equation over $\mathbb{Z}^{2}$.
\
\
$ax^{2}+by^{2}+cxy+dx+ey+f=0$
sterile pumiceBOT
MisterSystem:
fluid basin
Hi, i am confused about the a Special case to the Chinese Remainder Theorem ($where gcd(m_i,m_j) \neq 1$)
If we have $$ n \equiv 0(mod 2), n \equiv 2(mod 3), n \equiv 2(mod 4),
n \equiv 2(mod 5), n \equiv 2(mod 6).$ I notice that n \equiv 0(mod 2),
n \equiv 2(mod 4), n \equiv 2(mod 6) are congruence to 0 (mod 2). $$But, i am not sure if i can remove the three congruence and replace it by 0 (mod 2)?
leaden swan
You can't
You can always find a number(which is unique mod 30) such that it is congruent to 0(mod 2), 2 (mod 5) and 2(mod 3)(CRT)
It may or may not satisy those other 2 congruencies
Once you find that number,(say r) check if 30k+r satisfies your conditions for some k
fluid basin
If i am understanding what you are saying , we will you CRT to find a number which is congruence to above congruence equation. But, we will still run into a similar problem b\c n \equiv 0(mod 4), n \equiv 2(mod 6) , the gcd(30*4,6) =2
leaden swan
The number we find might satisy the above conditions( mod 4 and mod 6)
But we can be sure we can find a unique number satisfying mod2,mod 3 and mod5 conditions
(n is 2 mod 6 iff 0 mod 2 and 2 mod 3,so mod 6 condition is fine)
fluid basin
But in this particular case it violate the condition that gcd(30,4) should be 1.
fluid basin
Yes
Is there a way to reduce the congruences such that it satify the CRT. And we can use the CRT
leaden swan
Idts
fluid basin
Okay
I have a question, Why can we not say that n \equiv (mod 2) , n \ equiv (mod 4) and n\ equiv(mod 6) is congruence to (mod 2)?
leaden swan
take 10,which is
Congruent to 0 mod 2,2 mod 4 and 4 mod 6
Take 12,which is congruent to 0 mod 2 ,0 mod 4 ,and 0 mod 6
Both cases give 0 mod 2, but the congruences wrt mod 4 and mod 6 are different
weary depot
Does 2 satisfy all conditions?
leaden swan
Yes
weary depot
Well I just walked through the wikipedia article
you can simplify that system to n = 0 mod 2, n = 2 mod 3 and n = 2 mod 5
leaden swan
you can simplify that system to n = 0 mod 2, n = 2 mod 3 and n = 2 mod 5
@weary depot and n=2 mod 4
You can't remove that,I think
weary depot
yeah you're right, i might have removed the wrong ones lol
fluid basin
Can you please show me how to simplify 2 mod 6 down to 0 mod 2 and 2 mod 3?
leaden swan
Notice 3 mod6 is (1 mod 2,0 mod 3)
And
4 mod 6 is (0 mod 2,1 mod 3)
So, (3* 0+4* 2) mod 6 will be (0 mod 2,2 mod3) which is 8 mod 6 =2 mod 6
fluid basin
I understand
Thank you very much I understand how to do the problem 😀 @leaden swan @weary depot
ivory coyote
I know this is traditionally solved using bit manipulation
But I was wondering if number theory may offer a solution to this?
trim gust
addition is just an operation, so u cant get a way around that. if u avoid using +-, it is basically just getting other operations with have addition in them somewhere and then doing some stuff; which is what happens with this bit manipulation . so this isnt number theory
like if i wanted to i could define f(x)=x+b, and then say f(a) as the answer
supple furnace
log(e^a*e^b) or something like that
ivory coyote
gotcha okay I was just curious thanks for the response!
daring night
i got to x=1+p^-1 mod(p+2) - is this solved? what more can i do
sacred junco
How to multiply binomials again?
stoic bear
sacred junco
hey so I'm working on calculating the gcd between Arithmetic derivatives of a number and the number but for some reason the value of 39521 doesnt work and gives me a stack overflowerror , granted the values after it work fine, I really hope someone could help me understand whats causing this...
import java.lang.Math;
public class test{
private static long gcd(long x, long y){
if (x == 0)
return y;
if (y == 0)
return x;
if (x == y)
return x;
if (x > y)
return gcd(x-y, y);
return gcd(x, y-x);
}
private static long smallDiv(long x){
if(x%2 == 0){
return 2;
}else{
for(int i = 3; i * i <=x; i++){
if(x % i == 0){
return i;
}
}
}
return x;
}
private static boolean isPrime(long n){
if (n <= 1) return false;
if (n <= 3) return true;
if (n%2 == 0 || n%3 == 0) return false;
for (int i=5; i*i<=n; i=i+6)
if (n%i == 0 || n%(i+2) == 0)
return false;
return true;
}
private static long ArthDerv(long num){
if(isPrime(num)){
return 1;
}else{
long a = smallDiv(num);
long b = num/a;
long c =ArthDerv(a)*b + a*ArthDerv(b);
return c;
}
}
public static void main(String[] args) {
double upper = 5*Math.pow(10, 15);
long sum = 0;
int val = 39521;
System.out.println(gcd(val, ArthDerv(val)));
//for(long i = 2; i < 1000000; i ++){
//System.out.println(i + ", " + gcd(i, ArthDerv(i)));
//}
}
}
39522 and after work fine...
sacred junco
I added a while(true)
That seems to have fixed it
That’s not a bad idea aswell
Now my main problem is run time tbh, I have to calculate sum of gcds up to $$5*10^{15}$$
sterile pumiceBOT
Zeek:
leaden swan
Now my main problem is run time tbh, I have to calculate sum of gcds up to $$5*10^{15}$$
You mean like vary x from 1 to that number and y from 1 to that number and sum of the gcds of all possible pairs?
sacred junco
Yeah I noticed that, I might have to try something similar to the 100! Problem
leaden swan
Find out a way to count the number of coprime pairs
Then for no of times 2 occurs,Divide the sample space by 2 and repeat
And so on
sacred junco
@leaden swan thats the problem
I def see now why many people havent solved it yet despite the simple theory
sacred junco
Even if I don’t use recursion for the gcd, it’s still not enough to to get to the upper bound 😭
Someone told me it’s better if implement my own stack, I might give that a shot
vestal blaze
One thing that should increase the performance a lot (but is still probably not be enough) is memoization: Your current program calculates the arithmetic derivatives of the same numbers again and again (for example you need 100' in order to get 200', 400' etc.). Save those you have already calculated in some way that you can access them easily use these results.
fervent crest
Yeah but also you can't cashe everything
So I guess somehow finding a balance will lead to the solution
Or there's some clever easily computable formula for gcd(k,k')
sick rampart
Whoever
supple furnace
Here’s an exact formula for gcd(k,k’) (it’s still pretty bashy though): k/rad(k)*r(k), where r(k) denotes the product of all primes p|k such that p|v_p(k).
fiery root
Guys I think the answer should be 10C4/11C4. The solution given is 8C4/11C4 but I don't think that is correct because that is valid only if, assuming the stops are TABCDT, there is at least one stop between T and A, and D and T. The problem only mentioned one stop between A-B, B-C and C-D
What do you guys think?
This is their reasoning
sacred junco
I am buggin, cause this doesnt make sense to me
How does the backwards implication work
Assuming the second equality could still possibly give you 2 mod 4 in the first if the residue term is 1
cause that is definitely possible
I am probably missing something though, I have to be
supple furnace
x^2 can never be 2 mod 4