elementary-number-theory

[surreal tangle]

I was going to cite 4 not dividing 6 and gcd(4,6)=2

I just skipped the q is prime condition when reading the statement for some reason

[runic token]

lmfao

[surreal tangle]

Thanks 👍

[runic token]

tbf usually it would be p here

not sure why they picked q but ig it's still fairly common

[cursive girder]

can anyone explain how to solve this

[unkempt void]

This is very cool

I think I have another combinatorial method but probably the same lol

like ||I claim there's an action of G := (S_n)^(n^2) \semidirectprod (S_(n^2)) on the n x n x n cube. Think of the cube as a prism with cross section n^2 and length n. The first factor G acts on the cube by rearranging it "length"-wise i.e. moving points along the length of the prism. The second factor acts by changing the cross section.

This action embeds G in S_(n^3). Now apply Lagrange's theorem
||

I quite like that lol unless I have made an error

||Then you can do the same argument the other way round by viewing the cube as n^2 x n rather than n x n^2||

@ancient crow wdy think?

Oh wait yes it is the exact same argument lol as my cube corresponds to the "space" of people in your analogy

and I didn't even read your answer properly 😭 But makes sense

Very cool.

[teal pelican]

if we have a lattice point in R^2 how do we write its residue class

like the lattice point (n+1, n+2) is in the residue class of [1,2] mod n?

need some help with formal math language, thanks in advance!

[ancient crow]

ah this is nice! yeah this is equivalent but a cool perspective

[thick panther]

could i get a hint for this please? my line of thought went along the following:
|| the gcd(a,N) = 1 suggests that probably euler's theorem is used in some way or another, so i decided to calculate phi(N), and its in fact the product of the p_i - 1 since the N cancels
but we are trying to look at the lcm, and the p_i - 1 are not necessarily coprime (eg 7 -1, 13-1 are not coprime)|| so i'm not sure how to piece this together
i tried || looking at maybe using ab = lcm * gcd || but this doesn't particularly help either, or at the very least i cannot see how it would

[west glade]

you are trying to show that a^lambda(N)-1 is divisible by N

can you show that it is divisible by all the p_i ?

[thick panther]

ohhhhh

so its just || FLT + CRT ||

thank you

i don;t know why that didn't cross my mind

[west glade]

well CRT is a bit overkill. its just normal divisibility stuff on Z

[runic token]

i think fermat's last thm is a bit much as well

[surreal tangle]

Abbreviation confusion

[unkempt void]

i write flt for fermat's lil theorem and FLT for the big boi

just write "lagrange's theorem"

:chad:

[normal heart]

I write FlT for lil lol

[surreal tangle]

Euler's theorem also works

[still flare]

You could call it FLiT :3

[unkempt void]

euler's theorem is too vague xd

[surreal tangle]

Suffering from success

[unique cypress]

Euler's theorem? Huh what WHICH ONE??

[thick panther]

hahahaha yeah i have Gauss' lemma in my course but for two different things

the polynomial one and the qr one

[nova vine]

can someone help me with this proof please

[primal pewter]

@nova vine I have two solutions, one using the hint, and the other one without the hint

Extra hint for solution 1: ||use the order modulo p||
Solution 1: ||Deduce that the order of n modulo p is 3. By Fermat, n^(p-1)=1 (mod p), so 3 must divide p-1.||

Hint for solution 2: ||p | (2n+1)^2 +3||
Solution 2: ||so -3 is a quadratic residue modulo p. Using quadratic reciprocity, one easily shows that this happens iff p=1 (mod 3)||

[nova vine]

I understand this. Thanks for the hint!!

[rancid tartan]

Notationally is it ok to drop constants when you have a O term? ie. if you have something that's like h(x)=log(x)^2+x+13+O(1) can you just say h(x)=log(x)^2+x+O(1) since 13 can fit under the bound?

[dusty dragon]

yes that’s fine

basically the big-oh absorbs constants and functions of a smaller magnitude

[weary rune]

the "if" direction is the so called tHeOrEM 4.9 which i have proven but i don't see how to approach the "only if" direction

[weary rune]

nvm, figured it out

[twin forum]

currently doing a paper on the history of fermats last theorem

does anyone have a good website for how the failed proofs of fermats last theorem helped advance math?

[spare frigate]

Is this true: If $p > 3$ is prime then $(p + 1) \mid p!$?

[sterile pumice]

sxbuto

[normal heart]

Note p+1=2*(p+1)/2

[spare frigate]

ohh and (p+1)/2 is going to be in p!

thx!

[normal heart]

of course you need to check 2 =/= (p+1)/2 and (p+1)/2<p, but they are both easy to check

[spare frigate]

yep i see i think i had a brain fart

also, this is a notation question

is $\ZZ/p\ZZ$ denoted as the group of integers modulo p under addition

or is it also the set of integers modulo p

[sacred junco]

Why is that?

[west glade]

sometimes its also the ring of integers mod p. but either way, its the same set, just maybe with some operation on it

[spare frigate]

(p+1)/2 < p right so it’s in the factorial of p

[sacred junco]

My question was why it's in the factorial

[normal heart]

(p+1)/2 is an integer and less than p, and by definition p! is a product of positive integers less than or equal to p

[minor axle]

how do you prove the distrobution of prime numbers to infinity?

[sacred junco]

Do you mean, to prove there are an infinite number of primes?

[twin forum]

depends, choose a natural number between 2 and infinity and I can show you a way to prove infinite primes

[sacred junco]

Whats a simple example of a number field with class number >1 that embeds into a number field with class number 1?

[noble obsidian]

if you have a prime p not 2

can the prime factorization of p^n - 1 be determined partially in some way

its obviously even.

I am trying to find the amount of elements relatively prime to p^n - 1

[primal pewter]

usually prime factorizations are completely unpredictable

[noble obsidian]

do you have any idea how one would prove this?

Given a field of char p look at its multiplicative cyclic group of order p^n - 1 the only elements of the kernel x \mapsto x^2 is +- 1.

+- 1 obviously satisfies this but I am trying to show no other element has this property.

[primal pewter]

so you want those x's that satisfy x^2=1

[noble obsidian]

yes

[primal pewter]

the polynomial x^2-1 has at most two roots, so you are done

[noble obsidian]

i am missing something easy i feel

but we are dealing with a group

addition makes no sense here

under this hom

[primal pewter]

I know, but it makes sense in the original field

[noble obsidian]

oh really thats it

[rare barn]

very fun problem, pretty easy though

[sonic urchin]

How would I show that 2ⁿ does not divide 3ⁿ-1 for n ≠ 1,2,4?

[primal pewter]

you can use LTE (lifting the exponent)

so for n>=2 you have 4 | 3^n - 1, which implies that n is even

[rare barn]

induction, perhaps?

[primal pewter]

so we can apply LTE (remark: we need n to be even to apply LTE in the special case p=2)

v_2(3^n - 1)=v_2(3-1)+v_2(3+1)+v_2(n)-1=2+v_2(n)

On the other hand 2^n | 3^n - 1 implies v_2(3^n - 1) >= n

combining, we get v_2(n) >= n-2

and finally, since v_2(n) <= log_2(n), we have log_2(n) >= n-2, which can only happen for finitely many n's, so the rest is just checking

[sonic urchin]

Woah this is a really cool proof, thank you!

[sonic urchin]

I considered that for a while. The issue is that the naive induction hypothesis would not work because this divisibility relation does hold for n=3 and then not for n=4, so you'd probably have to strengthen the induction hypothesis in order to apply it. Once that happens, who knows what the correct induction hypothesis is

[rare barn]

could you not have the base case be n = 5, and then just manually check that n = 3 also isnt divisible

or you could prove it for n + 2 assuming n as a base case, and show that it works for 1 and 6

or wait it doesnt work for 1

nvm ignore me im being dumb

[sonic urchin]

Yeah the issue I had was that the naive induction hypothesis of "if this is true for n then this is true for n+1" is clearly not gonna work because if it did work for n ≥ 5 then it probably would for n ≥ 3 too since the induction hypothesis itself doesn't assume anything about n. Maybe the n+2 thing would work as you said. That's kinda what's happening in Filip's proof.

[sacred junco]

Let $c_r(n)= \sum_{\substack{j=1 \ gcd(j,r)=1}}^r e\left(\frac{nj}{r}\right)\$
Show that (c_.(n) \ast \iota^0)(r)= \sum_{j=0}^r e\left(\frac{nj}{r}\right)$ where $e(z)= e^{2 \pi i z}$ and $(a \ast b) (r)$ is the dirichlet convolution and $\iota^s(r)=r^s$.
I need some help. Already tried möbius inversion formula, but that doesn't help

[sterile pumice]

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

[runic token]

look up "erdos prime number theorem elementary proof" or something

[latent tusk]

I want to prove the following statement:

If n is a positive integer which is not a perfect square, then √n is irrational.

So if I assume that √n is rational then √n = p/q , where gcd(p,q)=1.

