elementary-number-theory

[tardy umbra]

you are given N (N is a number) and M(M is a range [1,m])

find two values X,Y such that gcd of X and Y should be greater than or equal to N
and absolute difference between X and Y should be maximum

Ex: N=13 , M=103
13 14 15 16 17 18 . ... .. . . . . . . . 100 102 103
different of 102 and 17 is maximum and gcd(17,102) >= 13

I understand the question but problem is that if we have a problem in which we can't find values by writing like this then there should be a generalized formula

[fervent crest]

Why should there be a generalized formula

[tardy umbra]

so that we get answer quickly

so that we don't need to do one by one checking

[fervent crest]

There's no reason such a thing should exist for any problem unless you show it

[tardy umbra]

Then I am sure there should exist one solution for this

[fervent crest]

I mean yes the solution exists but I don't think there's going to be a formula for it

The best you can do is probably write a program to find it

[tardy umbra]

Yeah I try to write a program for it but it will end up with Time limit exits

[fervent crest]

Bruh then should've specified that lmao

[tardy umbra]

What?

[fervent crest]

Doing math is very different than writing a program

Anyways

[tardy umbra]

Yeah

[fervent crest]

What you can do is let i be from N to M, then find the largest multiple of i smaller than M, let this multiple be n, then you're guaranteed gcd(i,n)≥i≥N, then just loop through all such i and n and it should work

Of course keeping track of the minimum pair

What is happening here

[sacred junco]

I think I've come up with an algorithm that loops only M/N times:

• find a=floor(M/N)
• for each 1≤i≤a find (floor(M/b)*b-b) where b=floor(M/i)
• find the index i of the maximum of the above results. Output floor(M/i)

this works because b=floor(M/i) as above is guaranteed to give the maximum difference for numbers between floor(M/(i+1)) and floor(M/i)

[fervent crest]

Lmao that doesn't work

Your program seems to output the quotient when the larger number is divided by the smaller one but sometimes it's wrong

[verbal cedar]

for a given n, is there a minimum power k>1 such that x^k=x for all x coprime to n in Z/nZ?

[inner anchor]

yes

at most its the lcm of the orders of each coprime element

[fervent crest]

Yea. Since we have a complete description of the multiplicative group of Z/nZ you can figure out the k based on the prime factorization of n

[still flare]

So yes

Everything said above is true ^

but it's way simpler

The units form a finite group, so by lagrange there is some m for which n^m = 1 mod n, and then we just choose k=m+1. The existence of a minimal such k is then trivial. You don't need to know how to calculate this in order to obtian this fact.

[fervent crest]

Well I mean yes we do know it exists but since we can figure it out why not figure it out

[upbeat berry]

is there a positive integer n where the greatest common factor of n,n+1 does not equal 1? I feel like there isn't intuitively but I'm not sure how to show it.

[latent hare]

the gcd must divide the numbers' difference, which is 1, so gcd=1

[upbeat berry]

oh interesting, I've never heard this property! let me make sure i'm getting this right: for two numbers, a & b, where b>a, the gcd is a factor of (b-a)?

[fervent crest]

It follows from the fact that if a divides b and c then a divides b-c and b+c

[ionic pier]

It’s like pulling a value out of brackets, you know, ac+bc=c(a+b), so c divides both of you can pull it out of brackets

[upbeat berry]

Oh alright, thank you! Im will take a proofs course this fall, so i’ll be learning more about this soon

[somber forum]

Hello! I need my proof of Lemma 4 to be checked. Though I have carried it out, it seems rather convoluted to me, and so I need some help to check all the details. I would be incredibly grateful for any assistance.

[heady basalt]

That does look very convoluted for something that looks like a counting argument

[somber forum]

This was just something that came to my head once I thought of the statement.

[heady basalt]

I'm sure there is a proof that doesn't require 3+ pages

let me try my hand at it

[somber forum]

Though it would be nice to have such a proof, it is more than enough to just have my proof checked.

[heady basalt]

In theory, no proof is better than another so long as both are correct. In practice, I'd rather try to work out a simpler proof than verify a long and treacherous proof

[somber forum]

(Or „proof” if it is absurd)

[heady basalt]

Verifying such a long proof would take a lot of dedication, perhaps a bit too much for me

[somber forum]

Could you at least rate the correctness and soundness of the general approach?

[somber forum]

Though I agree, perhaps I am asking for too much (no sarcasm intended)

[heady basalt]

Approaching it by induction is sound

Because induction is a sound proof strategy

Whether it's efficient is another debate

[somber forum]

Well yes, it is hard to disagree with this statement

[somber forum]

Glad you will never have to see my other proofs 😂

[heady basalt]

I did find a proof btw

Wanna see it?

[somber forum]

I would be a fool if I did not

Hit me with it

[heady basalt]

\begin{align*}\rho(m,r,n) &= |{0 \le k \le n,, k \equiv r [m]}| & \text{by definition} \ &= |{r \le k \le n,, k \equiv r [m]}| & \text{because } 0 \le r < m \ &= |{r \le k \le n,, m|k-r}| & \ &= |{0 \le j \le n-r,, m|j}| & \text{by setting} j=k-r \ &= \left\lfloor\frac{n-r}{m} \right\rfloor + 1 & \end{align*}

(i'll figure it out)

[somber forum]

Ah, yes, the eternal struggle

I know what you feel

[sterile pumice]

Syst3ms

[heady basalt]

Now, let me prove that last equality real quick

[sterile pumice]

Syst3ms

[somber forum]

I still have to get accustomed to the notation

[heady basalt]

I made a typo

[sterile pumice]

Syst3ms

[heady basalt]

Anyway, a lot of blah-blah to prove that there are floor(p/m)+1 multiples of m between 0 and p inclusive

[somber forum]

Are you talking about your proof?

[heady basalt]

yes

[somber forum]

To be fair, I would still use words to elaborate on some notational shenanigans

Much like in my original demonstration

Yours, however, does seem quite a good deal easier

Mine is just a little more…straightforward?

[heady basalt]

You're free to. I just use the language of sets because i feel comfortable with that kind of formality

My proof turns the problem statement into a divisibility statement using (rather) easy facts about modular arithmetic, then concludes by counting multiples of an integer in a given interval

[somber forum]

And my question still stands 😂. I have written just a little too much to screw it all, especially if it is correct)

Thank you, nonetheless

[heady basalt]

I don't mean any offense by this (I've done it a lot myself), but your proof is what we call "bourriner" in France

"bourrin" means "rough, brute, crude"

[somber forum]

I know that you never meant any offense. Never did I.

[heady basalt]

and "bourriner" is the fact of just bruteforcing your way through a proof or a computation by applying some method

So like, trying to prove a problem by induction and tunnel-visioning the problem using that strategy. For example, solving a problem about 2x2 matrices by just doing the full matrix multiplication.

[somber forum]

Perhaps the reason is that the purpose of this lemma is just to clear my conscience, it is a calculus problem after all

[heady basalt]

By extension, it also refers to the result of such a method : crude, very heavy, but still correct

[somber forum]

You would be laughing if you heard why I went through all this

[heady basalt]

I'm all ears

[somber forum]

The problem asks me to find the n-th derivative of the function you can see written at the first page of my proof (the very top). Knowing that it would eventually boil down to the multiplication of the exponential by the sum of the first n derivatives (including the original function, the zeroth derivative) of cos(2x), which I know to be „periodic” (period 4), just with the chain rule applied. I therefore wanted to split the sum into sums of those derivatives of cos(2x) that would produce specific functions, so that I would not have to deal with all those conditions that are dependent upon the orders of the derivatives in question. Though I am well aware that I could have just split the orders of the derivatives into sets by their congruence modulo 4 (and just write the set inclusion condition in the summation signs), I tried to dig to the bottom of this and try to express those part-sums directly, i.e. with all the lower and upper limits of summation numerically defined. This led me to this completely unrelated lemma and, concordantly, to my proof.

I know this is a very handwavy explanation of what I tried to accomplish with this lemma, but pardon me, English is my second language and it gets quite difficult to express myself with so much going on there)

This should be called „how to develop a brain tumor with coffee and Mathematics”

[heady basalt]

I see

[somber forum]

Well, I have ranted enough. Thank you!

[blazing mist]

Need help.

Trying to find a,b, and c given x values

The second picture is the original quadratic. When I’m done, I will compare the two to check if my values are correct.

[blazing mist]

Also “9” should be -9.

[pastel magnet]

Hi everyone, I'm watching a video on number theory and I was very confused because I couldn't understand why this inequality is true. The prof didn't give any explanation, so I imagine it must be very basic, but I just don't get it. Can anyone help??

video is this https://www.youtube.com/watch?v=KIvuGT5V1Fg&list=PL8yHsr3EFj53L8sMbzIhhXSAOpuZ1Fov8&index=8

[north pagoda]

it helps to timestamp these videos: your moment is from about 26:00

anyway, he spends the rest of the page giving a proof

do you not understand his argument?

[pastel magnet]

I don't understand why these two things are equivalent

[north pagoda]

what "two things"?

[pastel magnet]

the times p divides (2n n) and the left hand side of the inequality

and also I don't get why the times p divides (2n n) >= (2n n) according to his reasoning

[north pagoda]

they're not equivalent. he uses them to bound the number of times a given prime divides 2n choose n.

as he says:

"for each p^k that's ≤ 2n, we're going to get at most 1 factor of p dividing 2n choose k. so if we take ALL such powers, that makes ALL these terms equal to 1, which makes this product bigger"

