What's up
#elementary-number-theory
raven carbon
raven carbon
Well first off, can you identify the how the sequence changes with each element?
sacred junco
The common ratio is -3
@raven carbon
a is -1/3
l is 729
I applied that formula but it is giving some funny answee
raven carbon
So this is a geometric series, right?
sacred junco
I think yeah
Wait a sec
Brb
Holy shit it is in AP I just realized @raven carbon
Lmao
light flicker
How does $5^{a - b} \equiv 1 \mod 2^n$ imply that $a \equiv b \mod 2^{n-2}$?
sterile pumiceBOT
Zopherus:
light flicker
For n > 2
Okay I'm dumb. It was shown earlier that the order of 5 mod 2^n is 2^(n-2) which shows this
crimson lagoon
viscid flower
Can someone please explain what the relation between Legendre's Dirichlet Theorem and Quadratic Reciprocity is?
This is the Dirichlet Theorem
vague fable
What's wrong with Euler's proof?
I need to prove that the sum of the reciprocal of primes diverges, but I don't know how to get started?
light flicker
Do you have to do this for a class?
fickle schooner
on peter's link "Thus Euler obtained a correct result by questionable means"
lmao
me in every class
i think it is "wrong" because you can't say two things that diverge are equal?
pastel egret
@quick furnace i cant find the probabiltiy group again
it disapepared
<@&268886789983436800> did i get banned from proability chat
hi am i banned from probabiltiy
light flicker
gilded tinsel
@pastel egret u probs have the chats appear obly wheb there are new messages in them
whole quail
no
devout nexus
wat are ye doing
sharp gulch
<@&268886789983436800>
half fable
what the fuck
sharp gulch
scrEEEEch
half fable
@minor tapir fuck off
devout nexus
oh its a raid
strange ravine
what the heck is going on
half fable
@minor tapir yeah you heard me
devout nexus
its a pretty mild raid guys dwai
static sparrow
w h o p u n g
sharp gulch
Nani
tribal briar
hm
strange ravine
Jaboi you have any idea what is happening
half fable
what just happened?
whole quail
this is probably a raid?
tribal briar
sharp gulch
dry oak
woke me up
dry oak
or rather
whole quail
if it is a raid thats against discord ToS and you can probably get their server removed
half fable
what happened panda?
dry oak
interrupted my shutdown sequence
tribal briar
they woke me up 👀
devout nexus
lol
strange ravine
don't keep audio notifications on smh, I don't know why people do
tribal briar
half fable
pandas are really hard to be afraid of
strange ravine
I forgot to turn off audio once and scared me lol
blissful venture
I'm summoned
tribal briar
HI HORSE
north cave
what in tarnation
fathom sierra
dafak
elder bobcat
whomst pung
tranquil lintel
oml
versed storm
Number theory can be pretty intense
viscid flower
How do you work out the legendre symbol for cases of say (14/p), (5/p) or like (12/p) say?
I know we have to use the quadratic reciprocity law
so say for (14/p), this is equal to (2/p)(7/p)
so we have to determine for each case, where (2/p) = 1 and (7/p)=1 right?
light flicker
You know that (2/p) = 1 if p = 1 or 7 mod 8 and -1 otherwise
light flicker
Yeah
sterile pumiceBOT
!R. ¬:
light flicker
You're doing this for a general p?
viscid flower
yeah
so $(-1)^{\frac{p-1}{2}}=\begin{cases}1, &p\equiv 1\pmod{!4}\-1, &p\equiv -1\pmod{!4}\end{cases}$
sterile pumiceBOT
!R. ¬:
viscid flower
but I think i'm getting thrown off with the $\frac{7-1}{2}$ part
sterile pumiceBOT
!R. ¬:
viscid flower
how do we evaluate this now that we have a factor 3 in our (-1)^3(p-1)/2 part
viscid flower
oh right yeah yeah 🤦
light flicker
There's also this theorem that you can use
viscid flower
so now i know the case for the (-1)^{p-1/2} part
do i just solve the system of congruences with CRT for p/7
light flicker
Yeah
upbeat wren
Let p be any prime. If q > p and q is prime, q is odd!!
Sorry just goofing around.
hmm is there "oddness" in other algebraic structures? And well ordering? And would this make sense in those worlds?
oddness is not being a multiple of the smalllest prime.
ugh ... other rings and things. Where you can't assume the obvious.
quick furnace
well if a ring R that contains an ideal I s.t. R/I iso to Z/2, then perhaps one could speak of elements of R being "even" if they are in I and "odd" if they aren't
random sand
With what ann said about the iso to Z2 certainly holds,
as for well ordering, that may or may not hold since ya know, but AC guarantees a set can be well ordered (if you accept it)
"oddness" in groups wouldn't make too much sense unless you had a subgroup in which gave you Z2 as a cyclic group but that might still be a bit weird
upbeat wren
I'm somewhat happy with ... Let p be any prime. If q <> p and q is prime, q is not a multiple of p.
viscid flower
can someone explain to me how the complex numbers came about in proving the law of quadratic reciprocity?
i understand we have these equations called Gauss Sums, etc... but not really sure how it all works, and the method behind it
viscid flower
'O' is it because of cyclotomic equations? we always end up with imaginary roots etc?
sacred junco
Does analytic number theory fall into elementary or not?
woeful jackal
Prove that there are infinitely many primes of the form 6n + 5
Wondering if I could get a hint ... basically, I know that all primes > 3 either are congruent modulo 1, or modulo 5, to 6.
light flicker
Think about Euler's proof that there are infinitely many primes and try to adapt it
wait is it euclid's idk
woeful jackal
Gauss's proof? @light flicker do you perhaps mean Euclid's (with the construction, from any finite set p_1 ... p_n, of the product + 1)
yeah
okay cool we're thinking of the same thing 😎 thanks for the hint! (that was my hunch, just making sure)
one thing that doesn't work is multplying a finite set of primes, form 6m + 5; since, if evenly many, I get back something of form 6m' + 1, or if oddly many, of 6m' + 5. Then adding one gets me a composite number. Gotta think about this some more 
light flicker
Yep, it's not that straightforward as just copying down the proof
woven phoenix
Hi all... By drawing some diagram, I can show that 6 cannot divide 3 + 4b for any integer b. How should I approach the general problem of determining whether c_1 + c_2 b is divisible by another integer d? (where c_1, c_2, and d are constants)
here's another example. I can find some b where 2 + 4b is divisible by 6.... but only after drawing some diagrams.
light flicker
Try to do the same thing that you did in the second picture
@woven phoenix
Like the if and only if stuff
ivory patrol
3 + 4b = 0 (mod 6)
4b = 3 (mod 6)
4b = 3 + 6z
By properties of linear diophantine equations, since (4,6) = 2 and 2 doesn’t divide 3, there are no solutions for b
For the general problem of c_1 + c_2 = 0 (mod d), again subtract c_2 from both sides to get c_1 = d - c_2 (mod d)
If gcd(c_1,d) doesn’t divide into d-c_2 then there’s no solution
woven phoenix
Thanks all! Hmm diophantine eqs in on chapter 3, and im still on ch 1 of my textbook. I actually got to this problem trying to solve the an exercise in ch 1. Perhaps I took the wrong approach.
woven phoenix
Ugh I’m stuck even after 2 days. Would be great if someone can point me in the right direction. Here’s the probelm
And Here’s as far as I could get:
After that I tried fiddling with the variables but couldn’t get anywhere
light flicker
What can you say about x^2 + ax mod b?
woven phoenix
Thanks, will read around!
woven phoenix
Wow I think I found the answer. I can put the restriction that (c, d) = 1. Now because d | c.c and (d, c) = 1, then it must be the case that d | c. Thus d = 1 and the rational root is actually an integer
The wikipedia article about the rational root theorem assumes that p and q are coprime, so I used that property. Thanks a lot!
light flicker
Yep
That's what I was trying to lead you towards initially
But I did it for the wrong side of the polynomial whoops
woven phoenix
haha
woven phoenix
Completed all solutions for Dudley's textbook chapter 1. Might be useful for other learners:
https://github.com/agro1986/textbook-solutions/blob/master/elementary_number_theory_second_edition_solution.pdf
I'll probably ask around again when I get stuck in chapter 2 😃
silent magnet
If we say $x, m \in \mathbb{N}$ and $r = x \bmod m$, is there any rule or result that says that for any $d \in \mathbb{N}$, $(d \mid r) \Rightarrow (d \mid x)$?
sterile pumiceBOT
Big Nose JoJo:
woeful jackal
No, this is false in general (e.g. (m = 5) divides (r = 2) - (x = 7), so r = x mod 5; and certainly (d = 2) | (r = 2). But it is false that d | x
Congruence of two integers w/r/t some given modulus just has to do with how "far apart" they are; which, in turn, doesn't have much to do with their respective factorizations
However, think about what happens in the (special) case where m divides either of the integers
silent magnet
That's what I thought, but I'm reading a paper that seems to assume what I said should be the case
woeful jackal
Is it possibly looking just at that special case? (might show up elsewhere in the paper, but then be left implicit)
silent magnet
where m divides either of x or r?
silent magnet
Ok so I figured it out
in the paper, there is a set of natural numbers, which d is taken from
and m is the least common multiple of that set
so if we rewrite x as x = mn + r, it is always the case that for the chosen d, d | m, so d | mn, so if d | r also, then d | x
or did I make any mistakes?
woeful jackal
that looks good to me
upbeat wren
Tail-end divisibility:
A / B
Repeat as needed:
Find BK (multiple of B) such that A + BK or A - BK ends in a zero and lop off the tailing zeros.
54321 / 7 ...
54321 - 21 = 54300
543 + 7 = 550
55 + 35 = 90
9
7 does not divide 9. 7 does not divide 54321.
quick furnace
?
upbeat wren
sorry accidentally pressed enter too soon
I wanna say it works for any pair (A, B) where GCD(AB, 10) = 1 ... (not absolutely sure but pretty much sure)
woven phoenix
Hi everyone, I'm trying to solve the problem above from the book "Elementary Number Theory" that I'm self studying.
I use help of computer program (which I made myself) to show that there are many cases where the statement in a is wrong:
n = 20 6n-1 = 119 = 7x17 6n+1 = 121 = 11x11
n = 24 6n-1 = 143 = 11x13 6n+1 = 145 = 5x29
n = 31 6n-1 = 185 = 5x37 6n+1 = 187 = 11x17
n = 34 6n-1 = 203 = 7x29 6n+1 = 205 = 5x41
n = 36 6n-1 = 215 = 5x43 6n+1 = 217 = 7x31
But I'm stuck in solving b.
First I note that both 6n-1 and 6n+1 are odd (because 6n is even). Also they cannot have 2 or 3 as their factor.
I've found some patterns that might be or might not be useful. For 6n+1, there seems to be lots of n where it is a square.
n = 20 6n-1 = 119 = 7x17 6n+1 = 121 = 11x11
n = 48 6n-1 = 287 = 7x41 6n+1 = 289 = 17x17
n = 88 6n-1 = 527 = 17x31 6n+1 = 529 = 23x23
n = 160 6n-1 = 959 = 7x137 6n+1 = 961 = 31x31
n = 280 6n-1 = 1679 = 23x73 6n+1 = 1681 = 41x41
However there doesn't seem to be any n where 6n-1 is a squre.
There are many patterns where 6n-1 or 6n+1 can be written as p^2 q where p and q are primes. Here's for 6n-1:
n = 71 6n-1 = 425 = 5x5x17 6n+1 = 427 = 7x61
n = 139 6n-1 = 833 = 7x7x17 6n+1 = 835 = 5x167
n = 171 6n-1 = 1025 = 5x5x41 6n+1 = 1027 = 13x79
n = 196 6n-1 = 1175 = 5x5x47 6n+1 = 1177 = 11x107
n = 222 6n-1 = 1331 = 11x11x11 6n+1 = 1333 = 31x43
And here's for 6n+1:
n = 54 6n-1 = 323 = 17x19 6n+1 = 325 = 5x5x13
n = 57 6n-1 = 341 = 11x31 6n+1 = 343 = 7x7x7
n = 79 6n-1 = 473 = 11x43 6n+1 = 475 = 5x5x19
n = 104 6n-1 = 623 = 7x89 6n+1 = 625 = 5x5x5x5
n = 106 6n-1 = 635 = 5x127 6n+1 = 637 = 7x7x13
Any hints on how to prove statement b? Thanks a lot.
light flicker
@woven phoenix do it by contradiction
versed storm
there are infinite primes of the form 6k - 1 and 6k + 1.
autumn dune
arent all primes greater than 3 of that form
glacial coral
^ Yes since 6k, 6k+2, 6k+3, 6k+4 are nonprimes (and 6k-1 and 6k'+5)
autumn dune
2 and 3 arent really primes anyway since theyre divisible by 2 and 3
light flicker
@versed storm does that do anything to prove what you want here? I'm not sure it does?
modern tulip
woven phoenix
@light flicker Thanks for the hint! Something like this?
light flicker
@woven phoenix yeah nice wow
not the solution I had in mind. You might want to note at the end that your contradicted your original assumption, so there must not exist a largest such n
woven phoenix
Right, will add the explanation! Btw what was the approach that you had in mind?
light flicker
Start with the same thing you did
Let n be the largest such that 6n-1 and 6n + 1 are both composite
This means that for all k > n, we have at least one of 6k-1 and 6k+1 is prime
But we have that (6k-1)(6k+1) = 36k^2 - 1 = 6(6k^2) - 1 is composite. This implies that 6(6k^2) +1 is prime for all k > n.
Then it's not too hard to show that this can't always be true
woven phoenix
aaah great! Thanks for the different perspective
light flicker
your solution is super nice though
I was confused for a bit, cause seemed like you pulled the number out of thin air, but then everything worked out
woven phoenix
haha, found by scribbling this
regal pivot
Will gcd(k,k+1) = 1 for k !=0?? Is it true ??
light flicker
It's true even for k=0
light flicker
That is true yes
frank wigeon
hi guys how do i round 0.01 to 1 ?
rotund charm
but then again
quick furnace
if you round up to the nearest integer, i guess
rotund charm
how do you round
oblique crest
Search for the ceiling function
midnight knot
maybe someone here will be able to help me, I really need to solve this question
for which prime numbers p, polynomial $Q(x) = (x^2 + x + 1)^2$ does not divide $P(x) = x^p + 1 - (x+1)^p$
sterile pumiceBOT
cybergnostic:
light flicker
I'm not quite sure this question is answerable without knowing what ring we're working over
Like divisible as integer polynomials? Or real polynomials? Or complex polynomials?
midnight knot
ok, that crossed my mind at some point, but i couldn't see or anticipate what would be the difference? I guess that if its real or complex ring, there should always be a solution
so I guess (since its prime number power) that we are working with polynomials with integer coeff.
let me rephrase what I just wanted to say: if question is solvable in R[x] or C[x] - how exactly?
upbeat wren
Did you solve it for Z[x] already? Just wondering.
midnight knot
no
but I have some hints, x^6 is congruent to 1 mod Q(x)
which may have to do something with prime numbers greater than or equal to 5
or primes in the form 6n +- 1
but it was a dead end too
upbeat wren
ah okay.
if p congruent to 1 mod 6, x^p + 1 - (x + 1)^p is congruent to x^k + 1 - (x+1)^k mod Q(x) where k is p mod 6.
if p congruent to 5 mod 6, x^p + 1 - (x + 1)^p is congruent to x^k + 1 + (x+1)^k mod Q(x) where k is p mod 6.
Sound good so far?
midnight knot
wait i have to write it down to really get what u say
upbeat wren
hmm ... semi-oops. Always!! ...
x^p + 1 - (x + 1)^p is congruent to x^k + 1 - (x+1)^k mod Q(x) where k is p mod 6.
upbeat wren
so you only need to test k = 2, 3 and two sets of primes: k = 6n + 1 and k = 6n - 1.
midnight knot
hm ok but I think I can't see why is P(x) congruent to x^k + 1 - (x+1)^k, where k is p mod 6
upbeat wren
x^p --> (x^6)^m (x^(p mod 6))
midnight knot
-.- I'm dumb
upbeat wren
negativity is not needed <-- ironic
midnight knot
1 doesn't work, you can tell imidiately
or...
no, not working
wait its 0
5 will not work because I'll get binomial coefficients
shy wave
Why is x^6 congruent to 1 modulo Q(x) ?
upbeat wren
hehe. The hint said so 😃
midnight knot
but what I do with (x+1)^p, it becomes (x+1)^6m (x+1)^p mod 6
shy wave
To me it didn't seem true, maybe I am missing something
upbeat wren
ah nice.
shy wave
When I checked before I got x^6 -1 = (x^2 - 1) (x^2 + x + 1)(x^2 - x + 1)
shy wave
It's x^2-1 though so (x-1)(x+1)
midnight knot
so @upbeat wren it seems that answer is all p except p=1 mod 6?
but no, still: what I do with (x+1)^p, it becomes (x+1)^6m (x+1)^p mod 6
@shy wave no, you have (x^2 + x + 1)^2 = (x^2 + x + 1)* (x^2 + x + 1), so for each of the two you need one (x-1)
which makes it (x-1)^2
upbeat wren
er I think Mat is right.
x^6 + 1 = k(x^2 + x + 1)^2
x^6 + 1 = k(x^4 + 2x^3 + 2x^2 + 2x + 1)
for k = x^2 - 2x + 1
er so x^6 is congruent to -1 mod Q(x)
hollow bramble
sage: P.<x> = PolynomialRing(ZZ)
sage: x^6 % (x^2+x+1)
1
just a future suggestion if anyone gets lazy
isnt (x^2+x+1)^2=x^4+2x^2(x+1)+(x+1)^2=x^4+2x^3+2x^2+x^2+2x+1=x^4+2x^3+3x^2+2x+1
shy wave
Ariana could you show it modulo Q(x) = (x^2+x+1)^2 ?
Checking with wolfram alpha I get that x^6 is congruent to 2x^3-1 modulo Q(x)
midnight knot
it is congruent to 2x^3-1 but it's like reduced
midnight knot
i mean, 13 mod 12 is 1 but 25 mod 12 is also 1
shy wave
You typed x^6+1 though
upbeat wren
yeah x^6 - 1 pls 😃
shy wave
@hollow bramble
hollow bramble
sage: (x^6) % (x^2+x+1)^2
2*x^3 - 1
sage: (x^6-1) % (x^2+x+1)^2
2*x^3 - 2
kinda same thing
shy wave
Indeed, so I didn't get your nop
hollow bramble
(doing polynomials by hand is painful prone to mistakes)
upbeat wren
BUT this is fine for polynomials with real coefficients.
midnight knot
shy wave
(x-1)^2 Q(x) = (x^3-1)^2
upbeat wren
or not ...
midnight knot
lol we are golden boys and girl
midnight knot
fck I have to go out now, I'll work on it and check here again later/tomorrow
I can't think when I have pussy on my mind...
hollow bramble
i think should be p=1(mod 6)? just got to show it
upbeat wren
4 hours of sleep cause relatives are coming into town ... god I love my family.
midnight knot
@hollow bramble if you work it out ping me or pm me, I have discord on phone so I'll check it, that's how important it is 😄
hollow bramble
alrite
currently i have numerically worked out it should be all integers congruent to 1 mod 6, jus trying to show probably by induction
hollow bramble
well i got a pretty disgusting proof
working under mod Q
Assume $x^{6n+1}+1=(x+1)^{6n+1}$
First show
$$\left(x^6-(x+1)^6\right)\left(x^6-(x+1)^6\right)\equiv0$$
$$\left(x^6-(x+1)^6\right)\left(1-(x+1)^6\right)\equiv0$$
Then
Now consider
$$\left(x^{6n+7}-x^{6n+1}\right)-\left((x+1)^{6n+7}-(x+1)^{6n+1}\right)$$
$$\equiv x^{6n+1}\left(x^6-1\right)-(x^{6n+1}+1)\left((x+1)^6-1\right)$$
$$\equiv x^{6n+1}\left(x^6-(x+1)^6\right)-\left((x+1)^6-1\right)$$
Since $x^6-(x+1)^6\neq0$, the expression is equal to
$$x^{6n+1}\left(x^6-(x+1)^6\right)\left(x^6-(x+1)^6\right)-\left((x+1)^6-1\right)\left(x^6-(x+1)^6\right)$$
$$\equiv0$$
sterile pumiceBOT
Ariana:
hollow bramble
welp thats kinda ugly
@midnight knot quite sure there's a easier way but here's a really barbaric proof XD
shy wave
@hollow bramble
Really nice idea
I think though there is a step which should be adjusted.
Before the last two lines, you have an expression A and an element B != 0. But unless B = 1 you can't say that
A is congruent to AB
However, if B happens to be invertible,
AB congruent to 0 implies A congruent to 0
hollow bramble
Ahh righttt
there isnt a inverse mod since even $\left(1-(x+1)^6\right)\left(1-(x+1)^6\right)\equiv0$
sterile pumiceBOT
Ariana:
shy wave
Oh true I didn't remember that B^2 congr 0
hollow bramble
Ok update:
$$x^6 - 1 \equiv \left(2x-2\right)\left(x^2+x+1\right)\pmod{\left(x^2+x+1\right)^2}$$
$$(x+1)^6 - 1 \equiv \left(-2x-4\right)\left(x^2+x+1\right)\pmod{\left(x^2+x+1\right)^2}$$
$$x^6 \equiv 1\pmod{\left(x^2+x+1\right)}$$
continued...
$$\equiv x^{6n+1}\left(x^6-(x+1)^6\right)-\left((x+1)^6-1\right)$$
$$\equiv \left(x^{6n+1}\left(2x-2+2x+4\right)+\left(2x+4+1\right)\right)\left(x^2+x\right)$$
$$\equiv \left(x^{6n}\left(4x^2+2x\right)+2x+4\right)\left(x^2+x+1\right)$$
So we just need to show $\left(x^{6n}\left(4x^2+2x\right)+2x+4\right)\equiv0\pmod{x^2+x+1}$ which is pretty simple
sterile pumiceBOT
Ariana:
hollow bramble
This kindaish resembles hensel lemma tbh
shy wave
A very nice proof, in the end!
Yeah, the conclusion is quick if we notice that in mod(x^2+x+1):
4x^2+2x = -2x-4
and so the last expression is congruent to
-(2x+4)(x^(6n) - 1)
where x^2+x+1 divides x^3-1 which divides (x^(6n)-1)
@hollow bramble
However Ariana, going back to the initial problem, this is just half of the proof we were seeking, right?
I mean, suppose we want to find for which p primes Q(x) divides P_p(x).
Now we know that if p=1+6n (and since we didn't use the primality of p, the property actually holds for any natural number in that form), then Q(x) divides P_p(x).
Is it possible to also prove the other direction ?
i.e., these are the only solutions?
hollow bramble
hm tru
but i think showing that $x^{6n+5}+1-(x+1)^{6n+5}\equiv (6n+5)\left(x^2+x+1\right)$ should also be doable by a similar method? and thats all the odd primes
really got to sleep now mdr like 4:30am here.-.
sterile pumiceBOT
Ariana:
shy wave
@hollow bramble
Oh, probably it is then
Well so restricted to primes the question is fully solved
(Otherwise in general, maybe, it is just needed to consider all cases modulo 6)
Was it also possible to work modulo 4 in your opinion?
However thank you a lot for sharing your proofs, they've been inspiring
4.30am !? Sleep well
hollow bramble
lol thanks
modulo 4 idts doesn’t seem like its related
midnight knot
@upbeat wren @shy wave @hollow bramble
hey, a dude helped me solve that question. So here is the solution, if you are interested:
since Q(x) shouldn't divide P(x), then for roots of Q(x) (complex roots appearing twice since Q(x) is squared polynomial), say p and q, P'(p) and P'(q) shouldn't be zero, which only works for primes such that p = -1 (mod 6)
because if p = 6k+1, P'(x)= p( x^(p-1) - (x+1)^(p-1) = p( x^6k - (x+1)^6k)
midnight knot
the fact which is really neat is (perhaps you remember I asked something on that track at one point), if you take one root of Q(x), -1/2 + isqrt(3)/2 and add 1 (substitute x for (x+1)^p) you get 1/2 + isqrt(3)/2
which both become 1 when you raise it to 6k power
shy wave
@midnight knot
sterile pumiceBOT
Mat:
shy wave
I don't know, maybe @hollow bramble could spot if I am missing something
midnight knot
@shy wave its iff statement, just to point it out. So:
let $f(x) \in R[x]$ be nonconstant polynomial, k \in \mathbb{N}$. $a \in \mathbb{R}$ is zero of order $k$ of the polynomial $f(x)$ if and only if $f(a)=0$ and $a$ is zero of order $k-1$ of f'(x)$.
sterile pumiceBOT
cybergnostic:
Compile Error! Click the 
reaction for details. (You may edit your message)
shy wave
@midnight knot Thanks for the reply, I appreciate to have some light shed on this, these are my thoughts on it
sterile pumiceBOT
Mat:
shy wave
*On the right
woven phoenix
Yea the book doesnt limit m to be prime though. If it’s prime its kinda easy to prove
The answer said true so I wasted a few days tinkering with finding a proof
Only dealing with letters a, b, m. When I gave up and switched to numbers I found the counterexample above
Thanks for confirming it plum
hollow bramble
generally it is false tho
a!=-a
unless a=n/2 mod n if n is even
oh wait didn’t see the other line
woven phoenix
Yea a = a
hollow bramble
then uhh
since no. of quadratic residues of primes is (p+1)/2 by euler’s criterion
for composites it’s generally false
sacred junco
Hey so I saw this problem to find all natural numbers solution for 5^x+6^y=7^z
A guy told me to work with mod 35 and you can proof that there are no solutions
random sand
what about x = 0, y = 1, z = 1?
sacred junco
0 is not a natural number
random sand
ah, a man of culture as well i see
sacred junco
The problem is that when you figure out z is always equal to 4k
You get that 7^z is always equal to 21 mod 35
But it is possible 5^x+6^y=21 mod 35
So I guess mod 35 isn't the way to go or I'm just doing it wrong
hollow bramble
tldr
x = 2a
y = 5b
z = 4c
Ok so lets see
assuming x,y,z are positive integers
Mod 5 we have 1=2^z so z=4z’
Mod 6 we have (-1)^x=1^z so we have x=2x’
Now lets take mod 25
0+6^y=1
So y=5y’
quite sure theres a result with the generalized FLT but feels overkill
hollow bramble
if mod 35:
(5^2)^n = 25,30,15
6^n = 6, 1
(7^4)^n = 21
So x=6a and y=10b
Now consider mod 210
5^6=85, 85^2=85
6^10=36, 36^2=36
7^4=91, 91^2=91
But 85+36=121
grizzled badge
I’m being dumb and can’t use induction on n < 3^n
It clearly hold true for n = 1
So then it’s n + 1 < 3*3^n
But I’m not sure where to go beyond this
I considered writing it as 3^n + 3^n + 3^n
light flicker
Well what does your inductive hypothesis tell you
grizzled badge
That 1 < 3?
or n < 3^n actually
Like logically 3^n is a positive integer greater than 1, meaning 3* that will always be greater than just adding 1 on the Left side, but I don’t know how to write that mathematically
light flicker
Well you're trying to show that n + 1 < 3* 3^n
and you know that n < 3^n
So if you do write 3*3^n as 3^n + 3^n + 3^n, then what do you need to show to finish your proof
light flicker
No not quite
The inequality you want to get to is n + 1 < 3^n + 3^n + 3^n
And you know that n < 3^n
So all you need to do is show that 1 < 3^n + 3^n
and then if you add those last two inequalities together, you get what you want
grizzled badge
Oh I see your way too
Is it valid to just write that 1 < 3^n or do I have to prove that somehow
opal orbit
It's valid to say that as long as n > 0
grizzled badge
It was for all positive integers n so yes
Okay, I’ll keep practicing these induction proofs
calm wing
What does decimal powers signify?
short coral
l
grizzled badge
It would be the root
sharp plaza
10^(lg 2) = 2, that's for sure
midnight knot
so for every finite decimal number there is a fraction representation
so if 0.301 = p/q it would be 10^(p/q)
calm wing
yes I was asking in the sense of log
I understand what log (10^x) would mean but since log base 10 of any number other than powers of 10 gives decimals I don't understand their significance like what do they mean
calm wing
they couldn't have explained it easier on stackexchange lol
shy wave
I think first you define integer powers as repetition of multiplication
Then you define rational powers as roots of a polynomial, like 10^(1/m) is the positive solution to x^m=10
and 10^(n/m) is defined as (10^(1/m))^n
Then you define irrational powers approaching to their value with sequences of rational powers. So, irrational powers are the limit of some sequences which can be proved to have limit
calm wing
ah so power of roots
shy wave
Yes, that is the definition I was taught
shy wave
You're welcome!
vast dove
Hey guys
I have s and r integers
s>0
And s divides r^n for some n>0
Also gcd(r,s)=1
Does this imply s=1 ?
fleet thorn
you know what gcd(r,s)=1 implies?
vast dove
ar+bs=1 for some a,b integers?
light flicker
Let p be a prime that divides s, we know that this prime does not divide r. However, this prime divides r^n which is a contradiction, thus no prime can divide s
vast dove
Thanks
sacred junco
Not sure if it belongs here
question from the australian math competition
How many of the first 2004 Fibonacci numbers have their last digit ending in two?
I'm not sure how to do it
is there like a pattern>
inner crest
0 1 1 2 3 5 8 3 1 4 5 9 4 3 7 0 7 7 4 1 5 6 1 7 8 5 3 8 1 9 0 9 9 8 7 5 2 7 9 6 5 1 6 7 3 0 3 3 6 9 5 4 9 3 2 5 7 2 9 1 0 1
midnight knot
how would you extract numbers like that @sacred junco ?
sacred junco
Hey
midnight knot
maybe it would be useful to say that they are congruent to 2 mod 10
stiff rivet
im sure there is some theory that helps you with that
first of all, you only have to check every 3rd number
sacred junco
Every third number that is even
stiff rivet
exactly every third fibonacci number is even
stiff rivet
in general, the m'th fibonacci number divides the k*m'th fibonacci number
you can use this to remove some more
or maybe you can't, not sure
sacred junco
You just do the sequence
Until 2 ones appear again
You count how many 2s you got In that sequence
And you get that you have 133 twos
midnight knot
why two 1's?
midnight knot
and what if two numbers before end in say 7 and 5?
next one ends in 2
oh you think
calculate it in the first such period
inner crest
@sacred junco if you look at the list I gave you you should be able to figure it out
inner crest
oh wait they haven't responded yet
sacred junco
He gave it until he reached 0 1
midnight knot
yeah
sacred junco
Find all whole number solutions (a, b, c) such that ab/c+bc/a+ac/b=9
Any help with this?
sacred junco
Yes @midnight knot
midnight knot
ok so I got to some point, which is nice I think
i was able to show that ab/c is whole
same for the other two
you need that part?
then you just have to split the cases
which is pain in the ass
so I moved along, learning my own stuff
midnight knot
here, might help
you do the same process to show that b|ca and c|ab
hm might not be completely right but the identity should help
midnight knot
no, two of them has to be negative
oh no its possible... too many solutions
plus, 4, 2, 2 also works
every combo of two negative and one positive or all 3 positive works
for 333 and 422
shy wave
If I am not wrong it is possible to prove that 1<=abc<=27
So after proving that none of a,b or c can be 1, you are left with phew possibilities
abc = 27, 24, 20, 18, 16, 12
The divisibilities found by cybergnostic rule out all of them except
27=3*3*3 and 16=2*2*4
So if you permutate and add couples of minuses to (3,3,3) and (2,2,4) you should obtain all the solutions
@sacred junco
sacred junco
I just read this statement from my lecture: "An integer of the form of 2^n - 1 is a prime where n is also a prime number."
So what's the deal with finding larger primes? Once you find the next biggest prime number, can't you then insert that into the equation for n to find the next and so on?
Is it mostly about finding what that number actually is? I mean 2^(big number) - 1 is still a number, even if it is not completely expanded
light flicker
Because that statements not true lmao
How would 16 be prime
You probably mean 2^n - 1
But this still isn't true
sacred junco
woops
autumn dune
So what's the deal with finding larger primes? Once you find the next biggest prime number, can't you then insert that into the equation for n to find the next and so on?
what im assuming the lecture meant was
if 2^n -1 is prime, then n must be prime
sacred junco
and that isn't true?
shy wave
Is it an exercise to train counterexamples technique?
autumn dune
which doesnt mean that 2^(2^n - 1) - 1 is prime
sacred junco
This is what it states
The lecture is talking about how there are infinitely many primes and the proof involves mersenne primes
autumn dune
it is not known whether there are infinitely many mersenne primes
so the lecturer might be in error
sacred junco
oh...I'll email my professor. She has a lot of errors. Sometimes I catch them myself and let her know and she is at least willing to change it
she doesn't have very good English which may be why
autumn dune
might just be that
i could interpret her statement as meaning, 2^n -1 is prime only when n is prime
but that doesnt mean if n is prime then 2^n -1 is prime
sacred junco
well I'm glad that was cleared up. Sometimes I use Cunningham's Law to my advantage 😛
I do wish that she would prove her statements. She almost always will make some statement like "there are infinitely many primes of the form n^2 + 1" and then leaves it at that. If I ask her for why that is, she says to prove it at home
sacred junco
I suppose, but I'd rather not be given blanket statements with no evidence to back them up. I'd even be satisfied if she said by what theorem her statement comes from so I could look it up easily
light flicker
You proving it is also a good exercise
sacred junco
That's true. I think I'm the only one that does that lol
so for the non math majors in the class, they are being cheated of an education!
shy wave
Ahah I didn't know that law
light flicker
I mean they only have themselves to blame so
shy wave
Seems super effective
sacred junco
It's very effective, especially on the internet @shy wave
shy wave
I'm gonna make it a fine weapon
grizzled badge
its like really good exercise
ill actually give you a few thousand dollars if you do it, just uh give me all your work after :^ )
sacred junco
wow cunningham's law is such a neat thing
regal pivot
How can I solve modular equations?
a%p = ans
b%p = ans
c%p = ans
if a,b,c and ans are known then find p?
midnight knot
by the definition of congruences, if a=b mod p, then p|a-b.
or in your case @regal pivot p has to divide all of the 3 numbers you get by applying definition of congruence
regal pivot
@midnight knot a ≡ b (mod m) notation is same as b = a%m ??
midnight knot
yes
so think about what it really means
when you divide some number by the other, say you divide some a with a prime number p
if p is not multiple of a, there will be some leftover
midnight knot
where exactly?
inner crest
a ≡ b (mod m)
regal pivot
so u mean to say both a ≡ b (mod m) and b = a%m are not same ??
midnight knot
that won't change anything
they are just different ways of writing the same fact
a ≡ b (mod m) means that both a and b give the same remainder when divided by m
midnight knot
and how's that?
inner crest
b may be larger than m when looking at the converse
midnight knot
its in the same class, bigger or not
and if both a and b are less than m then they have to be equal
you can't have two numbers less than m to be congruent mod m if they are not the same
give the concrete example
inner crest
$1\equiv3\mod 2 \not\implies 3=1%2$
midnight knot
so, you want to say that b=a%m means that number b is equal to number a reduced mod m
sterile pumiceBOT
EpicGuy4227:
regal pivot
take a=2 b=3 and m=5 u don't get same result ??
midnight knot
2 is not congruent to 3 mod 5
so if a%p = ans and you know the a and ans then p|a-ans
regal pivot
So 3 = 2%5 is not equal to 2 = 3mod 5
midnight knot
3 = 2%5 is not true
regal pivot
3 = 2%5 is not true what do u mean ?? it is invalid??
midnight knot
because 3 is not congruent to 2 mod 5, neither is 3 = 2(reduced mod 5)
yeah
like 3+4 is not 6
midnight knot
numbers are congruent by some number iff their remainders after dividing by that number are the same
regal pivot
ok
midnight knot
i guess you can say that 3 = 24%7
because 3=3
but its the same as saying that 24=3 (mod 7)
inner crest
yes, but a ≡ b (mod m) is not the same as b = a%m, because we cannot establish a biconditional between them...
midnight knot
you are right, if you interpret it that way as you did
regal pivot
a=2 and b=3 and m=5 then both are not equal in this case
inner crest
both are not true in that case
midnight knot
% is maybe useful for programing
sterile pumiceBOT
cybergnostic:
grizzled badge
Is (a,b)*<a,b> = ab common knowledge?
Like can I use it in a proof without proving it beforehand?
midnight knot
I think yes, but the proof is elementary anyway
grizzled badge
No I know how to prove it
midnight knot
oh
midnight knot
oh thats my problem always
or like, they always say in books, "follows from lema 4.3.251"
like fk u
fathom sierra
Theorem 5 : \textit{states theorem 5} $\Box$
sterile pumiceBOT
emeric75:
midnight knot
LOL
or like this one
so I got to prove ix on exam
and i proved it
and she asked me
why didn't you prove the ones you need for ix???
but yeah for gcd * lcm you need divisibility theorem, bezuot's theorem and FTA
hazy thistle
how would you go about proving that if the number of divisors of n is n/2 then n must be 8 or 12? After a lot of not getting anywhere (other than proving it's true with a python program but that's not a proof) i went to my two research supervisors and they stared at it for at least 20 min and didn't have any ideas and decided i should deal with it after the meeting and their only word of advice was "think like an analyst not an algebraist" and when I asked if they had some more specific advice i was told they're algebraist not analysts :p
light flicker
@hazy thistle there are some upper bounds of the divisor function, do any of those work?
supple furnace
@light flicker if you’re interested, you can try proving log(d(n))/log(n)=o(1) if you haven’t done it before.
light flicker
I've definitely seen that before, don't think I've looked at any proof
hazy thistle
@midnight knot sorry I missed your message, just woke up!
broken igloo
Hmm, should be pretty simple, given a number n, we have at most n/3 divisors from 1 to n/3 + 2 divisors (n/2 and n).
That gives at most n/3+2 divisors. Hence n/3+2 >= n/2, which gives 12>=n really directly
@hazy thistle
hazy thistle
Thanks!
sterile pumiceBOT
rudy:
sterile pumiceBOT
rudy:
sacred junco
How do I prove these?
Hints?
We know these are special cases of:
$ F_{m+n-1} = F_mF_n + F_{m-1}F{n-1}$
sterile pumiceBOT
rudy:
inner crest
1st one set m=n
sacred junco
m isn’t even existent on the first...?
inner crest
for the 1st one, set m=n in your general formula
broken igloo
Well, probably some combinatorics methods also work
$F_n$ is the number of length n-2 binary strings without adjacent 1s, I think.
So, $F_{m+n-1}=$ number of length m+n-3 binary strings...
Okay, split the string into (m-2) (1) (n-2) characters. If the single character is a 0, first case, $F_mF_n$, If it is 1, adjacent is 0, so second case, $F_{n-1}F_{m-1}$.
sterile pumiceBOT
Element118:
broken igloo
There, combinatorics.
light flicker
Maybe sending the whole problem would help
But this is a pretty standard identity, probably easier for you to just Google it
inner crest
cool sum of 2 consecutive triangular numbers, that's a neat little intuitive thing
ivory patrol
How’s it intuitive?
sacred junco
Imagine two consecutive triangular numbers, you can jam them together to form a square.
Not repeat this to make a "square pyramid"
There's your intuition.
ivory patrol
Oh dang that’s pretty cool
inner crest
now that I think about it, not that cool since you can just do\
$\sum_{k=1}^n\frac{k(k+1)}2+\sum_{k=1}^n\frac{k(k-1)}2$
sterile pumiceBOT
EpicGuy4227:
sacred junco
Whats the difference between p-adic numbers and ring integers modulo Z_n?
Oh, apparently everything.
Mfw, I’m just dumb. My bad. The wikipedia made it seem as if they were related
I have a question. One of my classes said that:
$(\mathbb {Z} /n\mathbb {Z} )^{\times }$
sterile pumiceBOT
rudy:
sacred junco
My teacher said it doesn’t
light flicker
Usually this group only consists of the elements coprime to n
sacred junco
He said I can “take it” like that, but its not true
sacred junco
@light flicker hey
Do you know if rings can have subtraction?
Or would that mean its a field?
quick furnace
all rings have subtraction
it's in the axioms
for every element x there's an element -x that when added to x gives 0
sacred junco
Oh, ok— its just wikipedia says addition and subtraction .:.
sacred junco
Oops. I mean, addition and multiplication.
quick furnace
yeah
sacred junco
It doesnt really state subtraction as a point, so I was wondering
quick furnace
i mean yeah subtraction is not a primary operation
sacred junco
I know division makes it a field— isn’t division just repeated subtraction?
quick furnace
no, division is not repeated subtraction, and multiplication is not repeated addition
quick furnace
i mean like
division is just multiplication by the inverse
- and * are two different operations linked together by the distributive law, with each one also obeying its own set of axioms
sacred junco
I see. I get it, thank you.
sacred junco
Can someone solve this with LTE?
Show that a^n-b^n has a prime divisor that isn't a divisor of a-b
light flicker
Why do you want to do it with LTE? @sacred junco
It's just easy to factor a^n - b^n and look at the factorization
light flicker
you really shouldn't restrict yourself to just one tool
What's the saying
"if all you have is a hammer, everything looks like a nail"
sacred junco
Yes of course but trying to get used to thr idea
Because a lot of problems are way easier
With LTE
light flicker
well this one isn't
versed storm
you can solve it with LTE
sacred junco
gcd(a,b)+ ab/gcd(a,b) = a + b + 6
@light flicker any idea how you would tackle?
For only positive numbers
ivory patrol
Let gcd(a,b) = d, a=dx and b=dy. Then we have d + d^2xy/d = dx + dy + 6. Simplifying, d + dxy = dx + dy + 6, so d(1 + xy - x - y) = 6. We split into factor pairs:
d=1, xy - x - y + 1 = 6. (x-1)(y-1) = 6, so (x,y) = (7,2), (4,3), (3,4), (2,7).
d=2, xy - x - y + 1 = 3. (x,y) = (2,4), (4,2). (These don’t work since 2 and 4 aren’t coprime.)
d=3, xy - x - y + 1 = 2. (x,y) = (2,3), (3,2).
d=6, xy - x - y + 1 = 1. (x,y) = (2,2). (These also don’t work.)
Now just scale (x,y) by the respective value of d to get (a,b)
sacred junco
@ivory patrol awesome— thanks!
I can see quite a few pairs though, such as: (6,9), (9,6)
Damn
ivory patrol
No problem 😛 let me know if you need help with any other NT exercises!
cosmic shale
since P is a p-1 degree polynomial, and we know p-1 of its roots (the p-1 nonzero elements) then we know all of its roots and can factor it into that product
i didnt answer the question did i
sorry
sacred junco
Aren't its roots the roots of unity not that it makes sense in mod p :/
cosmic shale
we're in integers??
light flicker
@sacred junco you're right in thinking that doesn't make sense mod p
You see why every element is a root of that polynomial right
sacred junco
Putting x equals to 1 2 and so on till p-1 makes it 0 in mod p for both sides ?
Except well they put x=0 for the last part :/
sacred junco
Hmm I guess that makes sense
ivory patrol
What theorem is that? @sacred junco
light flicker
@ivory patrol Wilson's theorem
sacred junco
Yeh
sacred junco
Oh! I am meant to prove Wilson’s in class lol
It seems to be rather direct, hm
(n-1)! = -1 mod n
light flicker
How do you do it directly
ivory patrol
There's a much easier way to prove Wilson's theorem by simply grouping every number with its multiplicative inverse
Since you know that in mod p, the only two numbers who are their own inverses are 1 and p-1, and every other number always has a unique inverse
wild zinc
just prove it by exhaustion
cursive thicket
why do the second and third equalities here work
$1-2^{k+1}\zeta(-k) =$ \
$ \big(t +2^k t^2 + 3^k t^3 + \dots \big)|{t=1} -2\big(2^k t + 4^k t^2 + 6^k t^3 + \dots\big)|{t=1}$ \
$= t - 2^k t^2 + 3^k t^3 - 4^k t^4 \dots$ \
$= (t ; \frac{d}{dt})^k \big({t-t^2+t^3-t^4 + \dots}\big) = (t ; \frac{d}{dt})^k \bigg{\dfrac{t}{1-t}\bigg}\bigg|_{t=1}$
$$
\zeta(2m) = \dfrac{(-1)^m (2\pi)^{2m}}{2(2m-1)!} \zeta(1-2m)
$$
$$
\zeta(2m)= (1-2^{2m})^{-1} \dfrac{(-1)^m(2\pi)^{2m}}{2(2m-1)!}\zeta(1-2m) \bigg(t \dfrac{d}{dt}\bigg)^k\bigg{\dfrac{t}{1-t}\bigg} \bigg|_{t=1}
$$
sterile pumiceBOT
flimflam:
autumn dune
the second one doesnt, but the third does
versed storm
Just use maths
craggy plume
Prove or disprove: there are infinitely many positive integers (x, y, z) such that x^2 + y^2 = z^2 - 7
Can anybody help with this?
versed storm
Pythagoras
craggy plume
It's not pythagoras :(
quick furnace
consider considering the equation mod 4
craggy plume
@quick furnace Did that. Didn't help much.
quick furnace
did it not?
what'd you get
from what i can tell, you can get that both sides must be 2 mod 4
craggy plume
Either "all of x, y, and z are odd", or "z is even, and the parity of x and y are different"
craggy plume
And?
(I tried brute-forcing up to z=100, and there are both cases where z is even and cases where z is odd.)
Oh, another thing I tried: I tried brute-forcing to count the number of solutions mod m, for m=1...100. For some reason, the number of solutions mod m is always divisible by m.
And then I'm stuck. I suspect this requires something something gaussian integers.
Oh. And another thing I tried: I googled and found this page. https://math.stackexchange.com/questions/351491/integral-solutions-of-hyperboloid-x2y2-z2-1?fbclid=IwAR1sDF0p03z7Uyf2Q78_vL6-tsRtCZZ3BklXIJLiqgVLUzraleIP-jLL7SE
Couldn't figure out how that helps though.
sharp pagoda
z²-7 or z²+7
sharp pagoda
Try $ (2k,2k^2+3,2k^2+4)$
sterile pumiceBOT
Nick (Far From Home):
craggy plume
Oh yeah. That's a solution for the z^2+7 case. Doesn't seem to help with the z^2-7 case though.
sharp pagoda
,w (2k)^2+(2k^2+3)^2-(2k^2+4)^2
sterile pumiceBOT
Requested by Nick (Far From Home)#3263
sharp pagoda
,w (2k+1)^2+(k^2+k+1)^2-(k^2+k+3)^2
sterile pumiceBOT
Requested by Nick (Far From Home)#3263
sharp pagoda
$ (2k,2k^2+3,2k^2+4)\(2k+1,k^2+k+1,k^2+k+3)$
sterile pumiceBOT
Nick (Far From Home):
craggy plume
Oh. I somehow miscalculated.
Thanks .
@sharp pagoda
Now to figure out whether these are all the solutions.
How did you find these though?
At the very least these two don't cover the solutions (9, 9, 13), (11, 14, 18), and (13, 20, 24), among others.
There's also (28, 53, 60).
sharp pagoda
these maybe not all solutions but it answers if there are infinitely many or not
craggy plume
Oh. You can just set z=y+1, and then solve the thing.
And set z=y+2 and then solve the thing.
I think I have an idea of how to continue what I was doing now.
empty pecan
for $k_1 < k_2 < ... < k_n \in \mathbb{N}$\
prove that $\frac{\prod_{1 \le i < j \le n}(k_j - k_i)}{\prod_{1 \le i < j \le n}(j - i)} \in \mathbb{N}$
sterile pumiceBOT
Nguyễn Thành Trung:
empty pecan
any idea for this problem
I've posted it in art of problem solving but haven't got a solution yet
brittle sparrow
I don't think that's true?
oh wait nvm
You can try to show that $$\nu_p\left(\prod_{1\le i<j\le n}(j-i)\right) =\sum_{x=1}^{n-1}\sum_{k=1}^{\infty}\left\lfloor \frac{x}{p^k}\right\rfloor \le \nu_p\left(\prod_{1\le i<j\le n}(k_j-k_i)\right)=\sum_{1\le i<j\le n}\nu_p(k_j-k_i)$$
sterile pumiceBOT
daddy Kevin:
brittle sparrow
$$\sum_{x=1}^{n-1}\sum_{k=1}^{\infty}\left\lfloor\frac{x}{p^k}\right\rfloor \le \sum_{1\le i<j\le n} \nu_p(k_j-k_i)$$
sterile pumiceBOT
daddy Kevin:
brittle sparrow
Also WLOG, assume k_0 = 0
For $p=2$, I have $$\sum_{x=1}^{n-1}\sum_{k=1}^{\infty}\left\lfloor\frac{x}{2^k}\right\rfloor \le \sum_{x=1}^{n-1}x=\frac{n(n-1)}{2}$$
sterile pumiceBOT
daddy Kevin:
brittle sparrow
Also for a minimal choice of $k_i$, if $a_i$ represents the minimal increment of $$\sum_{1\le i<j\le n}\nu_2(k_j-k_i)$$, then I think $${a_1,a_2,\cdots}={0,0,1,3,4,6,7,9,10,\cdots}$$
sterile pumiceBOT
daddy Kevin:
brittle sparrow
so at some value $N_0$, the condition holds for all $n>N_0$, so it would remain to show that the condition holds for $n\le N_0$ as well
sterile pumiceBOT
daddy Kevin:
empty pecan
this's solution is too hard for me to read
broken igloo
hmm...
The main idea of $\nu_p$ is you are counting the number of times p is a prime factor of that thing.
sterile pumiceBOT
Element118:
broken igloo
So, far you do understand that @empty pecan
empty pecan
can you give ma an example
broken igloo
Hmm, $\nu_3(162)=4$, since $3^4$ divides 162.
sterile pumiceBOT
Element118:
broken igloo
Firstly, we want to calculate $\nu_p(n!)=\sum_{i=1}\left\lfloor\frac{n}{p^i}\right\rfloor$.
sterile pumiceBOT
Element118:
broken igloo
Do you get this?
broken igloo
Okay
Let's consider the numbers in n! that are divisible by p
We have p, 2p, 3p, 4p, all the way to floor(n/p)*p
Those contribute one factor of p
Consider the numbers in n! that are divisible by p^2
We have p^2, 2p^2, 3p^2, 4p^2, all the way to floor(n/p^2)*p^2
Those contribute another factor of p.
Consider the numbers in n! that are divisible by p^3
We have p^3, 2p^3, 3p^3, 4p^3, all the way to floor(n/p^3)*p^3
Those contribute another factor of p.
...and so on.
broken igloo
Do you understand this argument?
empty pecan
I understand the formula
but
"Let's consider the numbers in n! that are divisible by p
We have p, 2p, 3p, 4p, all the way to floor(n/p)*p
Those contribute one factor of p
Consider the numbers in n! that are divisible by p^2
We have p^2, 2p^2, 3p^2, 4p^2, all the way to floor(n/p^2)*p^2
Those contribute another factor of p.
Consider the numbers in n! that are divisible by p^3
We have p^3, 2p^3, 3p^3, 4p^3, all the way to floor(n/p^3)*p^3
Those contribute another factor of p.
...and so on."
I don't get anything from this one
sterile pumiceBOT
Element118:
broken igloo
Do you understand this part?
empty pecan
you mean
broken igloo
How to minimise this?
broken igloo
Yes.
empty pecan
why
broken igloo
Because if we minimise this, then it pushes us towards the equality case
It should push us to the equality case.
and we get more conditions
that would help us
broken igloo
Consider how $k_i$ are distributed mod p
sterile pumiceBOT
Element118:
broken igloo
So, it depends on how many $k_i\equiv j \pmod{p}$ for each j.
sterile pumiceBOT
Element118:
broken igloo
If a lot of $k_i$ are congruent mod p, this gives us a high $\nu_p$.
sterile pumiceBOT
Element118:
empty pecan
uh hu
broken igloo
so the way to minimise this is to spread out the $k_i$ mod p
sterile pumiceBOT
Element118:
broken igloo
The same argument can be made for $p^2, p^3...$ and so on.
sterile pumiceBOT
Element118:
broken igloo
Now, do you get the idea to finish off the proof?
broken igloo
Okay, what is the minimum number of $k_i-k_j$ that is divisible by $p$ (in terms of n and p)?
sterile pumiceBOT
Element118:
broken igloo
okay, so far, what did you understand?
Okay, what is the minimum number of $k_i-k_j$ that is divisible by $p^m$ (in terms of n, p, m)?
sterile pumiceBOT
Element118:
broken igloo
Find all those and add up, and you should be done with the question.
empty pecan
hm...
I think that
i need to time
time to
grab all things that you do
I'll ask if I need
thank youd 😃
undone bridge
question i thought of and i'm not sure if there's a nice solution:
for which positive integers x,y does x+y | x^2+y^2?
drifting kelp
stuck lintel
You can try this approach:
first, assume (x,y) = 1. Then since $(x,x^2+y^2) = (x,y^2) = 1$, then $(x+y)\nmid (x^2 + y^2)$. So now let's say (x,y) = d, and let x = ad and y = bd. Then we know $\frac{d^2(a^2+b^2)}{d(a+b)} = \frac{d(a^2+b^2)}{a+b} \in \mathbb{Z}$. But like we just proved, since a and b are coprime, $a+b\nmid a^2+b^2$, so a+b has to be a multiple of d
sterile pumiceBOT
Plum:
undone bridge
when you assumed (x,y)=1, how did you get that x+y does not divide x^2+y^2? how did you get from (x,x^2+y^2)=1 to that?
stuck lintel
Since (x,x^2+y^2)=1 and (x,x+y) = 1, then (x^2+y^2, x+y) = 1 so x+y is not a factor of x^2+y^2
undone bridge
ah i see now thanks
stuck lintel
np
stuck lintel
Oops thanks for the catch
naive trail
"Since (x,x^2+y^2)=1 and (x,x+y) = 1, then (x^2+y^2, x+y) = 1 so x+y is not a factor of x^2+y^2" -- why exactly? What happens for x=y=1?
stuck lintel
(1,1) is never ruled out by a coprimality argument so you just have to check it as a separate case (but I was too lazy to include it)
naive trail
And how does the argument go? Clearly one can't say "(A,B)=1 and (A, C)=1, hence (B, C)=1" for general A,B,C specialized to A=x, B=x^2+y^2, C=x+y. What is used?
broken igloo
any more context?
twilit rivet
So I have to do a project on Number Theory and I'm majoring in applied statistics. Is there any topics in number theory that doesn't require so much background knowledge that anyone could recommend me doing? Maybe ones that are related to statistics or use computational stuff would be cool for me. Thanks
light flicker
The first thing that comes to mind would be the prime number theorem
You could do some computational stuff to create some graphs to support it
If you go to https://en.wikipedia.org/wiki/Prime_number_theorem
And go to the section about arithmetic progressions
They talk about something called the prime race, which was a conjecture that was disproven for a pretty large value
@twilit rivet
twilit rivet
Cool I'll check it out thanks
broken igloo
This might be interesting too
It says that the prime numbers mod n are evenly distributed among all remainders coprime to n.
twilit rivet
thanks!
craggy solstice
For coprime integers $a$ and b there exists infinitely many primes in the form a + nb where n is a positive arbitrary integer
sterile pumiceBOT
Lionel:
craggy solstice
nope just showed him👍
fervent crest
I read in a book that says there are infinitely primes congruent to 1 and 3 modulo 4
So the dirichlet theorem is kind of the extension of this right?
autumn dune
yeah
fervent crest
Damn how tf did he prove this
opal orbit
Not really, it could be that they all are 1 modulo 4 (obviously not, but you'd need to show that)
sharp pagoda
true
opal orbit
You could just go through 6n+-1 for simplicity to show that though
wide shuttle
^
fervent crest
Um
I know how to prove the 1 or 3 modulo 4 case
That’s simple ik
But how tf do you prove dirichlet theorem
opal orbit
I wasn't suggesting that to you
sacred junco
lol
apparently they showed the proof to black MOP
and they didn't even understand the prereq
grave bough
A number is considered a bad prime when the sum of its digits is a prime (Example: 131.) Show whether $2^k+2$ will generate an infinite amount of bad prime, or finite amount of bad prime.
sterile pumiceBOT
xpoes:
opal orbit
$2^k+2$ won't give you any primes
sterile pumiceBOT
Ꞡꭍî╥(│-│ḛƉ քîҳӘꭍş:
grave bough
Yeah I know, but that's not what the question is asking
opal orbit
Finite then.
grave bough
how?
opal orbit
Oh wait, the original doesn't have to be prime sorry
sacred junco
fuck i've been exposed
silk vine
So uhhh. I already know how to find the parametric formulas that give you the answers to linear diophantine equations with two variables one.
I've seen the proof and all that.
So uhhh
First of all, I've been thinking about how can you solve it for three variables?
And then generalize it for n variables.
sacred junco
the general case is very similar
sacred junco
Bernstein, a known mathematician