elementary-number-theory

[left fable]

its a quadratic, so use the quad formula, and you get x = (-1 +- 4)/2

which is really (-1 +- 4) * 2^(-1)

so you just need the inverse of 2 mod 19

but thats a luck-easy solution, 2*10 = 20 = 1 so inverse is 10

so you got (-1+4)10 and (-1-4)10 as the other two solutions

and theres gcd(3,18) = 3 total solutions i believe

[charred roost]

For the other one equation, you have x^4 - 1 = (x^2 - 1)(x^2 + 1). Then you just need to solve x^2 + 1 = 0 (mod 17), for which I think you just have to use trial and error tbh. But you only need to find one solution, since both x and -x are solutions

[left fable]

no, x^2+1=0 is x^2=16

+-4

so +-1, +-4

[charred roost]

oh yeah, much easier than I thought lol

[junior swallow]

thanks y'all

Could I have a hint for this please

so if a is a nonresidue mod q it suffices to show that -a is a residue mod q

right?

Ah I think I got it. If $q \equiv (3) ; (4)$, then $(-1/q) = -1$. Thus $(-a/q) = (-1/q)(a/q) = -1 \cdot -1 = 1$

[sterile pumice]

okeyokay

[sacred junco]

A question appeared on our test which was:

If the gcd(a,b) = 1, then show that gcd(a+b, a²+b²) = 1.

I did the proof, but there is a catch, I got the gcd of a+b and a²+b² to be either 1 or 2.

Lemme send the solution.

Please verify the proof.

[dusty dragon]

That seems fine to me, you can show that the statement given in the exam is false when you take a, b both odd

your conclusion is right; gcd(a + b, a^2 + b^2) is either 1 or 2

[sacred junco]

Yeah that works too.

[red yacht]

i have a question

why is that p | a^n <=> p | a , with prime p, n in N and a in Z

[lilac bronze]

It’s because of Euclid’s lemma

One form of which says that $p \mid ab \implies p \mid a \lor p \mid b$ for $p$ prime and integers $a, b$

[sterile pumice]

