elementary-number-theory

[red drift]

how?

[leaden swan]

Note that (a^2-b^2+1)+(-a-b)(a+b)=1

That is gcd divides 1

Which implies gcd is 1

[red drift]

so i see that you got the original equation (a-b)(a+b) + 1 but why did you do "+ (-a-b)(a+b)?

[leaden swan]

If px+qy=c then gcd(x,y) divides c

I was trying to get p and q such that c=1 taking x=a^2-b^2+1 and y=a+b here

[red drift]

okay, and then how did you use p and q to imply the gcd is 1?

[leaden swan]

The details of p and q don't matter as long as you know px+qy=1

[red drift]

so by saying a^2 - b^2 + 1 = (a-b)(a+b) + 1, we know that (a+b) is included in (a-b)(a+b) + 1. Therefore the gcd(a^2 - b^2 + 1, a+b) is 1?

[leaden swan]

You can rearrange the terms to get 1,so gcd is 1

[red drift]

oh so by rearranging the terms to equal 1, the gcd(x,y) will be 1

ok kinda makes sense

[heavy palm]

there is no soln to a^b = b^a where a,b \in N/{0,1} and a \neq b right

since rearranging we get b/a = ln(b-a) and for this we need b - a = e^(b/a) but im reading e^(b/a) is transcendental, and hence irrational so contradiction

[haughty lichen]

a=2 and b=4 is a solution but that is the only solution in the natural numbers

[heavy palm]

hrm

[heavy palm]

so where does this reasoning break down?

[haughty lichen]

How do you get your first line

[heavy palm]

so true i made an algebra mistake

I'm interested in knowing how you got a = 2 and b = 4

is it not the case that b = a^a always works?

err no nevermind

[red drift]

@leaden swan im having trouble proving this

[heady basalt]

what's part a?

[heady basalt]

i take it that a and p are coprime?

[red drift]

yea....

[heady basalt]

Start by writing a Bézout identity for p and a

and then try to make the subject of the question appear

[red drift]

so could i say gp + ha = b, where g,h an element of integers?

[heady basalt]

recall what's on the RHS of a Bézout identity

It's the GCD (of a and p)

this whole question hinges on a and p being coprime, you don't want to waste that info

4 doesn't divide 2, it divides 2*6, but it doesn't mean 4 divides 6

[red drift]

let d = gcd(a,p) and m,n an element of integers such that a = md and p = nd such that b = ax + py = mdx + ndy = d(mx + ny) = b?

something along that

[heady basalt]

dude

already know what d is

[red drift]

what?

[heady basalt]

*you already know what d is

it's a given

if you take 5 and any number that's not a multiple of 5, you're not going to find a number that divides both of them, other than 1/-1

the Bézout identity/theorem states that for any two integers (m,n), you can find x,y (also integers) such that mx+ny=gcd(m,n)

[red drift]

oh okay

[atomic gale]

I'm a bit confused by these answers. So I already proved part a. And now I'm on b.

This is what I have for the answers.

And I'm confused. Like for the first one. I get how they got to 2^29. But how and why did they do the 16(mod 31)?

[atomic gale]

<@&286206848099549185>

[compact walrus]

this chapter does not deal with the ordering of distinct objects. but don't I have to multiply 5c2 with the result as the choosing of 2 members from 5 friends should be counted?

for the words ending with SSS, there are two variant SSS______, and ______SSS. So I think the answer includes both. So a deduction of 1 should be there...am I wrong?
edit: dividing by two is another thing on my mind. subtraction is not making sense anyone.

[red drift]

@leaden swan how do i start this?

[dusty dragon]

For the forward direction, let d = gcd(pa, p^4) > p. Since d > p, then d must divide some power of p (call it k with k >= 2). From this it's easy to see that p | a.

For the backward direction, suppose that p | a. Then we can express a as a = pk for some integer k. Then gcd(pa, p^4) = gcd(p(pk), p^4) = gcd(p^2 k, p^4) > p since gcd is at least p^2

That should at least give you some direction on how to start

[abstract flax]

The first part of your proof, I find confusing. d divides some power of p because d has to divide p^4. I don't see how it's related to the fact that d > p? I also don't see the relevance to the proof really.

[dusty dragon]

Hm yeah, I didn't word it that well I guess (what happens when I spent the entire day doing an assignment 😅). But I guess what I was going for was d has to divide some power of p since d | p^4. But since d > p, the power of p must be at least 2

[red drift]

hm so how would i continue from the forward and backwards

this is just rly confusing

[iron surge]

Based on their solution, they are assuming that those two friends that must be together are particular people. This is why they say tie THE two friends together; so that is why they aren’t counting any of the other possible pairings that tie two friends together

[iron surge]

Did you have a question about this?

@compact walrus

[compact walrus]

If only inferred that way but I didn't get the hint

[iron surge]

also @compact walrus , your question isn't really an elementary number theory question at all. It'd be more appropriate to post your question in a discrete math channel or a probability/stats channel. That's just so you know in the future where to post counting problems like the ones you brought here.

[compact walrus]

okay sure...but how much have I strayed from the elementary level?
I am working on a book suggested for beginners....counting by khee meng koh....

[leaden swan]

Sounds more like combinatorics than number theory

[iron surge]

um I've never heard of counting problems covered in elementary number theory like at all. Counting problems (these are combinatorial problems) are typically encountered in discrete math, combinatorics, and stats.

[compact walrus]

okay...so should I post it on #probability-statistics channel?

[iron surge]

Next time yes. I think I already answered your combinatorial question, right?

so there's no need to repost the same question elsewhere

[inner anchor]

#discrete-math is also a good place to post combi stuff

[iron surge]

they already know, but thanks for the confirmation

This channel is open for questions

[compact walrus]

@iron surge , I had another question which is not answered yet...and yes you answered the first one.

[iron surge]

oh! My apologies @compact walrus , I didn't see that for some reason. I can answer that now.

So their solution is correct because by "at the end" they literally mean the rightmost end

so they aren't including the front end in the count

[compact walrus]

so if we consider the both front and back scenario, then do we multiply it by 2?

[iron surge]

this is why they say "we fix the SSS at the end".

[iron surge]

yes

[compact walrus]

okay...thanks...👏 🙂

[iron surge]

You're welcome!

[shut echo]

I have to find the GCD of $(2018!+1)^3+(2018!+1)^2+1$ and $(2018!+1)^3+(2018!+1)+1$. I reduced it to finding GCD of $(2018!)^2+(2018!)$ and $2×2018!+3$ using the sub $(2018!+1)=a$. Can someone help?

[sterile pumice]

Schrödinger's cat

[leaden swan]

Let a=2018!+1 then gcd(a^3+a^2+1,a^3+a+1)=gcd(a^3+a+1,a^2-a)

Now a clearly doesn't divide a^3+a+1

So this is equal to gcd(a^3+a+1,a-1)

Which can be seen to be gcd(3,a-1)

Which is just 3

@shut echo

Idea is gcd (a,b)=gcd(a,b-ka)

[shut echo]

Why's this true

?

[leaden swan]

Long divide

Remainder of a^3+a+1 when divided with a-1 is 3

a^3+a+1=(a^2+a+1)(a-1)+(a-1)+3

[strong tulip]

Could anyone help me prove the following statement, "Prove that for any integer k we have that (17k + 6)^2

is con-gruent to 2 modulo 17.
Not sure how I would begin

[simple marlin]

Have you attempted induction?

[strong tulip]

yeah i just figured it out lol

However, I have been stuck on this problem, Suppose that a, m are positive integers, and x, y are integers such that
ax + my = 2. Find an integer z such that
[a]_m [z]_m = [6]_m. Not sure how to solve to one

[prime sparrow]

Multiply both sides of the equation by 3, what does this equation look like modulo m now?

[strong tulip]

not sure what u mean

as in 3[a]_m?

[prime sparrow]

3ax+3my=6

[strong tulip]

is it the case than that z = 3?

[prime sparrow]

No

[strong tulip]

i dont know to relate the two equations tbh

i dont see how multiplying it by 3 helps

[prime sparrow]

a3x+3my=6, now let us look modulo m we see that [a]_m[3x]_m + 0=6

Sorry, [6]_m of course

[strong tulip]

hmm ok

could you walk me through it, since this is just for practice

[prime sparrow]

Ok, how much do you know about modular arithmetic (so that I know what I can assume)

[strong tulip]

the basics

should of been enough to solve this but here we are lol

i know that it isnt too difficult

[prime sparrow]

So here is a rundown of the facts I’m using, if you have a question about any of them, just ask:
So firstly given some integer a and some other integer m we can look at [a]_m which is the class of numbers that leave the same remainder as a on division with m. Secondly multiplication and addition makes sense in modular arithmetic and [ab]_m=[a]_m[b]_m for any integers a and b, and similarly for addition. Thirdly [m]_m=0 (which is really the notation for [0]_m)

[strong tulip]

okay i see

[prime sparrow]