So n=p^2/q^2 it implies that nq^2=p^2 which implies that n| p^2 and p^2| n (because gcd(p,q)=1 ) so n=p^2, which contradicts that n is not a perfect square.

Is it correct?

[open mist]

I don't understand why you say p^2 | n

[primal pewter]

it's because p^2 and q^2 are coprime, so if you think about prime factorization, p^2 and q^2 have no common prime factors, so the only way p^2 could divide nq^2 is if it divides n

[primal pewter]

it's correct

[latent tusk]

Okay thank you

[sonic wharf]

I'm unsure where to begin with proving that infinite continued fractions are irrational, any hints?

[primal pewter]

@sonic wharf use contraposition

[rare barn]

i got 127 but that feels so wrong

but i also cant figure out where i might have went wrong

[primal pewter]

I also got 127

[rare barn]

what the hell

thats so cursed

1 less avalible digit and the available numbers are cut by 95%

[normal heart]

It's not that surprising, log_3(1992) is around 7, and the probability of a digit having a particular digit in base 3 is around 2/3, so you'd expect the probability of an integer from 1 to 1992 to not have that digit in base 3 would be (2/3)^7 which is around 5%
ofc this is too idealistic but you can see it's not incredibly surprising

[rare barn]

this is my first number theory book im not very experienced in all the patterns and what is normal

[weary rune]

it helps to have good general “number sense” which is a bit harder to describe

I think since this is the AoPS book there is a brief chapter on it?

[rare barn]

theres a chapter on number sense at the end iirc

id like to think i have decent number sense for the most part i think its just since this is my first time dealing with different bases

[fallow dirge]

what i have so far for part a is that since n and a are relatively prime, gcd(a,n)=1. let {x1,...,x_n} be any CRS, so multiplying the CRS by a would mean that the CRS is still a CRS since a and n are relatively prime. And then we can add U for any integer to the CRS and it would also still be a CRS.

does that sound right for part a?

for part b, im kinda stuck.

[ebon shell]

for both part a and b, a is a generator of the additive group modulo n ,,, which is the CRS. there should be something you can leverage from additive groups.

[latent tusk]

I want to prove that if 2^n -1 is prime then n is prime.

So if I let n be a composite number so n=ab , where 1 < a,b < n.

Now I have one result,
a^n -b^n = (a-b)( b^(n-1) + ab^(n-2) +.......+a^(n-2)b + a^(n-1) ), for all positive integers n.

So I can write now, 2^n-1 = 2^( ab ) -1 and 2^n-1 = (2^a)^b - 1^b.

So, here it can be equal to (2^a-1)( (2^a)^(b-1) +.....+1) since b > 1 so ( (2^a)^(b-1) +.....+1) this can not be 1 so 2^n -1 can written as product of two positive integer and no of them is 1. So 2^n -1 is composite.

Is it correct?

[surreal tangle]

Yes

[latent tusk]

Sure? Because you give a reply very fast

[surreal tangle]

Because I have seen this proof before

[latent tusk]

Okay thank you

[surreal tangle]

You should also say why 2^a-1 isn't 1

Its the same reasoning as the (2^a)^(b-1)+...+1 part though so it shouldn't be a problem. You have the correct idea

[latent tusk]

Yes, because 2^a= 2 only when a = 1 but a>1 so 2^a-1>0.

[surreal tangle]

Well you can improve the lower bound

[latent tusk]

Oh yeah

2^a-1>=3

[surreal tangle]

Yeah

[tribal palm]

So I've been working on a paper about prime number.

I end up deriving a function that generates every prime number in the sequence.

The function takes the form of a quadratic and the roots of the quadratic are the next prime number.

I show that there are two formulas that are required to generate the sequence of the primes.

This is just a list of the prime numbers.

Now this is the result I get in my paper. I show that there are two formulas needed to capture all of the primes.

The formulas themselves are locked down with a special recursion function that generate an RNG value (random number generation). However you can "hack" this by capturing all of the RNG data from this function and replace it with an alternative.

For this system, you are not allowed to predict a single prime, but they come in pairs with a random probability of the next prime being one of the two numbers.

I do this to predict the next prime which is 101 in this example.

The number that the formulas predict is 100.79 which is very close to 101.

This shows that these formulas actually work in predicting the next prime.

The paper is attached.

Any feedback is welcomed.

For any theory, its all about making good predictions, my claim is that this is the best prediction that you can make to predict the next prime.

[native monolith]

Have you tested it for high values using Python?

[latent tusk]

How can I show that well ordering of positive integers?

[quaint gate]

induction

[weary rune]

all the prime generating algorithms we know of fail for sufficiently high values

[latent tusk]

Okay thank you

[surreal tangle]

CP willans wants to talk to you

There are a bunch of formulas for the nth prime actually, but all of them in essence involve checking every number till you get to the nth prime

[sacred junco]

does anyone have intuition for this proof?

like. i understand every step. but how the fuck does someone come up with a proof like this? all the steps seem so arbitrary

[unique cypress]

That's how it goes with proofs in elem NT

[sacred junco]

someone must have come up with it. how did they come up with it?

[unique cypress]

Just getting used to the type of proofs?

[sacred junco]

how to get used to this? i dont see any sense of direction in this proof. feels like a bunch of random manipulations that end up somehow working

there has to be a better way to try to prove things like this than just trying random stuff until something works

Tell me you are doing elem NT without telling me you are doing elem NT

[sacred junco]

I don't even get how they got x^N-a^2 q

[sacred junco]

wym by got?

Why q divides this expression?

because q divides N

that means N = qd no?

yeah so x²N-a²q = q(x²d-a²)

so q divides it

Oh x^2 qd - a^2 q

@wooden remnant

[unique cypress]

Well you start with what's given and see if you can play around to get the result

[sacred junco]

i tried but i wasnt able to prove this on my own

And i dont feel like i learn anything looking at this proof

[unique cypress]

At first it might seem daunting but it will feel natural as you get used to it

[unique cypress]

Do something similar and see if you can imitate

[sacred junco]

Often proofs seem to have a direction to them, at least ones i see

There is a motivation for each step

[unique cypress]

Yeah the direction is not obvious in this one?

[sacred junco]

Not at all to me

idk why theyd consider x²N-a²q

Seems like a strange quantity to consider

[unique cypress]

It relates the sum of two squares and the fact that it has q as a factor

You see the hypothesis says N is sum of two relatively prime squares and you have some q which acts as a prime divisor of N

So the expression is natural to consider

[sacred junco]

its very assymetric using only the x and a

doesnt look that natural to me

[primal pewter]

they wanted to get some things cancelled out

it's the same trick you would perform if you wanted to calculate something like gcd(2n+1,5n+3)

[unique cypress]

Yeah

[sacred junco]

Tbf idk how id do that. i prob should try it ig

To this day I still don't understand how they got the binom

[primal pewter]

when all the exponents are 0, mu(...)=1 (and there is one case)
when only one exponent is 1, mu(...)=-1 (and there are (r choose 1) cases)
when exactly two exponent are 1, mu(...)=1 (and there are (r choose 2) cases)
etc.

[unique cypress]

This needs a bit of combinatorics argument. They are just writing out all the possible ways of using the mobius function. For example the C(r,1) case simply counts how many mu(p_k) you have with the sign being -1 because you have odd number of primes and so on

The ordering if mu(p_1)+mu(p_2)+...+mu(p_k) doesn't matter so this should give you a hint that it's a combination problem

[sacred junco]

huh

[sacred junco]

OHHHH THISSS

I feel so dumb

[primal pewter]

I was just running through all the cases: no 1s, one 1, two 1s, and so on

[sacred junco]

I was always wondering where the heck the binomial coefficient comes from

Thank you guys

Youre welcome

[wooden remnant]

holy shit

[trim jungle]

can someone hint me with this

[primal pewter]

calculate the first few sums and you will notice a pattern

or wait a second, I misread

I think I figured it, but I don't really have time to write in full details now

the pattern is odd, even, odd, odd, even, odd, odd, even, ...

the even terms are F[2], F[5], F[8], ...

the only way I can think of for finding the largest F[3k+2] <= 4*10^6 is by using the formula of the n-th Fibonacci term

and the formula would also help us evaluate F[2]+F[5]+F[8]+... (we get two geometric sums)

[prisma folio]

What I asked in #proofs-and-logic also fits here

[ashen talon]

I'm trying to understand the proof of Dirichlet's approximation theorem.