Pseudo (Cat theory #1 Fan)

[lilac bronze]

You can use this + induction to show the result you specified

The form of Euclid’s lemma i prefer is $d \mid ab \land \text{gcd}(d, a) = 1 \implies d \mid b$

[sterile pumice]

Pseudo (Cat theory #1 Fan)

[lilac bronze]

Ultimately this is true because of Bezout’s identity, which imo is a very important result in number theory

[red yacht]

thanks

or u can use the prime factorization of a^n is unique, if a doesn't have one of its primes in the prime factorization of a^n then it's contradicting

[kindred fulcrum]

thats the definition

[junior swallow]

Why can we assume that a can be written as (-1)^s 5^t

I'm not entirely sure,, but this is my guess: If $a = 2k + 1$, then $a - 5^t = 2k + 2 (2)^t + 2 (2)^{t - 1} + \dots + 2$. For large $t$, this will be divisible by $2^e$, by handwaving

[sterile pumice]

okeyokay

[pale steppe]

Consider the interval $(1/2, 1)$. Can $x\in (\mathbb{R}\setminus\mathbb{Q})+$ be chosen such that $y(x+y)$ is irrational for all $y$ in $(1/2, 1)$?
How about for arbitrary $(a,b) \subset \mathbb{R}+$?

[sterile pumice]

user

[pale steppe]

I feel the answer ought to be no by density of irrationals in R, but I can't figure out how to write it down well lmao.

If it were xy or x+y the answer is obviously no, but it is not quite either of these lmao

oh its a quadratic lol

for fixed x

[rugged locust]

oh yeah, you fix x instead of y

and it's solving a quadratic

[pale steppe]

$y = \frac{-x + \sqrt{x^2 + 4q}}{2}$

[sterile pumice]

user

[pale steppe]

it still seems not so simple lmfao

well it has to fall in (a,b)

but then q must be negative

i cant believe the answer is yes

wowie

[tranquil briar]

setting the discriminant to be less than 0 is a contradiction with assumptions

[boreal garden]

No, since f(y)=y(x+y) is a continous function over (1/2,1)

[pale steppe]

no this isn't right

[tranquil briar]

you want this to have no solutions for q in Q yeah

[pale steppe]

we want this to have no solutions in (a,b)

that would solve the problem

[tranquil briar]

but if you set the discriminant to be negative, that's a contradiction with the assumptions on x and y

[boreal garden]

the problem with this approach is that q can't be fixed. you dodge one rational but not all

[pale steppe]

right

image is connected and rationals are dense

cheers

[versed flax]

Ah also I came too late

Just wanted to say that because I thought that you may have missed the condition on x and hence still not convinced

[plucky gale]

$y=x

[worldly nova]

I have a question that says prove this formula using a combinatorial method only, IDK what it means by "combinatorial method", can anyone give me a hint

[versed flax]

can you use the multiplicativity of φ?

or is that not allowed

[worldly nova]

WDYM by multiplicity of phi? phi(ab)=phi(a)phi(b)? no IDT that is allowed ig

[versed flax]

yea i meant this

ohhh i see

(tho be careful that what you said isnt quite correct, it only holds if (a,b)=1 where (a,b) denotes the gcd of a and b)

[versed flax]

ok then i think it should be ok if you prove that phi is multiplicative using a combinatorial method and then use that property to prove the desired identity?

[worldly nova]

ig using isomorphism?

[versed flax]

wdym by that?

isomorphism of what exactly

what i had in mind was a pure counting argument

[worldly nova]

isomorphism between Z/mnZ and Z/mZ x Z/nZ such that m and n are coprime

[versed flax]

well i suppose you arent allowed to use statements like this?

[worldly nova]

then restrict it on U(mn)

restrict the isomorphism

[versed flax]

wait maybe my argument is missing something

[versed flax]

oh wait yea the approach was wrong

let me fix that

[tardy ether]

like inclusion exclusion principle maybe?

[versed flax]

||given n,m in N* with (n,m)=1, make an nxm grid of the numbers 1,2,...,nm where each row has n elements and each column has m elements. the first row consists of the numbers, 1,2,...,n, the second consists of n+1,n+2,...,2n up to the mth row which consists of m(n-1)+1,m(n-1)+2,...,mn.
Now check the number of columns and that of rows in which the number of elements coprime to mn are distributed to, then notice what the number of columns and rows really are||

so here you are essentially using that (mn,x)=1 iff (m,x)=(n,x)=1 too lol. But you are making a counting (combinatorial) argument just like what the question wants you to do

also sorry for messing up earlier

[tardy ether]

any ideas how to attack such a problem?
so a_1 = 1, a_(n+1) = (a_n)^2 + 1 and im trying to understand if all elements of the sequence are squarefree

so im looking at the sequence mod p^2

and like first few facts

if there's n such that a_n = 0 (mod p^2), p = 4k + 1 (comes from -1 being square residue mod p)

also first such n < p/2 (each element of the sequence mod p is some square residue + 1)

and that's about it, haven't got any further

[boreal garden]

Any proof will have to use the fact that a_1=1 since this isn't true in general, for instance take a_1=7.

If this is true, I don't think there's an easy way to proof this.

I'm convinced this a really hard problem, at least there's not hope that it can be solve by quadratic residues, I don't see any pattern that takes into account the case a_1=7 by a "small prime".
Where did you found this?

[tardy ether]

nono that's not an actual problem

that's just a prediction

like the original one was

prove that for each n there is a prime diving a_n that doesn't divide any of the previous elements

[boreal garden]

This doesn't look easy to prove either.

[tardy ether]

but it's like proving a_n > a_1 * ... * a_(n-1) and on the other hand if no other primes appeared as a factor of a_n, you could prove that powers of the primes dividing a_n are no greater than powers dividing previous elements

so you get a_n <= a_1 * ... * a_(n-1)

[tardy ether]

to be exact if a_n is divisible by p^k and not by p^(k+1) and it's the first term to do so, then the sequence is periodic mod p^(k+1) thus the power is at most k

[boreal garden]

How can you prove that the powers of the primes divideing a_n are not great than powers dividing previous elements?

[tardy ether]

well the fact is the power stays the same

like let a_n be the first term divisible by p

and p^k the greatest power dividing it

then the sequence is periodic mod p^(k+1)

past terms aren't divisible by p at all

a_n is divisible by p^k, the next one is 1 mod p^(k+1)

so we're back at the start

[worldly nova]

Yeah ig that what I should use, and actually I tried to turn that product into sum but didn't notice that the formula u get is the same one u get when applying that principle and counting intersection...

[worldly nova]

Idk if ur answer is true, but it seems a good approach

[boreal garden]

I don't see why

[tardy ether]

cuz a_n = p^k * m

a_(n+1) = p^(2k) * m^2 + 1

p^(2k) is divisible by p^(k+1)

so it's 1 mod p^(k+1)

so we're back at a_1

if we're looking mod p^(k+1)

[boreal garden]

Yeah, but like the next one is 2 mod p^{k+1}

[tardy ether]

yeah

a_2

[boreal garden]

ohhh

I see it

[tardy ether]

this does not help to bound k though :(

[boreal garden]

wait

[versed flax]

it is. when you count the rows and columns you will see that there are φ(n) columns and φ(m) rows which contain exactly all numbers =<mn which are coprime with mn. Which means that there are φ(m)φ(n) such numbers and hence φ(mn)=φ(m)φ(n)

https://www.math.uci.edu/~ndonalds/math180a/4euler.pdf

go to page 4

[boreal garden]

This won't prove that you can have k=1

[tardy ether]

yea

[boreal garden]

You have to study that cycle for any single prime

I see your point

[tardy ether]

yea, best i got is that its length is less than half of the prime lmao

[versed flax]

maybe this is worded a bit badly but if you didnt really get what i mean here then you probably will if you check the pdf i sent

you couldve also proved the identity directly using something like $\varphi(n)=\sum_{d\mid n}\mu(d)\frac nd$ but thats definitely not the intended way ig

here you let $n=\prod_{k=1}^mp_k^{\alpha_k}$ then $\prod_{p\mid n}(1-\frac 1p)=\prod_{k=1}^m(1-\frac 1{p_k})\=1-\sum\frac 1p_i+\sum\frac 1{p_ip_j}+\dots+\frac{(-1)^m}{p_1p_2\dots p_m}=\sum_{d\mid n}\frac{\mu(d)}d=\frac{\varphi(n)}n$

[sterile pumice]

ali yassine

ali yassine

[versed flax]

anyways, if you decide to prove that phi is multiplicative using an argument like this for example (or any other argument) first, then it will suffice to look at phi of a prime power then you can use the fundamental theorem of arithmetic along with the fact that this function is multiplicative to prove the desired result

[tall arch]

i think PIE works here (principle of inclusion/exclusion)

[boreal garden]

Isn't this like a consequense of aplying moebius inversion to the $n=\sum_{k|n} \phi(k)$ and this is a consequence of counting the amounts of fracions k/n which has k as their denominator when written in lower terms

[sterile pumice]

KevLee

[versed flax]

you can view it like this too yea, tho when i learned it i saw it in the way i presented above (i learned it in apostol's book)

[worldly nova]

I see it's good actually

[versed flax]

hahaha Tysm!

[junior swallow]

I am considering the case where $n$ is even. We wish to solve $(-1)^{yn} 5^{zn} \equiv (-1)^s 5^t \text{ mod } 2^e$. We can choose $y$ based off of the value of $s$, so this reduces to the congruence $5^{zn} \equiv 5^{t} \text{ mod } 2^e$. Since $U(\mathbb{Z}/2^e \mathbb{Z})$ is the direct product of two cyclic groups, one of order 2, the other of order $2^{l - 2}$, it suffices to consider the congruence $zn \equiv t \text{ mod } 2^{l - 2}$. Does this look correct so far? I'm a bit unsure

[sterile pumice]

okeyokay

[quick scarab]

((4p⁴ - q⁴)(4p⁴ + q⁴)²)² + (2pq(4p⁴ + q⁴))⁴ = (4p⁴ + q⁴)⁶

[worldly nova]

in this question they found that n is of the form 6k+1 or 6k+2 for k=0,1,2,...

can u tell me if what i did here is true

let n in N, 3|n(2^n)+1

then n(2^n) = -1 mod 3
then n(2^n) = 2 mod 3

then the sum from i=0 to n of 2^n = 2 mod 3

we know that if n is even
then 2^n = 1 mod 3
then the sum from i=1 to n of 2^n = n = 2 mod 3
then 3|(n-2) then n=3k+2

if n is odd
then 2^n = 2 mod 3
then the sum from i=1 to n of 2^n =2n = 2 mod 3
then 3|(2n-2) then 3|(n-1)
then n=3k+1

is what i did is true?

[boreal garden]

yes, I mean but kind of being nitpicking, why didn't you just put n2^n=2n instead of the sum of 2^n?

[worldly nova]

Well I want it to demonstrate it, is there another rule that let me say it directly?

[boreal garden]

You are just saying 1+1+...+1=n and the factoring 2^n in both sides.

[worldly nova]

ooh i see, i didnt saw that then lol

i could just multiply both sides by n

[boreal garden]

I mean, you are half correct. When you delete the (-1)^s you are already killing the order 2 subgroup. Then what can you say about the "periodicity" of each 5^zn and 5^t

[junior swallow]

What do you mean by the periodicity?

Here I'm trying to use the fact that $U(\mathbb{Z}/2^e \mathbb{Z}) \cong {-1, 1 } \times { 5^i \mid 0 \leq i < 2^{e - 2}}$. Thus the equation $(-1)^{yn} 5^{zn} \equiv (-1)^s 5^t \text{ mod } 2^e$ is equivalent to $((-1)^{yn}, 5^{zn}) = ((-1)^s, 5^t)$. By before, we know we can choose $y$ so that $(-1)^{yn} = (-1)^s$. Thus this reduces down to $5^{zn} \equiv 5^t \text{ mod } 2^{e - 2}$

[sterile pumice]

okeyokay

[boreal garden]

Yeah, like remember the main idea when you found a condition for a number to have a square modulo p?

[worldly nova]

isn't obvious that if n is odd then n and 2 r coprime
then 2^(phi(n)) =1 mod n
and since phi(n)<n then phi(n)|n!
(n!= (1)(2)...(phi(n))...(n-1)(n))
then 2^(n!) = 1 mod n
then n|(2^(n!)-1)
so why they did this to proof that if n is odd then n|(2^(n!)-1)

[boreal garden]

I mean, you came with a nicer proof for sure

[junior swallow]

Hmm I'll think about it

Why does $p \equiv 1 ; (8)$ and $p \equiv 1 ; (12)$ or $p \equiv 7 ; (8)$ and $p \equiv 11 ; (12)$ imply that $p \equiv 1 ; (24)$ or $p \equiv 23 ; (24)$

[sterile pumice]

okeyokay

[junior swallow]

Nvm

[shell needle]

[sterile birch]

Your proof is circular right now. The sentence "Since $p$ is prime and $\frac{p!}{k! (p-k)!}...$" is not true for arbitrary rationals. Moreover, that statement is essentially what you are trying to prove. Your final 3 sentences, you write, are under the assumption "If $p$ divides $\frac{p!}{k! (p-k)!}$". Thus you are again assuming what you are trying to prove.

[sterile pumice]

Ishan Panpaliya

[shell needle]

but i did show that P is not divisible by k!(p-k)! and therefore (p-1)! must be divisible by k!(p-k)! in the sentences before?

[sterile birch]

I might be nitpicking, but my point is that you are implicitly using the claim: "if ab/c is an integer and gcd(a,c) = 1, then b/c is an integer", and I think this needs to be proven.

[astral swift]

Hi, it's the first time I've written in a channel, I'm passionate about number theory, any advice on how to study it? (I'm Italian so I'm using Google Translator sorry for the translations)

[kindred fulcrum]

Pick up a book on it, or take a course in university/college

[dry eagle]

Given a natural number $n\geq 2$, I want to know when $(n-1)! + 1 = 0 ; [n]$.

It can be shown that a necessary condition for this to hold is for $n$ to be prime. Rewriting our equation, we obtain:
[
\begin{aligned}
(n-1)! = -1 ; [n] = n-1 ; [n] \
-(n-1)! = (n-1)(n-1)! ; [n] = 1 ; [n]
\end{aligned}
]
Hence $(n-1)!$ has a multiplicative inverse, hence $\gcd(n, (n-1)!) = 1$.

If $n$ were composite, it would be divisible by some prime $p \leq n-1$. Since clearly $p\mid (n-1)!$, we would end up with $\gcd(n, (n-1)!) \geq p > 1$. Thus $n$ is prime.

Furthermore, running a computer program seems to suggest that this property is true for all primes. But how can I rigorously check that?

[sterile pumice]

struct ∅ {};

[kindred fulcrum]

google wilson's theorem

[versed flax]

by wilson's theorem, if p is a prime number, then (p-1)!\equiv -1 mod p

oops sniped

[dry eagle]

oh it's already a theorem haha

thanks

[junior swallow]

Is there any issue with notation here, since (a/b) can denote also the Legendre symbol? Or does it happen to be clear in context, or they agree in some cases

[long lion]

well i mean (a/b) will be the Legendre symbol if b is prime, otherwise it'll be the jacobi symbol

the jacobi symbol extends the legendre symbol so most of the time it'll be clear

[junior swallow]

Ah okay thanks

Silly question but why can we assume that a is square free

[rugged locust]

write a = bn^2 where b is squarefree as its factorization in Z

then the quadratic roots of a (mod p) are exactly of the form n* sqrt b (mod p)

[junior swallow]

Sorry I don't think I understand - are you saying that there are no p such that there exist x with x \cong bn^2 mod p, since such an x will have to contain a root of b in its product expansion?

[rugged locust]

is this easier to read

[junior swallow]

So is the point that sqrt b is not an integer? and therefore there can't be any residues?

[rugged locust]

no, the point is that if you want to figure out if a number is a residue or not you can factor out all the squares

and look at the remaining squarefree component of that number

[kindred fulcrum]

the legendre symbol for a,b align

[rugged locust]

so we can WLOG assume a is squarefree

[kindred fulcrum]

so wlog you can assume a is square free

copy

[rugged locust]

you will be hearing from my lawyer shortly

or in terms of legendre symbols, (a/p) = (bn^2/p) = (b/p) (n/p)^2 = (b/p)

arises from the simple fact that a sqaure number..... is the square of some number

[junior swallow]

Wait dumb question, but what if in this case p happens to divide n and not b? then (b/p) = 1 and (bn^2/p) = 0, right?

[rugged locust]

oh yes but in that case a is 0 mod p to begin with

and its trivially a QR mod p

[junior swallow]

Ah okay I see

thanks goat

Silly question but if p is any prime number do there always exist nonresidues mod p

My guess is yes

Just thinking about how to prove it

[rugged locust]

I can give you a constructive proof and a nonconstructive one

or alternatively you can think really hard about it yourself :)

[junior swallow]

If so, then x -> x^2 is surjective...

Yeah I'll come back to it lol

[rugged locust]

-1^2 = 1

The more general result is that there are exactly (p-1)/2 quadratic residues mod p for every prime p

That’s a good exercise you can try and prove for yourself

[tardy ether]

a funny thing is that we don't know how to get a non square residue computationally in polynomial time

[tiny hazel]

you missed some parentheses 🥰

[shell needle]

whats the deal with the gamma function? i see it pop up now and then.. is it any good?

looks pretty wack

[kindred fulcrum]

It is good

For example it appears in the functional equation of reimann's zeta function

[mint stone]

It's a continuous variant of a factorial, as Г(n+1)=n!

[shell needle]

thats pretty dank

[kindred fulcrum]

meromorphic even (when you extend to the complex numbers)

[weak nest]

How we solve equation of 3 variable like
Ax+By+Cz=D? Where only integer solution we have to find?
For two variable we can use Euclid extended algorithm to find but how 3 variable equation ?

[worldly hedge]

Does someone know the translation of "concept lattice" in Spanish?

[boreal garden]

¿No es como un "reticulo" o un "haz" de algo? No conozco concept lattice pero googlearlo en wilipedia parece que es un reticulo o un haz como lo encontrarías

La verdad, "lattice" es de esas palabras que en casi todo contexto la gente le da la traducción que se le da la gana

[jagged spade]

Lattice tenia entendido que era una red universal de consciencias

[nocturne vortex]

Could someone check that my understanding of Diffie-Helmann encryption is correct?

I see that, in the original Diffie-Helmann protocol, we select a shared seed g, and all math on g is done modulo p. g is a generator for a cyclic group (subgroup of the finite field F_p?).

In elliptical curve DH, we have an elliptical curve, say e, over a finite field F_p. We then consider the solutions to e, which constitute a group. When the order of the group has a large prime factor, it contains large cyclic subgroups. Choosing g in the group correctly gives us one of these subgroups.

I have three questions. First, why does a large prime factor make the group in the second paragraph contain large cyclic sugroups? Second, why, in regular DH, is the finite field part significant - I.e. why can't I just choose g, say it's a generator mod p, and not mention finite fields at all? Third, what exactly is it that makes the discrete log problem harder in elliptical curve groups?

[rugged locust]

first question follows from cauchy's theorem - namely, if p is a prime that divides the order of a group G, then G has to have an element of order p

for the second question, the finite field property is important because for non fields there are multiple solutions to the discrete log problem, so the key is no longer enough information to decrypt the intercepted message.
but it's true that in this case it is equivalent to just saying mod p; it's still an important enough detail to point out anyway

not enough of a CS expert to comment on the third question

[nocturne vortex]

ty this was very helpful

[mint stone]

For the third question the short answer is this: there is no subexponential DL algorithm for the general elliptic curve, unlike in the finite field case where there is a NFS (number field sieve) algorithm.

[nocturne vortex]

ty!

[junior swallow]

What do you mean by this

I think I got it actually?

Assume for contradiction that it's false. Let $a$ be a primitive root mod $p$ so that $p - 1$ is the smallest integer with $a^{p - 1} \equiv 1 \text{ mod } p$. Now $a \equiv b^2 \text{ mod } p$ for some $b$. Thus $a^{(p - 1)/2} \equiv (b^2)^{(p - 1)/2} \equiv 1 \text{ mod } p$, contradicting the fact that $a$ is a primitive root mod $p$.

[sterile pumice]

okeyokay

[warped tendon]

the proof they were going for was probably that (-1)^2=1 and 1^2=1, so squaring is not injective. But since the integers mod p is a finite set, this means squaring isn't surjective either.

[warped tendon]

also technically p=2 is a counterexample, so you should really say "if p is any odd prime"

[junior swallow]

Oh yeah

ty

Why does the Proposition imply that $(q_i/b) = (b/q_i)$? It suffices to show that $\frac{(q_i - 1)(b - 1)}{4}$ is even, but I don't think this is always the case, right?

[sterile pumice]

okeyokay

[junior swallow]

For if q_i = 2k - 1, b = 2j - 1 we have (q_i - 1/2) x (b - 1/2) = 4kj/4 = kj, which is not always even?

[warped tendon]

they said $b\equiv 1 \bmod 8$, so $b=8k+1$, and therefore
$$\frac{(q_i-1)(b-1)}{4}=\frac{(q_i-1)(8k)}{4}=2k(q_i-1)$$

[sterile pumice]

Captainsnake

[junior swallow]

Ah okay cool thanks

[junior swallow]

Are quadratic characters and legendre symbols the same thing?

[unique cypress]

wdym by quadratic character?

[junior swallow]

It's used in this context

[unique cypress]

fwiw these concepts are related

(a/2) in this case I assume we are taking kronecker

[junior swallow]

Sorry idgi

I don't think it was defined previously in the text

[unique cypress]

oh okay nvm in this context you are still using legendre mb

jacobi/kronecker is just a generalization of legendre symbol

so quadratic characters are the same as legendre provided the "denominator" is p

Since you can still make sense of these things even if the denominator was not p

does that help?

[junior swallow]

i guess but what even is a quadratic character

how is it defined

[unique cypress]

have you seen dirichlet characters?

[junior swallow]

No I don't think so

[unique cypress]

It's that but specialized in the case where the outputs are {0,1,-1}

that's how you connect it to legendre symbol

[unique cypress]

what book is this btw

[junior swallow]

huh weird they haven't been introduced yet

[unique cypress]

i dont really like it

[junior swallow]

Ireland rosen

[unique cypress]

okay removing ireland rosen from my recommendation list for future reference

[junior swallow]

lmao really everyone recommended it to me

but yeah this is wack

[unique cypress]

anyhow the dirichlet character modulo n is a function chi: Z->C which is periodic w.r.t the modulus n, completely multiplicative and it's supported on units modulo n i.e chi(a) = 0 if gcd(a,n) not eq to 1

but if gcd(a,n)=1 then |chi(a)|=1

So essentially you start with a group homomorphism from (Z/nZ)^x -> C^x and then you extend it to Z appropriately

I think you should look at this. It's super helpful

Then you get phi(n) characters from the modulus n and you always get the trivial character which basically sends a -> 1 as long as gcd(a,n)=1

[tulip vortex]

I don't think you should go through the whole book, the early chapters (around the first six) are a solid introduction to elementary number theory. The later chapters can be skimmed imo.

[junior swallow]

So I shouldn’t read up to chapter 12, which is where ANT starts?

Aka if I just read the first 6 chapters and went to neukrich I’d be fine

[tulip vortex]

Yeah if you've done com alg for sure

Otherwise Marcus is a gentle intro to ANT

[junior swallow]

Okay I'm a little more than halfway through Atiyah Macdonald

[tulip vortex]

Yeah thats enough to start

I think Neukirch also does some of the com alg you need but it's easier if you've seen it already

[tulip vortex]

Even if you end up doing Neukirch, the exercises in Marcus are great you should check it out

[junior swallow]

You mean Marcus Number fields?

[tulip vortex]

yes

[tulip vortex]

Chapter 7 might be worth reading if you don't know that stuff already

Also it is worth asking, do you have an end goal in mind?

[junior swallow]

okay thanks

Yeah it's a bit ambitious but I want to be able to read about the langlands program and current research

sorry discord was lagg

y

[tulip vortex]

well I don't know anything about Langlands, but I'm assuming the next step is to learn some basic ANT and then class field theory

[junior swallow]

Yeah

[tulip vortex]

in which case yeah you don't need to read more

[junior swallow]

I was planning to do AM -> Hartshorne and Ireland Rosen -> Neukrich -> Milne maybe

[junior swallow]

really? I thought algebraic geometry was necessary

[tulip vortex]

No i meant you don't need to read more from Ireland and Rosen

[junior swallow]

oh ok

[tulip vortex]

The material in the later chapters is important but I think other sources are better

[raw herald]

im reading it right now(havent gotten more than a chapter in yet but i just started) and idk about the content but the first chapter has really hooked me, so its definitely good from a pedagogical standpoint imo

[unique cypress]

Yeah but I don't think you should be reading it all at some point. Better to move on to another book

[raw herald]

fair, I'll definitely be doing so, just saying its worth a mention just as a good hook that i dont see in many textbooks ive read for other subjects

[unique cypress]

I skimmed over the first couple of chapters and I thought it was nice. I didn't see the entire thing

I'm glad you find these things nice since it's really hard to motivate number theory

[chrome bluff]

So I'm looking into solutions to Pell's and Reverse Pell's equation.

This is the problem I want to solve:

• Suppose (x,y) is the smallest pair of positive integers that satisfies x^2-dy^2=1
  -Suppose (r,s) is the smallest pair of positive integers that satisfies r^2-ds^2=-1
  I want to show that
  (r+s\sqrt{d})^2=x+y\sqrt{d}

The main issue is that I need to somehow conclude that r+ssqrt(d)<x+ysqrt(d)....and the...gears just aren't turning

I'm going through E. Barbeau's exercise book on the subject, and he conveniently didn't spend too much time walking through how to figure this out 🤦‍♂️

Exercise 2.5 is the one

[chrome bluff]

<@&286206848099549185> I could use some help on this. I'm a bit stuck

[supple tide]

ur cooked 💔

[green marlin]

Is tis x2 math

[boreal garden]

You can prove that (x+y/sqrt(d))^k=(r+s sqrt(d))^2 since
(r+s sqrt(d))^2(r-sqrt(d))^2=1
and x,y is a fundamental solution. If k is even you can obtain another small solution of the negative pair by just substituing and taking k/2. For k odd, I genuinely have no idea

[boreal garden]

This just follows since (r+sqrt(d) s) is bigger or equal to 1 since sqrt(d)>=1 and r,s are positive interger with at least one equal or bigger than 1.

[warped tendon]

i second this recommendation

I read that book and it is the reason I am specializing in algebraic nt now

[chrome bluff]

I'm not following what you're getting at here. I'm not too sure this justifies that desired inequality

It's worth noting that (x,y) is not the trivial solution (1,0)

[boreal garden]

Both $x,y\geq 0$ and since the case (x,y)=(0,0) is removed then either $x\geq 1$ or $y\sqrt{d}\geq1$ in each case $x+\sqrt{d}y\geq 1$ therefore $(x+\sqrt{d}y)^2>x+\sqrt{d} y$

[sterile pumice]

KevLee

[chrome bluff]

That is...not the inequality I'm referring to

Remember, I wanted to show that $r+s\sqrt{d}<x+y\sqrt{d}$

[sterile pumice]

dackid

[placid stratus]

can it be shown (analytically, not heuristically) that next_prime(p)=2p-1 is rare

[patent acorn]

in fact the only primes with this property are 2 and 3

for any integer n > 3, by bertrand's postulate there is a prime number strictly between n and 2n-2, so it's not possible that the next prime after n is 2n-1

[placid stratus]

so if there are primes p and 2p-1, then there is a prime p < q < 2p-1

[patent acorn]

yes

[echo light]

Hello, does someone have a hint to solve x^{-33} =2 in Z/101Z ?

[clever pine]

What is Z /101Z

Can u clarify

[kindred fulcrum]

mod 101

[clever pine]

Thanks

[kindred fulcrum]

solve x^67 = 2 mod 101 instead

Z/101Z is a field so you can use fermat

[echo light]

yeah okej thanks, i figured it out

[boreal garden]

substitute $(x+y\sqrt{d})^2=r+s\sqrt{d}$
I think the notation is the other way around, (x,y) instead of (r,s) but it is the same idea

[sterile pumice]

KevLee

[boreal garden]

The last part was wrong, it is not a small solution of the equation but rather a pair (a,b) that would be both a solution of the negative and the usual pell's equation.

[wooden glen]

Could you stop posting just that emoji in several channels? If you want to have conversations, it will be a much better strategy to start talking about something math-related so they have something to respond to you with.

[charred roost]

<@&268886789983436800> this is just spamming at this point

[silent rock]

I got them

They were in a lot of other channels, trying to figure out what to do with them.

[real laurel]

Struggling to show that $P$ isn’t principle in part (c) of this problem from chapter 3 of Marcus. The hint indicates that I should show that there is no $\alpha \in P$ such that $N^K(\alpha) = 2 = |R / P|$, but I get stuck trying to show that $\alpha$ cannot be a solution to the diophantine equations:

[N^K(a + b \theta) = a^2 + ab + 6ab^2 = 2] or
[N^K\left(\frac{c + d \sqrt{-23}}{2}\right) = c^2 + 23d^2 = 8] (the latter being subject to $c \equiv d \mod 2$, from the characterization of $\mathbb A \cap \mathbb Q \sqrt{m}$ for $m \equiv 1 \mod 4$). Is there a simpler approach I’m missing?

[sterile pumice]

kesis

[unreal pecan]

i was reviewing for my number theory exam in the copy room on the board, and one of my other professors came in and shouted at me "2/15ths equals 2/3rds times 2/5ths?!?!" not realizing its jacobi/legendre symbol 😭

he is a very silly man

[boreal garden]

a(a+b+6b^2)=2 implies a=1 or a=-1 in the first case b+6b^2=1 and this doesn't have integrals solutions. I'll leave you a=-1 as homework.
For the other, we have d=0 by simply every other value being to big, and the equation c^2=8 has no integral solution.

[real laurel]

ah that’s so simple, thx 😭

[boreal garden]

As a rule of thumb, Diophantine equations can be generally solved by a human being if it is quadratic and the coefficients aren't too big. That's kind of why in algebraic number theory any reasonable examples is just quadratics with some ciclotomic extensions every now and then.

[broken bronze]

I've been diving into number theory a bit (a really tiny bit, we barely scrape the surface of that in the university), mainly cause I want to either approximate or compute the gcd(a,b) really fast. So far I have only discovered this relationship, which happens to satisfy the following conditions (which happen to be enough for Euclid's algorithm)

• gcd(a,b) = gcd(b,a)
• gcd(a,b) = gcd(a mod b,b)
• gcd(nb,b) = b, n = 0,1,2,...

So far, I've tried rewriting t(x) as seen above, but I've not found any simplifications

Any ideas?

[west glade]

we can already compute the gcd very fast with the euclidean algorithm

which uses gcd(a,b)=gcd(a mod b, b)

[raw herald]

out of curiosity, what would you recommend after reading the first 6 chapters of ireland and rosen? im about 2 chapters in, and dont have any past experience with number theory but its been overall very smooth and understandable, if that makes a difference.

(also, its interesting this book is discussed here, as it doesnt seem "elementary" by the channel description, it uses a few results from analysis early on and uses limits and such)

[tulip vortex]

Start doing algebraic and analytic number theory

[raw herald]

i meant more specifically book recommendations, but i guess there is a channel for that

thank you for the advice

[unique cypress]

Apostol is a good starter for analytic. You can try Montgomery if you feel Apostol is boring

For algebraic you have Marcus, Neukirch, Milne...

[tulip vortex]

Number fields by Marcus is a good intro to alg nt, I hear apostol is good for analytic nt but I learned the basics way later than I should've so I was introduced to it through Serre's a course in arithmetic

Problems in Analytic number theory by Ram Murty is also really good

[unique cypress]

Yeah it has nice exercises

[tulip vortex]

I call it elementary because of the methods used and the results covered in the first 6 chapters, it's called a "classical" introduction after all. The original proof of PNT was complex analytic, but ireland and rosen prove a weaker version using just limits and algebraic manipulations.

[ivory cosmos]

20x mod 100 is congruent to (20 mod 100) * (x mod 100), but i've seen that you can do even better and say that 20x mod 100 is congruent to 20 * (x mod 5)

can someone show me how you go from the former to the latter

[kindred fulcrum]

if x = 5k + r then 20x = 100k + 20r

[ivory cosmos]

mmm okay ty

[placid stratus]

what is the current verified maximal prime gap as a function of p? was this paper https://arxiv.org/html/2510.17065v1 withdrawn?

yeah, withdrawn https://arxiv.org/abs/2510.17065

[junior swallow]

Where is this highlighted assumption used? Since $la \equiv \pm m_l (p)$, we have $\frac{la \pm m_l}{p} = k$ for some integer $k$. Thus $\frac{la}{p} \pm \frac{m_l}{p} = k$, which is to say that they differ by an integer.

[sterile pumice]

okeyokay

[tulip vortex]

It's used in the next step, all the m_l are distinct so we get equality upto sign

and we get the sign from (a/p) im guessing

which Gauss' lemma is this?

[junior swallow]

It's this one

[tulip vortex]

oh then it's clear no?

This lemma says that (a/p) is precisely the product of minus signs = (-1)^number of minus signs

[junior swallow]

Oh yeah right

Thanks

Why is this congruence true? If (2/p) = 1 I can see it but I can't workout the case when (2/p) = -1

[tulip vortex]

that's always true, (a/p) is congruent to a^((p-1)/2)

[junior swallow]

oh damn

Oh right

[junior swallow]

In one of the proofs of quadratic reciprocity, one way is to use the complex function f(z) = exp(2 \pi i z) - exp (- 2 \pi i z). I am still trying to understand the nuance behind this choice of function. I understand that it carries nice properties such as f(z) = -f(-z) and f(z) = f(z + 1) but still it seems remarkable that complex techniques should be involved in number theoretic constructions

Although I guess that's true for all of number theory and this is just the start

[wooden glen]

That's just 2i·sin(2pi·z), right?

[junior swallow]

Yeah

[junior swallow]

Why is this true? Here, p and q are distinct primes

Nvm I got it

[tribal palm]

Hi I recently wrote a paper where I take the two previous primes and with the help of an approximation function, predict the next prime.

Looking for feedback and hopefully a publication of some sorts.

[junior swallow]

Why does y^8 = 1 imply that y^4 = -1

[wooden glen]

gamma has order 8, so gamma^4 is something that is not 1 but whose square is 1.

[junior swallow]

Ah ok thanks

Could we also say that the polynomial y^8 - 1 = (y^4 - 1)(y^4 + 1) = 0 but y^4 \neq 1 => y^4 = -1

[wooden glen]

Yeah.

(Once you know Z/pZ doesn't have zero divisors).

[junior swallow]

Ye

[rich wigeon]

👋

[junior swallow]

Why is this equality true?

Here (p/q) is the legendre symbol

I know that q + 4a is congruent to 4a mod q

But why is 4a congruent to a mod q?

Gemini got me 🙏

[misty tundra]

👋

[tardy ether]

it's not that 4a is congruent to a mod q

it's that you can write it as (4 q) * (a q)

and (4 q) is 1 obv

[wanton gorge]

I doubt this is the right chat to ask this, but I don't know which is the right chat to ask it. Anyways, someone knows a book about recurrence relations?

[junior swallow]

Why do we restrict our attention to (a, m) = 1?

[wooden glen]

I think because otherwise we can reduce the question to one with a smaller modulus.

[boreal garden]

Because that fully determines the problem. Basically if (a,m)=d>1 you can take a'=a/d and m'=m/d and study the same problem.

[junior swallow]

So solving the congruence x^2 \equiv a' mod m' admits a solution for x^2 \equiv a mod m?

@boreal garden

[wooden glen]

What do the primes in this notation mean?

[junior swallow]

In what notation?

[wooden glen]

(Hmm, a' and m' have explicit definitions in KevLee's post, but what is d'?)

[junior swallow]

Oh I assumed that was d and a typo

[wooden glen]

Yeah, but it can't be that simple.
Consider, for example: Is 12 a square modulo 27? The gcd is 3, but just dividing through by that leads us to ask whether 4 is square modulo 9 -- the answer to that is obviously yes, 4 is a square mod anything. But 12 is not a square mod 27, since 27n+12 is always divisible by 3 once but not twice.

<@&268886789983436800> crypto scam spam

[hollow ruin]

Thanks, ban auto delete somehow missed that one

[wooden glen]

If d is a perfect square, then it looks like it's valid to divide it out, but it get murkier if it's not. I think the rule needs to be something like

• If there's any prime factor of d whose exponent in d is odd and smaller than the exponent in m, then the original congruence has no solution.
• But if there's no such prime factor, then we can indeed ask whether a/d is a square modulo m/d.
• However, to get the actual the square root modulo m, we'll need to multiply the root modulo m/d by a conversion factor that includes half (rounded up!) of the multiplicity of each prime factor of d.

[junior swallow]

Hmm okay I see

I'll think about this, thanks

Why can we apply Proposition 6.3.2 here? In the first screenshot, a general quadratic gauss sum is g_t for any t, but the Proposition only applies to the case where t = 1.

Did they mean the quadratic gauss sum in the case a = 1?

[wooden glen]

It looks like the ± accounts for the possible difference between different a.

Oh, but only for a that are coprime to p.

Yeah, better read it as g_a specifically.

[boreal garden]

A fat finger mistake lol

[boreal garden]

Not really, but it makes the problem doable.

[lunar rover]

Help:

Given ( n \in \mathbb{N} ) and ( z \in \mathbb{C} ):

\textbf{a)} Find ( |z| ) so that
[
\frac{n + z^n}{n - z^n}
]
is purely imaginary (( n \neq z^n )).

\textbf{b)} Show that for this value of ( |z| ),
[
\frac{n + z^n}{n - z^n} = -i \cot\left(\frac{n \theta}{2}\right)
]
where ( \theta \in \arg(z) ).

\textbf{c)} Show that all solutions of the equation
[
(1 + i z)^n - (1 - i z)^n = 0
]
are real. Also, determine the number of solutions depending on whether ( n ) is even or odd.