Now that we know a3x+3my=6, we get:
[a3x+3my]_m=[6]_m and then by the second property [a]_m[3x]_m+[m]_m[3y]_m=[6]_m

But [m]_m=0

So it is just [a]_m[3x]_m=[6]_m

Hopefully this makes some sense

[strong tulip]

thats the answer?

cause tbh it does

i didnt think it was that simply

simple*

[prime sparrow]

Yep, its that simple

A lot of magic is hiding in the deceptively simple equation [a]_m[b]_m=[ab]_m (and the similar equation for +). This is what makes modular arithmetic really simple

[strong tulip]

Yeah I see what you mean, its starting to make sense. I should practice more of these tbh. I appreciate your willingness to break it down!

[prime sparrow]

Np

Btw why don’t you try tackling the (17k+6)^2 modulo 17 question from this perspective

I think you’ll find it becomes much simpler (no need to expand out the square)

[strong tulip]

good idea, I'll try that right now

[terse fog]

Anyone know how I would tackle this problem?

for pairs (a,b) the problem is quite easy using the totient function, but I cant seem to solve it for triples.

[leaden swan]

First select a and b. Now divide that problem into 2 parts:Case1) a and b are coprime Case2) a and b are not coprime

If a and b are coprime,any c will work

If a and b are not coprime,use that weird formula I don't remember to find the number of numbers coprime to gcd(a,b) in a bound

In short,Pick 2 numbers a,b and find their gcd. Now find number of numbers coprime to this gcd

[terse fog]

Thanks! That really helps!

[modern wave]

The last non zero digit of n! is the last non zero digit of 2^Q * Q! * R!
Where Q and R are the quotient and remainder when n is divided by 5

Why is this true?

[bright cloud]

if anyone is interested in checking out the culmination of 13 years of research into a seemingly impossible problem, have fun

[abstract flax]

Did you mean to dox your name? @bright cloud

Also, are you the dentist that comes up on google under that name?

No idea what's going on here

What are these expressions?

How do you get them?

[bright cloud]

dox my name? bruh i have no idea what that is haha

[bright cloud]

im such a nobody, i dont show up on google searches

[abstract flax]

@bright cloud your name is on the document

[bright cloud]

thats fine with me lol

[lunar scaffold]

I was curious about extending Wilson’s theorem, and I figured out the following:

$$\prod_{i=1}^{\phi(m)}{C_i} \equiv (-1)^\frac{k}{2} \text{ (mod $m$)}$$
Where the $C_i$’s are the units modulo $m$ and $k$ is the number of units that are their own inverses.

[sterile pumice]

Mathyland

[lunar scaffold]

Is there an easy way to find what k is (mod 4) given any m?

[light flicker]

It's the number of prime factors of m, but you have to be a bit careful with 2

if m is only divisible by 2 once, then you don't count it, if its divisible by 4, you count it once, and if its divisible by any higher power of 2, you count it twice

[lunar scaffold]

But if x is a self-inverse mod m, then so is -x, so k should always be even

And also I’ll rephrase my question to, for which m does k=2 mod 4 and for which m does k=4 mod 4? (Cause in the former case the product of units is -1 and in the later, it’s 1)

[light flicker]

Oh yeah whoops, you want to take 2 to the power of the number I described

In other words, the right hand side is only -1 if m is 4, a odd prime power, or twice an odd prime power. And otherwise it's 1

[lunar scaffold]

Oh interesting. Is it more than a coincidence that those are the moduli for which there exist primitive roots?

[light flicker]

That's exactly the reason yeah

the idea behind the ideas I described is to use Chinese remainder theorem to split things up into prime powers and then look at what happens to each prime power

[lunar scaffold]

Huh

I’m gonna have to wait until I have pencil and paper to figure out why that works, but that’s interesting

Thanks

[inner anchor]

Does there exist a nicer proof of dirichlets theorem

I didnt find the one in apostol especially illuminating

[light flicker]

@native garden One way is showing that m is equivalent to mu(a,p) mod 2 where mu(a,p) is the number of integers in the list a, 2a, 3a, ... (p-1)a/2 that become negative when reduced into the interval [-(p-1)/2, (p-1)/2) which you can show is equivalent to (a/p). You might like looking into chapter 23 of Silverman's Friendly Introduction to Number Theory where this is done and he uses this to prove quadratic reciprocity

[bright cloud]

is this correct?

[thick knoll]

If you know that $10n+11=0\pmod k$ and $5n + 27=0\pmod k$, that doesn't necessarily mean that $10n+11=5n+27=k$. One could equal $10k$, and the other could equal $3k$

[sterile pumice]

cgodfrey

[bright cloud]

look at the subscript of N in my equation

[thick knoll]

idk what that notation means

[bright cloud]

n_n = k_n

the first N is the first instance of k

dont worry my notation isnt the best, but what you are saying isnt ruled out by my paper

they could be on their own any instance of k independently of each other

but im guessing the smallest value we can possibly find, will be the mod?

[bright cloud]

maybe better?

[thick knoll]

I still don't know what those subscripts are supposed to mean

there's only one value of n and k

[bright cloud]

For k yes, but what about 10n = k(x) - 11? Is that solution for n not also 0 mod k for all x??

[rancid sandal]

Those modular equations imply $10n + 11 = m_1k$ and $5n + 27 = m_2k$ for some $m_1, m_2$ in the integers. Take the second equation multiply it by $2$ and subtract the first to eliminate the $n$ and you get $43 = (2m_2 - m_1)k$ since 43 is prime $k$ is either $1$ or $43$, both of which is $1 (mod 7)$

[sterile pumice]

holazach

[topaz ridge]

Hey everyone, not sure if this is the right channel to discuss the Lambert W function (product log) (if not, please redirect me to a better channel). My question is, how would I solve the equation $xe^{e^x}=c$ for $x$, where $c$ is any constant? I've tried many ways but keep getting stuck, so if anyone has any insight, I would appreciate it :)

[sterile pumice]

gmod

[sterile pumice]

JY1853

[light flicker]

I'm confused by that definition of phi(n), what exactly is the term in the sum? Do the terms keep going until the denominator is greater than l?

[light flicker]

Oh the inclusion-exclusion definition I see

I don't think you need the first fact about prime factors. I believe you can do it directly from the definition

You can write the #(numbers not coprime by 1 factor) as

sum over primes p dividing n of n/p

similarly, you can write the #(numbers not coprime by 2 factors) as

sum over distinct primes p1, p2 dividing n of n/(p1 * p2)

write this out, factor out the n, and see that what you have is exactly the product in the formula you want

[barren crane]

can someone explain chicken mcnugget theorem proof in simple and intuitive way, I skimmed through aops/brilliant.org but it was too complex 😔

[dusty dragon]

hi guys! I need a bit of help in an elementary coding theory problem regarding breaking the RSA scheme:
An RSA code has been constructed using the modulus M = pq which is a product of two primes p and q of the form p = 2^k + 3 and q = 2^n + 1 with positive integers, k and n. Design a strategy to use this information to break this scheme. Explain it on the example M = 33667

I'm assuming that I need to be able to find p and q somehow using the special form that p and q are in

but I'm not really sure how to continue from M = 2^(k + n) + 2^k + 3 * 2^n + 3

[sacred junco]

You would probably brute force it right? It takes a lot less effort to brute force when you know the form of the primes

I'm not great at coding theory but this would be quite fast to do

[dusty dragon]

Hmmm M can be made arbitrarily large so it would become much more expensive for larger M

I asked my professor and he hinted at converting M into binary which probably makes sense

[light flicker]

I mean, just expand out (2^k + 3)(2^n + 1)

[sacred junco]

Yeah actually I totally see it now, sorry

Expanding it to binary makes it real easy

@dusty dragon can you see why?

[dusty dragon]

Yeah so M = 2^(k + n) + 2^k + 3 * 2^n + 3 which is easy to convert to binary. So once we know the binary expansion of M, it’s easy to find the values of k and n which in turn makes it easy to find p and q

[sacred junco]

Yea exactly

[dusty dragon]

That’s actually pretty smart

My 12am brain just was not working xP

[sacred junco]

Your professor gave you a pretty fat hint tbf

[dusty dragon]

aka the answer

[sacred junco]

I guess the takeaway is to change the base if you see x^k a lot

[dusty dragon]

Yep. In hindsight, that makes intuitive sense too

Thanks for the help!

[lost arrow]

(10,12,15,18........95,96,99) find no of terms? pls help

[sacred junco]

10+3n

[night quail]

what's the pattern here

[sacred junco]

The differences seem a bit arbitrary ngl

2 3 3 ... 1 3

[night quail]

looks arbitrary to me too

[thick knoll]

According to OEIS, this could be composite evil numbers (i.e., have an even number of 1s in their binary expansion), numbers that are a multiple of 3 or a multiple of 5, or some relatively arbitrary sequence

https://oeis.org/A345995

[left sigil]

At least 7.

[steep raptor]