This theorem states that for all real \alpha and N (N here real, not integral, yes it's bad notation), with 1<=N, there exists integer p,q with q<=N such that |q \alpha - p| \le 1/N

This proof is by Minkowski's lattice theorem, which states that if you have a lattice with fundamental volume V in R^n, and a convex symmetric (about the origin, that is, x|->-x) set S with volume > 2^n V, then S contains a lattice point. The lattice we'll use will just be Z^2 in R^2 and the set S will be
{(x,y) : -N - 1/2 <= x <= N + 1/2, |x \alpha - y| \le 1/N}.

Now, clearly this is symmetric. It's also easy to see that it's convex. But why does it have volume > 4?

[ancient crow]

do you want a hint as to how to prove minkowksi in R^2 with Z^2?

but it's clear how to make counterexamples for any area <4

just make something convex that hugs the square with vertices at +-1,+-1

[primal pewter]

@ashen talon A strategy for calculating volumes like that is to use linear transformations.
if f is a linear transformation, then vol(f(S))=|det(f)|*vol(S)

Consider the following rectangle:
C={(x,y): -N - 1/2 <= x <= N + 1/2, -1/N <= y <= 1/N}

we have vol(C)=4

and now consider the linear transformation phi:R^2-->R^2 given by phi(x,y)=(x,ax-y)

Notice that S=phi^(-1)(C)

so if we let f=phi^(-1), we have vol(S)=|detf|*vol(C)

finally, the matrix of phi is

a -1

so |det(f)|=|det(phi)|^(-1) = 1

so vol(S)=4

there's no problem that it's equal to 4; Minkowski's theorem has this version that if the body is closed, than the theorem works with ">=" instead of ">"

[ashen talon]

I understand minkowski's theorem (i like it, personally)

[ashen talon]

Oh! I see. Thank you.

[ashen talon]

Yeah, because if the quotient map by 2L was injective, local area preserving become global area preserving would still mean that you fill up the entire fundamental volume, and thus you at least have density, so that if closed you can take a two limits that get you congruent points, and then continue with the proof.

[primal pewter]

yes, or you can apply Minkowski's theorem for the sequence of bodies (1 + 1/n)C, thus obtaining a lattice point (x_n,y_n) in each of them

and all these points lie in 2C, so they are finitely many, so one of them belongs to infinitely many bodies, and we pass to the limit for this point

[tribal palm]

There is a sequence listed here:

https://oeis.org/A056221

They list like 3 different formulas for it, but I can't make sense out of it. When I try and recreate the sequence using one of their formulas it doesn't make the sequence.

Also I have no idea what a "Little Hankel" transform is.

[primal pewter]

I see two formulas, and they are identical
p[n+1]^2 - p[n][n+2]
where p[k] is the k-th prime

[tribal palm]

I think I figured it out, it was (Pn+1)^2-(Pn)(Pn+2)

but I also don't understand the:

"little Hankel" transform that sends [c_0, c_1, ...] to [d_0, d_1, ...] where d_n = c_n^2 - c_{n+1}*c_{n-1}.

formula listed on the page

Oh its just a sequence, but why are we sending from c to d?

[primal pewter]

yeah, it's just a sequence sent to another sequence
the letters don't matter

[smoky cape]

okie

every?

you mean with denom < n and in that range right?

not "prove". we know that by induction hypothesis

okie so let me formalize what we're proving

we want to show S = Q n [1/2, 1]

what we prove is: given n > 0,
every m/n such that 1/2 <= m/n <= 1, lies in S.

let's call that statement P(n)

P(1) is true, because only rational in [1/2, 1] with denom = 1 is 1/1 which lies in S

doing an induciton means, you're assuming P(1), P(2), ... P(n-1) are true

and from this you conclude P(n) is true

so by induction we would know P(n) woudl be true for every n > 0

so yep. we assume P(q) is true for q < n.

and now we want to check P(n)

so we pick m/n in the range [1/2, 1]

since we already know 1/2, 1 in S, we may assume strict inequality 1/2 < m/n < 1

okie, i'll let you write then

.<

try explaining me >.<

[smoky cape]

how do you know this m/n is also in S

yee ofc

right

yep

and i suggested to take a = floor(n/2)/m and b = ceil(n/2)/m

[smoky cape]

clearly a,b are rationals with denominator m

if we show a, b in [1/2, 1] we're done right

because floor(n/2) + ceil(n/2) = n

lets take cases

if n is even

we know 1 < n/m < 2

oops

so a = b = n/2m lies in [1/2, 1]

and if n is odd,

we want to show 1/2 <= (n-1)/2m <= (n+1)/2m <= 1

that's the induction hypothesis. a, b are rationals with denominator = m which is less than n

we assumed that P(m) is true

[smoky cape]

that is, we want to show
n-1 >= m
n+1 <= 2m

and this is obvious because we assumed 1/2 < m/n < 1, which is same as n > m and n < 2m

n > m implies n-1 >= m

and n < 2m implies n+1 <= 2m

so we're done :3

so in summary:
we picked m/n in (1/2, 1)
proved a = floor(n/2)/m and b = ceil(n/2)/m lie in [1/2, 1]
by P(m) we knew a, b in S
so 1/(a+b) = m/n in S

this shows P(n) is true

[prisma folio]

#help-13 message also fits here

[sacred junco]

Can someone review this

[spice pelican]

ur handwriting is perfect lol

[meager remnant]

Hey guys, I'm a computer science student and I really like to solve coding challenges on project euler, leetcode, etc, and I feel like I could improve a lot on my abilities with number theory

Do you have a book or course you can recommend me?

I have more free time now, and would love to adquire knowledge

[rare barn]

I’m using AoPS intro to number theory book but idk if that’s the most comprehensive or best for what you’re looking for

[meager remnant]

Thanks, I will check it out

oh, yeah, I know :)

It's great

but I'm looking for a more structured approach, using a book or course

instead of just reading the solutions that use techniques that I don't know yet

but both are important

ooh

ok!

Thanks

I see!

thank you

[smoky cape]

hm?

so the same 1/(a+b)?

yee so since 2 is bigger i would think the range this time is [1/4, 2]

but we're also allowed sqrt3

so one guess would be Q(sqrt(3)) ∩ [1/4, 2]

then i'll try to prove/disprove that

rationals

Q(sqrt(3)) = {a + bsqrt(3) : a, b in Q}

idk, haven't thought much

i'm not so sure even about this.

if we just start with 2 (and ignore sqrt3 for now)

i'm not sure we get everything in Q n [1/4, 2]

last time, we specifically used that m/n < 1, so m < n

this time we would only have m < 2n

so obvious induction doesn't seem to go anywhere

the best technique is called "numerical examples"

try analyzing all fractions with small enough denominator and see what shit goes right or wrong

for the last one i tried till 4 and realized what was to be done

if the initial values are too complicated, maybe i'll think more about what other conditions are implied by that 1/(a+b)

for example, a, b in S then 1/(a+b) in S, so 1/(1/(a+b) + 1/(a+b)) = (a+b)/2 in S

well just knowing the examples doesn't always tell the thing

[smoky cape]

while computing stuff by hand you notice a few patterns which might be useful in the proof.

i don't see 1/1 in that, so it suggests that the guess [1/4, 2] ∩ Q might be wrong

[weary rune]

for part a, the "if" direction seems trivial, but not sure how to proceed without using prime factorizations for "only if"

[primal pewter]

refer to coprimality:
d_1 is a divisor of m
m is coprime to n

these together imply that d_1 is coprime to n, so in particular it is coprime to d_2'

and then use this in the given equality to conclude that ||d_1 | d_1'|| ||and prove similarly that d_1' | d_1||

[weary rune]

aight thanks

and for b how exactly do we apply multiplicativity of tau?

is it a counting argument to count the divisors in two ways or smth?

or am i off track?

"since tau(mn)=tau(m)tau(n) we see combinatorially that each divisor of mn is a divisor of m times a divisor of n, by part (a) the choice of constituent divisors is unique for each divisor of mn"

[weary rune]

wow that's crazy 😱

<@&268886789983436800> off topic spam across multiple channels, 🔨?

[weary rune]

^?

[verbal cedar]

what is tau?

[weary rune]

counts the number of divisors

i've read some more direct proofs that don't use that

so idk how to fit it in here

[primal pewter]

yeah, it's a counting argument:
m has tau(m) divisors
n had tau(n) divisors

so there are tau(m)tau(n) products d_1d_2 with d_1 a divisor of m and d_2 a divisor of n

according to part a), all these product are distinct, and it's clear that they are divisors of mn

||we know that tau(m)tau(n)=tau(mn), so we found tau(mn) distinct divisors of mn, but mn has tau(mn) divisors, so this means we found ALL the divisors of mn||

[weary rune]

ah yea i think that last part was what i was missing

that we count all of them

thanks!

[fleet bone]

ya its for high school olympiads

very popular book

may u share the prob : )

nvm i found it

[fleet bone]

i think a nice thing to observe is if a,b is in G a+b/2 is in G

for 1/(a+b) is in G so just use 1/(a+b) twice

so for any two numbers firstly u also have their average

can we show

all numbers of form 1-1/n are in G[not necesarilly the entire set]

[fleet bone]

all of form 1-1/(2^k) are in there

[prisma folio]

#help-24 message also fits here

[runic token]

ill js write out the combo proof for your future reference and because im bored:

claim: one of the first 173 elements in the sequence 1, 11, 111.. is divisible by 173.