[sterile pumice]

Rodro

[rotund gust]

What step are you on?
1. I don't know where to begin.
2. I have begun but got stuck midway.
3. I got an answer but I was told that it's wrong.
4. I got an answer and would like my work checked.
5. I have a question about someone else's work/solution.
6. I have completed the problem and don't need help anymore. Thank you.
7. None of the above

[lunar rover]

4

[wooden glen]

Then you had better show the answer you want someone to check.

[mint stone]

All three can be solved with geometry. For a) and b) n and z^n should be the sides of a rhombus (bc its diagonals n+z^n and n-z^n are perpendicular). And for c) 1 and iz are the sides of a rectangle (since the lengths of its diagonals should be equal). All that along with geometrical meaning of complex multiplication (it is rotation and scaling) give that |z|=n^(1/n) and b) and c) respectively

[wraith oasis]

I've thought of an interesting question...

When n is odd, is the sum of n consecutive integers always divisible by n?

Man... that's an annoying puzzle 😅

[dusty dragon]

hint: $k + \dots + \left(k + (n - 1)\right) = nk + \left(1 + \dots + (n - 1)\right)$

[kindred moss]

another easy way to see that is writing $n = 2k + 1$ and then $S = (m - k) + (m - k + 1) + \dots + (m - 1) + m + (m + 1) + \dots + (m + k - 1) + (m + k)$, and we can pair up terms that sum to $2m$, leaving $m$ in the middle