the point is that we can write 2n choose n as a product of SOME of these primes

but becuase, as he argues below, each "row" is either 1 or 0

meaning each prime divides the product at most [number of rows]

we have that the "right hand side" of the inequality is AT MOST a product of all these primes

whereas the "left hand side" is a product of all these primes, but it includes ALL duplicates (i.e. all rows)

for example, if n = 6, then 2^1 = 2, 2^2 = 4, and 2^3 = 8 are all ≤ 2n

so all of those show up in the "left hand" product

and if we check:

,w choose(12, 6)

[sterile pumice]

Results provided by WolframAlpha

Click here to refine your query online
Upgrade to WolframAlpha Pro!

Requested by Namington#1983

[north pagoda]

,calc 924/2

[sterile pumice]

Result:

462

[north pagoda]

,calc 462/2

[sterile pumice]

Result:

231

[north pagoda]

as we can see, the left-hand product is more highly divisible by 2 than the right-hand side is

[sorry, slightly misstated my argument initially, fixed with edits]

[pastel magnet]

that took me a while to understand, but thank you, you explained it very clearly

[north pagoda]

the point is that:

• every prime divisor of the RHS must satisfy p ≤ 2n and therefore must appear in the LHS product
• the amount of times it could possibly divide is the maximal value of k. in my example where 2n = 12 and fixing p = 2, we get that the maximal value of k is 3, since 2^1, 2^2, 2^3 are all < 12, but 2^4 is not.
• however, if we "count" the amount of times each prime divides (2n choose n) by using the rows below, we get that it's, at most, the number of rows - and the number of rows is the maximal value of k (so if we used my example, it'd be 3)
• so each prime appears "max(k) times" in the LEFT HAND side, but only "at most max(k) times" in the RIGHT HAND (becuase it could be at most 1 + 1 + 1 + 1 + .. + 1, i.e. k*1 = k times, but some of those 1s might be 0s, so its an inequality)
• hence the LHS has all the same prime factors as the RHS, but potentially "more" of them

[pastel magnet]

that's very clear, I didn't even think of prime factorizations before you pointed it out, I guess I should've watched the lecture more carefully....anyway thank you so much

[blazing mist]

…

[wind glacier]

Prove that $b^{x+y}=b^x\cdot b^y ::\forall:: (x,y) \in \mathbb{R}$

[sterile pumice]

Amorous aka Lucifer

[wind glacier]

it isn't just for positive integers but for whole real numbers

[floral vessel]

Set theory is allowed here? Curious about the properties of A°

[heady basalt]

What do you mean by A° ? The interior of A ?

[floral vessel]

Yeeep

Why if A=R (real numbers) we get that A° is an empty set?

I mean A° is a subset of A (A=R)
And if we have numbers from 0-1 that's subset of R, so shouldn't whole R be subset of itself?

Id understand IF definition is that A° is proper subset, then if A°=R that's not allowed bcs A=A°, which doesn't make a proper subset

[heady basalt]

@floral vessel This belongs in #point-set-topology

[floral vessel]

Thank uuuuu

[heady basalt]

We don't. $\mathring{\bR} = \bR$

[sterile pumice]

Syst3ms

[floral vessel]

Why tho Xd

[heady basalt]

Tell me the definition of the interior

[floral vessel]

Well, something being inside

[heady basalt]

That's rather vague

Can you tell me the precise definition, if you have learned any?

[floral vessel]

I mean we didn't mention it Xd

Union of all subsets?

[heady basalt]

Let's move to #point-set-topology

[nova raptor]

@heady basalt how can I speak in topology? It says I have no permission

[patent escarp]

fun fact: 804792605747199194484902925779806277109997439007500616344745281047115412373646521410850481879839649227439298230298915019813108221651663659572441609408556917739149315905992811411866635786075524601835815642793302504243200000000000000000000000000000000000 is the smallest factorial number whose number of trailing zeroes is 5 mod 6.

145!

[proven thistle]

Hi, everyone!

Can someone please explain 1.2 (a) to me?

I'm currently working through Rational Points on Elliptic Curves by Silverman and Tate.

[kind fog]

props to you by the way for being so organized with the question

[proven thistle]

thanks :)

I copied down the entire problem statement word-for-word so I just want to understand how I can approach this

The determinant uses coefficients not in the form of the Weierstrass Normal Form

1. I do know that if a cubic curve has a singularity, then it implies that f has a double or triple root. This implies we can rewrite it in the form of y^2 = x^2(x+1) or x^2(x-1), or y^2 = x^3 through algebraic manipulation

My question is, how does this relate to the cubic curve determinant?