proof: assume otherwise for contradiction. then divide the first 173 elements by 173. then each will have a remainder in between (inc) 1 and 172. by php we have that there are at least two w the same remainder, let's say $a_j$ and $a_i$. wlog let $j>i$. by euclidian algo we have $a_j=173k_j+r$, $a_i = 173k_i + r$ for appropriate $k_l,r$. then $a_j-a_i=173(k_j-k_i)$ so $173|(a_j-a_i)$. note that we have $a_j-a_i=a_{j-i}\cdot10^i$ and since $gcd(10,173)=1$ we have $173|a_{j-i}$ and we are done.

note: this proof is constructive in the sense that if we run a division algorithm with $a = a_n$ for $1\leq n \leq 173$ and $b=173$ we are guaranteed to find an $a_n$ for which $173|a_n$

[sterile pumice]

valley

[rare barn]

Anyone mind taking a look at this proof

[white lion]

what are you proving?

[leaden stream]

without knowing the assumptions given in the question, it's impossible to tell you if this is correct or not.
With the right assumptions, this works. with other assumptions this is false.

[rare barn]

The only assumption is that a is congruent with b mod m, and I’m trying to prove that for any positive integer n, a^n will be congruent with b^n

Probably extremely convoluted compared to what I could’ve done but I want to make sure my logic is sound

[leaden stream]

it looks like you're starting the proof with a^n is congruent to b^n

[rare barn]

I’m doing induction

Assuming it works for the base case of n = 1, it will work for 2, and 3, and so on

Is what mine says

[primal pewter]

@rare barn it's unclear, but it looks like you are simplifying things there, which is not always possible modulo

for example 2*5=4*5 (mod 10), but 2=/=4 (mod 10)

[rare barn]

We’re assuming congruence between a_1^n and a_2^(n-1)

Wait no we’re assuming congruence between that and a_2^n and a_1^n-1

And since those are congruent multiplying by (a_1 *a_2) maintains congruency

Which is the induction argument

And yes I know that’s overly complicated but I just want to make sure my logic is sound

[primal pewter]

@rare barn this parts confuses me

that symbol means "therefore"

[rare barn]

Yes

[primal pewter]

and that's why I mentioned simplification

that's not true

[rare barn]

Ah

Hmm

I’m not sure I see why

[primal pewter]

check the example I gave above

[rare barn]

I know the example

Fuck

Goddamnit

[primal pewter]

yeah, when working with congruences we can only simplify with things that are coprime with the modulo number

[rare barn]

How did I not see that fuck

I feel like one of the assumptions would take care of it though

[primal pewter]

no, any scenario is possible here

but you can just do classical induction

P(n) => P(n+1), rather than P(n-1),P(n) => P(n+1)

[rare barn]

?

[primal pewter]

what I mean is that you tried to use both a^(n-1)=b^(n-1) and a^n=b^n assumptions to prove a^(n+1)=b^(n+1)

but it's enough to work with a^n=b^n

[rare barn]

One sec I might have smth

Is this not valid

[primal pewter]

it's perfect

[rare barn]

Wow that is like infinitely simpler than what I did lol

I way overthought my first one

[thick panther]

hey :) is there a nice / efficient way of doing c? i can't really think of anything

[thick panther]

nvm i got it!

[fair vale]

Can this be proven just using the fundermental theorem of arithmetic with the well-ordering theorem on the natural? since it would just be a set of primes which are all natural when greater than 1? Or do i need to find another way?

[west glade]

this is the fundamental theorem of arithmetic...

[fair vale]

Not in my book.

[west glade]

well I mean its basically the same statement

it should be quite clear that you can write them in ascending order

[fair vale]

well thats why i mentioned the well ordering... but is it sufficient?

[primal pewter]

if you want all the details, then you also want that multiplication is commutative

[fair vale]

Oh yeah! good point.

[summer parrot]

And associativity

But one nevers does stuff in such a detail

The point is that if you wanted to do it you could

But omitting the details is the only reasonable way to go about it

[primal pewter]

associativity is pre-assumed, since otherwise the product would not be well defined

[summer parrot]

Yeah my point is that proving stuff in such a detail is overkill

If you can't conclude that you can order the primes in ascendent order immediately from the statement of the FTA then you're never going to be able to proof anything

And any proof would be pages and pages long

Specially when you start doing higher level math

[primal pewter]

that's true

but it might be the case that the book was really asking for a proof starting from the axioms

otherwise I have no idea why the proof was left as an exercise

or why the corollary was even mentioned

[potent patrol]

How can one prove that as p -> infty, the period of the decimal expansion of 1/p also tends to infinity?

p prime

<@&286206848099549185>

[runic token]

!help

[rotund gust]

To ask for mathematics help on this server, please open your own help channel or help thread. See #❓how-to-get-help for instructions.

[nova vine]

how do I prove this?

[weary rune]

is this just the general case of mobius inversion?

[nova vine]

i think its the dirichlet convolution of "number of divisors function" and "euler's totient function"

dunno where to begin

[unique cypress]

Start with phi * 1 = Id then convolve 1 on both sides

Where Id(n) = n and 1(n) = 1

[potent patrol]

Could anyone help with this?

I know the period is just the order of 10 mod p but where does that get me

[primal pewter]

@potent patrol if 1/p has period length n, then 1/p = k/(10^n - 1), where k is a number with n digits
so 10^n - 1 = kp, so p divides 10^n - 1

therefore, there are finitely many primes p for which 1/p has period length n (because 10^n - 1 has finitely many divisors)

[potent patrol]

Thanks. can you help with this one #help-30

[tribal palm]

Here is my attempt at solving the Goldbach Conjecture.

Constructive criticism is welcomed. If anyone wants to proof read it.

\

[west glade]

a graphical representation of the first 100 numbers proves nothing

[tribal palm]

read page 6

[west glade]

that page is essentially nonsense

https://i.imgur.com/09DgytX.png

you are using P_n here for half a dozen of different numbers

[tribal palm]

Its an infinite sequence.

[west glade]

that makes no sense

[tribal palm]

its in general

[west glade]

thats not how that works

[tribal palm]

you can test this construct to make any even number and its possible.

a prime plus a prime times a special function, and the special function has two options.

[west glade]

another thing, you are claiming that the practical numbers together with doubles of the primes, make up all even numbers. thats false. even 102 already isnt in either list

[tribal palm]

Hmmmm. I will have to look into that.

102=97+5

This does not fall under either case that I have presented.

you are correct, there is one other hidden sequence at play that I guess I overlooked.

44,50,52,68,70,76,92,98,102,110,114,116.......

well hang on, its true that 102 is not in either sequence, however 102 = 5 + 97, this falls under the even shift case.

So I think the only part that was incorrect was to assume two sequences to make up the even numbers, now there are 3 sequences.

Here is the update, the only thing that changes was that now there is a 3rd sequence needed to make the full set of even numbers.

[rare barn]

But how have you proven that every single even number works

[tribal palm]

By showing that there are only 2 functions which satisfy the formula.

there is a constant function, think

f(x)=1

And f(x)=1+(x/Pn)

The case of 1 is trivial, the case of the other, because there is a variable h or x it is flexible to generate an even number with this or should I say, an even shift.

Each time.

[rare barn]

You should maybe bring this to a more advanced NT channel, I’m not qualified to find the flaw in your proof

[patent acorn]

here's the incorrect step

you just claim this without proving it at all

this is also wrong

44 is the sum of 3 and 41, which are prime numbers that are 38 apart, but it is not in A005153

[rare barn]

Thx bee

[sacred junco]

Ahh elementary numbers

Don't even know what that is

[weary ivy]

No it's number theory

There's advanced number theory

[sacred junco]

What's a number theory?

Same as the bridges problemm

[weary ivy]

Study of the integers using elementary techniques: Prime numbers and divisibility, modular arithmetic, congruences