[sterile pumice]

snowflake

[kindred moss]

where m is the middle term

[lunar rover]

Ok I think I solved it

Its so cool seeing people coming up with different solutions

If anyone wants to share another method of how they've done it, DM me

[sterile pumice]

Miguxx

Miguxx

[sterile pumice]

Rodro

[lunar rover]

Geometric solution DEterminantion 21 posted (from another discord server)

[sterile pumice]

Rodro

[still flare]

Hi @serene palm and @plucky surge, I appreciate you may want to say hello, but it's best not to send the same messages across lots of channels -- that's spam. If you'd like to just say hello, maybe visit #discussion instead.

[icy epoch]

someone please give me a hint on this problem: if 2^n + 1 is prime and n > 1 and natural then n = 2^s

[wide snow]

The lemma I prove in my number theory lectures is

if k = ab for odd a, then 2^b + 1 divides 2^k + 1

Which I recommend trying to prove by working mod 2^b + 1

[icy epoch]

okay thanks for the tip

[brave tide]

How to do these type of questions?

[loud maple]

You could prove a lower bound for ϕ(n) in terms of n.

[kindred fulcrum]

For 13, try to understand the prime factorization of 24, and how the prime factors of n contribute to the prime factors of 24

[brave tide]

oo okay i got it! thanks