please ping me if anyone has some insight! I might be going to sleep soon :(

i've been trying the problem for 3-4 ish hours now? so i'd appreciate it ^^

[sharp atlas]

Suppose there's a point $(x,y)$ where $F = \partial_x F = \partial_y F = 0$.

[sterile pumice]

daveamayombo

[proven thistle]

mhm

[sharp atlas]

Then the vanishing of the partial derivatives gives $$2ax + by + d = 0$$ and
$$bx + 2cy + e = 0.$$

[proven thistle]

ou hmm

[sterile pumice]

daveamayombo

[proven thistle]

we know that y = 0 has to hold, right?

[sharp atlas]

And while $F(x,y) = 0$ might look unwieldy, you'll
have more luck with $$2F(x,y) - x \partial_x F - y \partial_y F = 0.$$

(Just based on playing around and seeing what would cancel)

[proven thistle]

hmm

[sterile pumice]

daveamayombo

[proven thistle]

how should we deal with d, e, 2f then?

in the last line

[sharp atlas]

The thing I just wrote -- it simplifies to $$dx + ey + 2f = 0.$$

[proven thistle]

this?

hmmm... i see

[sharp atlas]

Yup. 🙂

[proven thistle]

(2f?)

[sharp atlas]

Sorry typo -- yeah 2f.

[proven thistle]

thanks!!

[sterile pumice]

daveamayombo

[proven thistle]

btw, i have a question but

is this supposed to be high school math or...

i dunno

i got into contact with a professor and he recommended that i work through uh

the book i mentioned earlier

rational points on elliptic curves!

so i'm trying but this is harder than stuff i've been seeing in class :(

also i'm trying to create a latex document with all my work so :)

i hope it'll go well u.u

[sharp atlas]

Not usually highschool-level, I'd guess. But keep with it! As long as you're still interested, it's almost certainly good for you. 😄

[proven thistle]

also i'm looking through this one but

[proven thistle]

yeah!!

i like math a lot :)

i want to be a math major when i grow up so i've been trying my best :D

[proven thistle]

what i don't exactly understand is how the x and y go away

we know that the partial derivatives yield those equations

and while they resemble the matrix that we're taking the determinant of, i don't see how we can eliminate x and y

does that tie into the idea that a singularity must have y = 0?

but that would cause some of the elements to disappear... hm.

[sharp atlas]

So... here's the trick.

[proven thistle]

mhm

[proven thistle]

this is euler's identity isn't it

[sharp atlas]

Take any square matrix. Pick a column, multiply it by any number (zero, nonzero, doesn't matter), and then add the result to a different column. The determinant won't change.

[proven thistle]

mhm

[sharp atlas]

So if you take your matrix, add x times the first column to the third, and y times the second column to the third, the resulting matrix has the same determinant as yours. But when those three equations are satisfied, the new matrix has all zeros in its third column, so its determinant is zero (and so is the determinant of the original matrix).

[proven thistle]

oooo

i see!

[sharp atlas]

Wait, why'd I say minus...

[proven thistle]

so our matrix that we made with the equations above is equivalent to the matrix w/o x and y

[sharp atlas]

(Edited above -- should have been x times and y times)

Yeah. This is one of the rules for determinants. I can write it out in this case, one sec.

[proven thistle]

alright! thank you

[sharp atlas]

$$\det \begin{pmatrix}2a & b & d \ b & 2c & e \ d & e & 2f \end{pmatrix} = \det \begin{pmatrix} 2a & b & 2ax + by + d \ b & 2c & bx + 2cy + e \ d & e & dx + ey + 2f \end{pmatrix}$$

[sterile pumice]

daveamayombo

[proven thistle]

mhm

[sharp atlas]

That's just adding $x$ times the first column, and $y$ times the second column, into the third column. The determinants will always be the same, no matter what $x$ and $y$ are.

[proven thistle]

haha latex compiling the wrong things

[sterile pumice]

daveamayombo

[sharp atlas]

Yeah

[proven thistle]

:(

so lemme think

[proven thistle]

We can go from $$\begin{pmatrix} 2ax & by & d \ bx & 2cy & e \ dx & ey & 2f \end{pmatrix}$$ to the one on the rigth over here?

[sterile pumice]

Arkyter

[proven thistle]

right*

by adding column 1 -> 3

and 2 -> 3

then multiplying column 1 by 1/x and 2 by 1/y?

[sharp atlas]

You could.

But you probably shouldn't.

[proven thistle]

sorry my understanding of determinants is a little shaky

hm

[sharp atlas]

No worries! I'll explain.

[proven thistle]

alright!

[proven thistle]

so maybe it works in this particular case, but it's bad practice because it doesn't always work outside of this?

is that why i shouldn't?

[sharp atlas]

The thing you wrote here doesn't have the same determinant as your original matrix.

[proven thistle]

ouch i see

[sharp atlas]

And if $x$ or $y$ happens to be 0, this matrix will have zero determinant. It'll make it hard to conclude the original matrix (before we multiplied by $x$ or $y$) already had zero determinant.

[sterile pumice]

daveamayombo

[proven thistle]

hmm

i see.

[sharp atlas]

So instead, go directly from the original matrix to the modified one, exactly like I wrote here.

[proven thistle]

because we want the 3rd column to be 0

we don't know individually what d, e, 2f are but we want them to be 0 so we add 2ax + by etc... that kinda stuff

so that if the 3rd column is 0

the determinant is 0

and therefore that implies that there is some (x, y) that makes both partial derivatives vanish

like that? :D

[sharp atlas]

We want the third column to contain the three expressions that we know will be zero when there's a singluar point.

[proven thistle]

mhm!!

i see

[sharp atlas]

So -- when there is a singluar point $(x, y)$, then we know the determinant will be zero. Turning that argument around (sometimes called the contrapositive statement) we see that if the determinant is not zero, then there cannot be any singular point.

[sterile pumice]

daveamayombo

[proven thistle]

i see!

wow that was

surprisingly simple :>

[sharp atlas]

Math is usually like that -- hard until it's easy.

[proven thistle]

hehe

until you get the insight, i suppose!

[sharp atlas]

Exactly!

[proven thistle]

are you a math major?

sorry, i don't hang in this discord a lot so >w> i don't know a lot of things around here

[sharp atlas]

Yeah, have a PhD actually, but love tutoring. I just found this server a few weeks ago, and I'm just here having fun, basically.

[proven thistle]

:O

wait wait whaaaaaaa

awesome....

i want to go for that too!!! well, who knows.

i enjoy math a lot but idk if i'll be able to get there hehe

we'll see in like, 10 years lol!!

[sharp atlas]

Go for it! College and grad school are both tons of fun, especially if you generally like what you're studying. And be open to changing paths too -- I was originally a CS person. Who knows what you'll find to inspire. 🙂

[proven thistle]

:3

i see i see

[proven thistle]

i guess, i just dont have any interests aside from math rn haha

and well, games and anime

hehe

[sharp atlas]

Oh, and never be intimidated -- lots of my friends from grad school didn't fit into the usual 'math genius' stereotypes... just people who had fun playing with math.

[proven thistle]

:>

i like playing with math!

[sharp atlas]

There ya go! 😄

[proven thistle]

c:

thanks for your help

i should sleep though, it's like, 2 in the morning

goodnight!

[sharp atlas]

No prob! Friend me if you want -- if you get stuck again or whatever. 🙂

[proven thistle]

i did!

i sent you a request already u.u

[sharp atlas]

Ah, there it is. Ok, later!

[wind glacier]

https://media.discordapp.net/attachments/496785853180543027/1002242926413357106/892440209470419045.png

https://media.discordapp.net/attachments/496785853180543027/1002243992014037093/892440209470419045.png

Anyone, any ideas??

[abstract quail]

Hi guys, could someone help me with this exercise?

[unkempt void]

I don't see how this should be doable without knowing what f is

[fervent crest]

Imagine being so terrible at math that you can’t even deduce the question

[ionic pier]

Can you translate it

[sacred junco]

i feel like something is off with this proof

[unkempt void]

I wouldn't just say 'you can remove the constant c' since that seems to be basically assuming the statement you wanna prove

I'd say - what does it mean that a = b mod mc? What does it mean to say a = b mod m?

Once you unwrap those definitions it should seem more clear

[fathom sierra]

also the statement as written on your board is false

we have 3=1 mod 2, we certainly don't have 3=1 mod 4

[unkempt void]

That is also a good point It should be n|m that's assumed

[sacred junco]

i wrote it wrong

$a \cong b$ mod $n$ is given and I have to prove $a \cong b$ mod $m$

[sterile pumice]

baja blast

[fathom sierra]

okok

yeah your last sentence is problematic here

i don't see any other way of interpreting it than "since the statement we have to prove is true, then our statement is true"

which is circular af

[sacred junco]

i found some other theorems that'll help me

[fathom sierra]

now you haven't really looked at the modulo parts here

[fathom sierra]

yeah the definition of modulos or properties of them would certainly help

[sacred junco]

i feel like it's on the tip of my tongue

if i apply the modulo definition then the divisibility definition on $a \cong b$ mod m, would i end up with $b-a=mc$?

[sterile pumice]

baja blast

[fathom sierra]

for some integer c, yes

you're gonna confuse yourself by using c for two different things though

[sacred junco]

could the c's be equal

[fathom sierra]

they could be

you can't assume that though

anyway the beginning of your thing was alright

you could start from there

you know that a=b mod cm, and you know what mod means

???

a=b mod m

profit

[sacred junco]

yea

wait how do you get from a=b mod mc to a=b mod m

[fathom sierra]

that's the whole question

[sacred junco]

i can picture it but i can't put it into words

[fathom sierra]

I'm suggesting you with not much subtlety to apply the definition of mod to this statement

and see where that gets you

[sacred junco]

there are c times more solutions to b mod m than b mod n

i can prove this if i can figure out that b mod n is a subset of b mod m

[sacred junco]

wait a second

modular arithmetic is remainder division

@fathom sierra hows this

[low yacht]

is there a general formula for $\cos(\pi/2^n)$?

[sterile pumice]

Kraft Macaroni

[low yacht]

there seems to be a nice formula involving nested radicals of root 2

[fervent grove]

by iteratively choosing the positive root in the double angle formula, it should be possible to solve this by radicals explicitly

I am not sure what you are looking for

[inner anchor]

you know that $\cos \frac{x}{2} = \frac{\sqrt{1+\cos x}}{2}$, so by induction (starting the induction at $n=2$) you get $\cos \frac{\pi}{2^n} = \frac{\sqrt{2+\sqrt{2+\ldots}}}{2}$ where there are $n-1$ nested radicals

[sterile pumice]

Pappa

[nova raptor]

That 2 goes inside the square root

[inner anchor]

oh yeah sure

[nova raptor]

you know that $\cos \frac{x}{2} = \frac{\sqrt{1+\cos x}}{2}$, so by induction (starting the induction at $n=2$) you get $\cos \frac{\pi}{2^2} = \frac{\sqrt{2^1/2+\sqrt{2+\ldots}}}{2}$ where there are $n-1$ nested radicals

[sterile pumice]

Geo_Stellar

[wind glacier]

How to solve the equations of the form $a^x+b^x=c$ where $a\ne b\ne c$ and $a,b,c \in \mathbb{R}$

[sterile pumice]

Amorous aka Lucifer

[wind glacier]

@sacred junco you seem to be idle...can you help me with this?

[sacred junco]

i have no idea

[wind glacier]

np...thanks btw

[heady basalt]

In many cases you can show this equation to have only one solution using monotony arguments, but I doubt there's a nice closed form

[sacred junco]

can someone please explain to me why they solved it that way, and how to approach problems like these?

[sacred junco]

Given a natural number N, is there a function f(n), such that f(n) is the number of distinct ways N can be written as a sum of n natural numbers? If so, what is the expression for this function?

[unkempt void]

This is probably the closest right

https://en.wikipedia.org/wiki/Triangle_of_partition_numbers>

[low yacht]

does anyone know what the fundamental unit of the 12th cyclotomic field is?

[obsidian saddle]

Find the error

[unkempt void]

I mean that looks totally valid?

[wheat prairie]

Reindexing improperly on the 3rd equality I think

Should have shifted n choose i

@obsidian saddle right

[unkempt void]

Haven't they just pulled out the bottom term

[wheat prairie]

Wait

[unkempt void]

Rather than shift

lol

Like this seems totally fine

[wheat prairie]

Yea you're right my bad

I missed the r*n

The *n

That is

What's the name of this euqality

I knew it in a past life

[unkempt void]

Bernoulli

(well a specialisation thereof)

[wheat prairie]

Right

[unkempt void]

General bernoulli often allows for like

r >= -1 ig

[wheat prairie]

Yea

I don't see anything wrong either

It's just ditching a bunch of terms in the binomiap expansion

[unkempt void]

But yeah

[obsidian saddle]

Sorry can you clarify?

What exactly went wrong with the proof?

[unkempt void]

Oh it was tongue in cheek - the proof is p much fine

I was just kinda pointing out that sometimes you want to be more careful with the small cases since for example your method of proof would also show that for all $n\ge 0$, $n+1=\sum_{k=0}^{n} 1 = 1 + 1 + \sum_{k=2}^{n} 1 \ge 2$ which is false if $n=0$

[sterile pumice]

potato

[unkempt void]

Obviously you can just say that the statement holds for n=0 though so it's fine

[latent swallow]

at the moment I'm doing some research on the euler totient function and I found this relation on a course. However, no proof is given. After some research it is the discrete fourier transform of gcd(n,-) but I still couldn't find a proof. Does anyone know it to give me a hint?

(sorry im french, so pgcd is gcd)

[sterile pumice]

Toby

[west glade]

I found this https://mathoverflow.net/questions/394250/counting-squares-modulo-p-that-are-also-prime-in-an-interval post

seems to be highly nontrivial

or maybe this http://pollack.uga.edu/squares-tufts.pdf, slide 11

[sacred junco]

ah thanks, nice finds

I guess 'conjecturally half' is all we have lol

[narrow flint]

Can 0 be a gaussian integer?

[west glade]

0 is a gaussian integer, yes

all integers are also gaussian integers

[fervent grove]

I'm not sure if I'm reading the question correctly, but for the question I read, the answer is half
Half of the nonzero residues (mod p) are quadratic residues (i.e., squares). Each residue class (mod p) is hit evenly with natural density 1/(p-1) by Dirichlet's theorem on arithmetic progression, so the set of quadratic residues gets hit half of the time.

This is of course assuming that p is fixed and we are considering all rational primes

(for example, if you are only looking at rational primes up to p, this looks harder)

[sacred junco]

my phrasing probably wasnt the best, but I was looking at primes up to p only. Though what you said about density is interesting, thanks

[proven thistle]

this is exercise 1.14 from rational points on elliptic curves by silverman and tate

does anyone have hints on where to even start?

are we supposed to show, uh...

[ \left(\frac{\beta^2 u}{(t - \alpha)^2}\right)^2 = f\left(\frac{\beta}{t - \alpha}\right) ]

[sterile pumice]

Arkyter

[proven thistle]

any tips?

[proven thistle]

that took me too long to navigate

[proven thistle]

any ideas for B?

[wind glacier]

Really having a hard time doing it

[inner anchor]

Use the fact that $\left(\sum_{i=0}^n \binom{n}{i}\right)\left(\sum_{j=0}^n \binom{n}{j}\right) = 2^{2n}$

[sterile pumice]

Pappa

[lost yacht]

$\mathbb{Q}(x \sqrt6x) = \alpha^2 - 48$

[sterile pumice]

Loloitsjo

[lost yacht]

I want to solve for x

Minimal polynomial

[sterile pumice]

Per48edjes

Per48edjes

[sterile pumice]

Per48edjes

[opal dome]

Ah I got it -- ignore me (not sure how to delete the rendered above)

[wind glacier]

prove that greatest integer less than $n$ is $n-1$

[sterile pumice]

Amorous aka Lucifer

[wind glacier]

any ideas?

[wooden glen]

Depends completely on which axioms and definitions you have to base your proof on.

[wind glacier]

i initially thought that we have to just prove that there is no integer between $n$ and $n-1$.....was i right$?$

[sterile pumice]

Amorous aka Lucifer

[wooden glen]

Probably yes, if you already know that the ordering on the integers works like orderings ought to do.

[rugged moth]

for any n, does there exist a prime p and an integer k such that n | p^k-1?

[inner anchor]

no

[rugged moth]

counter ex?

[lyric wing]

n = 6

[rugged moth]

p=7, k=1

[lyric wing]

ok so "-1" is not in the exponent?

[lyric wing]

dirichlet theorem implies that for given n, there are infinitely many primes of form c*n+1, and any p = c*n+1 will do the job

so the answer is yes

[rugged moth]

i see

[inner anchor]

Oh wait i misread

Mb

Good thing you didnt get baited

[green linden]

Guys can anyone find the value of j please?

PS: Please tag me if anyone answers

[narrow flint]

I wont do it but let j be x and [j/29] be y, then it would be a system of equations modulus 29. Solve for x and y to get j and [j/29] and j would be in the form of a mod 29. Your floor function will give you a range for j to be in so you can work out j

Also whats the difference between the field Q[root d] and Z[root d] please reply so I can see thanks!

[mossy quail]

Hello, i want to ask, if this is a good course to start with number theory: https://www.youtube.com/watch?v=19SW3P_PRHQ&ab_channel=AcademicLesson

or you recommends a book to start?

[stiff rivet]

do you expect someone to watch this 02:30 video to judge it for you?

you have to use a book anyway to get exercises

and the first minute of the book even mentions a book

so either do both or just the book (or another one)

[mossy quail]

okay, thx

[fervent grove]

Q(sqrt(d)) is the field generated by Q and sqrt(d). More specifically, Q(sqrt(d)) contains all elements of the form a + b*sqrt(d) such that a,b in Q.
Z[sqrt(d)) is the ring generated by Z and sqrt(d). More specifically, Z[sqrt(d)] contains all elements of the form a + b*sqrt(d) such that a,b in Z.
For example, 1/2 + sqrt(d)/2 is an element of Q(sqrt(d)) but not Z[sqrt(d)].

[green linden]

Could you solve it for me please? I really am not able to follow here

[solemn sentinel]

Does anyone here know Extended Euclids Algorithm, I need help calculating beizuts identity with this formula.

[stuck shore]

probably just ask your question in full so when someone who knows bezout's identity reads they can help without asking again

[green linden]

Hi guys. Can anyone help with this question please? PS: Don't forget to tag me if you answer. Thanks!

[wheat tinsel]

Let $f$ be a quadratic form in two variables in the integers. Is f(1,0) a proper representation?

[sterile pumice]

Croqueta

[modern lake]

mod 20

[stiff rivet]

i dont know why you would expect anything here?

you are comparing $\frac{a}{c+d} + \frac{b}{c+d}$ with $\frac{a}{2c} + \frac{b}{2d}$

[sterile pumice]

Lochverstärker

[stiff rivet]

those will be close to each other if $c \approx d$

[sterile pumice]

Lochverstärker

[stiff rivet]

but other than that your choice of numbers seems arbitrary and i have no idea why what you found is supposed to be surprising

[tight bane]

@stiff rivet if have to calculate my Grand CGPA (from 6 SGPAs) by ΣCP/ΣCR formula, I am getting 9.5, while by using Σ(CP/CR) formula, I am getting 9.4. Which one would be correct?? Here I attach my result.

[stiff rivet]

i have no idea how to calculate CGPA, sorry
but this also isnt the right channel, maybe try a help channel

[tight bane]

Alright

[signal cedar]

What does $<<_\epsilon$ mean in context of analytic number theory

[sterile pumice]

bert

[fervent grove]

I think f(x) \ll_\varepsilon g(x) means that f(x) = O_varepislon(g(x)), or that there is an implied constant C(which depends on varepsilon but not x) for which f(x) <= g(x) for sufficiently large x

I'd need to see more context to give you a more precise answer

[green linden]

Hi guys. Can anyone help with this question please? PS: Don't forget to tag me if you answer. Thanks!

[stiff rivet]

how about you review what you know about primitive pythagorean triples

[cedar harness]

consider a circular sequence of natural numbers from 1 to n
let's eliminate (starting from the lowest not yet eliminated number) 1st, then 2nd, then 3rd etc

more formally, on k-th step let's list all n - k + 1 elements that are not yet eliminated
now in this list of n - k + 1 elements eliminate the one with index ((k - 1) mod (n - k + 1)) + 1 (aka kth element in a circular list)

e.g. for n = 5:
1 2 3 4 5
eliminate 1st: 2 3 4 5
eliminate 2nd : 2 4 5
eliminate 3rd: 2 4
eliminate 4th (= 2nd): 2

let P(n) be the last remaining number for such elimination strategy (P(5) = 2)
https://oeis.org/A128982 is very close to what I'm describing but shifted by 1

I wonder why:
(1) P(n) = 2 iff n is prime
(2) P(n) = n iff (n+1) is prime
it's mentioned on OEIS but I haven't been able to find the proof

a way of proving (1) based on (2) was already suggested in math-help section: #help-9 message
however a proof of (2) remains unknown

[latent hare]

Isn't it enough to show that n - k + 1 (index of the element n) is not equal to the index we will remove which is 1 + ((k - 1) mod (n - k + 1))?

Anyone confirm I am not butchering number theory

(this is true since n+1 is prime, so no factor from 2 to n should divide n+1)

[cedar harness]

you mean if k != n and n+1 is prime, right?

[latent hare]

yeah, we won't have k = n because at that point we've eliminated all elements, and yeah I was talking about the (2) problem you suggested

oh rip I have a mistake at the last line

[cedar harness]

n + 1 != 2k  (mod n-k+1)
n + 1 != 2k + (n-k+1)  (mod n-k+1)
n + 1 != n + k + 1  (mod n-k+1)
k != 0  (mod n-k+1)

is that right

[latent hare]

yeah... I mistook a sign

[cedar harness]

your last line is the same as my 2nd one

it seems correct

[latent hare]

No I suggested n+1 == 0 (mod n-k+1) which isn't correct

[cedar harness]

ah, that part yes

[latent hare]

But now I am wondering if it's enough to show that k != 0 (mod n-k+1) is always true

[cedar harness]

i think it's enough but how do we show it
i'm not sure if it's even true

oh wait, it's true

[latent hare]

wait wait k + (n - k + 1) is indeed n + 1

[cedar harness]

it's the same as (n+1) != 0

yep

[latent hare]

number theory blows my mind

[cedar harness]

so that should do it then

i guess

[latent hare]

yeah, though I advise that another user gives feedback just as a sanity check

[cedar harness]

at least it shows that if n + 1 is prime, P(n) = n
what about the other direction?
if P(n) = n, how do we know that n + 1 is prime?

[latent hare]

It would be the same argument no? It would mean that the index n - k + 1 is never deleted which must happen iff n+1 != 0 (mod n-k+1)

(the steps should be reversible)

[cedar harness]

makes sense

thank you

[latent hare]

np (hopefully it's correct)

[cedar harness]

wait, can we figure out on which step is n removed?

[latent hare]

In general?

[cedar harness]

yes

[latent hare]

I don't think there would be an easy way since you'd be trying to solve n+1 == 0 (mod n-k+1) for the first integer k that satisfies it, which isn't an easy task

[cedar harness]

what again is the proof that such k exists?

[latent hare]

There doesn't necessarily exist such a k for prime numbers as we've established

[cedar harness]

i mean if n+1 is not prime

[latent hare]

you mean for non-primes?

since you are basically checking if n-1, n-2, ..., 2 are divisors of n+1

if a number is composite, at least one must show 0 mod divisor

[cedar harness]

are we interested in the greatest divisor of n + 1 (except itself) then?

[latent hare]

I believe so, first integer k so that n-k+1 divides n+1 would be the greatest divisor

[cedar harness]

ok, thx again

[latent hare]

np

[cedar harness]

acutally, it's n+1 - (min. divisor of n+1), my bad

it's -, not /

but we still have it

so nvm

[latent hare]

Well I am still skeptical if this would work at all

[cedar harness]

why's that

oh, maybe it's rather n+1 - (max. divisor of n+1 which is not n+1)?

[latent hare]

Oh boy there might be a big flaw in everything I've written

In the original proof, the reason why I went from n-k != (k-1 mod n-k+1) to working with the whole equation in mod is because if two numbers aren't equal => the two numbers don't have the same remainder which should not be true (The reverse implication is true and used above, but we can't use the same argument for equality)

actually no it's ok, if two numbers don't have the same remainder mod smth, they can't be equal

but if we want equality, I doubt this would work

[cedar harness]

yeah i believe that's true

[latent hare]

Check it on a couple of cases, but I don't see how it would be true

[cedar harness]

at least it seems to work up to n=10

also, interestingly enough, it implies that for prime ns they are removed exactly in the middle (k = (n + 1) / 2)

[latent hare]

That pattern is true if you are looking at a circular arrangement, since whenever you have
1, 2, 3, 4, ..., prime The first numbers that are crossed out are the odd ones, so 1, 3, ..., and then p at the end, which leaves the rest evens

[cedar harness]

oh, right

another way of explaining it then

[latent hare]

Can you check this for n=20?

[cedar harness]

k=14 indeed

[latent hare]

k=16 in the OEIS table

[cedar harness]

16 is the last remaining number

20 is the removed on 14th step

[latent hare]

oh forgot the question was when is n removed :P

interesting

[cedar harness]

checked it up to 100,000 and it works

also for some reason it corresponds to this sequence https://oeis.org/A060681

(largest difference between consecutive divisors of n)

not sure why it is always the difference between n and the largest divisor of n

[latent hare]

Perhaps from n+1 == 0 (mod n-k+1) where n+1 is the number, n-k+1 is the divisor and n+1 - (n-k+1) = k which is the first integer that solves the problem (don't know why it's valid to work with the mod equation, nor how it relates to removing the element n)

[cedar harness]

i mean i'm not sure why the largest difference between consecutive divisors of n is always the difference between n and the largest divisor of n

[latent hare]

oh wait it is very much so related to removing the nth element if the mod equation can be used

[cedar harness]

nvm i think i understand why

[latent hare]

the largest divisor of n is at-most sqrt(n) which for bigger numbers sqrt(n) <= n/2 and thus it must be the biggest difference

since n - sqrt(n) >= n - n/2 = n/2

[cedar harness]

oh, it's ever mentioned there: a(n) = n - n/A020639(n) where A020639 is the least prime divisor

[latent hare]

there can't be another pair with difference bigger than n/2 because it would contradict that we are working with the number n (and instead working with a bigger one)

[cedar harness]

i'm now tempted to search for the general formula of P(n)

i wonder if we can calculate it in O(1)

or at least in o(n)

[latent hare]

P(n) being the formula for which position to choose to not be eliminated?

[cedar harness]

yep

[median skiff]

I want to use the Chinese Remainder Theorem to prove that if $f(x)$ is reducible modulo $m$ and $n$, then it's reducible modulo $mn$

[sterile pumice]

Michael0181

[median skiff]

I can't figure out where to start though

[exotic flame]

What is a your personal check list when doing NT problem?, like do you have any rules or properties that you check first or you stare at the problem and try to be more intuitive

[haughty knoll]

Does Lagrange's four-square theorem get any easier to prove if we use some number larger than 4 instead?
In other words, is the statement "There is an n such that every natural can be written as the sum of n squares" easier to prove than Lagrange's four-square theorem?

[leaden swan]

There is always such a n

@haughty knoll k=1+1+1... k times

[fervent grove]

this seems to not answer the desired question

for example, it is easier to prove a statement like

There exists a positive integer N such that every positive integer n can be written using N squares

(note the uniformity of N is the point)

I would also be interested in if it is easier to prove a statement like

Every (sufficiently large) positive integer n can be written using (log n) squares

[polar ruin]

hello can anyone explain why 3.81^(504n+503) congruent to 3 mod 11?

[stiff rivet]

3.81? that makes no sense

[polar ruin]

3 *

i used . as multiplication

[stiff rivet]

oh ok

i mean you can just calculate it

if you want the intended way, you use fermats little theorem

uhh

actually this is wrong

so no, nobody can explain it lol

[wind glacier]

Prove or disprove that the only solutions of
$$\begin{align}
xy = z\pmod {x+y} \
xz = y \pmod {x+z}\
yz = x \pmod {y+z}\
\end{align}
$$ in positive co-prime integers $x,y,z$ are $(1,1,1)$ and $(5,7,11)$.

My work:

The system of congruence is clearly symmetrical so we can assign the parameter labels so that $a<b<c$. In explicit form, the system of congruences can be written as
$$\begin{align}
xy = z+c(x+y) \
xz = y+b(x+z)\
yz = x+a(y+z)\
\end{align}
$$
where $a,b,c$ are integers. I tried adding and factoring these equations but nothing useful came out. I am stuck here.

[sterile pumice]

Amorous aka Lucifer
Compile Error! Click the reaction for more information.
(You may edit your message to recompile.)

[wind glacier]

there was this question which i saw on internet

this is the work of the Op

nobody gave an answer to it

but

i have some ideas regarding it

that i would like to post here

The equations written imply that
$$\left(\frac{x-1}{a}\right)\left(\frac{y-1}{b}\right)\left(\frac{z-1}{c}\right)-\left(\frac{x-1}{a}\right)-\left(\frac{y-1}{b}\right)-\left(\frac{z-1}{c}\right)=2$$
An equation of this form i.e. $$ABC-A-B-C=2$$
has the positive integer solutions $(2,2,2)$, $(1,2,5)$, and $(1,3,3)$, and the integer solution $(-1,-1,-1)$. However, not all triples $(a,b,c)$ that satisfy
the original set of congruences lead to integer quantities in the brackets.

Another interesting implication of the three coupled equations is
$$\left(\frac{z-x}{by}\right)=\frac{\left(\frac{z-y}{ax}\right)+\left(\frac{y-x}{cz}\right)}{1+\left(\frac{z-y}{ax}\right)\left(\frac{y-x}{cz}\right)}$$

which shows that the normalized distances [$a$ to $b$] and [$b$ to $c$] add up to the total distance [$a$ to $c$] in accord with the addition rule for velocities in special relativity. (This can be seen most clearly by setting $x=\frac{1}{z}$, $y=\frac{1}{y}$, and $z=\frac{1}{x}$. )

For any integer solution $A,B,C$ of the original congruences, define
$$\begin{align}
g=\textrm{GCD}(A,B,C)\
x=\frac{A}{g}\
y=\frac{B}{g}\
z=\frac{C}{g}
\end{align}
$$
and put $M = LCM(x+y,x+z,y+z)$. It's clear that $x,y,z$ are pairwise
co-prime and that infinitely many other solution triples are given by
$$\begin{align}
A' = x(Mk+g)\
B' = y(Mk+g)\
C' = z(Mk+g)\
\end{align}
$$
where $k$ is any integer. A solution $(xg,yg,zg)$ with $g < M$ is called a minimal solution. Examination of the minimal solutions with $g=1$ shows that certain values
of $(x+y+z)$ occur frequently.

The basic equations imply that if $(x,y,z)$ are co-prime then $x$ divides
$bc-1$, $y$ divides $ac-1$, and $z$ divides $ab-1$, but this doesn't seem to be sufficient to prove that $(1,1,1)$ and $(5,7,11)$ are the only positive
co-prime solutions. It appears that for most $($all$?)$ $g > 1$ there are
infinitely many minimal solutions, but I can't prove that either.

[sterile pumice]

Amorous aka Lucifer
Compile Error! Click the reaction for more information.
(You may edit your message to recompile.)

[tender wadi]

Hi there! I just had a quick question about a problem I got on HW. This is a review sheet and I never did solve something like this in my discrete class (we skipped it for the sake of time).

so for (a), it'll be 7x - 3 = 5k for some integer k. So then we get 7x = 5k + 3, but I'm not sure where to go from there, as x needs to be an integer

any advice on how to solve these?

[fervent crest]

Since these numbers are pretty small, the best way is probably just try 0 to 4 (or 0 to 9 for b and 0 to 11 for c), but in general you can use the euclidean algorithm to find all the solutions

[tender wadi]

thanks I'll look into it!

Since these numbers are pretty small, the best way is probably just try 0 to 4 (or 0 to 9 for b and 0 to 11 for c)
Yeah that's probably best, but our professor explicitly said to work it out and not plug and chug :/

[fervent crest]

Alright

a) you can recognize that 7=-3 (mod 5) you can try to continue from here. To argue the uniqueness of the solution try to use inverses.
b) If you write it out, you get 6x+3-1=10k or 6x+2=10k or 3x+1=5k, do you think you can solve it?
c) Again write it out and see what's happening

This way it's not just plug and chug

[tender wadi]

Thank you for the explanation!! I'll fiddle around with it 🙂

[rough thunder]

Can anyone help me with this? I'm asked to compute by hand. I've noticed 729=3^6 and 1024=2^10 but still doesn't help.

$729^{-1} \pmod{1024}$

[sterile pumice]

MCHappster

[west glade]

extended euclidean algorithm

[rough thunder]

yeah I clued onto that thanks

powers weren't helpful

[tender wadi]

howdy!
How would one start this problem? Is there no solution because it's not in correct form? I can't seem to find an example online :

[wooden glen]

Start by adding 7 on both sides.

(i.e. subtracting 3)

Then everything left is even.

[tender wadi]

So you would get 6x + 10 = 1(mod 10) + 7? Wouldn't the three not be divisible still though?

oh I see (I think...)

so you can change the LHS to 2x?

no wait, it would be 8 (mod 10) at that point right?

sorry I've never worked on these lol

[wooden glen]

The "(mod 10)" applies to the entire congruence as a whole, not just to the right-hand side.

So adding 7 to both sides gives you $6x+10 \equiv 1+7 \pmod{10}$.

[sterile pumice]

Troposphere

[wooden glen]

So, indeed 8 on the right-hand side.

And when everything (constants and the modulus alike) is even, you can divide by 2 everywhere and be left with just $3x\equiv 4 \pmod 5$

[sterile pumice]

Troposphere

[tender wadi]

Okay I see now. Thank you so much, I think I got it from there 🙂

[tender wadi]

I think I got it! I took another direction, but it seems to be working
Thank you @wooden glen

[visual path]

Hey all, I've been trying to adapt this sub-linear time approach for calculating the divisor summatory function for squares to work for $$d(2n^2)$$ instead. Any suggestions on how I could go about doing that? I can see that $$d(2n^2) = d(2)d(n^2)$$ for odd numbers but still somewhat stumped on how I could tweak everything to give me a sub-linear method for calculating $$D(N) = \sum_{n=1}^{N} d(2n^{2})$$ overall

[sterile pumice]

Grandmaster Shadow Morgue

[analog onyx]

Anyone got any idea how I can show the inequality portion? I think I know how to show the other two bits.

[latent hare]

Perhaps they just want to say that you can find a solution -n/2 <= x <= n/2 (which is an interval containing n integers) because for any solution that you find, you can always shift it mod n back down to the interval between [-n/2, n/2].

[analog onyx]

that makes sense

i was also thinking it has something to do with the fact that mod n is cyclic

[fervent crest]

Lol this isn’t quite true if you have n=4, a=1, m=2, then x=2 and -2 both work, so technically you need -n/2 < x <= n/2 or -n/2 <= x < n/2

[latent hare]

good call, the interval -n/2 <= x <= n/2 actually contains n+1 integers for even n, which makes it possible that both -n/2 or n/2 be solutions

[analog onyx]

hm, so maybe their isn’t a unique solution for even n, but only odd n

[sacred junco]

Would it also work if we factored the left as 3(2x+1) = 1 (mod 10), then multiplied both sides by 4 -> 12(2x+1) = 12 (mod 10), leading to 2(2x+1) = 2 (mod 10)?

I havent taken any number theory before, I'm just learning about it and trying ideas

[wooden glen]

The trouble there is that multiplying by 4 modulo 10 is not injective, so you'd risk ending up with spurious roots.

(That doesn't actually happen in this case, but verifying that it didn't happen will be an additional complication).

[sacred junco]

Oooh

So it could have extraneous roots to test, but it actually worked?

Like I could solve 2(2x+1) = 2 (mod 10) as an easier version of the original

[wooden glen]

I'm not sure it's actually easier, but you do have a valid ==> reasoning.

[agile comet]

Let a, b be positive integers such that b^n+n is a multiple of a^n+n for all positive integers n. Prove that a=b.

[west glade]

I'm just gonna link you the proof that you found yesterday and when you are ready to talk about which steps you are not understanding about it, then we can help you https://math.stackexchange.com/questions/988167/if-for-all-n-in-bbbn-an-n-divides-bn-n-then-a-b

[knotty oriole]

Hey, i'm working on this PUTNAM question and I was wondering if you could give me some hints on where I should go looking? I only have calculus under my belt so i'm guessing I need to learn some more maths for it, which is the direction I'm looking for.

the question:

Let N be an integer, and x^2 + y^2 +z^2 = N a sphere. Find the constraints on N so that the sphere has an inscribed regular tetrahedron, whose coordinates are integers

i'm guessing it's related to number theory so I've been watching richard brocherd's lecture series on youtube but so far I'm still clueless. Am I on the right direction?

[visual path]

https://en.wikipedia.org/wiki/Integral_polytope

Seems related

Especially the in optimisation section

You start with an integral tetrahedron and then apply your spherical restriction

Well that’s the hunch I have, don’t know much about solving these kind of competition problems

Did you try #competition-math ?

[knotty oriole]

oh thank you!

that's seems like a good lead, although I'm a bit scared the answer will be just there on the page

[knotty oriole]

no, my fault for rushing into the discord channels 🙇‍♂️

that's a great approach. I was sure i had to go the other way - restricting the circle, but first looking at what I can restrain just from knowing it's an integral tetra seems productive

[visual path]

Yep, think the wiki mentioned using linear programming as well so that might come in handy

[mossy rampart]

Here is a nice number theory problem:

Let $n \in \mathbb{Z}^{+}$. Determine all divisors $d \in \mathbb{Z}^{+}$ of $3n^2$ which are such that the number $n^2 + d$ is equal to a perfect square of an Integer.

[sterile pumice]

Emmanouel

[mossy rampart]

Here is what we've done so far:
Because $d \mid 3n^2 \implies 1 \leq d \leq 3n^2 \land \exists m \in \mathbb{Z}^{+}$ such that $3n^2 = dm$.
Now notice $n^2 + d = k^2$ for some $k \in \mathbb{Z}^{+}$. $n^2+d=k^2 \iff d = k^2 - n^2 \iff d=(k-n)(k+n)$.

[sterile pumice]

Emmanouel

[mossy rampart]

Now we are at a point where we need to reach the next step, however the vision is foggy, so we cannot easily see it...

[visual path]

Hmm guess we need to establish some bounds for k right

It is a nice problem

We could plug your value for d in $$1 \leq d \leq 3n^2 \implies 1 \leq k^2 - n^2 \leq 3n^2 \implies 1 + n^2 \leq k^2 \leq 4n^2 $$

[sterile pumice]

Grandmaster Shadow Morgue

[mossy rampart]

Also note that $\because if d = 1 \implies n=0 \notin \mathbb{Z}^{+} \therefore d \geq 2 \implies 2 + n^2 \leq k^2 \leq 4n^2$.

[sterile pumice]

Emmanouel

[mossy rampart]

This is getting a bit interesting...

[visual path]

why would d=1 imply n = 0?

[mossy rampart]

$d = (k-n)(k+n)$. $\because$ For $d=1$ we have $1=(k-n)(k+n) \implies k-n=1 \land k+n=1$. Solving the system we get $\implies k-n + k + n = 2 \iff 2k=2 \iff k=1 \in \mathbb{Z}^{+} \land n=1-k=1-1=0 \notin \mathbb{Z}^{+} \therefore d \neq 1$.

[sterile pumice]

Emmanouel

[warm timber]

Prove if a|d and c|d and gcd(a,c)=1 then ac|d. I can't seem to get it

[still flare]

Use Bézout's lemma, and multiply d by 1 (i.e. d = d*gcd(a,c))

If you're still struggling after giving that hint a fair shake, ask again

[warm timber]

I'm learning to solve congruences... Is there anything wrong with this method? The book says x is congruent to 4 mod 5. Is that because I can rewrite the equation 6•4=4•5+4?

[wooden glen]

It's not quite clear what your reasoning is when you're just showing a pile of formulas without any explanation of what their relation to each other is.

[warm timber]

Oh my b

[wooden glen]

However surely you agree that x=9 also works as a solution.

[warm timber]

I think I get it

[wooden glen]

Since you start by an assumption that's true about x=9 and end with a conclusion that's false about x=9, the step where you go from "this claim is true when x=9" to "this claim is false when x=9" must be invalid.

[analog onyx]

isn’t x = 2 and x=-2 the same in mod 4 though

[sacred junco]

for question 3b how do i prove it while also accounting for cases when n is even and i end up with a 2 as the answer?

[wooden crater]

use the binomial theorem with a clever choice of a and b @sacred junco

[sacred junco]

thank you.

[wooden crater]

alternatively, try finding a bijection between the even and odd subsets of an n element set using the symmetric difference.

proving this by cases on the parity of n is cumbersome and inefficient

and ur welcome

[dusty dragon]

I was messing around with some things regarding prime moduli in an attempt to write a problem which uses Wilson's theorem. I proposed this problem: Let $p$ be a prime. For what primes $p$ is [ \sum_{k = 0}^{p} (p - k)! \equiv p - 1 \pmod p?]

[dusty dragon]

Clearly, by Wilson's theorem, we have that $(p - 1)! \equiv -1 \pmod p \equiv p - 1 \pmod p$

[dusty dragon]

Is there anything interesting about p = 5 and p = 7 that makes this true?

I also considered primes because I know that I can exploit the existence of inverses to derive expressions for $(p - k)!$ since we have that [ (p - 2)! \equiv (-1)(p - 1)^{-1} \pmod p,] etc

[waxen tide]

Prove $11^n - 4^n$ is divisible by 7 when n is a positive integer. I know im supposed to use induction but could I get a hint

[sterile pumice]

Rishi

[dusty dragon]

The base case is easy enough to check since 11 - 4 = 7 which is divisible by 7. What does your inductive hypothesis look like?

[compact moth]

Are 3 and 2 the only primes seperated by 1?

[inner anchor]

yes

either one of two consecutive numbers is even

[compact moth]

Ah, yeah okay.

[inner anchor]

lol even sorry

[waxen tide]

Assume for induction that the nth case holds, we will use this assumption to show that the n+1th case holds

And idk what to do after that like

How do I use 11^n - 4^n is divisible by 7 to show 11^n+1 -4^n+1 is divisible by 7

[dusty dragon]

Note that 11^{n + 1} = 11 * 11^n and 4^{n + 1} = 4 * 4^n

[waxen tide]

Ok

[dusty dragon]

So
11^{n + 1} - 4^{n + 1}
= 11 * 11^n - 4 * 4^n
= (7 + 4) * 11^n - 4 * 4^n

[waxen tide]

Ohhhhhg

[dusty dragon]

Do you think you could finish the rest?

[waxen tide]

Yeah ill try that

Tysm

[dusty dragon]

It should fall out easily from there

[waxen tide]

Factor out a four

[dusty dragon]

Yep, sounds like you got it

[waxen tide]

Tysm

[warm timber]

How do I find the number of solutions there are to the congruency $x^7 \equiv 1 \mod{99}?$

[sterile pumice]

cali5nia

[dusty dragon]

It would help to decompose 99 into 9 and 11, and apply the Chinese Remainder Theorem to find solutions to the individual congruences: [ x^7 - 1 \equiv 0 \pmod 9, \quad x^7 - 1 \equiv 0 \pmod{11}]

[warm timber]

Ohh ok

I think I get it

[sterile pumice]

Hausdorff

[stone vapor]

How should I do this?

[sterile pumice]

Hausdorff

[dim steppe]

hello how do i prove the odd one

[still flare]

Let n be odd, so n = 2m + 1 for some integer m.

Then n/2 = m + 1/2

so floor(n/2) = m = (n-1)/2. QED.

[dim steppe]

thank you

[forest basin]

Having a look at this question here: https://math.stackexchange.com/questions/1441359/prove-that-p-1-cdot-p-2-cdots-p-r-1-is-divisible-by-some-prime i'm trying to mine for an alternate proof my idea was to negate Euclid's lemma and induction I ended up using the negation of Euclid's lemma to prove the induction hypothesis

But i'm not sure if the idea is correct

[sterile pumice]

Hausdorff

Hausdorff

[stone vapor]

Just need help finishing (2), the other cases seem fine

[proven thistle]

Let $C$ be the cubic curve [y^2 = x^3 + 1. ] For each prime $p \leq 5 < 30$, describe the group of points on this curve having coordinates in the finite field with $p$ elements.

[sterile pumice]

Arkyter

[proven thistle]

How do I do this...???

wth does

group of points on this curve having coordinates in F_p mean

[sacred junco]

I guess you look at the rational points of this curve and examine what group do these make.

[proven thistle]

for reference this exercise is from Silverman and Tate's rational points on Elliptic Curves

[proven thistle]

oh i just don't understand what this means

why F_p?

[sacred junco]

Because each rational can be viewed as some element of F_p, right?

[proven thistle]

hmm

can you explain that

[sacred junco]

Say, 5/7 in F_11. This is jsut 5 * 7^(-1)

[proven thistle]

i actually don't know what F_p is

[proven thistle]

fair, but what's the 11 doing

[sacred junco]

F_p is the p-element field.

For p nonprime it is not a field.

[proven thistle]

so for F_11 is it {0, 1, 2, ... , 10}?

[sacred junco]

Yeah.

[proven thistle]

i see

[proven thistle]

so this means

each P = (x, y) on the curve has x, y \in F_p

[sacred junco]

if x and y are rational you can treat them as elements of F_p.

[proven thistle]

i see

as long as the height < p?

[sacred junco]

Height?

[proven thistle]

as in x = a/b for coprime a, b. then height = max(a, b)

[sacred junco]

You reduce mod p.

[proven thistle]

3/11 has height 11

[proven thistle]

what do u mean?

[sacred junco]

Yeah I don't know how 3/11 would work in F_11. But for example, 3/12 would be 3/1 in F_11.

[proven thistle]

ohhh

wait a second what

but 3/12 and 3/1 are entirely different

[sacred junco]

They are as different as 6 and 10 are in say Z_4.

[proven thistle]

oh hmm

but if we're looking at an elliptic curve are we like

how would i visualize this...

drawing an elliptic curve in F_p

[sacred junco]

Are you sure you have enough background for this book? Not wanting to sound rude, but I thought it's quite advanced. And Im sure you probably have some theorems to work out this problem.

[proven thistle]

oh, i definitely don't have the background for it. im a high school student! im working through it for fun

and i got past chapter 1 and did almost every exercise

im on ch. 2 now and im just confused

because it feels like there's a big jump

i learned what holomorphic and meromorphic meant earlier, so im trying exercise 2.4 but i got confused heh

[proven thistle]

idk how advanced it's meant to be...

the book discussed the nagell lutz theorem, but I don't think that applies here

since it discusses points of finite order

not finite field

in fact ch. 2 never talked about finite field so i got confused

i imagine that if we have a curve C in F_p it implies we can only look at (x, y) where x, y have height less than p (i think)

[sacred junco]

Maybe someone else can help, I myself haven't learned that stuff yet. Although I really should, it sounds interesting.

[proven thistle]

thank you!!

i really want to go into number theory in the future so I'm trying my best here hehe

[sacred junco]

Well, don't want to discourage you on reading this book, but I think it would be better if you learned a decent amount of abstract algebra/nt beforehand.

[proven thistle]

yea i figured :3 i had to distract myself from the book to learn more of that

i might do that again, considering I can't grasp the idea of finite fields yet

[sacred junco]

Yeah, well, you have all the time in the world to learn this Id say. If you want to get into number theory then you will have to learn abs algebra at some point. I think a book by Dummit Foote is great for selfstudying, it goes through most stuff you will need.

[proven thistle]

alright I'll check it out

[mystic venture]

Someone help me with hw

[vernal void]

I believe I need to begin with binomial expansion

[vivid zephyr]

@vernal void try that

[vernal void]

Thank you @vivid zephyr 😄

[vivid zephyr]

I mean, what are you unsure about with the binomial expansion?

[vernal void]

like

if it was

(n+1)^2 then i'd write

(n+1)(n+1) but here i don't know what to do

because it's to the n power

[vivid zephyr]

Expand it out

For these sorts of things, I like to start with a small n to see what happens.

Perfect example is letting n = 2 as you have

[vernal void]

okay 🙂

we get to

n | n^2 + 2n

[vivid zephyr]

Yeah, so you can factor an n out. Try again for n=3 and n=4

[vernal void]

in which case we know that n^2 + 2n = n(w) for w integer

[vivid zephyr]

Yeah, it's a bit of a pain as you increase that exponent. I'm just trying to see if you can find the pattern.

[vernal void]

let me try with 4

yes

aalways has a +1 at the end

which is then deleted by the -1

so always has n in it

so obviously always divisible by n

[vivid zephyr]

Yeah!

[vernal void]

cause the other stuff is integers 😄

WOW

thank you!

Tho i am so new to proofs ahah

[vivid zephyr]

So now you just need to formalise this for all n

[vernal void]

i dont know how to put this in proof form

love the pfp by the way.

[vivid zephyr]

That's fine. We'll go through it. Are you familiar with the binomial expansion?

Thanks haha

[vernal void]

isnt binomial expansion what we just did?

also - i can call if u want

[vivid zephyr]

I can't call right now. Shared office and all.

[vernal void]

all good

[vivid zephyr]

Are you familiar of the general way of determining coefficients for binomial expansion?

Like for an arbitrary n without needing to multiply and add up a bunch of stuff

[vernal void]

i am not my good brother

[vivid zephyr]

No worries. I'll recite it here

[sterile pumice]

IamDerek

IamDerek

IamDerek

[vernal void]

i should be able to infer from ur above messages but no, off the top of my head, i am not familiar =[

[vivid zephyr]

It's usually read as "n choose i". So if you have n objects, how many combinations of length i can you form from them.

Usual example is something like poker. If you have 52 cards, how many different 5-card poker hands are there?

Anyway, you can compute this. $\binom{n}{k} = \frac{n!}{(n-k)!k!}$

[sterile pumice]

IamDerek

[vivid zephyr]

where n! = n(n-1)(n-2)...(2)(1)

[vernal void]

gotcha, okay

[vivid zephyr]

Going back to your problem, all of our a's are n's, and all of our b's are 1. So you can expand that puppy out you should see that you get something like

a bunch of powers of n along with a b^n at the end, where b = 1 in our case.

[vernal void]

😄

[vivid zephyr]

You can also see that anything of the form $\binom{n}{k}$ has a factor of $n$ for $k\neq 0,n$.

[sterile pumice]

IamDerek

[vivid zephyr]

But you should work that out (again, try a few small n) to convince yourself.

So basically use this to try and re-compute your n=2,4 examples to see if they match up.

If you want more on binomial expansion: https://en.wikipedia.org/wiki/Binomial_theorem

They explain it better than I ever could

[vernal void]

great, let me check that out!

Well thank you

I can figure it out from here

Tho derek i will say that

i will probably need help on so many problems this semester :/

[vivid zephyr]

Just ask if you do. People in here are generally pretty helpful

[vernal void]

and right now im saying

let (n+1)^n = binomial expansion (like the one you wrote)

every component has an n, and (1)^n = 1 for all n in Z

[sacred junco]

Uhh can someone help

[vernal void]

lol

therefore n|(n+1)^n -1 for all n > 0

but i feel like i'm missing proof structure =[

[vivid zephyr]

The only thing I'd maybe add is showing that every inner coefficient has a factor of n in it, and the leading term is n^n. So your only problematic term is 1^n = 1, but you subtract that off.

So show that $\binom{n}{0},\binom{n}{n}$ are both equal to 1. And show that $\binom{n}{k}, 0 < k < n$ has some factor of $n$ attached to it.

[sterile pumice]

IamDerek

[vivid zephyr]

Don't be too concerned with this. You're just writing up a statement and convincing someone a hypothesis is actually true.

The only thing you haven't convinced me of is that every inner coefficient has a factor of n in it.

Oh! It just occurred to me there's another way of doing this. You can just look at the powers of $n$. So by binomial theorem your only term with $n^0$ is the last term.

[sterile pumice]

IamDerek

[vernal void]

ahhhhhhhhh okay

thank you very much ❤️

[vivid zephyr]

No problem. Don't get too caught up in structure right now. You'll get better as you practice more. A proof is just a way of writing something to convince yourself and others that something is true.

[vernal void]

what's the best way to prove these?

im saying stuff like "by definition, any even number can be divided by 2" but idk if 'm allowed to say stuff like that

@vivid zephyr how would you go about these? do i have to prove both ways because the if and only if?

[vernal void]

Someone =[

[wooden crater]

first, what is your definition of an even number? of an odd number?

[wooden crater]

yes u have to prove both ways

[vernal void]

thank you!

[proven thistle]

hi nt ppl!

https://media.discordapp.net/attachments/873996574282358804/1017498734092890122/247713300115226625.png

any ideas how to go further with this?

i made a complete guess that the Legendre symbol here would work

considering that we're looking at y^2

in F_p

[proven thistle]

now i need to prove my conjecture is right

[still flare]

Haha I admire your humility but I don't think this is #elementary-number-theory. People who know how to answer your question will probably be in #advanced-number-theory

Maybe someone who knows will pop by

[proven thistle]

alright!

[proven thistle]

oh okay

ive been working on the same book since 2 months back and I was directed here from the hw channel

so ive been camping here when i needed help :)

ill move though! thank you

[proper shadow]

Why is it that given a positive integer $n$ and $x = (n + 1)! + 2$, that the next prime number is $n$ numbers away from $x$?

E.g. if $n = 2$, $x = (2 + 1)! + 2 = 8$, then the next prime is $2$ numbers away, i.e. $11$.

**Is there a name for this result? ** I know $x$ will always be even because of $2$ being in the product and adding 2, but can't tie this back to the result.

[sterile pumice]

mmerc

[umbral bridge]

Are you sure this is always true?

n = 6 is a counter example

[proper shadow]

No sorry, I just took it for granted as I came across it in a proof of the theorem that "for every positive integer n, there is a sequence of n consecutive positive integers containing no primes."

[umbral bridge]

Huh, interesting

Well it's not true for n = 6 so...

perhaps you misread this lemma

[proper shadow]

He says "Suppose n is a positive integer. Let $x = (n + 1)! + 2$. We'll show that
none of the numbers $x, x + 1, . . . , x + (n − 1)$ is prime."

[sterile pumice]

mmerc

[proper shadow]

So for n = 2, x = 8, he's showing that 8 and 9 are not prime?

But what about 10

The quote in my previous message doesn't make sense to me

Or is the point of the proof to show that the distance to the next prime grows with $n$ and is at least $n$?

[sterile pumice]

mmerc

[proper shadow]

So it doesn't matter that 10 isn't included in the sequence.

And I had misread the quote as saying that none of the numbers from x+1, ..., x+n are prime.

But is there an intuitive reason as to why x, x+1, ... x+(n-1) are not prime?

[undone monolith]

Hey guys, I am currently reading Tom Apostol's Calculus 1. I've come across this proof that shows the existence of square roots. I kinda generally understand this proof, but I am not sure where the value "c" comes from. Any thoughts would be appreciated.

[west glade]

you just take the average of b and a/b which are two numbers which multiply to a. the idea being that this will be closer to sqrt(a) than b

for example if we wanted to approximate the sqrt of 3, we could start with b=2, then 3/b=1.5 and the real sqrt should be between 1.5 and 2. so we set our next approximation as average of 1.5 and 2

[umbral bridge]

Yeah so it’s not saying that x + n is certainly prime.

Just that the integers starting from x and ending at x + (n - 1) inclusive are not prime

[umbral bridge]

There should be a proof given when it made that statement.

[sacred junco]

Help

[still flare]

#❓how-to-get-help

[signal cedar]

I am asked to show that $\sum _{p \leq x} [\frac{x}{p}] \log p = x \log x + O(x)$ where p is a prime

[sterile pumice]

bert

[signal cedar]

can I get any hint

I have already been told that I must use von - mongoldt function but I don't understand how exactly does that help

[sterile pumice]

lord of crime

[signal cedar]

yea but I don't see how that helps

we reduce to summing log p / p and log p but the sum is still over primes

so we still cannot apply any of the summation formulas

[sterile pumice]

themateo713

[high hinge]

Hi ! Can anyone tell me if this argument is alright? I want to prove that the only positive solution to this equation is irrational : x^5+x=10. So first of all, I suppose there is a rational solution, let's say x=p/q with p and q relatively prime. That means (p/q)^5 + (p/q)=10 and so p^5 + pq^4=10q^5. We can write p(p^4+q^4)=10q^5, so that means 10q^5 is a multiple of p. Either p divides 10 or p divides q^5 (This was the part I wasn't sure about). We know that the last option is false since p and q are relatively prime. So p is in {-10,-5,-2,-1,1,2,5,10}. Also, we have p^5= 10q^5 - pq^4 so that means p^5 = q(10q^4 - pq^3). p^5 is a multiple of q so q divides p^5 ---> q divides p (Can I say that?) Since q divides p and since they are relatively prime, q is in {-1,1}. We can test all of p/q to see none of them works.

[buoyant mason]

for the part you aren't sure about, you could just say that since p | 10q^5 and p and q^5 are relatively prime, p divides 10

by euclid's lemma

I wouldn't say "either p divides 10 or p divides q^5" though

other than that it sounds ok

also if you didn't realize, what you pretty much did is go through a special case of the rational root theorem

[rapid plover]

I'm struggling to understand this proof. More specifically, I'm not sure where "k" comes from (is it just a?) and also why (k-b)p_i = + or -1 and not just -1

wait I got it now

[high hinge]

I didn’t réalise actually! Thanks a lot

[knotty oriole]

I would like to start learning some number theory, and I'm looking for any1 who wants to learn with me. I'd like to set up a VC every stretch of time.
Multiple ppl welcome, ping me please
Edit: were now a group of 2! Feel free to join in the fun

[grizzled escarp]

I’m struggling with this problem that I found. I’m guessing that it’s true, and that in the proof I’ll need to involve the division algorithm. Other than that, I’m not sure how to approach this. Does anyone have any ideas or tips?

[verbal axle]

is there a general "solution" to a^n (mod n)?

can this be reduced for all integers n?

[stiff rivet]

wdym?

solution in terms of what

[supple palm]

for questions like this, it is often a good start to look at n for small values of m, and see if you note a pattern.

[verbal axle]

Like is there a way to simplify a^n mod n?

Well for non prime n

Because for prime n was could use fermats little theorem

[umbral bridge]

You could always write it as

(a mod n)^n mod n

[rapid plover]

Can someone help me with this question please?

Corollary 2.10. Let p be a prime and $a,b \in \mathbb{Z} p | a^n \implies p | a$

[sterile pumice]

swifteeee

[rapid plover]

Exercise - use corollary 2.10 to show that for any prime p, p^1/n is irrational

[stiff rivet]

what have you tried?

[rapid plover]

Essentially I've proved that p^1/n isn't an integer

But I haven't used the corollary and I can't find a use so I think I've done something wrong

Sorry for the sloppy work I was just trying to get my thoughts down

[stiff rivet]

this isnt correct

and you cant really talk about divisibility properties of p^(1/n) if it isnt an integer

try a proof by contradiction

and if you want to use corollary 2.10 you probably want to raise everything to the exponent n at some point

[rapid plover]

Sps p^1/n is rational

Then p^1/n = a/b for some a,b in Z b \neq 0

Then p = a^n / b^n

B^n \in Z, implying that p is factorised by integers b^n and a^n, contradicting the fact that primes can only be factorised by themselves and 1

[stiff rivet]

the last line doesnt quite work

[rapid plover]

And a \neq p^1/n as a \in Z

[stiff rivet]

you cant talk about factorizations unless you have integers

you can only get something like pb^n = a^n

now there are multiple angles of attack

[rapid plover]

This implies that a^n divides p, and that is only possible if a = p^1/n, which contradicts our assumptions?

[stiff rivet]

it does not imply that a^n divides p

at least not immediately

you do get p | a^n

and can use your corollary

[rapid plover]

Hence p | a