Includes: Simple Diophantine equations, reciprocity, number bases, results on number theoretic functions (Euler's totient function, the prime counting function, etc.), the rings ℤ/nℤ, etc.

Questions requiring analytic techniques (e.g. limits, complex calculus) do not belong here; try a channel in the "Advanced" section.

[weary ivy]

That's graph theory

So the Chinese Remainder Theorem is number theory

[sacred junco]

Ahh

Is this simple?

Could i manage to do these?

[weary ivy]

With enough study yes, you just need time

And effort

[whole oracle]

can i ask questions in this room?

: give n be natural number show that there is positive number of a,b so that 4a^2 + 9b^2 -1 can be divided by n

[wind juniper]

please can someone help me prove the wilson's theorem

i am stuck at some point

like i understood most of the way

[west glade]

it would help to say where you are stuck

[wind juniper]

when how can this guy say that every number has an inverse in that range?

i understood all the proof

but i can't get why does every number have an inverse in that range

[half yacht]

Since p is a prime, then every number from 2 to p-1 is relatively prime to p. Hence, each of them has an inverse

[wind juniper]

yes

but how can you suppose that the inverse is also smaller that p

[half yacht]

Suppose?

Did you mean prove?

[wind juniper]

i ment assume

sorry

[half yacht]

Wait, I don't get why we have to assume that the inverse is smaller than p.

[wind juniper]

like is it an already acquired information?

[half yacht]

In the provided proof, there were no assumptions about having an inverse smaller than p

Since we are already working modulo p, which guarantees it being smaller than p

(about this last sentence i said, don't take it so seriously, I am not sure about it. Just my intuition)

[wind juniper]

because when the guy ordered all the numbers he assumed that every number multiplied in (p-1)! has an inverse that is also multiplied?

[still flare]

As stated, remember we are working modulo p. So for example 15 == 2 modulo 3.

[wind juniper]

why is that?

[half yacht]

Well, we listed all numbers from 1 to p-1. Since every number less than p has an inverse (mod p), then it must be found on that list

[still flare]

Because every number not congruent to 0 mod p has an inverse modulo p, when p is prime. You are hopefully familiar with this fact because I don't want to rehash number theory.

[half yacht]

We just don't know what it is, but we definitely know it exists there

[wind juniper]

so every number not congruent to 0 mod p has always an inverse mod p that is also always in the product of (p-1)! ?

[still flare]

Yes

[wind juniper]

OK thank you so much

i am not that good with number theory because i am still in high school and the teacher gave us homework to prove the wilson's theorem

and we didn't get that deep into number theory

[sacred junco]

From the following system of equations:

$$

\begin{pmatrix}
d_1 r_1 - r_2 =0\
r_1 + d_2 r_2 - r_3 =0\
-r_2 + d_3 r_3 =0\
\end{pmatrix}

$$

How do I determine how $r_i \mid r_j$? For instance, from Equations (1) and (3), it is clear that $r_1 \mid r_2$ and $r_3 \mid r_2$, but what can I gather from the second equation?

[sterile pumice]

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

[primal pewter]

from the second one alone you can't get much information, but you can combine equations
for example, from (2) you get r_1 | d_2r_2 - r_3
but since you have r_1 | r_2 from the first one, it follows r_1 | r_3

and using a similar reasoning you can find r_3 | r_1, which combined with the above relation yields r_3 = +/- r_1

[sacred junco]

Okay I see

Thank you!

Do you happen to know any software that would be able to do this for me?

[primal pewter]

no, I don't know

but maybe wolfram alpha could solve the system

although it's not hard to do it by hand

I mean solve without the constraint that the numbers are integers

[sacred junco]

I agree that it's not hard to do by hand but it gets much harder the more equations you have. For instance:

\begin{pmatrix}
r_1 - r_2 - r_3 - r_4 =0\
-r_1 + d_2 r_2 - r_3 =0\
-r_1 - r_2 + d_3 r_3 =0\
-r_1 + d_4 r_4 - r_5 =0\

• r_4 + d_5 r_5 =0\
  \end{pmatrix}

[sterile pumice]

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

[sacred junco]

Is pretty nasty to figure out

[unique cypress]

are you comfortable with R, MATLAB or anything?

[rare barn]

This problem is kicking my ass and the people in the help channels told me to go here

[rare barn]

Citrus you’ve been typing for like 30 minutes are you ok

[serene sinew]

i know nothing about number theory but:

if the number of repeating digits is m, and 1/3^n is x, then:
10^m * x - x = x(10^m - 1) is a whole number, call that whole number y
that means y = (10^m - 1), which is just m 9s, must be a multiple of 3^n
so y mod (3^n) = 0
and m is the smallest natural number that satisfies that equation (cuz if there was a smaller m, the number of repeating digits would just be that m instead)

also, any number made up of just 9s must be divisible by 9, so if we divide everything by 9 we have:
y/9 mod (3^(n-2)) = 0
y/9 is just m 1s, so the sum of its digits is m. say y/9 = z, so z is divisible by 3^(n-2)
in order for z = m 1s to be divisible by 3^(n-2), it needs to be divisible by 3, and we see that for a number to be divisible by 3, its digits must sum to a multiple of 3, and the smallest possible multiple of 3 is 3

in general, we have that in order for a number to be divisible by 3^(n-2), we have to be able to divide it by 3 n-2 times. say you do that and get a number q, which is no longer divisible by 3. thus:
q * 3 = z / 3^(n - 3) must have digits summing to a multiple of 3
q * 3 * 3 = z / 3^(n - 4) must have digits summing to a multiple of 3 * 3
q * 3 * 3 * 3 = z / 3^(n - 5) must have digits summing to a multiple of 3 * 3 * 3
...
q * 3^(n-2) = z must have digits summing to 3^(n-2)
since z is m 1s, the smallest number of digits that would do this is when the number of digits is m = 3^(n-2)

[rare barn]

I don’t just want the answer

[serene sinew]

idk how to help sorry 😭 i know nothing about number theory

i just decided to have a go at it myself

[rare barn]

Does a single person in this discord know anything about number theory

[serene sinew]

tbh idk if my solution even works

lol

[rare barn]

Istg no one does

I have an idea that i feel is on the cusp of working

[topaz raptor]

Number theory is... just kinda over done ngl
I personally don't want to do it

[topaz raptor]

ig u can use induction

[rare barn]

I have an idea to use induction but I’m not sure it’s rigorous

[topaz raptor]

ah, i see, ill tell u if i get anywhere

[rare barn]

HOLY SHIT

I GOT IT

[topaz raptor]

you did? awesome
what did u try?

[rare barn]

So the base case is 1/9, which is 0.111…

To divide this by 3^n, there must be 3^n total division steps due to divisibility rules for powers of 3

So it must take 3 steps to get to 1/27 since 1+1+1 is the first that leaves a remainder of 0

And that goes for any power of 3

[topaz raptor]

i was just exploring this too! good job!

[serene sinew]

👏

congrats

a much better proof than my "proof" lol

(ive never done proofs before tbh, thats why it took me 30 minutes of typing, tryna formulate my thoughts into words)

[rare barn]

That was probably my biggest brain blast ever

[serene sinew]

waow

[topaz raptor]

are u doing comp math?

[rare barn]

My books I’m using have problems from comps but I’m not actively participating in any atm no

I do want to soon though

Also the book used this but I prefer my solution

[topaz raptor]

yep, yours is concise, what book are you using btw?

[rare barn]

AoPS introduction to number theory

[topaz raptor]

oh, I have to do AoPS, gonna try math comps again this year, thanks

[rare barn]

GL!

[weary rune]

undergrad NT books are too bogged down in symbol pushing formalisms

that's why i like aops books bc they cut out all the bullshit and get straight to the point

[rare barn]

God that was an amazing problem

Kicked my ass for like an hour only got me to have a single insight that instantly cracked it wide open

[weary rune]

i may or may not have bought their entire line of books in middle school, i still read them even as an undergrad now - they're that good with lots of interesting problems to chew on

[rare barn]

I’m going through all of them to learn math

This is my 3rd

[weary rune]

nice

which other ones have you done

[rare barn]

Pre algebra and intro to algebra

[weary rune]

nice

well going through the whole series will give you a great math foundation, much better than what you'd get in a standard curriculum

[rare barn]

Indeed

[weary rune]

i wish they'd publish an intermediate NT or intermediate geo text tho 😔

[rare barn]

I’m excited for the geometry book

[weary rune]

oh yeah geo is really fun too

people in the contest circuit usually hop to evan chen's euclidean geometry in mathematical olympiads once they've mastered the basics (basically the content of intro geo + a bit more)

[rare barn]

Honestly all of their books seem so good

I’m excited to learn more

[weary rune]

they have some structural issues in some places but their approach of having you try the problems first works so well

especially when they guide you through some of the bigger proofs

[rare barn]

Ikr

[weary rune]

lets you see the motivation for them better

[rare barn]

I’m prob better at what math I’ve learned than my college educated mom

[weary rune]

i have a really old beaten up copy of volume 2 that i studied religiously in early high school lmao

not all majors require very much math :)

[rare barn]

True

[weary rune]

in the US the standard seems to be calc 2 or 3 for non math STEM majors

and either calc 1 or stats for everyone else

[rare barn]

She was a psychology major tho so I assume she’s taken stats

[weary rune]

yea

[sacred junco]

I'm comfortable with Mathematica

I'm kinda comfortable with MATLAB and Sage

[mint dew]

Sorry, I'm an absolute beginner... Can I ask for recommendations for the best number theory book ..?

I've decided to learn number theory to support my cryptography class... so I have no idea about this branch:(

[white lion]

an elementary introduction to number theory by calvin t long

[half yacht]

if you want to speedrun number theory, there's that article by Sato from AOPS

[white lion]

he also has a crytpography section in the 3rd edition I believe. I think it is out of print but it's a wonderful book and worth picking up IMO (they might have it in your schools library)

[urban dust]

#book-recommendations message

[weary rune]

not sure how to work with the "less than 4 solutions" condition here

[primal pewter]

basically you have to prove that if p=1 (mod 4), then the equation has 4 solutions

[weary rune]

so in that case, $4\mid\phi(p)$

[sterile pumice]

elrichardo1337

[weary rune]

since $p-1\equiv 0\pmod{4}$

[sterile pumice]

elrichardo1337

[weary rune]

how do we connect that to the congruence having 4 sols

[primal pewter]

are you familiar with quadratic residues?

[weary rune]

we haven't covered those yet 😭

so idk what the intended approach is without them

[primal pewter]

it can be done without them

firstly, x^4-1=(x^2+1)(x^2-1)

two solutions are 1 and -1 and we want to get other two from x^2+1=0 (mod p)

[weary rune]

oh d'oh factoring

[primal pewter]

in other words we want -1 to be a quadratic residue, but we avoid this

we just want to construct a solution

[weary rune]

is this where $p\equiv 1\pmod{4}$ comes in

[sterile pumice]

elrichardo1337

[primal pewter]

and then if x is a solution, -x is another solution

yes

it's related to Wilson's theorem

[weary rune]

hmm how so

[primal pewter]

(p-1)! = -1 (mod p)

so 1*2*3*...*(p-1)/2 * (p+1)/2 * ... * (p-1) = -1 (mod p)

and from the second half use k = k-p (mod p)

[weary rune]

so our solutions would be of the form $1\cdot 2\cdot\cdots\cdot \frac{p-1}{2}?$

[sterile pumice]

elrichardo1337

[primal pewter]

yes

[weary rune]

hmm aight

[weary rune]

it seems like this would just be fermat

but i'm not sure about the cases where $p\mid a$

[sterile pumice]

elrichardo1337

[weary rune]

oh wait that wouldn't matter would it?

we would reduce the base mod p first then apply fermat, and clearly $p$ does not divide any of ${0,1,\dots,n-1}$

[sterile pumice]

elrichardo1337

[primal pewter]

yeah, I guess they want to use a^p=a (mod p) to reduce degrees

this implies a^(pk+r)=a^r (mod p)

[weary rune]

yea

[primal pewter]

but induction doesn't really seem to be necessary

[weary rune]

yeah

you could just take any arbitrary term

[primal pewter]

and in fact the problem has a one line solution using Euclidean division

[weary rune]

and clearly all terms must be reducible to degree less than p

[primal pewter]

we can divide f by X^p-X and take the remainder

[weary rune]

is the following an acceptable proof that $\gcd(a,mn)=1$ implies $\gcd(a,m)=\gcd(a,n)=1?$
since $\gcd(a,mn)=1,$ there exist integers $x,y$ such that $xa+ymn=1=xa+(ym)n=xa+(yn)m$
but that means there also exist integers $x,y_1=ym,y_2=yn$ such that $xa+y_1n=xa+y_2m=1,$ so that $\gcd(a,m)=\gcd(a,n)=1$

[sterile pumice]

elrichardo1337

[topaz raptor]

Yup, it works

[weary rune]

aight

[sacred junco]

What is the use of the elementary number theory, can someone please brief it for me please.

I am in high school so this is the first time i ever saw this.

[weary rune]

https://letmegooglethat.com/?q=elementary+number+theory

at a basic level, number theory deals with divisibility, primes, factorizations, modular arithmetic, and other things

[silver oak]

if you heard gcd, you were learning this

[fleet bone]

i mean

at school level its not rigorous at all

[sacred junco]

Nope

K is nothing related to it

Know*

[fleet bone]

they assume that factorization is unique

and stuff

[though any formal oly course in India pretty sure doesnt care proving the uniqueness too lmao]

[fleet bone]

ur school didnt even teach what greatest common divisor is

💀

its called HCF in some curriculums

[sacred junco]

Yes HCF

I was confused about what GMD was

[lime oar]

A lot of current encryption technology relies on prime number stuff which comes out of number theory. Hth.

[sacred junco]

Oh, is it primarily for computing or is there any other use for it in terms of maths?

[lime oar]

I think the Wikipedia article on the topic has a good summary. I’m no expert. It’s certainly applicable to most aspects of modern communications and computation (networking, error correction, memory management). Anything to do with randomness. I’m sometimes unsure of the boundaries between number theory and combinatorics. I’ve heard it applies to physics also but I’ve not studied that aspect.

[sacred junco]

Ahh I see, I will look into it then.

[lime oar]

I believe there’s also been a bunch of connections between number theory and analysis that have yielded really profound results. The structure of Andrew Wiles’s proof of Fermat’s Last Theorem, for instance, pulled together a bunch of analysis, algebra and number theory in ways I don’t fully understand but look like they’d be really cool to learn about :)