[junior swallow]

Can somebody please explain to me why Gauss' Lemma implies this?

Something like... suppose that it has non nontrivial factorization in Z[x] and suppose for contradiction that its reducible in Q[x]. p(x) = f(x)g(x). Multiply f(x) and g(x) by the products of the denominators to get a polynomial with coefficients in Z...

[west glade]

isnt gauss' lemma just that p is irred over Z iff over Q?

what other statement of it does your book have?

[ionic latch]

Maybe they and I have a similar book because I was wondering how in the world I could apply gauss' lemma to that 😂 given that my book says this

[west glade]

exercise 4 at the end of this chapter

gauss has proved a few lemmas

[ionic latch]

I guess so 😂 I'm glad to know I'm not stupid for being confused given mine

[boreal garden]

I think it gives the fg is primitive if f and g is primitive

[junior swallow]

Product of prim polynomials is prim

[keen quartz]

I just want to verify my understanding of an ideal real quick. A set $$ I $$ is a set for which it is closed under addition and multiplication by some integer $$ a$$.

[sterile pumice]

ginja - ギンジヤ

[kindred fulcrum]

Not multiplication by integer but multiplication by any element of the ring you are working with.

[left fable]

another way to look at it, ideals are like vacuums

if you start in an ideal, you end in an ideal regardless of how you travel

so x in ideal times r from RING gets sucked back into ideal

of course its possible that two elements in ring multiplied and not in ideal end up in ideal but that isnt relevant to the definition

[west glade]

adding on to this, prime ideals are exactly about such a scenario

if two elements multiplied together are in the prime ideal, then at least one of them already was in it

[left fable]

yea thats fair to add. so to keep it consistent
ideals: if you START in the ideal, you end in the ideal (through any number of multiplications by any ring elements)
prime ideals: if you END in the ideal, and are a prime ideal, then you necessarily started in the ideal as well.

ofc this isnt technical math definition, its a visual idea to get the ball rolling

as an example, in something simple like 4Z
2*2 is in the ideal, but 2 is not itself in it. so 4Z is not a prime ideal

(you ended there, but nothing was forced to start there)

[keen quartz]

Thanks for the Christmas present

Yeah, they’re interesting structures. I wanna find some algorithm that utilizes principal ideals aZ and that definition to some degree. Apparently, you can use them in coding theory to generate really strong and secure codes.

[untold orbit]

yo

[hushed jasper]

hi

[left fable]

aloha

[supple saffron]

Could someone explain the proof for the dividing algorithm to me? I get it intuitively but I’m getting lost on how they prove it

[west glade]

it would help if you showed the proof you are trying to understand

[dusty dune]

hi i am trying to learn inter universal teichmuller theory, can anyone help me.

[kindred moss]

if u figure it out make sure to email some math professors

[tiny hazel]

So true

[warm hazel]

How do I formally specify that the set {2^n | n element N } is smaller than the set N?

Both are infinite but one fits inside the other

[tiny hazel]

Wdym smaller?

That set has the same cardinality as N

If you mean N fully contains ${2^n | n \in N}$, use the subset symbol

$${2^n \mid n \in N } \subset N$$

[sterile pumice]

zAltanis

[west glade]

you can also consider the density of that set https://en.wikipedia.org/wiki/Natural_density

[junior swallow]

Isn't this obvious? We can assume that a is a quadratic residue mod p. Then if b^2 \equiv a mod p then (-b)^2 \equiv a mod p too

[kindred fulcrum]

yep

just note that this requires p > 2

[modest coral]

#help-20 message

i got || n = 15 ||, anyone else?

[carmine tide]

,w integer solutions \frac{n^2 (n+1)^2/4}{n+3}=k, n \geq 15

[sterile pumice]

Results provided by WolframAlpha

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

Requested by civil_service_pigeon

[carmine tide]

sounds good

[modest coral]

[boreal garden]

You can prove this is the maximun value by reducing the sum modulo n+3, in the case n>15

[modest coral]

$\frac {n^2 (n+1)^2}{4} \equiv 0 \pmod{n+3} \iff \frac {n^2 (-2)^2}{4} \equiv 0 \pmod{n+3}$

[sterile pumice]

Axe

[modest coral]

i think this is illegal

because of division by 4

[boreal garden]

Just do it carefully. Compute n^2(n+1)^2 first and then see if division by 4 makes sense

[modest coral]

by compute do you mean expand?

[boreal garden]

I mean, what is n modulo n+3

More precisely what is n^2(n+1)^2 modulo n+3

[modest coral]

n is -3 so n^2(n+1)^2 is 36

[boreal garden]

Right so if n+3 divides the sum, it has to divide n^2(n+1)^2. You just have to check out the case where 36 is 0 modulo n+3.

[modest coral]

then you have to rule out n = 33 somehow

[boreal garden]

This is a necesary condition but not sufficient, since the dividing by 4 thing. So you just check n=33 and if it doesn't work you haven't break anything.

But you rule out some extreme case that wolfram isn't able to detect

[modest coral]

you can check 33 manually (check if 33+3 | (1/4) 33^2 * 34^2) then check n = 15 and you will be done

[boreal garden]

indeed

[modest coral]

[junior swallow]

Can somebody please explain to me how this hint helps? Then we have uv \equiv a mod p but I don't understand where to go from here

Also why does the result follow immediately, and I don't know if I'm going insane, but if p is equivalent to 1 mod 4 then (p - 1)/2 - [(p + 2)/4] does not simplify to (p - 1)/4??

[boreal garden]

how many solutions does uv=a have?

[rugged locust]

(Assuming a != 0)

[junior swallow]

Moreover if there are (p - 1)/4 negative terms when p \equiv 1 (4) that doesn't tell us the sign of the expression, right? for p = 4j + 1 and therefore there are j negative terms, but we don't know j

[boreal garden]

p+2/4=(p-1)/4+3/4 then what is the floor of this value if p=1 mod(4)?

[viscid coral]

What book is this?

[boreal garden]

a classical introduction to modern number theory

[tribal palm]

Okay I just finished writing up a Power Point presentation on prime numbers. I will post it here. Let me know what you guys think.

[west glade]

dont post random files

[junior swallow]

I guess just p - 1 huh

You fix u, then the solution is v = u^{-1}a

Since there are p - 1 choices of u (they must be nonzero) this follows

I'm just trying to see how each of the solutions u and v correspond to x and y

Never mind, I guess I see

[junior swallow]

Why are we taking the floor?

Never mind

[sharp shadow]

Hmm, is there an elementary way to prove that any integer can be represented as a sum of 8 cubes of integers? Without using any serious NT machinery. If so, can you give me a little hint?

[dusty dragon]

do you require the integers be positive

[sharp shadow]

I tried it manually, seems to work easily for smallish numbers, but sometimes I need negatives, for example for 23: 27-1-1-1-1

[sharp shadow]

No, otherwise I would say so

[dusty dragon]

then 5 is sufficient

[sharp shadow]

Sure, but I’m asking for a hint to an elementary proof with 8 🙂

[dusty dragon]

what tools are you allowing

i think the proof for 5 integers isn't too bad

[sharp shadow]

It’s from a book that is supposed to be a bridge between high school and Uni mathematics for UK/US audiences…

I’d expect that they don’t know much NT in high school

Probably basic divisibility and knowledge what a prime number is

[dusty dragon]

the proof i've seen just requires a somewhat ingenious way to write 6n + r as a sum of five cubes

[sharp shadow]

So yes, should be for 8 numbers and elementary

[sharp shadow]

Maybe then we need to come up with something simpler

[dusty dragon]

here's one way to derive the proof for five integers: ||for any integer k, we can write 6k = (k + 1)^3 + (k - 1)^3 - k^3 - k^3. Now, if we look at n - n^3 = n(n + 1)(n - 1), then we note that 2 is a factor and 3 is a factor. So 6 is a factor (not sure if this is already too much). So, we can write n - n^3 = 6k for some integer k. Using these two facts, we can write n = n^3 + 6k = n^3 + (k + 1)^3 + (k - 1)^3 - k^3 - k^3||

[sharp shadow]

Do you mind putting it behind a spoiler tag, if it’s not just a hint?

[dusty dragon]

yup

maybe there's an even more elementary solution for eight integers

but i don't suspect we need anything about primes

[slim vortex]

when I hear sum of eight squares I think of the norm on octonions

[ionic latch]

Thankfully this is eight cubes

[slim vortex]

ohh.. not sure how that happened

[sharp shadow]

