True, that’s much easier
#elementary-number-theory
fervent crest
storm sinew
yeah thats how i solved it when i figured out eulers theorem wouldnt work
how about this one tho? 6 isnt coprime with 1000, and i dont think its possible to spot a pattern here since its the last 3 digits and not 1??
seem to struggle with these problems lol
fervent crest
There will be a pattern, but it’s very likely to be very long
storm sinew
yeah^
fervent crest
So in this case you can use what I said above
But with different numbers
Or you can just brute force and use repeated squaring
storm sinew
lol ill stick to the first thing u said above xD
torn escarp
I thought you were trolling but didn't read that it said last 3 digits this time lol
fervent crest
Lol
storm sinew
lol im frfr, really struggle with these problems
would it help splitting 1000 into 2^3 * 5^3?
then 6^600mod2 would be 0
would i still need to combine them with chinese remainder theorem at the end? even tho 6^600mod2 would be 0?
torn escarp
don't forget now 6 and 5 are relatively prime
fervent crest
Nice
near frigate
these exercises (3 & 4) were trying to get me to verify the sum of the first n natural numbers, not derive it, right?
torn escarp
yeah, I'd say so
near frigate
on 4, setting a_n to n(n+1)/2 is only valid since theyre both "nth terms" right?
near frigate
oh, i was under the impression that the a_n from ex4 was the same as the one from ex3
raven carbon
So I'm not taking this (a friend showed it to me) but there has to be a quick number theory solution to this right?
fervent crest
It’s a very typical probability problem
I don’t quite see a quick number theory solution, but I do see a quick solution
raven carbon
Hmm ok, What is it?
fervent crest
So you can calculate it using complement. P(product is even) = P(one of the dice is even) = 1-P(all the dice are odd) = 1-(1/2)^3=7/8
harsh mirage
That seems too quick; the product must not only be even, but the square of an even number
e.g. 1,1,6 would not be valid, even though one of the dice is even
harsh mirage
I think I've got at least an approach for a solution though, even though that still takes some time
harsh mirage
Find all the even number squares which can be gotten by the product of the three dice
So, we look at 4 = 2², 16 = 4², ... , until 196 = 14²
The largest number you could get from three dice is 6³ = 216, so you definitely don't need to go higher than these numbers
raven carbon
yeah but then you need to get the PMF weight contributions of each
harsh mirage
Yeah, but we can reduce it even further
raven carbon
Or do we necessarily fix one of the 3 dice to be 1
harsh mirage
Namely, look at the prime number decomposition of these squares, and see if there is a way to write this number as the product of three numbers from 1 to 6
raven carbon
what about 2 2 4
harsh mirage
e.g. 100 = 10² = 2 * 5 * 2 * 5 can be gotten via 4 * 5 * 5
bby maybe the questions clear up if you let me finish
raven carbon
well ofc, but there are many ways to obtain these factorings and not all are equally likely
harsh mirage
Yeeah, there's not suuuper many at least
raven carbon
kk mb
harsh mirage
Actually
sacred junco
That's not a bad suggestion, consider all squares up to 6^3
harsh mirage
Hm, I thought you could exclude 144 and 196 but maybe you can't
sacred junco
There aren't many
harsh mirage
So, 4 = 2 * 2 * 1 = 4 * 1, 16 = 4 * 4 * 1 = 4 * 2 * 2, ...
raven carbon
You can't
harsh mirage
196 you can, though! Because it needs a 7 somewhere, which you can't have
So the largest square you need is 144 it seems, which you can get from 12 * 12 = 4 * 6 * 6
So I think every square gives you one or two decompositions at max
So at the end you get 12 or so decompositions, and then, yeah, you still need the probability distribution, but I think that's somewhat feasible still
Because it boils down to questions like "how many different ways are there to get 2 * 1 * 1", which are quick to calculate
raven carbon
harsh mirage
now it is still completely possible that i'm a foooool and there's a big-brain way that i'm not seeing
sacred junco
Bruuh don't
harsh mirage
Does that include 7 or not?
sacred junco
What do you think
harsh mirage
i hope that it doesn't but then it's a strange syntax imho
but i'm not a python big brain
raven carbon
No
raven carbon
this is how I saw it and it just seemed infeasible especially without error
harsh mirage
So up to permutation there's not that many
Yeah I definitely see what you mean, you're gonna have to be really careful with this solution, but I'd be really surprised if a casual math-person had a better one off the top of their head
they probably just want to check if you're really careful at calculating lol
raven carbon
We can all agree that for a 30 question 1 hour test this is a little silly right
raven carbon
Its 6^3 +31 I guess
raven carbon
216 + 31 would be the answer
raven carbon
It's for a quant internship
I assumed there had to be a fast NT way because of the context of the test
Guess it's just dumb
harsh mirage
Hm, nah, there's still the option that I am (or we are) dumb, too
harsh mirage
I'm thinking there might also be a better way to think about the prime factorization of an even square
sacred junco
I mean the possible squares are not many
raven carbon
I think they explicitly don't allow coding
sacred junco
Oh i see
hollow basalt
By a quick calculation I got 61/6^3, not 31, but I might have doublecounted something.
harsh mirage
oh yeah, wait, (2m)² = 4* m², so the only way you can get this as a product of three numbers between 1 and 6 is if you write it as : 4 m² = 4 * m * m, 4 * m² * 1 or 2 * 2 * m²
sacred junco
216 + 31 would be the answer
hollow basalt
sketch:
square of even => even number of factors of 2.
each die contributes at most 2 factors. only a 4 contributes 2 factors, 2,6 contribute 1 factor, the odds contribute 0.
2,2,2 1 possibility
2,2,0 9 possibilities
2,1,1 12 possibilities
2,0,0 27 possibilities
1,1,0 12 possibilities
So answer is 61/6^3
error somewhere there if 31 is indeed the correct number of favourable outcomes.
oh wait yes am overcounting
odd prime factors must also occur with even exponents, so these possibilities can be culled considerably, and probably in a clever way.
raven carbon
Same
harsh mirage
yeeee okay this is smert
hollow basalt
yeah it is easy to tweak my counting method above actually.
harsh mirage
okay yeah my 4mm, 4m²1 and 22m² splitting was a bit too simple because there's also products like 236 that are not of this shape, because factors of 2 can be distributed to the m's
it was a plebeian attempt at what gomez did better
i suppose the best way to be prepared for questions like this, is to already have seen them, so hooray for my future job interviews
near frigate
possibly dumb question but:
if i have a set C = {1, k, k+1} (k is a positive integer) this set contains all natural numbers, so can i claim C ⊆ Z^+?
trim gust
umm it has 3 natural numbers not all
even if it has 3 or all natural numbers you can still use that notation
near frigate
i didnt describe C well enough then, i got that definition by reading the first form of mathematical induction
runic vector
sacred junco
Fermat Little Theorem will help
sacred junco
Solve in IN
fervent crest
Try to factor it
trim gust
@sacred junco the equation is equivalent to: (2x-1)(2y+3)=15, so go through factors of 15, keeping in mind that it can be negative too
although you didnt say what number system, it seems like integers
(i multiplied both sides by 2 in order to factorize)
fervent crest
He said solve it in N
trim gust
oh yea i thought he just said "solve in", but he actually said "solve in IN"
just note IN should be written as either Z or N, depending on what u want
sacred junco
thanks !
last grove
sacred junco
p³- 4p + 9 = n².
( n, p ) ∈ Z.
for p = prime.
help me , please!
sacred junco
how ?
fervent crest
I don't think that'll help here
Ok well the only process I could make was factoring it as (p-2)p(p+2)=(n-3)(n+3)
sacred junco
I made the same progress
fathom pike
Would the solutions be limited to the combinations of the roots?
sacred junco
rrt is for polynomials in one variable
fervent crest
Huh is p prime here? @sacred junco
sacred junco
@fervent crest yes, sorry....
fervent crest
Oh ok
So for the start, we can see that p=2 gives two solutions n=±3
And then you can assume p is odd, then the LHS of (p-2)p(p+2)=(n-3)(n+3) is odd, so the RHS is also odd which implies that n is even
If p odd then one of (p-2)p(p+2) is divisible by 3, so n-3 or n+3 is divisible by three, and in either case n is divisible by 3
If n is divisible by 3 then (n-3)(n+3) is divisible by 9. There are a few ways (p-2)p(p+2) can be a multiple of 9: either two factors in the product is divisible by 3 or from a single factor in the product is divisible by 9. If p is divisible by 3 then neither p-2 nor p+2 are divisible by 3; also p-2 and p+2 cannot be both be divisible by 3. This shows that either p-2 is divisible by 9 or p+2 is divisible by 9
Hmm now it's probably case work, but I don't see how to continue
Maybe writing p±2=9k, n=6m
swift shard
I wrote up a solver and have some bad news. Looking for p, n between 1 to 1000, I found two new solutions:
p = 7, n = 18
p = 11, n = 36
sacred junco
I have some good news related to that
there are no more solutions from 1 to 1 million
so that may be all of them
swift shard
Whew that must have taken a while to run
sacred junco
my algorithm was very naive so it kinda did but it could have been a lot faster with a little more work
swift shard
Nvm I just coded it dumb. Rearranged and I could do it much faster
sacred junco
me too lol
fervent crest
Those two are probably the only solutions then
sacred junco
maybe a root jumping argument could show that there are no solutions for p>11
if it's even true
ah wait I think I found a bigger solution
never mind, I think it is just my algorithm breaking down for large numbers at the cost of speed
ok how about p=29310727 and n=158686465026
p=55344437 and n=411728529152
i give up
So for the start, we can see that p=2 gives two solutions n=±3
@fervent crest thank you!
thanks @sacred junco
fervent crest
,calc 29310727^3-4*29310727+9-158686465026^2
sterile pumiceBOT
Result:
4.194304e+6
,calc 55344437^3-4*55344437+9-411728529152^2
sterile pumiceBOT
Result:
0
fervent crest
,calc isPrime(55344437)
sterile pumiceBOT
Result:
true
fervent crest
@sacred junco
Neither work
Probably floating point problems
@sacred junco also @swift shard gave two solutions
p = 7, n = 18
p = 11, n = 36
sacred junco
yes
yea in hindsight I don't know why I put my faith into google calculator for verification
I gave up and googled it
https://math.stackexchange.com/questions/1580363/find-all-primes-p-such-that-p3-4p9-is-a-perfect-square here is a solution
swift shard
That question is nuts haha
sacred junco
the bottom solution in that link is almost a carbon copy of the solution in the first link
empty yew
p³- 4p + 9 = n².
( n, p ) ∈ Z.
for p = prime.
a math channel posted a video about this problem literally today, oof
can I link it?
upbeat wren
p^k + m^2 = n^2. Where m, n, p are in the integers and k is a whole number > 3 and p is a “positive” prime not equal to 2. Find n in terms of p if p does not divide n.
patent oak
Are there integer x>2 such that, for any n, x^n-1 can't be prime?
trim gust
this is easily refuted by fermats little theorem
fervent crest
$x^n-1=(x-1)(x^{n-1}+\cdots+1)$, so if $x>2$ and $n>1$ then $x^n-1$ is never prime
sterile pumiceBOT
Whoever:
fervent crest
@trim gust @patent oak
trim gust
that also works
patent oak
okay, should have seen that, I was looking for big factors
going beyond these factors, the answer is clear if n is not prime via
torn escarp
or if n is not prime, then there's a divisor d
$x^n -1 = (x^{n/d})^d-1 = (x^{n/d}-1) (x^{n/d -1} + \cdots + 1)$
sterile pumiceBOT
Merosity:
trim gust
how is this observation relevant
torn escarp
Nikolaj just gave that the answer is clear if n is not prime
I just gave an alternative for when n is not prime using the previous argument
since I think using cyclotomic polynomials seems weird, but I really didn't get the whole discussion so maybe I missed something, didn't give it too much thought here lol
trim gust
ok, it's just that this is a case in what Whoever put
torn escarp
that's what I meant when I said using the previous argument
Nikolaj's comment seemed to imply that it only worked for primes, but he seemed really backwards from the very start
so him using cyclotomic polynomials to show for n composite seemed further misguided
lol
torn escarp
how is this observation relevant
trim gust
jovial hemlock
I believe that if AX = BX mod CX, then A = B mod C. Is this correct? If so, how can I show it?
For example, 21 = 9 mod 12, so 7 = 3 mod 4
torn escarp
you can look at it as saying AX-BX = 0 mod CX then that means AX-BX | CX
in other words there's some integer N such that (AX-BX)*N = CX
stuck lintel
Did you mean CX | AX-BX?
fervent crest
assuming X≠0
stoic bear
I work in wheels
torn escarp
smh the X=0 case is trivial to handle please no wheelies
the X=0 case you go directly to jail, do not pass go
upbeat wren
p^k + m^2 = n^2. Where m, n, p are in the integers and k is a whole number > 3 and p is a “positive” prime not equal to 2. Find n in terms of p if p does not divide n.
Spoilers:
||Note: p^k = n^2 - m^2
p is positive and thus n^2 - m^2 is positive. Just saying.
p^k = (n + m)(n - m). p must divide (n+m) or (n-m) or both.
Case 1: Both: p divides both so p divides the sum of n + m and n - m. p divides 2n. p is not 2. p divides n. Ouchies. Sword fight.
Case The Rest: p divides only one of the two.
p either only divides n + m or only divides n - m. But, the ony way two factors multiply to p^k (correction here was: "p^k" instead of "p") where one is NOT a multiple of p is if the factors are 1, p^k or -1, -p^k.
Let K = n + m and J = n - m. Note that n = (K + J)/2
K = 1 and J = p^k gives us n = (1 + p^k)/2. K = p^k and J = 1 gives us n = (1 + p^k)/2
K = -1 and J = -p^k gives us n = -(1 + p^k)/2. K = p^k and J = 1 gives us n = -(1 + p^k)/2
Thus, n = (1 + p^k)/2 or n = -(1 + p^k)/2.||
trim gust
Okay good I was right
umm this is literallly a rule in modular arithmetic: you can divide both sides by n, but then also divide the modulus by gcd of the modulo and n
that is a benefit of primes is that you gcd is always 1, unless a mulitple of it
sacred junco
i can factor this?
serene mesa
I can’t see any useful way to factor it. I guess it could be useful to rewrite this as $y(x+y+z)=xz$ if it’s a number theory problem
sterile pumiceBOT
willrum:
sacred junco
Show that $a²-a ≤ a⁴-a³$. Please provide a rigorous proof with explanation.
sterile pumiceBOT
235711131719232931:
torn escarp
what have you tried so far
abstract flax
helped in #prealg-and-algebra
torn escarp
thanks
sacred junco
helped in #prealg-and-algebra
👍
amber osprey
can there exist a composite x which satisfies a^(x-1)=1 mod x for all a just like a prime
i havent thought about it so if i miss something super trivial sorry
fervent crest
These are called carmichael numbers,
You can't have a^(x-1)=1 mod x for all a, even if x is prime you still have to assume that a and x are relatively prime
amber osprey
yes yes sorry for not mentioning
fervent crest
Yeah so a number x is a carmichael numbers if a^(x-1)=1 (mod x) for all a relatively prime to x
The smallest one is 561
amber osprey
very nice
i was seeing the rabin miller test
and they use the fermats little theorem to check for large primes
so i got this question
atomic sable
Why does solving the positional notation expansion of a number of any base always result in its base-10/decimal equaivalent?
For instance:
or
Why does this expansion always solves to decimal form?
torn escarp
it's the same number, so it is the same, it just happens that for every calculator you've used it writes it in base 10 since that's what most people use
atomic sable
I know its the same number but in decimal. But why does that expanded form always result in decimal? That's what im asking
torn escarp
because your calculator does it that way
torn escarp
you're asking about "something" that "always result in decimal"
that "something" is your calculator
atomic sable
Sorry, let me rephrase my question. Why does this expansion form give you the decimal equivalent
?
atomic sable
Ok
torn escarp
11 in base 2, and 10 in base 3
and of course it's 3 in base 10
using the example I've given can you ask your question?
torn escarp
"Why does this expansion form give you the decimal equivalent"
what a number is doesn't depend on what base you represent it in
atomic sable
What do you mean by what a number is?
torn escarp
if I give you three stones
atomic sable
ok
torn escarp
then that's three, there's nothing there that depends on base 2, base 3, or base 10 or any other bsae
torn escarp
a base is just a way of writing down a number so we don't have to write down three tally marks
atomic sable
understood
but why does expanding 345 subcript 8 give you base 10 rather than its base 2 or base 3 etc?
torn escarp
it doesn't
atomic sable
why does this form always give you base 10 rather than any other base
torn escarp
what you're saying is false
atomic sable
how so?
torn escarp
345_8 is just a base 8 representation of that number
"this form always give you base 10 "
what's doing the giving here?
the form is fine how it is just sitting there
there's nothing there to "give you base 10"
atomic sable
I meant why does performing this operation gives you the decimal of that number?
torn escarp
I think you're so used to using base 10 to do calculations you have some kind of misconception
that's because you're converting it to base 10
you could convert it to base 2 by writing it differently, I'll show you if you like
atomic sable
yes, but my question is why does it convert it to base 10, rahter than any other base
oh you can?
torn escarp
yeah
torn escarp
when you write 8 in base 8 you're in base 10
eight is 10 in base eight
eight is 1000 in base two
$(38^2)+(48^1)+(5*8^0)$
sterile pumiceBOT
Merosity:
torn escarp
this is base ten
if it was really written in base eight, you'd write 8 as 10
$(310^2)+(410^1)+(5*10^0)$
sterile pumiceBOT
Merosity:
atomic sable
ohhh, How about base 3
torn escarp
sure, more than one way we can try to do that
we can work entirely in base eight if you like since we're already here, that might be helpful
atomic sable
sure
torn escarp
to determine the smallest digit of 345 we have to divide by 3 and see what the remainder is
so you can walk thorugh the division in base eight like you would normally
atomic sable
So the reason why this form converts octal to decimal is because we are using decimal symbols in this form?
torn escarp
yeah
torn escarp
sure you're welcome
atomic sable
Wait, so using the same expansion, how do we convert 345 base 8 to its base 2 equivalent?
sterile pumiceBOT
Merosity:
torn escarp
this being the base 8 form, but since 8 = 2^3 then we replace 10 with 1000
and then replace 3, 4, 5 with what they are in base 2
$(111000^2)+(101000^1)+(101*1000^0)$
sterile pumiceBOT
Merosity:
atomic sable
but why are we using 10?
torn escarp
10 is b in base b
atomic sable
i thought we were converting base 8 to base 2
sterile pumiceBOT
Merosity:
torn escarp
this is base eight
because '10' is how you write eight in base eight
if you literally expand it out you get 300 + 40 + 5 = 345
that's the base eight number
here, type out how you count to twelve in base eight
torn escarp
perfect
atomic sable
Ahhh
torn escarp
ok so now because 10 is eight in base eight, if we want to convert to base two
what's eight in base two?
count to eight in base two now
atomic sable
0000, 0001, 0010, 0011, 0100, 0101
torn escarp
why are you typing it weird with leading 0s?
torn escarp
wrong, you missed a number
if a base 2 number ends in a 1, it's odd
you did 101 then 111
which are 5 and 7, you skipped six!
atomic sable
Oh
torn escarp
what's six look like
atomic sable
0110
torn escarp
nice ok we'll need these
to convert from base 8 to base 2
$(310^2)+(410^1)+(5*10^0)$
sterile pumiceBOT
Merosity:
atomic sable
uh huh
torn escarp
so 3 is 11, 4 is 100, 5 is 101
and 10 is 1000
the same rule for when you look at powers of ten works in other bases
because 10^3 in base 2 means 10*10*10
so you have 1000 is eight in base 2
but you also got it just by directly counting
so plug all that in and you get
$(111000^2)+(1001000^1)+(101*1000^0)$
sterile pumiceBOT
Merosity:
atomic sable
Oh crap
torn escarp
looks complicated but really isn't
atomic sable
That's the first time i've seen it written like that
torn escarp
11000000 + 100000 + 101
now you can just add these to get
110100101
uhh did I count that righ tlol
I think I put one too many zeroes
atomic sable
Ah i see why the teacher never taught it like that. Instead, he just groups the bits when going from base 2 <-> base 8 <-> 16
I think its because the way your sohwing me is a lot of work
torn escarp
yeah you can just concatenate them now
take base 8 digits 345 and write them as 0011, 0100, 0101
to get 1101000101
atomic sable
The only time in class we use the expanded form is when going from any base to decimal
torn escarp
most people are just more comfortable with base ten so that's why you just do things that way
atomic sable
So thank you! That puts everything into prespective
torn escarp
trying to do multiplication or division in a different base is confusing, like for instance 14 was twelve in base 8
your gut wants to tell you it's 2*7 but you memorized a bunch of base 10 specific rules in this sense
yeah you're welcome
atomic sable
Yeah, that's much more work.
torn escarp
well going between powers of a base is easy in general once you know the trick, just me walking through it slowly with you is not really how slow it goes
converting base 2 to base 8 and back is super quick and easier to do than converting between base 10 to base 2 and back
atomic sable
because 8 is a mutiple of 2 rather than 10, right?
torn escarp
yeah exactly
if you want to see an example of going from base 8 to 2 or 2 to 8 just make up a number and I'll just answer real fast
atomic sable
7345
torn escarp
1111 0101 0100 0101
I spaced them out so you see which digits map to which in their base 2 rep
,w convert 1111010101000101 from base 2 to base 8
sterile pumiceBOT
torn escarp
don't think it likedd the spaces
uh oh
I went to base 16 my bad, 7 is 111 not 1111
I added an extra 0 that didn't need to be there
111 101 100 101
atomic sable
Thanks for everything man, I think i'll be done for the day
torn escarp
this is what I should have written
atomic sable
I just had class so I'm worn out
torn escarp
,w convert 111101100101 from base 2 to base 8
atomic sable
@torn escarp How did you get this understanding of bases?
torn escarp
I guess I picked up mostly while learning about the p-adics which essentially forces you to work in base p
atomic sable
i have no idea what that is
anyways I have been practicing and i think i get the gist of what you taught me. However it hasn't been working well. For instance, 965 base 10 = (9x10^2)+(6x10^1)+(5x10^0). You taught me that if I want to convert the number into base 8 I have to convert each number in this expanded notation and then solve it.
9 decimal = 11 octal, 10 decimal = 12 octal
torn escarp
no no that trick only worked for the special case when it's a power like 2 and 8 were
atomic sable
huh?
torn escarp
to do different bases you have to take 965 and divide by 8 to find the remainder
that trick only worked because base 2 and base 8 are nearly identical
atomic sable
Ohhhh
Ok, I'll keep that in mind
Why did it work when we converted 345 octal to decimal?
torn escarp
you can do it that way
atomic sable
Sorry about all of this, I'm a visual thinker
torn escarp
it's just you're more comfortable working with base 10 arithmetic
so it's not very hard
if you try to do it the same way backwards, you'll run into issues since you're just not used to doing stuff in base 8 is all
so it's not that it doesn't work, it just requires you to do more math because the terms won't line up
atomic sable
So that method works only when converting to decimal?
torn escarp
sort of, well you can see for yourself by doing what you described to see why I'm saying that
(9x10^2)+(6x10^1)+(5x10^0)
you converted everything over to base 8 now
(11x12^2)+(6x12^1)+(5x12^0)
now you have to work out everything, like what's 12^2?
atomic sable
multiplying and adding is different in each base?
atomic sable
so what is 12^2 in base 8
atomic sable
?
torn escarp
you asked, this is it
so what is 12^2 in base 8
@atomic sable
that's how you work it out
atomic sable
isnt that how you normal multiply 12?
torn escarp
144 is how you write a hundred in base 8
it turned out we didn't have to carry at any point
so it looks the same yeah
atomic sable
Oh
torn escarp
1 and 2 are small digits so we didn't end up carrying is all
atomic sable
Bamboozled again
atomic sable
Dude, you would make a great teacher. You have been very patient with me and I really appreciate it!
torn escarp
so you put the 0 and carry the 1
torn escarp
just a reminder, this is the way that I'm suggesting you don't do lol
torn escarp
do it in base 10
divide by 8, look at the remainder, that's the right most digit
then you look at what you divided and then divide that by 8 again and the remainder of that is the next digit to the left
you do this until you can't anymore
atomic sable
Oh yeah. We covered that in class
torn escarp
yeah haha
I was only showing you how to do it in base 8 to show you why you don't do it that way
that trick is really only like for when you convert between a power of the same base like base 7 to base 49 or base 125 to base 5 etc
atomic sable
Oh
One last question. I stil dont feel like I have an intuitive understanding of this. Any books you recommend that goes more in depth?
the online tutorials barely scratch the surface
torn escarp
no books, I'd suggest just try to work out a handful of stuff in different bases like adding, subtracting, multiplying, dividing to get more comfortable with it
intuitively I just think of it as counting stones and having buckets, each time I get 10 stones, I just place one stone in another bucket to the left of it
but for different bases I just change how full my buckets are before I shuffle the stones over
I really think of it as just being alternate practical way of counting a large number of things to just writing tally marks, you make a rule that represents bigger stuff to save you from writing so much
atomic sable
thats a pretty good analogy. I will try to think it that way
torn escarp
cool 👍
you can get weirder too like
for instance how time is measured can be thought of as a really weird basis sytem
base 10 each bucket holds the same amount
but with time, we have 60 seconds before we put one in a minute bucket
60 minutes in an hour, then it gets weird cause it's not base 60
there are only 24 hours in 1 day
and 7 days in 1 week
52 weeks in a year, etc
but it's handy for when you start to do arithmetic of adding and subtracting to just use one size bucket for everything
cause then when you carry, you'd have to think in terms of which digit you're at depends on how much you carry which is no fun at all
atomic sable
ah ok
warm glacier
i understand the induction principle itself, but the writer has chosen to write (7/4)^(k - 2) (11/4) < (7/4)^(k - 2) (7/4)^2 = (7^4)^k in the proof of this inequality. because of the way that last line is written i assume he's using the alternate form of (7/4)^k to clearly show how the inequality holds.. but i'm confused about how one would arrive at (7^4)^(k-2) * (7/4)^2 without looking for that algebraically from the start.. am i misunderstanding something? to me it seems like this proof hinges on seeing an alternate form that shows explicitly (11/4) < (49/16) therefore a_n < (7/4)^n for all n >= 1
is that a typical thing for induction proofs, that you try to algebraically manipulate things to a common form to establish implication?
sacred junco
the order a proof is written is not usually the order in which ideas are generated
warm glacier
by that, do you mean that you can't expect a statement to become "directly proven" by its initial form; in other words, that you might have to find some tricks to prove things clearly?
sacred junco
although this one seems kind of straightforward after reading through it a bit closer
I mean like...
it may seem like something is just pulled out of a hat, or you might not know why the person writing the proof is even mentioning something
warm glacier
ah, yep
sacred junco
for example, you may need to play around with an inequality
before attempting to write the proof
warm glacier
that's pretty much what i struggle the most with in this text. i'm not sure whether he's left steps out or if it's put in to clarify, because that (7/4)^(k-2)*(7/4)^2 doesn't seem to arise directly from following the finite induction principle
sacred junco
btw @warm glacier I wouldn't really say this is pulling expressions out of a hat which are obtained from playing around with the problem beforehand, as much as it is knowledge of strategies to prove statements like this
since you or anyone else could probably think of this proof in pretty much the order it is written, with more experience
warm glacier
yeah for sure, but the issue is that it's mainly intended as an undergrad teaching textbook, but it already seems to be inconsistent pedagogically, as in, it assumes a certain understanding, but sometimes it makes leaps or expects the reader to see more connections than what are carried out previously
and there are likely multiple ways to prove this, but idno, it made me think i was missing something by condensing it like that
sacred junco
you'd have to... get used to it I guess
warm glacier
dammit
jovial hemlock
Can I ask a stupid question? Is it meaningful to talk about “half of all natural numbers”?
fervent crest
There is a way to make that precise
jovial hemlock
I know that there are exactly as many even natural numbers as there are natural numbers, but I don’t know if the sentance “half of all natural numbers are even” makes sense
And if it doesn’t work, how would I phrase it so it does work?
fervent crest
Let $S$ be a subset of $\bN=\brc{1,2,\dots}$, then let's say $S$ contains half of the natural numbers if $$\lim_{n\to\infty}\frac{|\brc{k\in S:k\leq n}|}{n}=\frac12$$
sterile pumiceBOT
Whoever:
fervent crest
So basically we see how many numbers in S are below N, then divide this number by N to get the proportion of numbers in S, then we take the limit
jovial hemlock
So new question
fervent crest
I mean this definition is quite arbitrary, but I believe it's a pretty good definition to make the notion of "half of the integers" precise
jovial hemlock
What if you aren’t sure that exactly half of the numbers below any given N have a property, but you are sure that exactly half of the numbers below 2^n have that property for any n. Can you still take that limit and claim that half of all integers have that property?
fervent crest
I'm not sure what you mean
But also you can notice that adding finitely many numbers in S won't affect it having half of the natural numbers or not: the limit will stay the same if finitely many numbers are added into S
supple furnace
Let S contain the positive integers that begin with 10 in binary and let S(x) denote the number of elements of S at most x. Then S(2^n)=2^(n-1), but S(3*2^(n-1))=2^n and so S(x)/x is always 1/2 and 2/3 in the first and second examples, respectively.
@jovial hemlock
This is an example fitting your conditions where the natural density fails to exist
jovial hemlock
Yes that’s sort of what I’m saying
Given such an example, can you state that 1/2 of all natural numbers begin in 10 in binary?
jovial hemlock
What exactly is a “natural density”?
supple furnace
Because the value can fluctuate
jovial hemlock
I assume it means like
jovial hemlock
“the amount of numbers that begin with 10 over intervals of fixed finite length with an arbitrary starting point”
supple furnace
This is the standard definition
Just think about what it means for a limit to exist though
jovial hemlock
Aaargh infinities are annoying
supple furnace
Epsilon delta applies here
jovial hemlock
There’s so many places where I have an intuition, and I know it’s wrong, but I can’t figure out the exact point at which it breaks down
supple furnace
If for some eps>0, there exist m,n>N for arbitrarily large N such that |S(m)/m-S(n)/n|>eps, then your natural density isn’t defined.
jovial hemlock
In this case
supple furnace
Which is the case in my above example
jovial hemlock
I still don’t understand exactly why epsilon delta doesn’t work here
Oh nvm I had it backwards
okay hmm
Yeah okay I see
stoic bear
intuition can be very misleading
especially if you don't formally define what you are dealing with
warm glacier
cancelling it out... how? i'm sure there's a validity here, but this notation seems very suspicious. i could take it as meaning e.g: (n choose k) = (n*(n - 1)!*(k + 1)) / (n - k)! which shouldn't be correct.. but if i interpret it as n times (n - 1) UNTIL n = (k + 1) it seems to be correct in that it "cancels" / skips the portion of the denominator represented by k! ... but how can i show this algebraically instead of with ambiguous notation?
sacred junco
$\binom{n}{k}=\frac{n!}{k!(n-k)!} $
sterile pumiceBOT
HoboSas:
warm glacier
any specific reason why there's a j index in only the one statement for b(a + b)^m or is it just lazy editing? the same does not occur for the first part
abstract flax
They used a j index to show they changed (shifted) the index to k
warm glacier
but why only in the second part
warm glacier
but wouldn't it be the same result without substituting index variables?
or is it illegal to shift an index like that if you assume it is the same throughout?
pardon my retardation, i am very new to number theory
abstract flax
I don't know what you're asking, but it's definitely not illegal
In the second part, they did the substitution k = j + 1
That's why they used a different variable before
You don't have to use a different variable, it just makes it easier to see a shift happened
warm glacier
ok, let me see if i understood the point of this correctly then.
for the first equation it just pulls out the 0th index from the sum therefore k = 1 in the end.
for the second equation it wants to get the specific shifted form of the binomial coefficient, therefore it begins with j as index and substitutes it with k?
or is the shifted form just a result of the substitution to unify the two equations
as you can tell i'm very confused
abstract flax
First part it just takes out the first term from the sum. I think you see that
warm glacier
yeah that's what i meant, 0th term
abstract flax
Second part it shifts the index, then it takes out the last term.
warm glacier
OH, i think i get it now. i wasn't noticing the exponents
d'oh, that definitely helped
so i'm assuming the exponential shift is a strategy to then add the binomial coefficients together in the end for using pascal's rule to simplify?
abstract flax
I would guess so, but surely you can see what they do next. I can't
warm glacier
yeah sorry for not being clear, i'm trying to understand proving the binomial theorem by finite induction
the resulting expression looks like an alternate form of pascal's rule, although this proof never stated what each step was trying to accomplish i'm assuming that's what it was
abstract flax
Yep, that's what it's doing
warm glacier
thanks pal, good to get some clarification
abstract flax
Np
indigo surge
yo just tryna prove that sqrt{2} is irrational
my textbook says p^2 = 2 can be written as (m/n)^2 = 2, but it says that m and n cannot both be even. why can't m and n both be even; what is the basis of that assumption?
rugged umbra
Have you learned contradiction for proofs ?
sacred junco
The idea is that all fractions have a “lowest form”
Or they have a representation with a relatively prime numerator and denominator, whatever you want to say
There are probably some more details written in the proof (likely at the start) relating to this
indigo surge
im reading baby rudin
it doesnt explan it
@sacred junco but yeah i get it now. all fractions have lowest form that is all fractions have a form that is irreducible
sacred junco
Ah yea I think the proof given there is a bit terse
sacred junco
Of integers*
That proof, and many other variations, are everywhere
So if you want a version with more detail it is probably easy to find
warm glacier
@indigo surge yeah, if m and n are both reduced to lowest form and are shown to be even integers, then you contradicted the assumption that sqrt(2) is rational because both m and n cannot be even
fervent crest
I personally like this version of the proof much better:
Suppose $\sqrt{2}$ is rational, then $k\sqrt{2}$ is an integer for some integer $k$. Let $S=\brc{k\in\bN\setminus\brc{0}:k\sqrt{2}\in\bN}$, then $S$ is nonempty. By Well ordering principle let $n\in S$ be the minimum element. Since $n\in S$, $\sqrt{2}n$ is an integer, so $\sqrt{2}n-n$ is an integer. However, $(\sqrt{2}n-n)\sqrt{2}=2n-\sqrt{2}n\in\bN$ shows that $\sqrt{2}n-n\in S$, and you can easily show $\sqrt{2}-1<1$ using ordered field axioms so $\sqrt{2}n-n<n$, contradicting the fact that $n$ is the minimum element. Therefore $\sqrt{2}$ is irrational.
sterile pumiceBOT
Whoever:
fervent crest
@sacred junco @indigo surge
sacred junco
Nice, haven’t seen that one before
trim gust
lol there is no need to specify N without 0, as it is already without 0
sleek cove
0 is my favorite natural
trim gust
sacred junco
angry von neuman noises
Here is my personal favorite
let $a$ and $b$ be positive integers such that $\frac{a}{b}=\sqrt{2}$. We will show there is no positive pair $(a,b)$ with a minimal $b$ that satisfies. Suppose for contradiction we have the pair $(a,b)$ with the minimal the value for $b$. From the equality we can write $a=\sqrt{2}b$ and $2b=\sqrt{2}\cdot\sqrt{2}b=\sqrt{2}a$. Consider the fraction $$\frac{2b-a}{a-b}.$$
On one hand, by some substitutions we have $$\frac{2b-a}{a-b}=\frac{\sqrt{2}a-a}{\sqrt{2}b-b}=\frac{(\sqrt{2}-1)a}{(\sqrt{2}-1)b}=\frac{a}{b}.$$ On the other hand, Since $1<\sqrt{2}<2$, we have $b<\sqrt{2}b<2b$, or $b<a<2b$, which means $0<a-b<b$. Hence our original choice of $(a,b)$ did not minimize $b$, and by descent there is no such $b$ and no possibility of writing $\sqrt{2}$ as a fraction of integers.
sterile pumiceBOT
Botnuke:
sacred junco
Get em thinking proofs are all about pulling things out of your ass early on
sacred junco
I like yours better since it is new to me
fervent crest
Ok to be honest I like both equally, because both are very quick and don't involve much technicality
I don't really like the standard proof because proving that a^2 is even iff a is even is just not very elegant
sacred junco
I also think it’s so overused
There are so many proofs but I’ve seen the standard one a billion times
fervent crest
It is super overused
But I have not seen any other proof other than the standard one and the two we just sent
trim gust
I don't really like the standard proof because proving that a^2 is even iff a is even is just not very elegant
proving that is trivial though
how would it be inelegant at all
fervent crest
It's casework
trim gust
but it isnt though
fervent crest
Usually you show that if a is even then a^2 is even and if a is odd then a^2 is odd
And I don't really like that part
hushed ether
Fun toy problem: for what values n do the first n-1 triangle numbers take on every non-zero value mod n?
fervent crest
|| Huh this is equivalent to for what values of n do a,b≠0 (mod n) and (a-b)(a+b+1)/2 = 0 (mod n) => a=b (mod n) ||
|| You can check 2 works and 3 doesn't, then larger odd primes don't work since the (p-3)/2th and (p+1)/2th triangular numbers are congruent mod p ||
|| wrote a script, and seems like only powers of 2 work ||
hushed ether
can pm a solution if interested
supple furnace
Here’s my full solution: ||Suppose that n has an odd prime factor p. Then if the map
sending a to a^2+a mod n is surjective, it is necessarily surjective mod p, which cannot occur because if a+b=p-1, then a(a+1)/2=b(b+1)/2 mod p and because the inputs {0,...p-1} produce all possible outputs mod p. Now we show that it holds for powers of 2. To do this, we show that if a,b are distinct nonnegative integers less than 2^k, then a(a+1)/2 is not congruent to b(b+1)/2 mod 2^k. Indeed, a(a+1)-b(b+1)=(a-b)(a+b+1), and so it is the product of two numbers of opposite parity. But the first factor is bounded by 2^k in absolute value and cannot be 0, implying that it is not divisible by 2^(k+1), and the second is between 1 and 2^(k+1)-1, so it also cannot be divisible by 2^(k+1). This proves surjectivity.||
supple furnace
I was able to prove an analogous result for tetrahedral numbers
Some really weird things happen for more complicated ones though
For example, (aC7) only takes on 5 values mod 9
hushed ether
what's aC7?
fiery root
The way this has been solved is:
Select one couple from which a spouse is chosen in 4C3 ways. Then select one of the spouses from those in 2C1 ways each giving a total of 4C3x2C1x2C1x2C1 = 32 ways.
My method was:
Select the first person in 8C1 ways and remove the spouse from the list. Select the second person in 6C1 ways and remove the spouse from the list. Select the third person in 4C1 ways. Total: 8C1x6C1x4C1 = 192 ways.
Why is my answer wrong?
I don't see the redundancies, I'm sure those are the cause of this gross exaggeration
Ohh okay, let me think about this a bit. Thank you for tagging btw! :)
Shoot I get it instantly, great example
fiery root
Yes, I was essentially permuting the results
pliant monolith
Could anyone help me to solve these eqs? I think the middle system will essentially be a proof that sqrt2 is irrational but I'm not sure about 1 and 3
supple furnace
Modular arithmetic for iii
trim gust
yea mod 4 number 1 and 2, mod 3 number 3
supple furnace
Completing the square for i
trim gust
and use the fact that quadratic residue is 0,1 for mod3 or 4
trim gust
oh nice, i knew that there would be some factorization but i thought mods would be simpler
pliant monolith
Is this enough to show there are no solutions?
trim gust
why are u writing 3x^7 as {0,1,2}; it is clearly 0
trim gust
also 6xy is 0 and not 2
pliant monolith
Here I am wondering why I’m having such a hard time lol
trim gust
also as i already said y^2 is {0,1} not {0,1,3}
trim gust
oh right
pliant monolith
Sorry my handwriting is kinda bad
trim gust
also you need to consider how the reside of y^2 influneces the reside of y
pliant monolith
After that I only need to consider case 1 - {1,2} right?
Which is obviously not a solution showing each of the 2 cases
Since 0 - 0 also isn’t congruent 1 modulo 3 from the influenced case
Alright I got it now thank you
fervent crest
The procedure you defined always produces a strictly decreasing sequence unless the number is 1
pliant monolith
Is it not correct to say that 1 - {1,2} /=/ 1 mod 3? -> no solutions
pliant monolith
Hello again, I have this query, I noticed that subbing x=n+2 helps to simplify this system quite a bit down to the following 3 eqs: (after image)
22x=11 mod 13
22x=57 mod 59
x^2 = 1 mod 47
But I'm not sure how to proceed, I notice that all the modulo are pairwise coprime
Which means CRT applies but then I'm stuck
void widget
the first two can be put into one using CRT
the second you can bring the -3 over and factor the quadratic
once you find its solutions you can join that in with CRT again
pliant monolith
How do I combine them with CRT again?
I thought it just guarantees an inverse exists
sleek cove
its similar to just finding the zeros of a polynomial
pliant monolith
This is what I have
leaden swan
Find a number 1 mod 13,0 mod 59,0 mod 47
empty yew
you don't need to make that substitution. for the first two ones, use inverses and division to simplify. example for first one:
||22x=11 mod 13 => 2x = 1 mod 13 (this is valid because gcd(11, 13) = 1)||
||then notice 7*2 = 1 mod 13, so multiply both sides by 7 to get:||
||x = 7 mod 13||
hint for the second: ||57 = -2 mod 59||
and for the last, try factoring. ||bring 1 to the other side and factor||
if you do want to use the substitutions, try to find the inverse of 22 mod each of those guys so you can multiply both sides by that
empty yew
looks like you're using the euclidean algorithm to do it. that works, yep. though do note the inverse is -8, not just 8 (if you take the mod 59, you get 1 = -8*22 mod 59)
sacred junco
- p, q prime integers
pliant monolith
I completed part a), but I'm not sure why b) implies a=b, is it because theta(a) = a?
Since theta maps G to itself?
But theta^2 here is?
It's not isomorphism?
Like so?
And then apply theta again to make use of theta^2 as the id map?
sterile pumiceBOT
Viburnum:
pliant monolith
I am a little bit lost I guess
It preserves the operation right?
That it maps the identity of the first group to the second?
Oh hold up
Does it mean that I can combine the thetas?
So theta(a^-1)theta(b) = theta(b/a)?
Or something similar
And then we use theta^2?
Or that isn’t necessary because theta : G->G is demonstrated with theta(a^-{1}b)=a^-{1}b?
Ah so that is false
My conclusion there
Hmm
Theta(g) = g if g=e_g
Sorry why is this wrong?
Implies*
So this is saying that a^{-1}b=e_g?
Then just multiply by a
Awesome
Thanks, I’ll probably be back again after I attempt the next parts
stoic bear
Nothing to do with mod in this case
quiet mesa
wat
stoic bear
sacred junco
"linear operator property" maybe
frozen wren
ok
sacred junco
I think you already have to know what a homomorphism is to understand what he means
he was not defining it
stoic bear
it's not important for working with mods anyway
quiet mesa
i don't exactly know what he's referring to
frozen wren
oh
wait when im i allowed to ping honorable
or kaynex
@swift shard hey sry buddy
/friend
could u clarify smth
im stupid so im confusing pocofrosty12 and maximwebb
quiet mesa
@frozen wren as i was saying, textbook + exercises is going to be the way to learn this stuff
learning a bunch of definitions isn't very helpful, you don't get any appreciation for why we're taking mods of numbers here
if you're still at high school or wtev, i'd start with this
stoic bear
@frozen wren what property are you talking about?
frozen wren
@quiet mesa im in middle school, does this change naything?
taking alg 2
@stoic bear
so if we have
a = b (mod m)
a + x = b+x (mod m)
a-x = b-x (mod m)
quiet mesa
i mean obviously it helps to have seen more maths
but have a go, and see where you get to
frozen wren
ok
stoic bear
Those are just basic properties of mod
quiet mesa
i guess what he might mean there, is if you consider mod as a function, then addition behaves the same or smthg
stoic bear
I can't think of a specific name for it, probably cause it's unimportant
quiet mesa
so if f_m(a) = remainder(a/m)
stoic bear
Yeah
"Linear operator" as botn said
Anyways for a = b mod n
a * c = b * c mod n
a+ c = b+c mod n
a - c = a - c mod n
Note division is more complicated and doesnt hold
quiet mesa
yep: 3 = 6 mod 3
dividing both sides by 3 gives you 1 = 2 mod 3, which is clearly wrong
stoic bear
Oh and raising both sides to a power
sacred junco
here is a useful list @frozen wren
you can try to prove some of them if you want
seems like a big list but they kind of... make sense once you get used to it
and you won't forget them
they'll just feel natural to apply
frozen wren
Cool
pliant monolith
What is the reason why a finite cyclic group of even order has exactly one element of order 2? 
leaden swan
Look at the cyclic condition and check what it means for a subgroup to be order 2
pliant monolith
Ah I got it, thank you
fossil salmon
im doing math chat with bois and we just conjectured conjecture: if n is prime, n^k will have k+1 factors is this true or false? we dont know how to prove it but I think its just cause primexprimexprime the prime has 2 factors next time u add prime^2 to it and then prime^3 then so forth
i probably would find this in a number theory book
I think that proof is sufficient
rancid halo
Sounds right although you should use p instead of n for primes
Usually what you would do is appeal to something like unique factorization. Any factor must only have p among its prime factors
And so the possible factors are p^0, p^1, p^2, ...., p^(k - 1), p^k
fossil salmon
lol yes youre right p>n
rancid halo
Lol it's more standard, but it really doesn't matter as long as its clear
fossil salmon
I was thinking about using the same symbol as an operator for a variable
like +=4x
really confusing
rancid halo
Yeah please don't do that
fossil salmon
then all my proofs on my homework assignment will be correct by esoteric notation
rancid halo
Would be kinda funny though
pliant monolith
Could someone provide some direction on how to define a mapping as well defined? I'm not sure what it means
leaden swan
Let $a,b\in A;$ if
$a+I=b+I \implies \phi(a+I)=\phi(b+I)$ $ \phi$ is well defined
sterile pumiceBOT
DrunkenDrake:
leaden swan
Or if 2 equal terms give the same output, when the function is applied
@pliant monolith
pliant monolith
Thank you
pliant monolith
You're right, my bad
warm glacier
i started by saying $a = q' b + r', 0 \le r' < b$, and then i added 2b, but i have no clue how to go from here to show that q and r are unique for the initial interval
sterile pumiceBOT
Bne:
fervent crest
Well if a=q''b+r''=q'b+r' with 2b≤r'',r' < 3b, then a=(q''+2)b+r''-2b=(q'+2)b+r'-2b and 0 ≤ r''-2b, r'-2b < b
Then see what you can do
@warm glacier
warm glacier
honestly that's kind of just more confusing to me with the double primes and inequalities
warm glacier
am i supposed to substitute r' with something
it seems like there are some steps being carried out here that i don't see yet
fervent crest
So you know if a=qb+r where 0≤r<b then q,r are unique right?
warm glacier
yeah, that's essentially what we show by proving the division algorithm, correct?
at least part of it
fervent crest
Yeah that is part of division algorithm
So are you allowed to use that?
Anyways let's assume that we can use the uniqueness if 0≤r<b
warm glacier
yes, but i am having trouble with the uniqueness part because earlier we'd use some abs tricks to show it
and i guess i just am confused in general about uniqueness
warm glacier
oh, so we subtract 2b instead of adding?
fervent crest
Yeah
That's essentially what I did
So suppose a=q'b+r'=qb+r and 2b ≤ r,r' < 3b, then a=(q'+2)b+r'-2b=(q+2)b+r-2b
Since 2b ≤ r,r' < 3b we have 0 ≤ r-2b < b and 0≤ r'-2b <b
So by the uniqueness of the division algorithm
We must have q'+2=q+2 and r'-2b=r-2b
warm glacier
but didn't we say that 0 ≤ r' < b, why are you saying 2b ≤ r,r' < 3b
i'm not sure i follow honestly, i end up with
a = qb + r = q'b + r' - 2b = b(q' - 2) + r'
fervent crest
Ok so the original problem was to show that if r is between 2b and 3b then the r and q are unique
warm glacier
yes
fervent crest
Then I said that part of division algorithm is that if 0<=r<b then the r and q are unique
If you don’t know this I can show you the proof
Now, using the fact that if 0≤r<b then the r and q are unique, we can prove the uniqueness when 2b≤r<3b
warm glacier
yeah, so what i'm thinking is saying r' = r - 2b so we get 0 <= r' < b. but then a = q'b + r' - 2b, so for this to become equal to our original problem i must also add 2b => a = q'b + r' - 2b + 2b = b(q' - 2) + r' + 2b
is this line of thinking correct?
so now q = q' - 2 and r = r' + 2b
fervent crest
Yeah you already did that to show that there exists an r with 2b≤r<3b
The reasoning is correct
warm glacier
since 0 <= r' < b, then 0 + 2b <= r' + 2b < b + 2b => 2b <= r < 3b
fervent crest
Why does it show uniqueness?
Uniqueness means showing that if a=qb+r=q'b+r' and 2b ≤ r < 3b and 2b ≤ r' < 3b then q=q' and r=r'
warm glacier
yeah, but since our choice of q and r leads to 0 <= r' < b which in turn is 2b <= r < 3b
isn't that the uniqueness?
fervent crest
No
warm glacier
maybe i'm just really confused about the division algorithm's proof and what exactly uniqueness and existence is
fervent crest
You constructed two numbers
You didn't show that they are unique
You just need to show what I wrote
if a=qb+r=q'b+r' and 2b ≤ r < 3b and 2b ≤ r' < 3b then q=q' and r=r'
That is what it means to be unique
warm glacier
but that's what i'm confused about, because i was saying the same thing, that it implies uniqueness without showing they're exactly the same
warm glacier
how?
sterile pumiceBOT
Whoever:
fervent crest
Well yeah
You have to explicitly say it
You are trying to show it of course you have to explicitly say it
warm glacier
but if i already said q, r are unique and my choices of q', r' implies uniqueness, then i should still say it explicitly because it's part of the definition for the division algo?
fervent crest
Well you need to say unique q,r by division algorithm, so q',r' are unique
It's not the definition of division algorithm
division algorithm is not a definition
it's a theorem
warm glacier
part of defining the theorem is saying there exists unique integers q, r satisfying a = qb + r, 0 <= r < b, no?
part of, meaning this: "exists unique integers q, r"
fervent crest
Yeah
But you need to mention that in the proof
and you need to mention the uniqueness of q and r imply the uniqueness of q' and r'
fervent crest
You need to understand that theorems are not definitions
warm glacier
i wasn't really saying that
which is what i tried to clarify, and you just said yes to
fervent crest
Ok
well it's not part of the definition of division algo
you just say it is part of division algorithm
warm glacier
alright, i'll keep that in mind
fervent crest
and still you need to mention the two things: division algorithm says that q and r are unique, and this imply the uniqueness of q' and r'
warm glacier
yeah, i guess my problem is with the rigor of proofs. in my head it seems obvious, but i have to explicitly state what something is clearly
fervent crest
Yeah that's a hard thing
warm glacier
so my solution was "technically" correct, but not exactly correct because i didn't really say q', r' is unique by the theorem used - to begin with. yes?
warm glacier
yeah that makes sense, especially by what you said earlier of uniqueness, it's much more clear than indirectly showing it via a previous proof
thanks for helping!
fervent crest
You're welcome
sterile pumiceBOT
rush7:
fervent crest
Well
Don't think too hard about it
We can easily factor 2019=3*673
Then 1001! definitely has a factor of 3 and 673, so 1001! = 0 (mod 2019), similarly for 2001!
@sweet girder
sweet girder
so only 1! left and the answer is 1 ?
fervent crest
yes
sweet girder
thank you, simpler than i thought
fervent crest
yeah don't overthink it
warm glacier
i've been able to show a = 6k + 5 = 3 * 2k + 3 + 2 = 3(2k + 1) + 2 and setting j = 2k + 1
fervent crest
Yes