[lime oar]

There’s also “numerical analysis,” where number theory is applied to continuous objects that are otherwise intractable https://www.mathworks.com/discovery/numerical-analysis.html
https://www.reddit.com/r/math/comments/10aetmr/what_actually_is_numerical_analysis/

Personally number theory is my current favourite math, because it’s often easy to describe problems, and I’m interested in Paul Erdős :)

[primal pewter]

wait what? numerical analysis is not related to number theory

[lime oar]

Fair. I was not being precise, and like I said, I’m no expert. I meant in the sense that it involves application of numerical and computational methods.

[patent acorn]

"numerical methods" and "number theory" are different meanings of number

number theory is natural numbers/integers, continuous objects if they're "numbers" would usually be real or complex numbers

the word "number" is honestly pretty vague

[sterile pumice]

Godspell

[nova vine]

this is a legendre symbol and p>7 is a prime. I dont understand what the statement is asking me to find

[fleet bone]

basically find (7/p) in terms of p mod 28

[nova vine]

dont get it

[fleet bone]

ok so basically

given p mod 28

they want u to determine (7/p)

like similar to how u find critetnions of (3/p),(2/p),... and stuff

or (-1/p)

if ur solving any book those prolly would be given before

[nova vine]

do I need to find if 7 is a quadratic residue?

[fleet bone]

what does (7/p) mean in first place lmao

finding (7/p) is same as that [as p>7]

[lime oar]

This. Thank you. I was just reading the introduction to a number theory book that traces the historical evolution of number as a concept. Pretty wild stuff.

[meager sand]

Guys, how can I proof 2²⁰²³ == 8 (mod 10)?

[weary rune]

“prove” not “proof”

look at the units digits for smaller powers of 2, and try to notice a pattern

[white lion]

use the fact that a^phi(n) = 1 (mod n)

[round swift]

you can't use that

2 is not coprime to 10

[white lion]

oops you're right, rookie mistake.

so you're going to have to just good ol basic modular simplifcation

note that 2^5 = 2 (mod 10)

that should be enough

[heavy plover]

🚀

[sacred junco]

Is my solution to the problem correct? Please let me know 🙏

I am not sure if the solution is correct or not

But would like to know if there are some mistakes

[primal pewter]

it's wrong

this conclusion is false

if you have ab=cd, this does not imply a=c or a=d

[distant sandal]

I don't see any contradiction

How does it contradict the theorem premise

[patent acorn]

well $y \in \mathbb{Q}$ contradicts the assumption that $y \not\in \mathbb{Q}$

[sterile pumice]

bee [it/its]

[distant sandal]

👍

[sacred junco]

Then it seems you haven't seen the conditions I used after that.
Even though, There at that conclusion of ab = cd I am trying to say that 'a' may be equal to c or 'a' may also be equal to d.

And if a = c then b = d or

If a = d then b = c

[primal pewter]

@sacred junco 12*30=15*24

[sacred junco]

Hmmm....

[sacred junco]

Then in this case we cannot say that a = c or a = d

But the problem which I was trying to solve had given an equation

Wait wait

I got what's wrong

Okay

[novel locust]

Hi there, can someone explain how could I visualize the regions this proof describes? I don't get how their area is $(2n+1)^2$. I understand the rest of the proof well enough, including the conclusion. By the way, here $\Lambda$ is just the set of point with integral coordinates. Thanks in advance

[sterile pumice]

lazur__

[novel locust]

I was thinking of something like this, the conclusion would make sense but that region wouldn't have area (2n+1)^2... can someone help me?

[primal pewter]

@novel locust you have (2n+1)^2 identical regions that do not overlap, and the area of a region is delta
therefore the total area is (2n+1)^2 * delta

for visualization, it's something like this (not necessarily circles, but this was easier for me to draw)

[unkempt magnet]

How can I know there are (2n+1)² regions though? What does n depict? and why do we make it approach infinity?

No, wait. Nevermind I'm dumb

Thanks a lot, that makes a lot of sense

[wheat patio]

Hello hello! I'm trying to figure out this proof, but I feel like I'm missing something. Does anyone have any ideas of where I would go with this proof?

[coral venture]

if ab divides c then a divides c

[west glade]

what does n|a-b mean

[wheat patio]

N divides a-b, so there exists an integer y such that ny=a-b

[wheat patio]

Oh okay so it is okay to conclude that m|a-b and thus a is congruent to b mod n? I didn't think I had enough proof yet since we don't know if it would be m or x that divides a-b.

Wait that wouldn't matter

[wheat patio]

I see this is correct now

So this would be enough for the proof right?

[primal pewter]

yes, but you can even skip the mx=n part

m | n and n | a-b implies m | a-b

[wheat patio]

I could, but I don't want to run the risk of my prof docking points if I don't show I know why I can skip that part. Duly noted though, I'll check with my TA and see what they think I should do.