Maybe this problem is some sort of a joke by the author, I am not sure: it is hidden as one item among a multi-item problem where all other items are easy…

[dusty dragon]

the problem becomes slightly more interesting if you force the cubes to be non-negative i think

[ionic latch]

Maybe the case with 8 could be proved by (strong) induction and some argument based on distance between cubes, although I wouldn't expect that to be within the reach of high school students

[sharp shadow]

Here it is, in full

[ionic latch]

How random XD

[sharp shadow]

Yeah, and it looks non-trivial hence it caught my eye while I was sampling this book

[dusty dragon]

if you force a, b, ..., h to be Z^+, then finding the counterexample becomes slightly nontrivial

[sharp shadow]

23 I think, no?

[dusty dragon]

yes 23 and 239 are the only counterexamples

[sharp shadow]

As I mentioned at the beginning (my second message)

[dusty dragon]

but the fact that only two counterexamples exist is somewhat interesting (to me at least)

[sharp shadow]

Yeah, it is

[golden coral]

👋

[sharp shadow]

Can someone pedagogically minded choose some problems to solve for me? 🙂 This is for the chapter on congruences, residue systems, Fermat and Wilson theorems:

Around 5 would be nice, preferably varied and educational. Thank you!

[boreal garden]

Honestly, they all look fun to solve. I'm kind of bias since I just love interger related problems but I would just solve them all, not specifically writting a "full" solution, but just trying to get the general idea.

[sharp shadow]

well, there is 1.5 pages more 😄

if I solve them all I won't finish until (choose your own favourite metaphor for end of the world)

[kindred fulcrum]

29, 33, 34, 35

Also making sure you know how to solve 17-27 is good

[sharp shadow]

cheers! I'll solve some of 17-27 too

will let you know how it goes

[tribal palm]

Okay, I updated my power point presentation and converted it over to a PDF file. I'm posting this for feedback purposes. (Its not just some random file)

[junior swallow]

By this theorem, $7$ is a quadratic residue mod $p$ if and only if $p \equiv \pm1 ; (28)$, $p \equiv \pm 9 ; (28)$, or $p \equiv \pm 25 ; (28)$. Can this be reduced further?

[sterile pumice]

okeyokay

[kindred fulcrum]

How do you expect to reduce it further?

[sharp shadow]

yeah, I've done 17-20 yesterday too 🙂

quick summary of proofs: || 17. follows directly from Fermat theorem 18. divisibility by 7 from Fermat, and by 6 - from the fact that factorization has (n-1)n(n+1) factor -- three integers in a row, so must be divisible by 3!=6, then because (6,7)=1, we have our divisibility by 42. 19. n^6 = 1 (mod 7) comes from Fermat, and then we just square both sides. 20. just like in (19), but instead of squaring we raise to power k ||

[sharp shadow]

yeah. I wonder if there is some other way to prove (18), without || resorting to factorization of that polynomial || - did you have the same solution?

yeah, I thought about that, || i.e. in order to prove divisibility by 6 using just congruences, I could have taken all potential residues: 1,2,3,4,5 and check r^7=r (mod 6) on them, but that looks kinda too calculational hence lame 🙂 ||

fair enough 🙂 it's hard to get on without proofs in math though...

I also kinda like that theorem that says that if something has n consequent integers as its factors, then it's divisible by n!

[sharp shadow]

Done 21-26 just now, 27 is trickier, I haven’t looked at their suggestions yet though

[versed flax]

||the answer to 27 is 01||

||you get this by considering 3^400 mod 100||

||you use euler-fermat's theorem, so calculate φ(100) and then you use the theorem which then lets use find the answer to the question||

I wrote separate spoilers so that you can get a hint each time without getting the whole answer immediately

[sharp shadow]

I think you put hints in unexpected order. I.e. the answer first. I solved it without hints though, but somehow differently. I showed that 3^400 = 1 (mod 4) and also = 1 (mod 25) - that took some tricks. And then it’s = 1 (mod LCM(4, 25)) which is “mod 100”

For mod 25 calculation I noted that 3^3 = 2 (mod 25), and then that 2^10 = -1 (mod 25), that allowed me to get to powers of 1

But the idea to use Euler’s directly is nice as well and less “hacky”, need to calculate phi(100) though, a little bit tricky to do mentally (I was solving this while trying to sleep 💤)

[junior swallow]

Could I have a hint in showing that if p is a prime then p \equiv 1 mod 12 and p \equiv 4 mod 5 is impossible

[carmine tide]

Doesn't 109 work

,w is 109 prime

[sterile pumice]

Results provided by WolframAlpha

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

Requested by civil_service_pigeon

[carmine tide]

,w 109 mod 12

[sterile pumice]

Results provided by WolframAlpha

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

Requested by civil_service_pigeon

[carmine tide]

,w 109 mod 5

[sterile pumice]

Results provided by WolframAlpha

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

Requested by civil_service_pigeon

[junior swallow]

Oh okay that's fine too lol

[west glade]

by dirichlet there are infinitely many primes like that

[ionic latch]

I should learn about dirichlet

The way I did it was using chinese remainder theorem since 12 and 5 are coprime

p == 1 (mod 12)
p == 4 (mod 5)

M1 = 5, M2 = 12
Inverse of 5 mod 12 is 5
Inverse of 12 == 2 mod 5 is 3

Therefore p == 1*5*5 + 4*12*3 = 25 + 144 = 169 == 49 mod 60
49 is not prime but 49 + 60 = 109 is prime

Ah wait is dirichlet the one who said any arithmetic sequence contains infinitely many primes

Maybe where a and d are coprime or something of that sort

In this case we have 49 + 60n and 49 and 60 are coprime

[versed flax]

ah right lol mb, i shouldve put them in a better order. Ohh nice, yea thats another way to do it

[neat rock]

Hello. I am having some difficulty in this question in the part where $p$ does not divide $a$. What I have been able to show is that $a + y^2$ as $y$ ranges from 1 to p-1 covers $\frac{p-1}{2}$ residue classes mod p because of the fact that $y^2 \equiv (p-y)^2; (p)$ . So the total no of solutions is

No. of solutions for $x^2 \equiv a ; (p)$ which equals $1 + (\frac{a}{p})$
plus
2*(no. of solutions for $x^2 \equiv a + y^2$ as y ranges from 1 to (p-1)/2)

Only thing I know from the hint is that if (x,y) is a solution of this then $x \not\equiv \pm y; (p)$

[sterile pumice]

shinzo_pedia_77286

[kindred fulcrum]

the map (x,y) --> (u,v)=(x+y,x-y) is bijective, so you just need to count the solutions to uv=a (p)

[neat rock]

oh yes, thanks. So u has p-1 choices and for each of these v has 1 choice hence p-1 solutions

[modest coral]

it's not a bijection if p = 2, right?

[sharp shadow]

Finally got back to this. Is problem 33 just wrong though? For example for a=2, m=3, n=1, I get (65, 5) = 5, and not 1, like their formula seems to suggest. Am I missing something?

[kindred fulcrum]

yeah it looks wierd

[sharp shadow]

It looks like they removed this exercise from a newer edition of the book

[neat rock]

I think it should have been a^(2^m) (and also a^(2^n))

[sharp shadow]

Not sure. Does their suggestion make sense to you then? The one after the problem

[neat rock]

yes. the suggestion only helped me figure it out

p divides f(x) if there exists an integer n such that p divides f(n)

Can someone help pls. Substituting $x^2 = y$ and completing the square, I get $(2y -1)^2 \equiv -3;(p)$. So -3 is a quadratic residue mod p, which gives me $p\equiv\pm 1;(12)$. Now I need y itself to be a quadratic residue mod 12 and this will somehow get rid of the case where $p\equiv -1$ (12). How to do that?

[sterile pumice]

shinzo_pedia_77286

[carmine tide]

[https://en.wikipedia.org/wiki/Euler's_criterion]

[eager silo]

they told me to talk about this here (reasonable of course, this is by no means advanced number theory I just didn't know this channel existed)
"
Interesting
so for any prime p
from what I understand, the first n such that p | F_n must be smaller or equal to p+1
this is because so to speak, the transformation from F_m to F_(m+1) is either *k, for a k such that 0<=k<p (mod p btw), or it's "1/0" so to speak
basically, p+1 choices, so, the first n such that p divides F_n must at most be p+1
"

[sharp shadow]

Hmmm, in Problem 34, proving the part about reduced residue system for even m > 2 is not easy... Still have to try some ideas before giving up though :)

[versed flax]

I think things should work out nicely if you use the following: ||1+2+...+m/2+...+m\equiv 1+2+...+m/2+(m-m/2)+...+(m-2)+(m-1) mod m||

[hollow wyvern]

what kind of elementary number theory is this

im like so confused rn

[dusty dragon]

you can read the channel description for some further info on what typically constitutes “elementary number theory” but it’s generally the kind of number theory you see in a discrete math course or in an early undergrad course

[sharp shadow]

Mm, yeah, for complete residue systems that is one way to prove it (which I already did, and also for reduced systems and odd m), but I can’t see how that can help for reduced systems with even m > 2

I used an analog of the proof of Fermat theorem, but took a sum instead of the product. I.e. we use the fact that if we multiply all elements of a residue system modulo m (be it complete or reduced) by some a (that is relatively prime to m), then we get also a residue system

And then we can either multiply the elements (and get a proof of Fermat) or add them (to get a proof of this problem 34). But this proof idea doesn’t work for even m and reduced systems (because it never uses the fact that it’s actually reduced, it treats reduced and complete systems in the same way)

[brittle prairie]

you know how, if m,n in N are coprime then for all k in N there exists a,b in Z such that k = am + bn (bezout identity corollary). if you restricted to a, b to be in N_0 would it be true that there exists some k' such that for all k > k', k = am+bn

(context: trying to intuitively grasp why markov chains need aperiodicity to converge)

[dusty dragon]

this is the frobenius problem (of dimension 2) or the coin problem

and in fact, you can find k' explicitly

[brittle prairie]

thanks

[neat rock]

for reduced residue system, look out for a similar kind of symmetry as in the hint given by ali yassine for the case of complete residue system mod m, ||which when summed up leads to 0 mod m||. ||if gcd(a,m) = 1 then what can you say about gcd(m-a,m) ?||

[sharp shadow]

BTW, I’ve proved Problem 33 with your fix to the problem statement, thank you!

[versed flax]

oh mb i thought that the question was asking about complete residue systems

[sharp shadow]

it is asking about both. Por que no los dos?, as they say :)