Hello, how do I solve $x^2+y^4=z^4$ has no solutions other than $x=y=z=0$? I can easily apply infinite descent for equations like $x^3+3y^3=9z^3$ since it just consists of modding out the equation and substituting using what we know from the mods. How do I extend it to equations where the coefficients are all 1 since modding out is not a possibility?

[sterile pumice]

Juno

[light flicker]

Do you mean no solutions other than when xyz = 0, because otherwise you can have solutions like (0,1,1) or something

You should be able to use descent combined with the idea that (x,y^2, z^2) is a primitive pythagorean triple to do what you want

[steep raptor]

@light flicker I just want to solve it for all integers. And why is (x, y^2, z^2) a primitive pythagorean triple? How can we ensure that they share no common divisors

I am not familiar with prmitive pythagorean triples so if there is any theorems related to them i wouldnt know

[light flicker]

By the usual way, if x and y share a common prime factor, then z shares the same prime factor and we can factor out this prime factor to get a smaller solution

Yeah, I was thinking of using the usual parameterization of primitive Pythagorean triples

[steep raptor]

I don't know most of the technical terms, for reference, I'm taking the Intermediate Number Theory class on AoPS. I don't know what parameterization is, although I know it's a precalc subject and I'm reading that.

[sacred junco]

@light flicker do u know any good number theory book

[light flicker]

Try reading Silverman's a friendly introduction to number theory, or maybe the Theory of Numbers by Hardy and Wright

[sacred junco]

Thx

[wooden crater]

anybody know how to show that the map $\mathbb{N}^2\to\mathbb{N}$,$(i,j)\mapsto\frac{(i+j)(i+j+1)}{2}+j$ is bijective, where $\mathbb{N}={0,1,2,\dots}$? Finding inverse function is equivalent to showing that each natural number $n\in\mathbb{N}$ can be written uniquely as $n=m(m+1)/2 + j$ where $m=\left\lfloor\frac{\sqrt{8n+1}-1}{2}\right\rfloor$ and $0\leq j\leq m$ so that we can take the inverse map as $n\mapsto (m-j,j)$.

[sterile pumice]

c squared

[wooden crater]

having trouble showing that the map is injective as well

[prime sparrow]

Isn’t this just the usual diagonal map?

[wooden crater]

pretty sure

ive never seen the proof that this is bijective tho. been trying to do it on and off now for a while. ran out of ideas

[prime sparrow]

Well, this should be pretty easy now that we have the intuition, right? I mean we just have to show that n(n+1)/2 differs from (n+1)(n+2)/2 by n+1 so two things on different diagonals will have to be different, and two different things on the same diagonal are different

And surjectivity should be similar I hope

[wooden crater]

im not really sure im following tbh. intuitively it makes sense, that things on different diags are different and diff things on the same diag are different, but im not sure why showing that the two terms differ by n+1 implies injectivity

oh wait. the lexicographic order on N^2 is a total ordering on N^2. any function between two totally ordered sets that is strictly monotone is injective.

this map is strictly monotone im pretty sure

[wooden crater]

what makes you say surjectivity should be similar?

[wooden crater]

i guess i don't need to be that specific with my choice of m, although it would be nice to know how to get that.
there is a largest triangle number m(m+1)/2 such that m(m+1)/2 <= n.
the distance between m(m+1)/2 and n is at most m,
so there is an integer j between 0 and m such that n = m(m+1)/2 + j, hence the map is surjective.

oh but m(m+1)/2 <= n is equivalent to (2m+1)^2 <= 8n + 1 so m should be the floor of the stuff...

[prime sparrow]

Oh sorry, when I said similar I meant it in an informal way, ie: we should be able to “translate” the picture of the diagonal mapping into the algebra. Sorry for the late response

[wooden crater]

no worries. i think i figured it out

[prime sparrow]

Nice

[unkempt void]

the existence of prime factorisations doesn't use the infinitude of primes, so it's not circular

[unkempt void]

(Also I think people usually view the original proof as not a proof by contradiction in a sense?)

Like instead it's a sort of way to generate arbitrarily many primes

[gleaming juniper]

Maybe express the proof slightly differently... Suppose there are only a finite number n of primes given by p_1, p_2,.., p_n. Let P = p_1 * p_2 *** p_n + 1. Each of these primes p_i leave a remainder of 1 when P is divided by p_i, so P is not divisible by any of these primes. But P > 1, so P has a prime factor which must be one of these primes. This is a contradiction.

[iron surge]

well really since $p_i\nmid P$ for each $i\in{1,2,3,\dots,n}$, and since $1<P\in\mathbb N$, it must be that $p|P$ for some prime $p\notin{p_1,p_2,p_3,\dots,p_n}$. But this means ${p_1,p_2,p_3,\dots,p_n}$ isn't the complete of primes, a contradiction. Therefore, there are infinitely many of primes.

[sterile pumice]

logician

[iron surge]

your proof is solid! I'm just showing another way to prove the infinitude of primes

[gleaming juniper]

cool. 🙂

[iron surge]

@sacred junco see above^. Maybe try proving that "for every integer k>1, q|n for some prime q." in advance so you can cite it in the proof for the infinitude of primes

[gleaming juniper]

We can devise many different proofs for it. lol

[iron surge]

Yes, it's good to see different proofs for it

[unkempt void]

the Euler product proof is really nice imo

[wise seal]

it also matches with these

terrible explanation of it but i cant really condense a discord conversation down to much (discovered it with a friend)

started off with thinking about twin primes and 'triplet primes' (only ones being 3->5->7) and how to make them exist properly

easy answer is just make the gap between them longer

it needs to always be even tho (otherwise it cant lead to a prime) so i just chose multiples of 2

i think it stops at 41 because after that primes arent dense enough to support the small gaps needed

although there are some long sequences sometimes like 26681->26683->26687->26693->26701->26711->26723->26737

but in that range the sequence has to be thousands long to be maximal so i dont think its possible

[winter bear]

ok so this is interesting

apperantly these are related to heegner numbers

so whenever the ring of integers in Q[sqrt(1-4p)] is a UFD

you have the x^2+x+p be prime

for 0<=x< p

[wise seal]

i dont understand any of that the most advanced class i took was alg 1

[winter bear]

this is a very hard problem in general.

[jolly mural]

TGR are u in school?

[wise seal]

nope lol

[winter bear]

but these are the only solutions

[wise seal]

it was years ago

[winter bear]

I can tell you that.

[wise seal]

how is something that complex attached to prime gaps?

[winter bear]

prime gaps are very complicated.

Finding the patterns of the gaps has taken up a lot of research in number theory

I can tell you what to look into if you wanna understand this more

[wise seal]

nah i'll mess around in the less complex space for now

what if i try with powers of 2 instead

[turbid orbit]

p, p+2, p+2+4, p+2+4+8, p+2+4+8+16, etc. all being prime? 2^n mod 6 alternates between 2 and 4, so even if it's impossible, it's not trivial

[wise seal]

hi yto

[turbid orbit]

hi

so that's p+2^n-2 for n>0

[wise seal]

not much

[turbid orbit]

it doesn't seem to go very far with low values, but at least it's not capped at p-1

so maybe there is an infinite sequence somewhere

[wise seal]

?

which one isnt capped

[turbid orbit]

the one with powers of 2

[wise seal]

it looks capped to me

[turbid orbit]

is there an obvious proof that for every prime it's finite?

[wise seal]

no but ive hit the forties and theres no sequence more than 7 long

[turbid orbit]