[primal pewter]

you technically still skipped it

[coral venture]

m and x both divide a-b if mx divides a-b

[primal pewter]

the short argument is that the divisibility relation is transitive

which you tacitly used when you concluded that mx | a-b implies m | a-b

[wheat patio]

True

[wheat patio]

@coral venture ^ thank you though! Appreciate you making the effort to clarify further

[coral venture]

No problem

[turbid fable]

hi

[heavy plover]

🚀

[sterile pumice]

Plazzi

[sacred junco]

v_p is the p-adic valuation

[primal pewter]

@sacred junco the point is that if you use binomial expansion for (1+p)^(p^(n-1)), then you have 1 + (...), where the remaining terms are multiples of p^n

[sacred junco]

I'm stupid

Thanks

[frail swift]

What are the solutions of this equation $9a^3 +10b^3 + 11c^3 = 0$?

[sterile pumice]

Abir

[frail swift]

<@&286206848099549185>

[primal pewter]

@frail swift work modulo 9
||infinite descent||

[tribal palm]

I am working on the Goldbach conjecture. The paper is attached.

The main thing I have to prove is this:

[cinder linden]

we claim to prove the goldbach conjecture, which states that the sum of two prime numbers is always an even number

uh

[patent acorn]

ok yeah that's false and also isn't the goldbach conjecture

[cinder linden]

at least the paper doesn’t try to prove the statement in the abstract

[patent acorn]

i think it might in section 4? but i can't actually understand that well enough to work out what it's supposedly a proof of

section 3 states that the goldbach conjecture is true, and claims to have thereby proven the goldbach conjecture

[cinder linden]

can i ask why you’re trying to prove it?

since the combined sequence represents the set of all even numbers
i think listing that it works for the first 50 even numbers is not a proof that it works for all even numbers

[pale lagoon]

Let $a_n$ be the number of positive divisors of $n!$ for all $n$, and $(u_n)$ defined for all $n$ by $u_n=\frac{a_{n+1}}{a_n}$. Can you help me to show that the subsequential limits of $(u_n)$ are 1 and the $\frac{k+1}{k}$ with $k\in\mathbb{N}^*$ please ?

[sterile pumice]

TimourX

[pale lagoon]

Don't hesitate to ping me

[unique cypress]

Are you serious rn?

[void abyss]

Isn’t 44 in the green sequence?

It’s hard to point out exactly what things are wrong since the entire structure of the proof doesn’t make sense to me. But at least I can tell you that this step is wrong. P_n will be different for each natural number

[gleaming dome]

hi i m new in this server

[cinder linden]

hello!

[errant otter]

theorem 112: if p is prime, then x^(p-1) -1 = (x-1)(x-2) ... (x-p+1) mod p. if we compared the constant terms, we obtain a new proof of wilson, and if we compared the coefficients of x^(p-2), x^(p-3), ..., x, we obtain:

theorem 113: if p is an odd prime, 1 <= l < p-1, and A_l is the sum of the product of l different numbers of the set 1, 2, ..., p-1, then A_l = 0 mod p
I'm unsure as to the definition of A_l here, it feels vague. Could anyone elaborate?

"sum (over how many?) of the product of (any?) l different numbers of the set {1, 2, ..., p-1}"

sum over all possible ways to pick l numbers from the set?

[errant otter]

ah, okay, so it is (alternatively it A_l = the coefficient of x^(p-l-1) for the polynomial (x-1)(x-2) ... (x-p+1))
.... now I'm having trouble understanding why this is true

[nova vine]

How do I calculate 55125 by using its given prime factors since our function uses the divisors of 55125?

[runic token]

$\sum_{d|n}$ is summing over the divisors of $n$. in this case, prime factorization is $3,3,5,5,5,7,7$

[nova vine]

there are 35 divisors of 55125, i think there is some trick

[runic token]

ohh

hm

[sterile pumice]

valley

[nova vine]

<@&286206848099549185>

[runic token]

don't ping helpers in topic channels

[neat harness]

think it's just writing it out, using properties of jacobi symbol and grouping things up that repeat

[nova vine]

but writing out all 35 divisors is a bit tedious innit

[neat harness]

well that's the part where grouping things up that repeat would come in

since (-1/ab) = (-1/a)(-1/b) you could do a counting argument of how many (-1/3)'s, (-1/5) and (-1/7)'s show up

[nova vine]

hmm interesting

[neat harness]

not sure if it's the intended approach but can't think of any tools that give you a faster answer off the top of my head

[nova vine]

wouldnty that get exponentially long since I'll be splitting up almost every divisor

[nova vine]

yea

[neat harness]

well no because (-1/3) = -1, (-1/5) = 1, and (-1/7) = -1

[nova vine]

oh yes i overlooked that

[neat harness]

and jacobi symbol is a multiplicative function

so when you come across the term, say (-1/ (3 ^2 * 5 * 7^2))

[nova vine]

but the "numerator" has to be from natural numbers for it to be multiplicative

[neat harness]

you could use the fact that it's (-1/5) * (-1/(3^2 * 7^2)) where in the second jacobi symbol should have already been computed earlier

[neat harness]

nop

the denom is positive odd

numerator can be any integer

[neat harness]

ok well it's also true for integers

[nova vine]

i see

[neat harness]

if t were negative, you can just shift by some multiple of m so it lies within [0, ... , m - 1]

[nova vine]

okay hear me out

if the jacobi is multiplicative, then the whole f(n) is multiplicative, and we can put our primes from the prime factorisation in the function like, f(p_1)f(p_2)...

is this correct?

significantly reduces the tediousness

[neat harness]

OH

isn't there some tool uh

mobius inversion theorem

[nova vine]

yea but i dont see how i can use that here

[neat harness]

ok yes sorry, i misremembered the statement

[neat harness]

uh but as for this

how do you combine sums of jacobi symbols

[nova vine]

i tried, but it seems that even if one symbol becomes 0 then everything becomes zero. Since (-1/1)=1 and (-1/3)=-1 and adding them gives zero. I think this is why the "numerator" is restricted

[neat harness]

huh

[nova vine]

theyre multiplicative, and I got f(3)=0

but the answer should be 1, as I checked by brute force

unless im wrong

[neat harness]

oh yes

uh

just double checking you did

f(3)^2 * f(5)^ 3 * f(7) ^ 2

and f(3) = 0

[nova vine]

yes

then everything becomes zero

[neat harness]

wdym you checked by brute force

wait im stupid

it should be

f(3^2) * f(5^3) * f(7^2)

the exponents don't get factored out

[nova vine]

1, 3, 5, 7, 9, 15, 21, 25, 35, 45, 49, 63, 75, 105, 125, 147, 175, 225, 245, 315, 375, 441, 525, 735, 875, 1125, 1225, 1575, 2205, 2625, 3675, 6125, 7875, 11025, 18375

trhese are all the divisors

1 is 1

3 is -1

5 is 1

7 is -1

and so on

[neat harness]

this is answer

[nova vine]

and at the end i get -1

not 1 sorry

[neat harness]

f(3^2) isn't equal to f(3)^2

it's too late for math

[nova vine]

but still

f(9) = f(3)f(3) since its multiplicative right

[neat harness]

no

[nova vine]

how

[neat harness]

gcd(3,3) != 1

[nova vine]

hmmm

interesting, easy thing to overlook

[neat harness]

if f is multiplicative, f(ab) = f(a)f(b) only when a,b are coprime

[nova vine]

yes youre right

[neat harness]

yes sorry it's been a long time since elementary number theory and im tired

completely forgot sum of multiplicative function over its divisors is itself a multiplicative function

[nova vine]

hahaha no worries, I appreciate your effort

[calm sparrow]

Hello everyone! I'm a mathematics enthusiast, and I've recently delved into studying an introductory book on number theory. I'd appreciate some assistance along the way. 😁

I aim to prove that the cancellation law of multiplication in the set of integers Z (if a.c = b.c then a = b) need not be accepted as an axiom. It can instead be derived as a theorem from a proposition ensuring that for any integers a, b, and c, if a > b and c > 0, then ac > bc, and if a > b and c < 0, then ac < bc. However, I'm struggling to devise a strategy; transitioning from a strict inequality to an equality seems daunting. The book has equipped me with the fundamental laws of addition and multiplication operations (closure, commutativity, associativity, etc.), a theorem on the unique existence of the additive inverse, a.0 = 0, and the axiom of good ordering. Nonetheless, I'm open to any suggestions or tips to get started.

[spare frigate]

Assume ac=bc, then show that a is not greater nor less than b

so then it must be equal

[calm sparrow]

Great, I'll try it here 😁

[calm sparrow]

I've outlined the proof here and stopped at 4 cases to be checked, all of which lead to contradicting the adopted hypothesis that ac = bc. After verifying these cases, I could then use the law of trichotomy to conclude that it must be the case that a = b. Does that seem okay? Is there a more "intelligent" way to avoid checking all these cases?

[spare frigate]

No that’s a pretty good way of doing it.