[versed flax]

ok then when you are talking about a reduced residue system, you are talking about the group of units (Z/nZ)^x. Now this group is ||cyclic||

[sharp shadow]

mm, algebraic methods are likely not allowed here

[versed flax]

||the goal is to add the elements of this group, its a geometric series||

[versed flax]

🥀

it doesnt matter, one can cheat from time to time 😉

[sharp shadow]

well, it's not an exam, so I can't cheat anyone except myself!

[versed flax]

I mean you could first prove that (Z/nZ)^x is cyclic if you want and then this argument wouldn't be cheating?

no need to mention fancy words like cyclic if that still makes it look like cheating

[sharp shadow]

Ah, right, I got it, looks quite simple in retrospect! Basically, we need to show that if (a,m) = 1, then (m-a, m) = 1

Then both a and m-a are in the reduced residue system (up to multiples of m)

And so we can pair them up, and their sum is 0 mod m

And the only way when the number would be paired with itself is m/2, but m/2 is not relatively prime to m

So we can pair all of them up, because if x is paired with y, then y is paired with x, so all of them are paired with exactly one partner. Then we get 0 as a total sum (mod m)

And (a,m) = (m-a,m) follows from Euclidean algorithm basically

So an interesting question is why this argument breaks at m=2

Because then m/2 is actually still in the residue system

[versed flax]

because 2 is too small

[ionic latch]

Because 1 is not 2? XD

[sharp shadow]

So this part breaks

And 1 is paired with itself in that case

But for m>2 all good, no algebra needed

Thanks @neat rock and @versed flax for your hints!

[sharp shadow]

I am interested in finding the author’s intended solution, because it would likely teach me something about the current subject. Using adjacent areas is also eye-opening (here I was intrigued to learn that units of a finite ring form a group), but I’d prefer to get both solutions in that case

[versed flax]

Yea it's good to know different approaches to the same problem whenever possible, tho its probably time consuming

[naive dagger]

Hello, does CFT means class field theory?

[abstract ferry]

yes

(outside of NT context it could mean conformal field theory or whatever)

[naive dagger]

In number theory yes, I was reading some the sloth's recommendations for algebra and number theory

and CTF comes up, didn't know what it means

[unique cypress]

It's the natural thing to study after algebraic number theory

[sharp shadow]

Ok, for Problem 35 I’ve got sets of form (a, a, ka) for any positive integers a and k.

[sharp shadow]

I think this completes your task: I’ve done 17-27, 29, 33-35, some with mild hints

Now it’s time for the next page!

[kindred fulcrum]

xD

its not mine

[sharp shadow]

Any selection of nice problems from this one? (say 3-4). And then I’ll call it a day and move on to another topic

[kindred fulcrum]

38, 49, 50, maybe 51, 43

[sharp shadow]

Ah, I think I’ve seen the proof for 38, it’s basically a binomial formula and then we show that p divides the binomial coefficient (which I’ve already done before)

[kindred fulcrum]

yeah

most of these just look annoying

[versed flax]

you are just describing elementary number theory

[sharp shadow]

Come on, don’t kill my motivation 😅

Or I’ll switch to topological manifolds

[kindred fulcrum]

oh no

[kindred fulcrum]

what is the next topic?

[sharp shadow]

Group actions!

[kindred fulcrum]

thats nice

[sharp shadow]

I’m doing one section of number theory and one section of abstract algebra interchangeably

[versed flax]

switch to abstract algebra instead sotrue

it contains whatever you need from elementary number theory but in a more general setting

[sharp shadow]

Nah, I’m already doing that

Yeah, I feel that I am looking forward to my weeks of abstract algebra with more enthusiasm than to ones on Number theory…

But NT is decent too, and I want to get to Algebraic NT eventually

Also I suspect it will provide nice motivation and source of examples for rings

[versed flax]

yea i dont like elementary number theory because its full of things like find the last 2 digits of 4738^39308

[abstract ferry]

so true, start number theory with serre a course in arithmetic

[versed flax]

tho there are some parts of it which lead to nice things that i am looking forward to study, like quadratic reciprocity which leads to more general reciprocity laws

CFT moment

deltoid would be happy

[versed flax]

I am looking forward to study algebraic NT, CFT and these nice things

coming soon

[abstract ferry]

AoEC when

[unique cypress]

38,39,43,48,49,50,51

[sharp shadow]

It’s strictly a superset of the problems by @kindred fulcrum :)

So I’ll probably start with the intersection and then expand to yours if I still have energy

[unique cypress]

Have fun

[sharp shadow]

Problem 43 is nice, its result was somewhat unexpected, which is always good. Here is my proof:

[ionic latch]

Oooo yes

[ionic latch]

Looks nice, looks good

Well the last line should say a^p

Instead of a^b

Otherwise I like it

[sharp shadow]

ah yes, a typo

[ionic latch]

Always a typo

[kindred fulcrum]

a different approach is to say that a = b + np, and then expanding (b+np)^p

[sharp shadow]

ah, using binomial theorem

nice

or even better, directly the result of Problem 38

[dusty dragon]

this result reminds me of Hensel’s lemma

[ionic latch]

Ugh that horribel part of our book

[kindred fulcrum]

yeah I was thinking if hensel is useful here

[sharp shadow]

what's that?

[ionic latch]

The proof looks very similar

[dusty dragon]

It’s a general result that shows if you have a solution to a polynomial congruence mod p, you can lift it to a congruence mod any power of p

[ionic latch]

A theorem that allows you to find solutions to the same congruence mod p^k in mod p^(k+1)

Called lifting

[dusty dragon]

the proof of it is quite nice

[kindred fulcrum]

uniquely

[ionic latch]

Uniquely if f' neq 0 mod p (or if f neq 0 mod p [in which case there are none])

[kindred fulcrum]

yeah

[ionic latch]

Could also be p solutions

[sharp shadow]

it's probably somewhere later in my books

[ionic latch]

Almost certainly

😔 it was the last question on one of my number theory tests and took a full page of computation

[sharp shadow]

hmm, doesn't show up in the index :(

[dusty dragon]

my elementary number theory course didn’t cover Hensel’s lemma

[ionic latch]

That's interesting

Ours is pretty far early in our book

Maybe 2/5s of the way through

[dusty dragon]

I think a lot of the students in my class would have struggled with it as well lmao

[ionic latch]

I found the question 😔

[ionic latch]

Me taking number theory independent study with no support:

[sharp shadow]

it's not even in Ireland/Rosen's index!

[ionic latch]

All I was allowed to do was show up for the tests

It's in Rosen because that's what we used

[sharp shadow]

maybe index is wrong

[kindred fulcrum]

hecke character?? isn't this an ENT book?

[ionic latch]

ikr why is hadamard and hypersurface here

[dusty dragon]

class fields being mentioned and indexed

interesting

[sharp shadow]

Is this Rosen or Ireland/Rosen?

There is another Rosen (Ken)

[ionic latch]

Ah

Just rosen

Now it all makes sense

[unique cypress]

I taught elementary number theory before and my approach was to get students used to thinking about number theory the right way. A lot of students appreciated the methods. Can't say the same for cs majors though they hated it

[ionic latch]

What is 'the right way'

Also that makes sense

As a CS-math major I both feel it and hate it

(feel the hate and hate the love-hate relationship)

[dusty dragon]

cs students at my undergrad uni generally hated studying anything that wasn’t coding-intensive

[ionic latch]

I get that here 100%

OS is usually the first completely theoretical class CS majors take here and the complaints are endless

[dusty dragon]

It works in their favour in that the curriculum is very much a software engineering curriculum lol

[ionic latch]

I thought it was great, felt like I was back in a math class

[dusty dragon]

there’s barely any proper computer science 😭

[ionic latch]

Damn

Sadge

[dusty dragon]

yah like cs students don’t even need to take a models of computation course

[ionic latch]

What's models of computation 🤔

[dusty dragon]

Automata theory and complexity theory basically

[ionic latch]

Complexity theory as in analysis of algorithms or a more formal interpretation

[dusty dragon]

you learn about regular languages, context-free languages, decidable languages and their respective models of computation

[ionic latch]

Oo

I need to finish the article I was reading on programming language semantics

[dusty dragon]

so DFAs, NFAs, CFGs and PDAs, TMs

[ionic latch]

Gonna take my turing machine and go

XD

[dusty dragon]

and also a bit of complexity theory (as in P, NP, coNP complexity classes) at the end

[ionic latch]

Ah okay

We touched on those at the beginning of data structures

I was really unhappy we never got more

If we had I likely would have gone into that

Instead of where I am now

[dusty dragon]

it makes sense cos you need a bit more background for the right rigorous treatment

so you should learn about Turing machines for the P and NP classes to make sense; luckily, the Church-Turing thesis posits a nice correspondence between algorithms and Turing machines so you get the equivalent definition in terms of algorithms and verifiers

[ionic latch]

Now that I think about it my friend at nother niversity took a class like that

All I ever remember him talking about was turing machines though

I think the professor did turing machines all semester

And he said the professor invented his own notation for them

And that the professor talked a little bit like he barely understood them

[dusty dragon]

theory cs moment

[kindred fulcrum]

guys this is elementary number thoery

[dusty dragon]

I learned about Turing machines in my ENT class

[tiny hazel]

os theory is hot

[naive dagger]

How do you teach number theory? Could you explain please?

[ionic latch]

That's what I wondered too

[neat rock]

Idk hensel's lemma exactly but I think this is a special case of it in Ireland and Rosen in context of nth power residues

[ionic latch]

Mmmm

[ionic latch]

Looks like jt

We have f(x) = x^n - a with f(x) == 0 (mod p)

If there exists a solution r such that f(r) == 0 (mod p), we note that f'(r) = r^(n-1) = r^n/r == a/r (mod p) is nonzero as p not divides a

Therefore by Hensel there exists a unique solution f(r + tp) == 0 (mod p²) where t = ...*f(r)*... == 0 (mod p)
So f(r) == 0 (mod p²) is the unique solution and so on

Nice

[sharp shadow]

Yeah, it looks like in my Niven Zuckerman there is something similar too, but no Hensel lemma in its whole generality

[sharp shadow]

Do you know how they call this result (Problem 38) in MIT? @kindred fulcrum

"Freshman's Dream" :D

[karmic thorn]

how would you (formally) prove this?

I can yap sth like