with p+n^2+n, it was obvious (n=p-1 implies p+n^2+n=p^2 which isn't prime)

here, you only have experimental evidence, which doesn't really mean much in math

since there are still infinitely many cases you'd have to check

[wise seal]

what about the 2^prime thing i suggested

did that fit mod 6

[turbid orbit]

no

[wise seal]

then wouldnt 2^n not fit either

[turbid orbit]

2^n does fit it, because it's alternating

2^prime is just weird

and obviously not alternating

[wise seal]

2^n eventually includes all 2^prime tho

[turbid orbit]

yeah but there's other stuff in between which fixes it

like

2^2 mod 6 is 4, 2^2+2^3 mod 6 is 0, 2^2+2^3+2^5 mod 6 is 2

but if you add 2^1, it shifts to 0, 2, 4

and if you add 2^4 (but only to the 2^1+2^2+2^3+2^5), it becomes 0, 2, 2

so it fixes the 4's

because 2^n mod 6 alternates between 2 and 4, so if you add the first few up you always get 0 or 2, but if you skip some then you also get 4's

[wise seal]

ok

[turbid orbit]

anyway i'm not that good at math, but i'm guessing you smart people have some UFD ring stuff that proves or disproves this

[wise seal]

so far longest under the thousandth prime is 1607->1607->1609->1613->1621->1637->1669->1733->1861->[2117] and thats a far cry from the 1607 length needed

[gloomy hare]

My first thought was to add the two to get the linear combination $3x+2y=1$ and use the Euclidean algorithm, but that gave me $x=1$ and $y=-1$ which makes the sum congruent to 0.

[sterile pumice]

modus ponens

[prime sparrow]

Just because x=1 and y=-1 satisfies 3x+2y=1 doesn’t mean it is a solution to the original equation. (Indeed plugging those values into the equations you see that it is wrong, 3/=5 mod 11 for example). This maybe more useful: multiply the first equation by 4, and the second by 6.

[gloomy hare]

Oh wow, that's simple. Thank you.

I see the motivation, I think, 12 is congruent to 1 modulo 11, so it effectively gives you x+y.

I'm a dumb ass, thanks.

[prime sparrow]

Yep, that was the motivation.

[iron surge]

You're welcome @sacred junco

[light flicker]

@turbid orbit @wise seal a little late, but the 2 power case is finite in kind of the same way that the multiples of 2 case is finite. You have that 2^p - 2 is always divisible by p due to something called Fermat's little theorem

[wise seal]

finite as in there are only a few cases of maximal sequences?

[light flicker]

Ah sorry, this is only showing that it's always capped at p-1

[wise seal]

whats capped

[light flicker]

The sequence

[wise seal]

ah

yeah that makes sense

[light flicker]

I think it's hard to say whether or not there are infinitely many maximal sequences. If there are, this implies that 2 is a primitive root mod p for infinitely many primes, which is a unknown (but suspected to be true) open conjecture

[wise seal]

suspected to be true?? i highly doubt it is true (intuitively primes cannot be that dense (a sequence has to be k long to be maximal and ive searched up to k=10,000,000th prime)) but who knows what goes on in the numberscape

[light flicker]

I think you've misunderstood

This implication only goes one way, not necessarily the other way

[wise seal]

ah

so if there are infinite maximal sequences, that is true but if its true that doesnt mean theres infinite sequences

[light flicker]

Yeah exactly, I'm just highlighting why answering such a question might be difficult

I do agree that there are probably only finitely many maximal sequences, and you can probably confirm this idea through some density argument using the prime number theorem

[wise seal]

do you think its possible that there exists an only-even sequence that does have infinite maximal sequences

a_k = 2 doesnt cause twin primes only come in pairs

a_k+1 = a_k+ 2k probably doesnt (thats the one i searched)

[light flicker]

I'm not super sure what you mean by an only even sequence

[wise seal]

the difference between the primes has to only be even otherwise it is guaranteed to stop at the first odd

the difference between primes i was searching was 2,4,6,8,...

17->19->23->29->...

the difference between them is only even

[light flicker]

I understand this

I'm just not sure what you're looking for

Because you can just trivially choose the even sequence 2,2,4,2,4,.. where the kth term is the difference between two primes and you'd have an infinite only even sequence

[wise seal]

oh

[heady basalt]

Take two coprime integers m and n. A theorem (sometimes called the Chicken McNugget Theorem or the Nugget Theorem) states that mn-m-n is the largest integer that can't be expressed as a nonnegative linear combination of m and n, i.e am+bn with a,b nonnegative

but is there a nice way to identify which of the numbers below that threshold cannot be expressed in this way?

With 5 and 7, these numbers are 1,2,3,4,6,8,9,11,13,16,18,23

[heady basalt]

Found a way ; i'll use the 5 and 7 example

We want to check if n can be expressed in such a way

If n ≡ 0 [5], yes

If n ≡ a [5] then there must be k such that 7k ≡ a [5]. If n >= 7k, then yes.

[wise seal]

hi Syst3ms

a lot of overlap with here and GS

although that isnt very suprising

[heady basalt]

yup

[heady basalt]

Also, I think I stumbled upon an extended version of this theorem, but I didn't look into trying to actually prove it

If gcd(m,n)=d, then the largest multiple of d that isn't expressible as a nonnegative linear combination of m and n is mn/d-m-n

actually, the proof is simple

Let m'=m/d and n'=n/d

Then m'n'-m'-n' is inexpressible as a nonnegative linear combination of m' and n'

BWOC suppose there exist nonnegative a,b s.t am+bn=mn/d-m-n. Then, dividing by d, am'+bn'=m'n'-m'-n'. Contradiction.

The maximality is easy to see from that

[gloomy hare]

My approach to this problem was to think about how many solutions you would have in a period which intuitively seems like 2 (up and down). Then calculate how many periods of cos(97x) are in [0,1] and multiply that by 2 because cos(x) is even. This gets me 60, if I did my math right, but that doesn't seem to be right.

[heady basalt]

Why did you multiply by 2

It's restricted to positive solutions

[gloomy hare]

Oh shit

So that makes my answer 30

[heady basalt]

And as for why it would be 31 instead of 30, i'd wager some weird rounding thing because 2π/97 isn't the nicest proportion

[gloomy hare]

right right

OK, so my approach wasn't stupid, I guess

[heady basalt]

no, it was quite right in fact

[gloomy hare]

OK thanks for the help

[heady basalt]

don't just ping people, even if they were active recently

[cinder dagger]

can someone give me an eli5 explanation to eulers approach at the basel problem?

[wooden crater]

sin(x) can be expressed as an infinite product in terms of x and when you expand out the product looking at all of the terms with an x^2, the answer just pops out

[unkempt void]

(I think sin(x)/x rather? Or equivalently x^3)

[wooden crater]

ye

[unkempt void]

I wrote up an explanation but I'm not sure it's going to be much better than what's already online :/

[tawdry matrix]

I recently wrote this one up as an extension problem for my calculus class. It's broken down into problems for you to try first.

[potent basalt]

@tawdry matrix are u a teacher?

[urban peak]

anyone have an idea on how to prove n!m! = \pm modp where n+m=p-1

[light flicker]

Do you know the proof of Wilson's theorem?

[urban peak]

no

[light flicker]

Looking at that might give you an idea on how to do this

[urban peak]

seems a bit similar but not really sure how to approach this question

[light flicker]

It might help to see that since n + m = p-1, you can write m! as (-(n+1))(-(n+2))...(-(p-1))

[prime sparrow]

I think we can also just directly use wilson’s theorem because n!m! divides (p-1)!

[tawdry matrix]

I sure like to think so!

[potent basalt]

do you have any websites that could be useful or study tips for algebra 2

[potent basalt]

its my freshman year in highschool and i am just used to in person school

[tawdry matrix]

I'm a uni teacher in Aus, but lots of people here who are learning "algebra 2" equivalent seem to like https://www.khanacademy.org/ still.

[urban peak]

how can i show that if s = r mod t then a^r = a^s mod m where (a,m)=1 and a has order t mod m

[tender shore]

Straightforward by definition of order of a mod m,
ord_m(a) = t <-> a^t == 1 (mod m)
and from s == r (mod t) we get s = k*t + r for some integer k
you can proceed easily from a^s (mod m)

[elder gate]

can someone help with this? (I assume it belongs here)

[sweet mist]

its definitely not but thats alright. Ill answer in questions-0 since this isn't number theory

[haughty harness]

I suppose it belongs to calculus

[urban peak]

anyone know how to show that for a set {ar+bs where r and s are Gaussian integers} contains a gcd of a and b?

think it might have something to do with smallest norm but idk

[light flicker]

Are a and b also gaussian integers here?

[bronze raven]

hi which is the correct answer?

[swift shard]

They're telling you, I believe?

[bronze raven]

?? the same qn has a different answer

[swift shard]

Oh weird they're both the same question haha

I agree with the first picture

[bronze raven]

oh okay 👍

[sacred junco]

Automorphic numbers are very pretty

If you don't have a lot of number theoretic tools that come to mind try to see if you can find a pattern between the automorphic numbers (excluding 0 and 1) for modulus power of product of two distinct primes

If you have more tools try to code up the explicit formula generating them for arbitrary modulus power of any product of distinct primes

They're very natural as you might discover them by asking "huh why do the last digits remain the same when I multiply certain numbers?" (modulus 10^k in base 10 ofc here)

[urban peak]

no just r and s are gaussian

[light flicker]

So a and b are just integers?

If so, then the set {ar + bs where r and s are integers} is a subset of the set you're considering, and this set contains a gcd of a and b by Bezout's identity

[urban peak]

does Bezouts identity apply to gaussian integers too? i was thinking the same thing but idk if it is directly applicable

[light flicker]

It doesn't need to

The integers are also gaussian integers

[livid raven]

I have a multiplication: Z/nZ - >Z/nZ, x to kx and its bijectiv iff gcd(k, n) = 1. Now the proof says in one direction: assuming k and n have a common divisor m. So k(n/m) is element of nZ so k(n/m) =0=k*0 mod n, so n/m is congruent to 0 mod n.

Why n/m has to be non 0 regarding our assumptions?

Modulo 0 makes no sense and m has to be non zero. But can a division n/m not reach 0 in modulo?

I have no example... I miss the reason.

[light flicker]

Maybe you can take a picture of the proof? What you've written down doesn't make much sense to me

@livid raven

[livid raven]

The proof was in German.

[light flicker]

hmmmm

My best guess from what you've said

is that they're arguing that if gcd(k,n) > 1, then the map x to kx is not bijective

[livid raven]

yes

[light flicker]

To do this, they're showing that n/m maps to 0, and obviously 0 maps to 0, so it cannot be bijective

[unkempt void]

(könntest du das Bild teilen, bitte?)

[livid raven]

I have the intuition. You mean more than one element maps to 0 is the idea?

[light flicker]

yes

[livid raven]

Wait.

[light flicker]

and to do this, we must show that n/m is a different element from 0

[livid raven]

My problem is how can I know n/m could possible hit other elements than 0?

🦢It might be stupid question...

[light flicker]

I'm not really sure what you're asking

[livid raven]

Will delete this any moment.

Idk how to tell my question.

With modulo I get always problems...because I have to be careful its not like non modular algebra...

[unkempt void]

ah okie that clears it up

this is more of a contradiction: if k,n have a common factor, then k.(n/m) = 0 = k.0 mod n. if the map were invertible, we would have n/m = 0 mod n, but this is not the case unless m = 1

@livid raven

[livid raven]

Omg

unless m=1... Made me think of n/m... So we have not a multiple of n anymore. It cant be 0

?

[unkempt void]

genau, 0 < n/m < n

[livid raven]

Okkk

Thank you both 😭another day I miss the simplest idea...

[unkempt void]

np!

tbf, the explanation was not the clearest in the world imo

[livid raven]

I will look in 20 mins again 😂to understand it with the intuition. But need a clear head rn.

[unkempt void]

yeah dww

maybe examples might help? consider the map φ: Z/4Z -> Z/4Z defined by φ(x) = 2x

φ(2) = 4 = 0 = φ(0) mod 4, so φ is not injective (and hence not invertible)

that's the key idea ig

[livid raven]

Before I read urs. I just got the intution i think. Since n/m is smaller n it cannot be the zero element. So n/m it has to be a nonzero class element that also projects to 0.

[unkempt void]

tbf we can assume n is non-zero anyway

[livid raven]

Yes I know that potato. I also checked with mod 4 and tried multiplying by 3 or sth.

Like I understand the statement.

If n can be zero the entire modular thing makes no sense I guess.

Idk what mod 0 is.

[unkempt void]

yee

me neither lmao, ig you could view Z/0Z as just being Z/{0} iso to Z

[livid raven]

_too advanced 😂I cant follow _

I dont get it srsly. XD but maybe in future.

What is Z/{0}

[unkempt void]

i guess the elements of Z/{0} are x + 0Z = {x} as x varies across the integers so it's naturally isomorphic to Z

quotienting by the identity just gives smth isomorphic to the original group

[livid raven]

I thought sth like all Z but no 0 included.

[swift shard]

Have you learned quotient groups before? If not, you'll understand this notation soon

[livid raven]

Ah. We call it Nebenklassen.

[swift shard]

That sounds sick

[unkempt void]

TIL

oh, Nebenklassen must be cosets, which are the underlying sets behind quotient groups

Ah, Quotientengruppe = quotient group

[hushed loom]

would analytic number theory go in this channel or #advanced-number-theory ?

[swift shard]

Analytic usually falls under advanced, but use your best judgement

[hushed loom]

number theory is the one field where the difference between elementary and advanced feels really fuzzy to me

[tranquil island]

Help pls

[merry knot]

Anyone interested in doing "Elementary Number Theory" by David M. Burton?

[sacred junco]

Anyone interested in doing "A Classical Introduction to Modern Number Theory" by K. Ireland and M. Rosen?

[urban peak]

trying to prove that if F_n is prime then n is prime where F_n is the nth fibonacci number

i noticed that for m,n where m|n then F_m | F_n which makes the problem easy but feel like there a shorter way then proving the first part

[wooden crater]

n : 0 1 2 3 4
F_n : 0 1 1 2 3

here F_4 = 3 is prime but 4 is not prime

how is are you defining the fibonacci number here/ how are you indexing the sequence?

[merry knot]

That's in the future for me

[sacred junco]

The future is near.

[merry knot]

Far far away

[merry knot]

How to prove a + b <= ab - 1?

[sacred junco]

you can't

[merry knot]

They used this while proving another problem. How can they be sure a+b <= ab-1?

when a,b>=2

[sacred junco]

idk its false for a=b=0

please specify when askign about problems

[merry knot]

I feel hurt. I forgot the condition

Bye

[sacred junco]

Bye

[merry knot]

If anyone can help me understand how a + b <= ab - 1, when a,b>=2, I'd really appreciate it

[sacred junco]

its not even true when a=b=2 but ok

a+b <= 2max{a,b}<=ab

[weary sundial]

There's a whole non-empty interior of it not being true

It's true when a,b>=sqrt(2)+1

[merry knot]

This is actually beautiful, thank you. It opened some new kind of thoughts in my mind

[merry knot]

This looks very interesting, I'll have to think about it

[urban peak]

Sorry forgot to mention I was proving it for n prime besides n=4

[wooden crater]

breh lol

[quartz needle]

could someone please explain how is

proved by

[light flicker]

@quartz needle What exactly are you confused by?

[quartz needle]

b = a + sm
means that a is equivalent to b mod m, that is
a mod m = b mod m
definition of mod: r = dividend mod divisor, as in
given some division, mod returns the remainder from that division, e.g. 11/3 = 3 * 3 + 2
so
b = a + sn
means, that the remainder of both a/n and b/n is the same

now,
a + c is equivalent to b + d (mod m), says that the sum of the remainders of 4 different numbers is the same, yes? @light flicker

that is, the modulo of the sum of a and c, is the same as the modulo of b and d

anyways
b + d = (a + sm) + (c + tm) = (a + c) + m(s + t)
says that the sum of b and d is equal to the sum of a + sm (=b), and c+tm (=d)

[light flicker]

Yes thats correct so far

[quartz needle]

okay, so how does saying that something is equal to itself prove that a + c is equivalent to b + d (mod m)

also what's up with just using (mod m) at one side rather than both? shouldn't it be
a + c (mod m) is equivalent to b + d (mod m)?

[light flicker]

Instead of thinking of this in terms of remainders when dividing by m, it might be easier to think about it in terms of the Theorem 4 that they use

That theorem 4 should say that a = b (mod m) if and only if a = b + sm for some integer s

So what they prove there at the end is that b + d = (a + c) + m(s + t)

which, by Theorem 4, exactly means that b + d = a + c (mod m)

[light flicker]

Right

[iron surge]

all they did @quartz needle was take out congruence modulo notation and replace it with equivalent equations and then just did algebra

[light flicker]

To answer your other question, we usually write a = b (mod m) and not a (mod m) = b (mod m) because mathematicians don't really think of a (mod m) as looking at the remainder of a when you divide by m

[quartz needle]

so in this sense
a = b+d
b = a + c
s = s + t
lol?

[light flicker]

I'm not sure where you're getting those equations from

[quartz needle]

a = b (mod m) if and only if a = b + sm for some integer s

b + d = (a + c) + m(s + t)

[light flicker]

Uh, I still don't see how you get those equations from that

This is an equation of integers, the integers on both sides are the same

[quartz needle]

b + d = (a + c) + m(s + t) (mod m)
lhs = rhs (mod m)
lhs = a = b+d
rhs = b = a+c + m(s+t)
rhs can be rewritten as b + sm
so b = a + c,
m = m
s = s + t

[light flicker]

For example, you can take like a = 1, b = 3, c = 2, d = 6, with m = 2 and see that b + d = (a + c) + m(1 + 2)

Yeah, this isn't an equation mod m. This is a regular old equation

I'm not really sure what you mean by lhs and rhs

[quartz needle]

left hand side, right hand side

[light flicker]

Sure, but what do you mean by that here

how is lhs = a?

[quartz needle]

i've made the two equations equal to each other

guess it's wrong?

[light flicker]

Just because a = b (mod m) and b + d = a + c (mod m) doesn't mean you can say that the two lhs's are equal

its like saying that since 3 = 2 + 1 and 5 = 3 + 2, then 3 = 5

[quartz needle]

k

maybe

[quartz needle]

could you elaborate on this

[light flicker]

Mathematicians usually think of (mod m) as saying that the equality is true (mod m)

Rather than thinking of it as finding the remainder of a when dividing by m and finding the remainder of b when dividing by m and seeing that they're equal

This line of thought is valid of course, its just that it doesn't generalize well to other situations where we do similar things

In fact, most people tend to use theorem 4 as the definition of a = b (mod m), rather than proving it as a theorem

[quartz needle]

so what's the difference?

[light flicker]

I'm not sure what you mean by that

[quartz needle]

?

equality is true (mod m)

[light flicker]

Yeah so, the integers are nice because there's always a smallest remainder in some sense

[quartz needle]

this means that if each side of the equality is (mod m)

[light flicker]

And that's kind of the canonical remainder we choose, but this doesn't hold true in general

[quartz needle]

then the equality is true

yes/

[light flicker]

Kind of

The problem is that you're thinking of (mod m) as something that can act on an integer a and give you back the remainder

And computer scientists usually think this way too (this is the remainder operator % in many languages)

But mathematicians don't tend to think of it that way

And the reason for this is like I've been saying, it just doesn't generalize to other settings very well

[quartz needle]

how do mathematicians think of it

[light flicker]

They think of it basically in terms of theorem 4

That a = b (mod m) if and only if a - b is a multiple of m

This allows you to avoid all the division stuff and work solely with multiplication, which is nice in settings where we can't always divide

Do you know what equivalence relations are?

[quartz needle]

i guess, but i would appreciate if you'd remind me

[light flicker]

They're kind of a way to generalize equals means

They basically say that an "equality" should satisfy the properties that a = a, if a = b, then b = a, and if a = b and b = c, then a = c

This isn't super important, but I just wanted to say that mathematicians usually think about (mod m) as introducing a new equivalence relation or "=" that is different from the usual =

[swift shard]

Nice exopunks pfp Jiagu

The way I think of it:

• (mod 4) is not a function that takes a number and returns a remainder.
• Instead, I put (mod 4) at the end of the line to signify that we're working in mod 4 arithmetic.

In mod 4 arithmetic:
9 ≡ 17 because you can get from one to the other by adding 4 multiple times.
-2 ≡ 6 For the same reason. -2 + 2(4) = 6.

This has a few advantages. You can freely sub in one number for another at any time:
(346)(3234) ≡ (1)(-1) ≡ -1 (mod 5)
Notice I didn't have to to the awful multiplication, I instead swapped each for easier replacements.

[quartz needle]

okay, so I really understand what mod means now, but I still don't get

[light flicker]

What exactly don't you get? They're just using Theorem 4 repeatedly. At the end, they get that b + d = (a + c) + m(s + t), which, by Theorem 4, means that b + d = a + c (mod m)

[quartz needle]

well, you've denied that line of thought before, albeit I haven't really expressed myself that well

Thank you all

[light flicker]

I'm not really sure where I denied that line of thought, but I apologize if I made it seem that way

[quartz needle]

why is it

a mod d = a - d
when the remainder is equal to
a -d(floor(a/d))?

i mean, it only makes sense in the context of

because if something divides a-b, then it necessarily must divide a-b(whatever)

@empty owl

[empty owl]

yo

Im looking over it now

[quartz needle]

at any rate, idk why it is the case that

a is congruent to b modulo m if m divides a -b
i'd guess that
'a is congruented to b modulo m if a modulo m = b modulo m'
and have no idea how to derive the former from the latter

@empty owl do you have any ideas?

<@&286206848099549185>

[quartz needle]

lol

[iron surge]

a is congruent to b modulo m if and only if m divides a-b. This is just a definition.

@quartz needle

Since it’s a definition, we don’t need to wonder why it’s the case that a is congruent to b modulo m iff m divides a-b

[quartz needle]

it is stated as a theorem, not a definition

[iron surge]

That should be an if and only if theorem if it is stated as a theorem

[quartz needle]

nvm

it indeed is stated as a definition

at any rate

[iron surge]

Yea it’s a definition fosure

[quartz needle]

both this and the aforementioned definition are true, how could it be?

[iron surge]

What other definition are you talking about?

[quartz needle]

dividend mod divisor = remainder = a -d(floor(a/d)), where a = divident, d= divisor

[empty owl]

For that, think about the Division algorithm

[urban peak]

Anyone have any ideas on how to prove that the pisano period (fibonacci sequence mod n), pi(n), is always even for n>2?

wikipedia has a proof but uses generalized linear groups which i know nothing about

[quartz needle]

I will never understand this definition

Why is a -b

Why isn't it b-a

Why isn't it anything else

[light flicker]

you can replace a - b with b - a, they're the same

The idea is that if a and b have the same remainder when you divide by m, then a - b (or b - a) will have no remainder when you divide by m right?

That's the same as m dividing a - b (or b - a)

@quartz needle

[quartz needle]

This means that it might as well be a+b, no?

[light flicker]

No

Try proving the idea that if a and b have the same remainder when you divide by m, then a - b will be divisible by m

[quartz needle]

Why? If m | a and |b then m |a +b, no?

That's the idea behind a-b, no?

[light flicker]

That's true, but we're not saying that m | a and m | b

We're just saying that a and b have the same remainder when you divide by m

[quartz needle]

Oh right

[light flicker]

The point is that when you subtract a - b, the remainders cancel out and you get a remainder of 0 basically

[quartz needle]

How?

[light flicker]

Write out the definitions of what it means to have remainder r when you divide by m, figure out what the remainder of a - b must be

[quartz needle]

give me a sec I'm at school

[quartz needle]

I will take some time to respond

a = bq + r
a = dividend
b = divisor
q =quotient
r = remainder

means
a mod m = b mod m
which is the same as
a = b (mod m)

a mod m by definition is a remainder of a divided by m

r = a - q(floor(a/b)
so
a mod m = a - q(floor(a/m)

by contradiction:
(contradicted conclusion) m doesn't divide a -b, (premise) while not dividing a and b
@light flicker good so far?

[light flicker]

No, I'm not really sure why you're trying to look at a divided by b? I'm also not sure at all how you're coming to a contradiction

[quartz needle]

Right, so existence of modulo doesn't imply that the given thing is not divisible by something, as the remainder may be equal to 0.

As for the contradiction, I'm merely setting up the way I'm going to go about proving this

[light flicker]

The premise isn't that m doesn't divide a and b, the premise is that a and b have the same remainder when you divide by m

[quartz needle]

alright i'm back from school

Proof by contradiction
Premise (the negation of the 1st conclusion):
m doesn't divide a - b
Conclusion
a mod m = b mod m

a = bq + r
a = dividend, b = divisor, q = quotient, r = remainder
b = cd + e
b = dividend, c = divisor, d = quotient, e = remainder
which means that

a - q(floor(a/m) = b - d(floor(c/m)

now, how do I prove that this true (conclusion), whereas the premise false?
@light flicker

[light flicker]

Again, I'm not really sure what you're trying to do

Like why are you dividing a by b? Why are you dividing b by d? What is d in the first place?

[quartz needle]

?

that's just the definitions

[light flicker]

I mean sure

I agree that you can say this. I'm just not very sure why you think it'll help

The point is you want to look at the remainders of a and b when dividing by m

Aka you want to write a = mq + r

[quartz needle]

a - q(floor(a/m)

b - d(floor(c/m)

remaindes are equal, so

a - q(floor(a/m) = b - d(floor(b/m)

[light flicker]

You want floor(b/m) on the right but sure

So I'm not really sure why you write b = cd + e when because you want to write b = md + e

[quartz needle]

it's just notational, the formula for the division algorithm is
a = bq + r

[light flicker]

And rather than writing this in terms of floor. You can just say that since the remainders are equal, you have that r = e

[quartz needle]

rather than pointlessly differentiating, i made it just as 'irrelevant'

[light flicker]

I mean sure, but you're dividing by a by m, not b

[quartz needle]

yeah, ik, it's just to show you that i'm using the division algorithm, as for *, you might as well do

a - q(floor(a/m) = r
b - d(floor(c/m) = e,
I didn't do so because it's the same thing anyways

[light flicker]

So you know r = e, so now what happens if you divide a - b by m

[quartz needle]

a/m - b/m

i don't know what else to do

maybe
a/m = (mq + r)/m = q + r/m
b/m = (md + e)/m = d + e/m
but I don't know how that helps me

[light flicker]

Plug those in

And remember that the remainders are equal, in other words r = e

[quartz needle]

plug those in?

into what?

[light flicker]

You're looking at a/m - b/m

And you know that a/m = q + r/m and b/m = d + e/m

So a/m - b/m is equal to what

[quartz needle]

q + r/m - d - e/m
is that what you mean?

q - d + (r-e)/m lol

[light flicker]

Be careful

Check your arithmetic

[quartz needle]

anyways

m divides r -e

so conclusion is true

q.e.d?

[light flicker]

I mean, sure

r = e so r-e is zero

[quartz needle]

r = e wasn't proved?

[light flicker]

Yes it was

[light flicker]

.

[quartz needle]

'you know'

i haven't proved it though

[light flicker]

Remember that r and e are the remainders. Our assumption at the very beginning was that the two remainders are equal

[quartz needle]

i mean

i've proved the conlcusion of this proof

and this proof asserts that remainders are equal

so i guess in that sense

[light flicker]

What no

I don't really know what you're saying

[quartz needle]

oh wait

i wrote it correctly

i've proved the premise

because it's
m divides a -b -> a is congruent to b

so i'm doing direct proof

[light flicker]

Okay sure, I was thinking that we were doing the other direction but this is fine too

[quartz needle]

okay, so the question remains

[light flicker]

You still have to be a little careful. You've proven that m divides r - e, but this doesn't show that r = e

[quartz needle]

how do i prove that
a = b (mod m) or equivalently
a mod m = b mod m

[light flicker]

It depends on which definition of mod you're using

[quartz needle]

a mod m = a - q(floor(a/m) = r
definition: a mod m = the remainder of a/m

[light flicker]

Yeah, so you need to show that r = e

You've shown that m divides r - e

[quartz needle]

I don't know how to, which is why I'm asking

[light flicker]

You should go back and look at the definition of division

In particular at what properties the remainder must satisfy

[quartz needle]

remainder must be >= 0

oh right

so since r - e = e - r

2r = 2e
r =e

or equivalently
'as the difference of remainders must never be equal, this must mean that neither e > r (in r - e case), and e < r (e-r case), so by the trichotomy law e = r

so basic lesson i've gained from this is that i'm stupid and should comprehend the topic in one sweep, rather than come back to it ~10 times over the period of 2 days, so sorry @light flicker for wasting so much of your time

[light flicker]

I'm not really sure how you're getting that e-r = r-e

[quartz needle]

because
(e-r)/m = (r-e)/m
from

btw

why is it a definition and not a theorem?

theorem is a statement that can be shown to be true

this can be shown to be true

[light flicker]

I don't see how you're getting this

This is one way to define = (mod m)

Like I said last time, you can take either definition and prove the other as a theorem

[quartz needle]

Are all numbers divisible by m congruent to each other mod m?

[unkempt void]

by definition, they are all cong to 0 mod m, so ye

[quartz needle]

thanks

[quartz needle]

how?

@scarlet geode

3rd is intuitive, but dunno how to prove it

[scarlet geode]

ah yes

[quartz needle]

i understand the floor and ceiling functions but proofs with them seem to be tricky

[scarlet geode]

pick 2 cases: 1. n and k have the same parity
2. n and k are opposite parity

prove for each case separately

and maybe actually 3 cases

or 4 actually

hell

just do

n odd k odd

n even k odd

n odd k even

n even k even

you'll have to do this i think

note that for any even number k there exists a j integer such that 2j = k

nad for odd k you have 2j+1=k

[quartz needle]

n, k are divisible by 2
floor and ceiling functions do nothing
n/k = n/k - floor(1/k) + 1
floor(1/k) = 1
k = 1, true
otherwise false

not a tautology, so the theorem is false

where have i messed up

my best guess is

n/k - floor(1/k)

[scarlet geode]

if n and k are divisible by 2,that doesn't mean floor and ceiling do nothing

floor of 6/4 is 1

ceiling is 2

[quartz needle]

right

i'm stupid

oh fuck

i can't use that word

[scarlet geode]

ya delet

lol

[quartz needle]

ok so em

ceiling(n/k) = upper bound of n/k
floor((n-1)/k) = lower bound of (n-1)/k
which is the same as floor(n/k)
okay so
x <= n/k <= y
then ceiling = y
floor = x
so for them to be equal y-x = 1

and I have no idea what to do. I probably made a mistake somewhere @scarlet geode

lower bound of (n-1)/k
which is the same as floor(n/k)
seems suspicious but this would only be false if
floor((n-1)/k ) != floor(n/k) - floor(1/k)

rosen didn't mention it, so i just assumed that it's ok

can't think of a counterexample anyways

<@&286206848099549185>

[quartz needle]

rip

[lone goblet]

Oh 3. is a neat fact for integers, it's actually false for non-integers for example ceil(0.5/1) = 1, floor(-0.5/1)+1 = 0. For the proof I have a case n/k integer and the other is a non-integer already done, using the remainder n mod k \equiv m
@quartz needle Do you need it still or have you figured it out?

[quartz needle]

i still need it

[lone goblet]

This is false for k=2 and n=6 for example 2!=3

but I think if you were to write ceil(1/k) instead of floor(1/k) then that would be correct

[quartz needle]

but it relies on floor

this 'proof'

[lone goblet]

Yeah but in general it's false so I wouldn't use it in a proof

[quartz needle]

yeah alright

so my idea for solving this is wrong

how do i go about doing it then

[lone goblet]

Anyway I won't post the entire solution just that. I can recommend making a case analysis with 1. n/k is a perfect integer and 2. n/k isn't a prefect integer. I recommend taking a m = n mod k to assist you for the second case

[quartz needle]

perfect integer?

[lone goblet]

just integer like 6/3 = 2, basically k divides n, n mod k = 0

[quartz needle]

what's the difference between a perfect and otherwise integer

[lone goblet]

none

[quartz needle]

what's the point of your terminology then

[lone goblet]

it's just a word added to make clear the division doesnt have a rest

[quartz needle]

k

Okay so

1. n/k is an integer
   As such, floor and ceiling functions have no effect (because it isn't an actual fraction, btw what's the word for it?).
   n/k = n/k - 1/k + 1
   1/k = 1
   This means that k is equal to 1.

Good so far? @lone goblet

[lone goblet]

the floor function does have an effect because if k != 1, (n-1)/k is not an integer and gets rounded down

[quartz needle]

oh right, same mistake

well, i have no idea how to prove it

[lone goblet]

ok so a hint

[quartz needle]

proofs with these ceiling and floor functions seem to be rticky

[lone goblet]

if n/k is an integer, floor((n-1)/k) = n/k - 1

can you see why that's true

[quartz needle]

yes

intuitively

I can't prove it though

[lone goblet]

(n-1)/k = n/k - 1/k
If k = 1, then this reduces immediately, if then n >= 2, you have an integer minus a qunatity 1/k which is 0 < 1/k <= 1/2 < 1, so taking the floor if it you get n/k - 1

[quartz needle]

righg

I'm going to sleep now, I will look at it in a couple of h

[lone goblet]

ah ok good night

[chrome bluff]

So I'm working on this problem and I feel I'm a little stuck.

I could use some help getting in the right direction.
Tbh: pretty sure this approach isn't going anywhere

[light flicker]

I'm not super sure what you're starting with. You say "to the contrary" but then assume that a and b are relatively prime to n which is the same as the assumption to start with

[chrome bluff]

True, I needed to reword. I was going to assume ab was not relatively prime to n with that assumption

[light flicker]

Even if you mean ab is not relatively prime to n, this doesn't necessarily mean that n divides ab

[chrome bluff]

It seems I failed to right that down

[chrome bluff]

Yes, I noticed that issue. This approach is not going to work.

[light flicker]

I think the general idea works out though

If gcd(ab,n) > 1, then there's some prime p that divides both ab and n

Which is the same thing you get

Now apply Euclid's lemma like you did

[chrome bluff]

But does this show that a or b is relatively prime to n?

If so, do you mind explaining a little bit as to why? I am having trouble seeing it right now.

[light flicker]

No it shows the opposite actually

This has turned into basically a proof of the contrapositive statement

That if gcd(ab,n)>1, then gcd(a,n)>1 or gcd(b,n)>1

[chrome bluff]

Ah, I see what's going on now. Yeah, this will do it. Thank you

[iron surge]

A direct proof for the statement you're trying to prove uses Bezout's Lemma if that helps

[iron surge]

Pretty much @chrome bluff , you know ax+ny=bs+nt=1 for some integers x,y,s,t. So for such x,y,s,t, you can algebraically reach a point where you obtain abk+np=1 for some integers k and p. Reaching that point will show gcd(ab,n)=1

[iron surge]

This might be an interesting direction to try @chrome bluff because not only can you assume gcd(ab,n)>1, you can also assume gcd(a,n)=1. And then just prove gcd(b,n)>1.

[rugged flower]

Hi.

i tried to write it as $3(a-b)^2 +3(a-c)^2+3(b-c)^2 < a^2+b^2+c^2$ but it leads me to nothing

[sterile pumice]

Pealover

[rugged flower]

i also tried to do $8(a^2 + b^2 + c^2) < 3(a+b+c)^2$ but it leads me nowhere

[sterile pumice]

Pealover

[rugged flower]

and finally i did $11(a^2 + b^2 +c^2) < 3((a+b)^2+(b+c)^2+(c+a)^2)$

[sterile pumice]

Pealover

[rugged flower]

and now i'm running out of ideas

a helping hand would be frankly welcome

[gleaming juniper]

I tend to agree that the direct approach using xa + yn = sb + tn = 1 , where x,y,s,t are integers, is pretty straight forward. Do you need a hint?

[opal falcon]

Does anyone know how to calculate the following types of integral $$\int n^{(ax^2+bx)} dx$$

[sterile pumice]

SSK

[lone goblet]

If $\frac n k$ is a perfect integer then
[\left\lceil \frac n k \right\rceil = \frac n k, \text{ while } \left\lfloor \frac{n-1}{k} \right\rfloor + 1 = \left(\frac n k -1\right)+1 = \frac n k]
@quartz needle

[sterile pumice]

T0lgi01

[lone goblet]

I had a typo with the explanation of floor((n-1)/k) = (n/k - 1) but that should be fixable

[quartz needle]

wait a sec, it might be my bad memory, but
floor(-1/k) for n/k being an integer, means that unless k = 1, floor(-1/k) = 0

oh wait

no

because it's negative

[lone goblet]

the - is excessive

[quartz needle]

right

[lone goblet]

my argument was just that just without the minus sign

Ok so let's focus on [\left\lfloor \frac{n-1}{k} \right\rfloor = \frac n k -1]

[sterile pumice]

T0lgi01

[quartz needle]

so there are 3 cases?

n = k
n > k
n < k

[lone goblet]

no?

1. Case is k=1
2. Case is k>1

[quartz needle]

oh right

n doesn't matter

[lone goblet]

If $k=1$ then it's easy, right?

[sterile pumice]

T0lgi01

[quartz needle]

yeah, that's what you did

[lone goblet]

So if you have k >= 2, you have (n-1)/k = n/k - 1/k and because 0 < 1/k <= 1/2 < 1 and n/k is an integer, floor(n/k - 1/k) = n/k - 1

That was my argument last time

[quartz needle]

actually

why are you thinking of it as k > 1

rather than k > n-1

[lone goblet]

why should I?

The proof is perfectly fine and I see no reason why to make a case with k > n-1

[quartz needle]

i mean i think it's easier

[lone goblet]

I dont think it helps a bit

[quartz needle]

if k is greater than n-1

then you have a fraction

[lone goblet]

cool but you have to prove k smaller than n-1

and then you're stuck

[quartz needle]

right

@lone goblet wait, but
ceiling of n/k = n, no?
so you have
n = n/k - 1 + 1

[lone goblet]

ceiling of n/k is n/k

[quartz needle]

why?

0 < n/k < 1
for k > n

[lone goblet]

?

If 0 < n/k < 1 then ceil(n/k) = 1

[quartz needle]

ceiling of n/k is n/k
then ceil(n/k) = 1

[lone goblet]

You're doing things in all sorts of cases

[quartz needle]

aren't there 2 cases?

[lone goblet]

also don't split apart an if...then... sentence it has a meaning

[quartz needle]

just showed you that you are contradicting yourself

we've done the case in which k is = 1, then clearly ceil(n/k) = n/k

[lone goblet]

that was not in the proof tho

[quartz needle]

wut

[lone goblet]

dont forget we still are in the assumption that n/k is an integer

[quartz needle]

well, i had thought we already left it because it was proved, lol

[lone goblet]

Well only if you understood it

[quartz needle]

if k = 1, then
ceil(n/1) = n
floor((n-1)/1) + 1 = floor(n/1) + floor(-1/1) + 1
floor(-1/1) = -1
floor((n-1)/1) + 1 = n - 1 + 1
thus
ceil(n/1) = floor((n-1)/1) + 1

[lone goblet]

floor((n-1)/1) + 1 = floor(n/1) + floor(-1/1) + 1
this step isn't valid

the argument is floor((n-1)/1)+1 = floor(n-1) + 1 = n-1+1 = n

[quartz needle]

okay

[quartz needle]

?

you have (n-1)/k = n/k - 1/k
floor(n/k - 1/k)

[lone goblet]

I mean (n-1)/k = n/k - 1/k is true in any case so floor((n-1)/k) = floor(n/k - 1/k)

[quartz needle]

floor(n/k - 1/k) = n/k - 1

how?

i think you've made a mistake, i replicated that mistake, and you've then noticed that it's a mistake

[lone goblet]

floor(n/k - 1/k) = n/k - 1 is always true if n/k is an integer, no other dependence for n or k, no mistake about that

[quartz needle]

you haven't said anything aobut n

just that k > 1

[quartz needle]

@lone goblet

[lone goblet]

idk how to explain this to you I gave up

[quartz needle]

lol, my question is just

If floor(n/k - 1/k) != floor(n/k) + floor(-1/k), then what is it?

you are saying that it's n/k but it's pretty odd since ceiling and floor functions calculate an integer out of a fraction

i mean, if you consider some values then it makes sense

but i'm looking for proof rather than a formula

[stiff rivet]

a proof of what?

notice that $\frac{n}{k} = \left\lfloor\frac{n}{k}\right\rfloor + \frac{r}{k}$ with $r \in {0, 1, \dots, k-1}$

[sterile pumice]

Lochverstärker

[quartz needle]

and?

proof of
Floor(n/k - 1/k) = n/k - 1

[stiff rivet]

its not true. floor(4/3 - 1/3) = floor(3/3) = 1 != 4/3 - 1

[quartz needle]

that's his formula

what's the correct one, then?

[stiff rivet]

for what?

[quartz needle]

floor(n/k - r/k)

[short dawn]

i got a question

but drk where it fits

[quartz needle]

occupied

[stiff rivet]

what makes you think there is a better formula?

[quartz needle]

How do you calculate stuff like this then

[stiff rivet]

you calculate n/k -r/k first and then floor it

[quartz needle]

but for proofs

[stiff rivet]

you write it like ^ and do case work

[quartz needle]

in this case it's necessary to calculate it for the case k > 1

[stiff rivet]

there are basically just two cases, either n/k is an integer, then floor(n/k - 1/k) = floor(n/k) - 1 = n/k -1; or n/k is not an integer, then floor(n/k - 1/k) = floor(n/k)

<@&268886789983436800> see @tulip arrow

[civic elk]

Cheers

[heavy cipher]

Heyy so uh, sorry if this is a dumb question lmao but what are the rules for mod division? Like if I know a mod c and I know b mod c, is there an easy way to compute (a/b) mod c?

If c is a prime

[lone goblet]

not easy because you need to know the multiplicative inverse of b in mod c (Not easy to compute for high values of c)

[heavy cipher]

Ah damn, I see I see, wait so let's say I find the multiplicative inverse as d, would (a/b) mod c just be equal to ((a mod c) * d) mod c?

[lone goblet]

a*d mod c is enough

[stiff rivet]

actually computing the inverse is computationally pretty easy

the extended euclidean algorithm is extremely fast

[heavy cipher]

Oh yeah ahaha, that makes sense! Tysm you've been so helpful 😊

Oooh

[stiff rivet]

(just as a note)

[heavy cipher]

Yee I'll check it out for sure! That's great to hear, thank youu

[stiff rivet]

by hand it's still gross but a computer can do it really fast

[heavy cipher]

Ah, sweet 👌

Yeah I'm not going to be calculating this by hand haha, it's a coding problem

[rain mountain]

what is this question even asking for

[urban peak]

how do i show sqrt(n^2+1) = [n,2n,2n,2n,...] where [n,2n,2n,2n,...] represents the value of denominators in a continued fraction?

[chrome bluff]

That is the direction I ended up taking. It honestly just makes a lot of sense to me.

[iron surge]

nice!

[polar ruin]

They got 4.6y = 4.1 by finding inverse of 6y=1 mod 23 right?

[quartz needle]

sorry for coming back to it that late, but i can't figure out how you got

floor(n/k - 1/k) = floor(n/k)

[stiff rivet]

if n/k is not an integer then floor(n/k) < n/k, so n/k is an integer plus something, lets say q
so n/k = floor(n/k) + q with 0 < q < 1
now we must be able to write q as a fraction with denominator k, since the left hand side is given in that way
or in other words n/k = floor(n/k) + r/k with r in {1, 2, ..., k-1} (because otherwise r/k would be <= 0 or >= 1)
now n/k - 1/k = floor(n/k) + r/k - 1/k = floor(n/k) + (r-1)/k and r-1 is in {0, 1, ... k-2}, so 0 <= (r-1)/k < 1
finally floor(n/k - 1/k) = floor(floor(n/k) + (r-1)/k) = floor(floor(n/k)) = floor(n/k) since floor(n/k) is an integer

[quartz needle]

ok

but given this, do you jsut use the definition to prove that
ceil(n/k) = floor(n/k) + 1?

[stiff rivet]

yes

if n/k is not an integer, then the ceil(n/k) = floor(n/k) +1

[quartz needle]

brb i gtg

[stiff rivet]

[polar ruin]

i don’t understand modular arithmetic. So can anyone explain to me with modular arithmetic for Diophantine equations?

[stiff rivet]

how did you define modular arithmetic?

[polar ruin]

this

[stiff rivet]

that is not a definition

[polar ruin]

hmm modular arithmetic has the mod beside it?

[stiff rivet]

yes, but if you don't know how it is defined then you cannot possibly understand it?

in which case you have to learn that first

[polar ruin]

right,

hmm I haven't seen any vid explaining what modular arithmetic is, they're only showing examples...

[stiff rivet]

https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/what-is-modular-arithmetic

this isn't great but 🤷

[polar ruin]

is comp sci and normal one the same?

[stiff rivet]

alternatively use a book on elementary number theory

the introduction here is a bit odd

but its fine

[stiff rivet]

normal one? but (largely) yes

[polar ruin]

what's the easiest way to find

-a mod b?

nvm

u have to divide with - num so it is larger

[stiff rivet]

the fastest way in general is euclidean divison

[polar ruin]

it's faster than dividing normally? :v

[stiff rivet]

what do you mean by dividing normally?

euclidean division is division with remainder

[polar ruin]

it';s almost the same as dividing normally

[stiff rivet]

i don't know what you mean dividing normally

[polar ruin]

nvm , now I understand modular arithmetic...