I would do it that way it’s simple enough

I would however group the cases where c>0 together and c<0 together

But that’s a proof writing choice rather than a detail

[calm sparrow]

Thank you very much! 😀

[errant shore]

Suppose $a$ has order $d mod p$. So, we can write $a^{d} \equiv 1 mod p.$ Similarly, suppose $a^{b}$ has order $d$. So, we can write $(a^{b})^{d}\equiv 1 (mod p)$. For the sake of the argument, suppose $gcd(b,d)>1$. Let $gcd(b,d)=k$, such that $k>1$. Since $gcd(b,d)=k$, we can use Bezout's identity and write $bx+dy=k$, for some $x,y\epsilon\mathbb{Z}$.

[sterile pumice]

Matt.Rey

[errant shore]

This is my draft so far. I'm generally confused if this is correct or if I'm far off the mark

[primal pewter]

@errant shore if gcd(b,d)=k, then (a^b)^(d/k)=1

[rare barn]

That doesn’t sound true

[primal pewter]

it is true, but I meant to say =1 (mod p)

[rare barn]

Ah

[quartz crater]

$\pmod{p}$ :(

[sterile pumice]

ethan

[quartz crater]

does anyone have opinions on Stillwell or Silverman for nt?

[runic token]

silverman is fine as an intro

[quartz crater]

thanks!

[zealous swift]

guys

need help

[sacred junco]

Me too I need help

How can I prove the product of 3 continuous integers is divisible by 6

[rare barn]

What numbers must at least one of 3 consecutive integers have as a prime factor

[sacred junco]

2?

[rare barn]

That is one of them yes

[sacred junco]

...

Uhmm 1 is certainly not

I think it only has 2

[ashen stump]

Given three numbers n, n + 1, and n + 2, it is easy to prove that at least one of them is divisible by 3

[sacred junco]

Sorry I am completely new w number theory 😭

[acoustic shale]

I have a theory and I don't know where to post it so I'll just post here.

In short I've come up with a way to enumerate any number of infinite sets to the set of natural numbers. I don't see any flaws here but I'm told it should not be possible so I'm curious.

Suppose we need to map the set of even numbers, the set of odd numbers and the set of prime numbers to the set of natural numbers.

Take the natural set and pick apart the even positions. Map the whole of even numbers to those even position. We will still be left with odd positions. Separate the odd positions and write them down in assending order in a new set.
New set =[1,3,5,7,9,11...]
Now break those odd positions down further into even-odd positions and odd-odd positions
Even-odd positions will be the numbers like 3,7,11 etc that are by themselves odd but occupy the even positions of our new set. Likewise will be the odd-odd positions.

Now map the Even-odd positions with the odd set and finally map prime numbers with odd-odd positions.

In this was we can map an infinite amount of infinite series of numbers to just 1 set of natural numbers.

We can use the formula
(2^k)n - (2^k) - 1
To find the place of nth number of our kth series on Natural set of series.

[patent acorn]

yep, this is an example of a pairing function https://en.wikipedia.org/wiki/Pairing_function

i don't think that formula is quite right but the idea is sound

whoever told you that this isn't possible was either wrong, or they actually said something different

[acoustic shale]

I did check the formula upto 3 series, it's fine upto that point atleast

[acoustic shale]

Wait so I did not discover anything ground breaking 🗿

[patent acorn]

k=1, n=5 and k=2, n=3 both produce 7

[acoustic shale]

Wait what

[patent acorn]

yeah no, in fact i would not be surprised if this exact construction has already been found previously

[acoustic shale]

Also how did you find this our so quickly I'm impressed

[patent acorn]

probably the thing it was supposed to be referring to was cantor's theorem, which implies you can't enumerate all infinite sets using the natural numbers - as in, an assignment like "even numbers = 0, odd numbers = 1, prime numbers = 2, non-prime numbers = 3, all numbers except six = 4, ..." must miss some set

[patent acorn]

well it's the same as (n-1)2^k - 1

the -1s don't affect much so it's kind of just "is n2^k a pairing function"

and it isn't, because if you halve n and add one to k those cancel out and the answer doesn't change

so something like 2*2^1 and 1*2^2 are both 4

(2n+1)2^k-1 is a pairing function and i suspect that that's what the correct formula is for your construction

[acoustic shale]

Damn that's so awesome

What should I study in math to get on your level?

[patent acorn]

hm
i don't think it's really about particular knowledge? i just have more practice at mathematical thinking in general

...or i guess in this case it was the particular knowledge i had about the existence of pairing functions and what the correct statement of cantor's theorem is, but that's more just "you asked about something i happen to know about"

[acoustic shale]

Ah

Well thanks for the info, appreciate it

[patent acorn]

although, here's one generally useful trick: if you seem to have two proofs that prove opposite things, you can often run them against each other to see what happens

like, if you think you've found a bijection between the set of natural numbers and the set of sets of natural numbers, you can apply cantor's theorem to the bijection and it will actually give you a set that you missed

[acoustic shale]

Idk about cantors theorem and biejction yet but I'll watch a vid on it today, too curious now

[severe ermine]

is it good for the start?

[dark tiger]

I am taking a look at the theory of continued fractions. For a number $\alpha$ in the interval $[0,1]$ there corresponds a unique sequence $(a_1, a_2, \ldots)$ of natural numbers which may be thought of as the continued fraction of $\alpha$. If we think of each $a_n = a_n(\alpha)$ as a function of $\alpha$, is there an explicit formula for $a_n$?

[sterile pumice]

mdc

[patent acorn]

i think just, $a_1 = \lfloor\alpha\rfloor$, $a_2 = \left\lfloor\frac1{{\alpha}}\right\rfloor$, $a_3 = \left\lfloor\frac1{\left{\frac1{{\alpha}}\right}}\right\rfloor$, etc

[sterile pumice]

bee [it/its]

[patent acorn]

where $\lfloor x \rfloor$ is the floor of $x$, and ${x}$ is the fractional part of $x$, or $x - \lfloor x \rfloor$

[sterile pumice]

bee [it/its]

[dark tiger]

Do you have a reference for this that I can check?

[patent acorn]

no

but it's kind of just implied by the way you compute a continued fraction

you first split the number up as $\lfloor\alpha\rfloor + {\alpha}$, an integer and a fractional part

[sterile pumice]

bee [it/its]

[patent acorn]

then you write it as a reciprocal, $\lfloor\alpha\rfloor + \frac1{\frac1{{\alpha}}}$

[sterile pumice]

bee [it/its]

[patent acorn]

then you split that, $\lfloor\alpha\rfloor + \frac1{\left\lfloor\frac1{{\alpha}}\right\rfloor + \left{\frac1{{\alpha}}\right}}$

[sterile pumice]

bee [it/its]

[patent acorn]

etc

in particular $a_{n+1}(\alpha) = a_n\left(\frac1{{\alpha}}\right)$

[sterile pumice]

bee [it/its]

[patent acorn]

just because of how the process is iterated

[dark tiger]

Makes sense. Thanks

[dusk ore]

Let $d = gcd(s, n)$, where $s$ is integer and $n$ is natural. $\varepsilon_i$ is a complex primitive root of unity of degree $n$. $\mu(n)$ is Mobius function, $\varphi(n)$ is Euler Totient function.
Prove that $$\sum_{i=1}^{\varphi(n)} \varepsilon_i^s = \frac{\varphi(n)}{\varphi(\frac{n}{d})} \mu \left(\frac{n}{d}\right)$$

I'm not quite sure if this topic is a proper place to post this problem because of complex numbers but it suits better than others I guess... I know a plenty of properties of Mobius and Totient function as well as about roots of unity, but the equation is so clumbersome it's hard to apply anything.

[sterile pumice]

Moonlight

[dusk ore]

There was a task about the fact that $\sum_{i=1}^{n} \varepsilon_i = \mu(n)$ which seems to be a special case of the fact above, but it's hard to generalize this

[sterile pumice]

Moonlight

[thick panther]

could i get some help with both 5.1 and 5.3 please
im not really sure what to do

[dusk ore]

Can you use quadratic reciprocity law here?

[thick panther]

which one?

if you mean in general, yeah

[dusk ore]

It just looks like you can easily make a step from mod p^2 to mod p using it

flipping the Legendre symbols

[thick panther]

🤔

i dont really follow

[lethal cedar]

is x (mod y) and congruence related in some way?

[proud lodge]

well congruence mod k is... what it sounds like

ex. 1 and 11 and 21 and etc. are congruent to 1 mod 10

1 mod 10 == 11 mod 10 == 21 mod 10

[wheat patio]

What would I do to prove this? I included what I was able to come up with, but I don't know if it's any good considering I don't know where to go from here

Sry bout the double message, discord mobile is... discord mobile

[neat harness]

suppose ax0 = b mod n

then what is a(x0 + nk) ?

[wheat patio]

Is that what I'm supposed to have formatted it as? That a(x0+nk) = b?

I had that at one point but I didn't think it was right

wait how would you get an a to the nk to allow factoring out that a?