$xord(F) = 1$ where $p = ord(F) + 1$ which gives us $xp = x$ but I doubt that is anything close to a proof 🤪

[sterile pumice]

xtea418

[sharp shadow]

Use binomial formula to expand the left hand side, and then prove that all binomial coefficients except first and last are divisible by p

[karmic thorn]

(I've only really done some limited amount of number theory for cryptography)

[sharp shadow]

i.e. that $p \mid \binom{p}{i}$ for 0 < i < p, for prime p

[sterile pumice]

dying_sphynx

[sharp shadow]

(that is a good exercise in its own)

[versed flax]

we need sophomore's dream fr

i think there is something like that

let me check

[ionic latch]

<@&268886789983436800>

It's really fun watching all the moderators come on at the same time to a ping

Also interesting that person joined the exact same day as that other person in my chat

Who may or may not be vending e-services

#help-25 message

[tiny hazel]

<3

[dull jasper]

does this lemma have a name? (i mean a universal one unless freshamns dream is genuinely what its called)

or what textbook is it from

[kindred fulcrum]

not really

[dull jasper]

ah okay nws

[unique cypress]

Frobenius

[dull jasper]

thank u !

[sharp shadow]

it's from MIT lecture notes on ENT from Spring 2012: https://ocw.mit.edu/courses/18-781-theory-of-numbers-spring-2012/resources/mit18_781s12_lec4/

[sharp shadow]

is this an application of something more generic named after Frobenius? I'm trying to google it, but can't find anything named Frobenius for "Freshman's dream"...

I also found this:

Burnside's lemma, sometimes also called Burnside's counting theorem, the Cauchy–Frobenius lemma, or the orbit-counting theorem, is a result in group theory that is often useful in taking account of symmetry when counting mathematical objects.

Also found this gem: "Consequently, this lemma is sometimes referred to as the lemma that is not Burnside's."

[unique cypress]

I'm referencing the map

[sharp shadow]

I see, thanks. This one, if anyone is curious: https://en.wikipedia.org/wiki/Frobenius_endomorphism?wprov=sfti1

This Frobenius was a productive guy

[unique cypress]

Anything named after frobenius is good

[karmic thorn]

whats trace of frobenius?

i've seen tht one pop up a couple times

[karmic thorn]

ah

[sharp shadow]

it's refreshing to see some code instead of this never-ending TeX :)

[karmic thorn]

idk the "correct"/appropriate notation

maybe sth like $t(E) = 1 + ord(F) - ord(E)$

[sterile pumice]

xtea418

[sharp shadow]

haha, someone is asking about exactly this integral: #math-discussion message

[unique cypress]

Yeah no worries. The frobenius comes up a lot in number theory

[versed flax]

lol

[sand yarrow]

how to get started with elementary number theory? what are the prerequisites to get started with it?

[unique cypress]

You just need basic set theory and knowledge of proof techniques

Nothing crazy

It's called elementary for a reason :')

[versed flax]

i mean it probably doesnt even need that

just needs noggin, also known as common sense

[unique cypress]

I say basic set theory but like don't assume you need esoteric set theoretic mumbo jumbo to get into it

[versed flax]

because induction is done in ent if i am not wrong

so you really the only prerquisite is willing to study it kekw

[unique cypress]

Yeah and if you end up not liking ENT that's a normal response to have

[versed flax]

exactly

so note: dont hate number theory because of elementary number theory

[ionic latch]

Very good point

[sand yarrow]

I'm weak with proofs.

[ionic latch]

Gonna need to study up those then 👌

[versed flax]

dw much about it, from what i know discrete math is sometimes used as into to proofs

so just start with elementary number theory and then you will see what you do next

[ionic latch]

Some of the ENT proofs I dealt with (we used Rosen) even at the beginning of the book (WOP) were ones I had to sit down to get, would you really suggest just going into it 🤔

[versed flax]

yes i suggest going into it

i mean you shouldnt expect whatever you want to study to be a walk in the park

its like wanting to clear a stage in a game which has recommended level 5 and you wait till you become level 500 to attempt it

[ionic latch]

I would call this more recommended level 10 and going from level 8 instead of level 4

But you may be more expert than I

[versed flax]

i mean you can always leave it if you find it too hard

[ionic latch]

True

[versed flax]

no the numbers were irrelevant

the only relevant thing was the difference between the 2 numbers

the thing is that you shouldnt be afraid of trying

try it, if you find it too hard then see where the gap is and fill it. then come back when you are ready

[sand yarrow]

I wonder how much of elementary number theory would be mechanical, and how much would require proofs. like, I have this book on elementary number theory by burton, and I see the euclidean algorithm for example. I wonder about starting with something mechanical and learning proofs as I go along, if possible. I did get stuck with some of the early problems though, which did require proofs.

I get the gist of the logic of how proofs are supposed to work, but I do lack a lot of experience writing them out and finding proofs.

I'm just trying to find a good entry point into it from where I'm at I think.

for example, how might I go about solving this problem: Prove that if a and b are integers, with b > 0, then there exist unique integers q and r satisfying a = qb + r, where 2b <= r < 3b.

another problem is, use the division algorithm to establish the following. the square of any integer is either of the form 3k or 3k + 1.

[ionic latch]

There's probably a book that has a more 'applied' approach

Rosen (since that's the only one I know it's the only one I can talk about 😆) does a good job of presenting how to use any techniques they present, usually after the proofs

And our tests in the class were basically split 2/3 computation and 1/3 proof

[karmic thorn]

computation? 👀

[ionic latch]

Computation as in evaluating by hand

We only had one computer project

[karmic thorn]

[versed flax]

thats the case with anyone taking elementary nt for the first time

so dont let it bother you

you will get more used to proofs in the process of learning elementary nt

[karmic thorn]

AFAICT, I can apply what the channel description describes, but idrk the proofs

[ionic latch]

(Also I'm not sure how this can be proven without induction tbh)

I was gonna say an informal approach is possible

Which it usually is

But idk about that one specifically

[versed flax]

you can brute force it for example

[karmic thorn]

like what is the formal definition of/for CRT

[versed flax]

let a be an integer, use the division algorithm to write a=3k+m, what are the possible values of m?

[ionic latch]

Cauchy remainder theorem?

Oh chinese

XD

[ionic latch]

Ah that's nice as hell

I actually did notice when I was exponentiating 2 that it kept going back and forth between 1 and 2 mod 3

But that's 2^phi(3)'s problem anyway anyway

[versed flax]

now divide into cases and square each number you get then see the result

[karmic thorn]

like yea, if I have x in F_p and x in F_q I can lift it into Zmod(p*q) (given stuff is coprime)

[versed flax]

you mean 1 and 0 right

[ionic latch]

2^k is never divisible by 3

@karmic thorn

Your formal def

[karmic thorn]

yes but that wouldn't really cover the fact that I can also do the same for elliptic curves, right?

[versed flax]

what does that imply tho

[ionic latch]

Yeah unless you move to an algebraic tbook ig

[ionic latch]

That since 2 is prime, 2^phi(3) = 1

[versed flax]

you are squaring a number and seeing its remainder mod 3

2^k is not necessarily a square, its not a square if k is odd

[versed flax]

thats wrong tho

[karmic thorn]

algebraic t?

[versed flax]

phi(3)=2, 2^phi(3)=4

[ionic latch]

textbook

[ionic latch]

= 1 mod 3

[versed flax]

ah lol

[versed flax]

still this is statement is meaningless in this context

[ionic latch]

You said 1 and 0

2^k never = 0 mod 3

Is what I was referring to

[versed flax]

yea but its 1 if k is even

which doesnt contradict my statement

the only possible remainders of a square mod 3 are 1 and 0

[ionic latch]

Ah

[versed flax]

when 2^k is a square, ie when k is even, its 1 mod 3

[ionic latch]

Yes that was the part that I was mentioning I noticed

As I exponentiated, it alternated

Between 1 and 2

And the theorem yields that the squares were the 1's

Which explains the alternation

I was just connecting it to something I had noticed and gone huh interesting phenomenon

But didn't know the reason for

[sharp shadow]

For this, you already have 0 <= r < b (from the division algorithm). How can you transform this inequality to the one you need to prove?

[sharp shadow]

Hint 1: || you can add 2b to all sides, then it becomes 2b <= r + 2b < 3b. It is not quite what you want though (you have an inequality about r + 2b instead of r). What to do about that? ||

Hint 2: || we can introduce r’ = r + 2b, then 2b <= r’ < 3b. Now we are good with r’, but the other equation with q still uses r. How to deal with that? ||

Hint 3: || a = qb + r = qb + 2b - 2b + r = qb + 2b + r’ = (q + 2) b + r’. We can call this (q+2) a new name: q’. Now we have a = q’b + r’, where 2b <= r’ < 3r, so we found our integers q’ and r’ as required ||

Hint 4: || we proved that such numbers q, r exist. Now we also need to prove that they are unique. How to do that? ||

I hope OP will come back at some point to actually read those hints 😅

[sharp shadow]

Problem 49 is not easy… I am trying to prove it à la Euclid: i.e. by contradiction, assuming that the set of primes of this form 4n + 1 is finite, and then trying to demonstrate that I can build a new prime of that form (or a new prime divisor of a new composite number). But it breaks because a product of two 4k+3 numbers is a 4k+1 number, so I can’t claim that my new prime divisor is necessarily of the right form :(

Trying to come up with some workarounds for that

[sharp shadow]

I remember that Richard Borcherds had a video lecture on NT and he mentioned this problem, but I can’t remember the details of his proof

[long lion]

hint: ||you wanna find an expression that isn't divisible by 3 mod 4 primes||

[junior swallow]

What is the motivation between quadratic Gauss sums? Why should I care?

Is it because they're another convenient tool used to determine Legendre symbols?

[unique cypress]

One obvious motivation (which you might have already seen) is you can use them to prove the quadratic reciprocity. They are finite Fourier transforms over finite groups

[wraith oasis]

Is there such a thing as "base prime"? Like where each digit represents a coefficient of the prime number whose ordinality in the set of primes corresponds to the digit's position

so for example, 490 (base 10) would be written as 2101

for each digit, where the digit's position is n, the digit's value represents how many times the nth prime number shows up in the prime factorization

[wide snow]

I don’t expect that to be useful in the sense of a base

Like addition is borked

[wraith oasis]

Lol true

Kinda fun to think about though... I wonder if it might have some usefulness in discovering a p-complexity algorithm for factoring