elementary-number-theory

[long lion]

hint: use bertrand's

research-wise, pretty much everything that can be done with just elementary techniques has been done

ofc you could probably find some really obscure problem no one is working on or find a new proof of a proven result

but like we have long since passed the days where you could prove i.e. fermat's last theorem by just some random elementary arguments

[compact swift]

there is a way more simpler way to prove that n = 1 is the only case
It is by using the fact given any n, there exist a k such that 2^k =< n < 2^(k+1)

where k is ofcourse an positive integer

within the sum

[robust dirge]

i'm very suspicious that that idea will work

can you elaborate?

[compact swift]

there exist an unique 1/m where m = q.2^k

where q is odd

so consider the sum S = 1 + 1/2 ... 1/n
you multiply S with r where r = b.2^(k-1) where b is the largest common odd multiple of 1,2,...n

now for any other term beside 1/m

r/t (t =/= m) will be an integer

so r.S = a + r/m where a is an integer

and as r/m is not

r.S can't be an integer

hence S can't be an integer

[robust dirge]

ahh i see

[compact swift]

you see you can extend this for more

[robust dirge]

wait

[compact swift]

like given any set S such that there exist an integer k such that there exist a unique element in S (denoted a) where a.k^m is an integer and a.k^(m-1) is not

[robust dirge]

oh essentially computing the 2-adic valuation

[compact swift]

tbh there is the Bertrand's postulate proof also

which is also extendable in it's own unique way

i remember proving the sum of all 1/a where (a,n) = 1 and a =< n is not an integer

using the same arguement used for the proof of this using Bertrand's postulate

Here is a better one

prove that if p == b^2 (mod 28) for some integer b iff p = x^2 + 7y^2 for some integer x,y

(p is prime)

imma peace out

[modest coral]

does $a\nmid b$ imply $\gcd(a,b)\leq |a|/2$?

[sterile pumice]

Axe

[wintry oriole]

What does a not dividing b tell you about prime powers that divide a and b?

[modest coral]

there is a prime p for which the power of p dividing a is greater than the power of p dividing b

[wintry oriole]

So you would have to divide a by p (and some other stuff maybe) to find a common divisor

[modest coral]

it seems to work

i noticed it fails when a=0 cause i think gcd(0,1)=1

[sacred junco]

,rccw

[hollow ravine]

❤️

[modest coral]

ok i get the hint, but what's the third factor?

[primal pewter]

11

you find 3 and 673 from the hint, and then try 2,5,7,11 - the first two are straightforward

[modest coral]

wow

Why 3 and 673?

I thought the hint just guarantees their existence, I didn't know you can actually find them

I don't think 3 is a factor

But yeah 11 looks right

Do you use fermat's theorem to check 2,5,7,11?

[robust dirge]

11 doesn't work since it's a factor of 2020, so 2019^2018 + 2020 = 1

[modest coral]

11 doesn't divide 2020

[robust dirge]

oops

[robust dirge]

2019^2 + 2020 isn't divisible by 11 but you still need to ensure that the other factor isn't filled to the brim with 11s right

[modest coral]

there were other problems before this that said "not necessarily distinct"

[robust dirge]

ah

[modest coral]

but yeah that's a good point

[robust dirge]

wait so do they want distinct or no

[modest coral]

i'm not sure

[wooden glen]

If we don't need three distinct prime factors, all that is needed is that 2019^2+2020 = 4078381 is not itself prime.
It fails the Fermat test immediately with base 2, but that's still a lot of computation if we're supposed to do it with pencil and paper.

Oh, even that is overthinking it.

Let 2019^2018+2019+1 = k·(2019^2+2019+1).
Fermat shows that the large number is divisible by 11, and since each of k and (2019^2+2019+1) are larger than 11 [citation needed], whichever of them the 11 comes from must have a third prime factor in it ...

[primal pewter]

my bad; I was thinking about 2019 instead of 2019^2+2019+1; so yeah, the point is that the prime factors of this are also prime factors for the initial number, but it's a bit harder to find them (but as Troposphere showed, it is not necessary to find them)

[primal pewter]

only for 7 and 11
for 2 it's just odd+even
for 5 just use 2019=-1 (mod 5)

[modest coral]

thanks 🙏

[modest coral]

what's the point of freshman's dream (a+b)^p = a^p + b^p (mod p) when we can say (a+b)^p = a+b (mod p) by fermat's little theorem?

[charred roost]

(a + b)^p = a^p + b^p holds more generally in rings of characteristic p (for prime p)

[rugged locust]

it's a very useful result for studying polynomials in characteristic p rings

for instance a corollary of the freshman's dream is that the Frobenius map f(x) = x^p is a (natrual) endomorphism of rings

(and usually is an isomorphism as well as long as your ring is nice enough)

and that in particular is extremely useful, because in general it almost never happens that a ring endomorphism can be given by a simple polynomial

and also on the diff geo side of things the fact that this endomorphism is a polynomial lends to some nice analytic techniques that I am not privy to

[modest coral]

cool, thanks

[modest coral]

are these really equivalent?

[robust dirge]

n is coprime to p^2

[modest coral]

ohhh

i think i get it

that's kinda hard to see

[modest coral]

what about this situation, where we don't have a,b coprime?

[robust dirge]

wlog you can reduce them to be coprime

[modest coral]

cool, thanks

i think this only works when we're looking for stuff congruent to 0

if we want congruent to nonzero k, i think we have to consider the denominator

like if a/b = some sum s, and we find s congruent to 2 mod 3, then i think we conclude a = 2b mod 3

hmm

yeah i think so

[dreamy pine]

I've been trying to solve this proof like since last night

for context, I'm self studying elementary number theory

there's this one problem that goes:

Prove that [x] + [x + 1/2] = [2x]

The [] indicate the floor function

The definition is:

[x] ≤ x < [x + 1]

[dreamy pine]

And, I've been trying to prove this, but I keep going around in circles

[dry knot]

you do this one on cases

when x+1/2 rounds up vs down

we define the fractional part of the number {x} = x - [x]

so, case 1: {x}\ge .5, case 2: {x}< .5

[dreamy pine]

Wow, didn't think of using cases 😭

I was so hooked up on manipulating inequalities

And trying to make the thing work

[fervent crest]

Is it possible to compute (a^b mod c) mod d where mod means finding the representative in 0,…,d-1, and here d is small, c is very large, and so are a and b

[normal gull]

@dreamy pine Heltin use x as I +f where I is the integer part and x is the fractional part so the floor function of I+f becomes I. Then manipulate terms a little bit

[lament gyro]

I mean, why wouldn't it be?

Also, you don't really need to define the mod function here btw.

[modest coral]

they might be asking if it can be computed efficiently

[lament gyro]

Oh yeah, maybe.

But also, not really. That function is fairly elementary hash function I believe. And so if we could reduce it, I feel like we would have found something.

Although, there a couple things we could do.

You could use eulers theorem to solve the inner mod.

Also, if gcd(c,d) != 1, then I'm pretty sure that there's something that you could do.

But also, you'd have to find the gcd which if c is very large, then that could be quite arduous as you'd have to use the ext euc alg.

[dreamy pine]

I did it

Perhaps I've spent too much time on a problem in a textbook (24 hrs+)

Or maybe elementary number theory is still way beyond my level

[fervent crest]

The whole point is to have an efficient algorithm

Like c is 2^{10^7} roughly

b is on the same order

[normal gull]

Which textbook @dreamy pine

[dreamy pine]

Rosen

Elementary number theory

@normal gull

[solid oxide]

My number theory class experience (with emotes for illustration)

• Divisibility 🐣 🖖 ➗
• GCD and LCM 🤏 🔢 🧑‍🧑‍🧒‍🧒
• Primes
• Modular arithmetic 🕰️ 🔃
• Solving congruences 💡
• Arithmetic functions 🥧 🐂
• Floor function 🧼 🤣 🗓️
• Primitive roots 🛖 🫚 🎰
• Cryptology 🧑‍💻 🪖 🪵
• Quadratic residues ⏹️ ⏲️
• Diophantine equations 🏺 💰
• Rational points and elliptic curves 📊 🪢
• Analytic number theory 🤡 📈

[regal summit]

hey yall, this is a problem from silverman's friendly intro to number theory

im having a tough time demonstrating the first part of the hint

i tried considering quadratic residues but it doesnt seem to work

though now im thinking it has to do with the squarefree-ness of x or smth

i know that x cannot be a square but otherwise idk what else

[dreamy pine]

Hey guys, found a rather puzzling question on Rosen's textbook

"Show that if m and n are integers, and x is any real number,

[(x + n)/m] = [([x] + n)/m]"

But there are loads of counterexamples if m < 0

Ex: x = 4.3, n = 2, m = -3

[(x + n)/m]
= [(4.3 + 2)/-3]
= [6.3/-3]
= [-2.1]
= -3

But

[([x] + n)/m]
= [([4.3] + 2)/-3]
= [(4 + 2)/-3]
= [6/-3]
= [-2]
= -2

-3 ≠ -2

[worn folio]

it doesn't say positive integers?

[dreamy pine]

No it doesn't

[uneven cedar]

So.. if I wanted to create a number system where the integers are just consecutive primes. Non primes thereby becomes decimal places..
No stupid questions right?
How would one do this?

[robust dirge]

what is a "decimal place"

the real numbers and the integers are not analogous in the sense that integers correspond to primes

for example if you multiply or add two integers you get an integer, but if you multiply or add two primes you don't get a prime back

[tacit pier]

I suppose you mean we don't always get a prime. Just the thought came 2+5=7, so sharing.

[tacit pier]

I love this thought

[regal summit]

it doesnt matter

for it to be possible, we need addition to be closed

but clearly it is not

[high frost]

3+17 and 13+7 would represent the same number, for example

So you have...

er

Non-uniqueness ig

[graceful inlet]

IG you can argue that H = {au + bv : a, b ∈ ℤ} is a subgroup of ℤ, hence equal to nℤ for some n using Euclidean division. Then u, ∈ H ⇒ n ∣ u, v and n ∈ H ⇒ n = au + bv for some a, b ∈ ℤ.

[tacit pier]

I will read about being closed to better understand it

[acoustic moss]

Hello

Prove that there exists infinitely many positive integers 4n²+1 divisible by 5 and 13.

Does anyone know this?

[modest coral]

||4n^2+1 = 0 (mod 5) has solutions n = 1,4 (mod 5) ||

|| 4n^2+1 = 0 (mod 5) has solutions n = 4,9 (mod 13) ||

|| then n=4+65k is a solution for any k ||

[slate juniper]

chat is this true? $k! \mid (p^{n - 1} - 1) \ldots (p^{n - 1} - k + 1)$ where $p$ is an odd prime and $n$ is a positive integer and $1 \leq k \leq n - 1$

[sterile pumice]

Neamesis

[modest coral]

i don't think so

[slate juniper]

[slate juniper]

RIP

thanks

[sacred junco]

Oh yeah makes sense

@high frost how do I write math like u do in chat

[sacred junco]

Bro your bio is really creative

Funny 🤣

[tacit pier]

I think you use latex. By adding $ before and after your latex commands, then the bot auto generates the math text

[tacit pier]

I learned what closed means! Just sharing because I think it's beautiful

[regal summit]

nice!

closure is a pretty important thing to consider for various algebraic structures

considering those structures require that closure is satisfied

[tacit pier]

So wonderful, can't wait to study abstract algebra

Thank you so much for your support!

[sacred junco]

Thanks

$1$ $+$ $1$ = $2$

[sterile pumice]

ζaνδυsaξzar

[inner jungle]

You can encase entire mathematical expressions within the delimiters instead of every term. For example, $1+1=2$. If I wanted to do display math, I could do $$\int_0^\infty \frac{x}{y}, \mathrm d x $$

[sterile pumice]

Alex W.

[jade mulch]

Quick question: why does the following hold? Here the sum runs over primes.

$$\sum_{p \le Y, \ p^k > Y} \frac{1}{p^k} \le \frac{1}{Y} \sum_{\sqrt{Y} \le p^k \le Y, \ k \ge 2} 1$$

We can upper-bound $\frac{1}{p^k}$ by $1/Y$, but I just don’t see why we get this particular index set...

[sterile pumice]

octopus

[thorny jewel]

Seems strange. Do you have a source for this particular inequation?

I would believe it if it was something like this
$$\sum_{p \le Y, \ p^k > Y} \frac{1}{p^k} \le \frac{1}{Y} \sum_{p^k > Y, \ k \ge 2} 1$$
So, the index set on the right side is greater than the index set on the left

[sterile pumice]

EastSyberian

[thorny jewel]

But then, it would be infinite. Okay, I need to think about it

[jade mulch]

It's from a textbook (https://people.math.ethz.ch/~kowalski/probabilistic-number-theory.pdf, page 72).

[long lion]

i can get a bound of $\ll \frac{1}{\log{Y}}$ without too much difficulty using PNT, is that enough?

[sterile pumice]

LY

[long lion]

i mean the RHS is probably roughly 1/log(Y) anyway so asymptotically should be fine

oh wait sorry nvm it's k>=2

[long lion]

i kinda cba to read through all this to understand the context, try posting in advanced NT to see if anyone can answer ur Q

[jade mulch]

Understand haha. Will do!

[sacred junco]

27 ain’t prime

😵‍💫

[formal sorrel]

Hello everyone, I'm new to the discord, so forgive me if this is not the correct board to post such a question on. I'm just beginning to work through Understanding Analysis by Stephen Abbott, and I've immediately encountered a point of confusion. While working through the preliminaries section, the first question asks the reader to prove that sqrt(3) is irrational, then to prove that sqrt(6) is irrational, and finally it asks the reader to detail the issue with applying the same method of proof to the sqrt(4). I think that I completely understand the proof for the sqrt(3). Begin by assuming there is a rational number p/q in lowest terms whose square is equal to 3, then show that both p and q must have 3 as a factor which is a contradiction. But, I am a bit confused as to how this is extended to the proof for the irrationality of the sqrt(6). I assumed the reason we could confidently say [p^2 = 3(q^2) ] ==> [3 divides p] is because of Euclid's Lemma stating that if a prime number p divides the product of two integers ab then p divides a or p divides b. So since 3 is prime and divides p^2 it must divide p. Isn't the same not true during the proof of the irrationality of sqrt(6)? Beginning with lowest terms p/q, then p^2 = 6(q^2) aren't we unable to confidently say that since 6 divides p^2 it must divide p?

[barren elbow]

But 6 is not prime?

[formal sorrel]

Exactly. That's where my confusion comes from. I thought the fact that 3 is prime was a crucial part of the first proof. In that case, It doesn't seem like we can apply the same logic for the proof of the irrationality of sqrt(3) to prove the irrationality of sqrt(6). Is there a different approach that is needed or is there something that I'm missing that allows us to use the same method: assume p^2/q^2 = 6 and arrive at a contradiction?

[barren elbow]

You could use the fact that if a divides c and b divides c with a and b being coprime, then ab divides c.

[west glade]

p^2=6q^2=3*(2q^2)

and from there you repeat the same argument as before

[formal sorrel]

Thank you both! Those explanations were very helpful.

[barren elbow]

No problem. The statement 6 divides p^2, then 6 divides p actually does hold though because ||6 is square free||

[shy juniper]

Hello there,
I have a small question to people that might have saw something similar before.
Let $\left ( a_{k} \right ){0\le k \le n} \in \mathbb{N}^{n+1}$ be a sequence of whole numbers. Can we say anything on the divisibility of $\left (\sum{k=0}^{n}{a_{k}} \right )^{2} - \sum_{k=0}^{n}{\left ( a_{k} \right )^{2}}$ by a prime number ? In a non rigorous way, for $p$ prime,
\begin{center} $\left (\sum_{k=0}^{n}{a_{k}} \right )^{2} - \sum_{k=0}^{n}{\left ( a_{k} \right )^{2}} \equiv ? \left [ p\right ]$\end{center}
For me with no constrain on the sequence $\left ( a_{k} \right )$ we can't really say anything except for $p=2$ in which we can use Fermat's small theorem about the congruence of the power of any number by a prime number

[sterile pumice]

Lilly Astar

[sacred junco]

newton identities?

[west glade]

if you fix the first few numbers and let the last one be a variable then this is equal to a linear function in that variable. and linear functions hit every possible value

[sacred junco]

but i dont think you gonna get something

[west glade]

except for the case that the coefficient turns out to be zero

(which is the case for p=2)

[shy juniper]

I see where you are going but since we have some squares all over the place won't it be non linear ?

[shy juniper]

Yeah taht's the thing sadly

[west glade]

the square cancels

I am only considering the last variable

I dont care about the rest. I consider those as constant

[sacred junco]

you get $2\sigma_2$, in the end

[sterile pumice]

♱

[sacred junco]

it's because of that that it works for p = 2

the rest is like a bunch of permutations of ai's summing

[shy juniper]

For the case p=2 you can apply a bit of Fermat's theorem to say that $\forall k$, $a_{k}^{2} \equiv a_{k} [2]$ and $\left (\sum_{k=0}^{n}{a_{k}} \right )^{2} \equiv \sum_{k=0}^{n}{a_{k}} [2]$ so it works itself out

[sterile pumice]

Lilly Astar

[shy juniper]

Oh that's well seen

[sacred junco]

idk why you're trying to apply fermat little theorem as well since it's only algebra

maybe i'm missing something

[shy juniper]

I mean isn't this channel for arithmetic and whole number theory ? Divisibility and etc ?

I got recommended here by someone in an help channel

And since it's arithmetic I am doing some arithmetic. Btw have anyone saw how to prove fermat's theorem in a genral way for any ring ?

I recommend the lecture of it it's really nice

[foggy granite]

hello! this may be hard to read so please let me know if i should resend it, but can someone help me verify where i went wrong in the last part?

i need to use the descent method to find a reprsentation of 2125 as two squares.

[lament gyro]

Hey y'all, imma apologise in advance cos I'm on my phone and I can really type set. So, for convenience define eulers totient function as t(n).

I'm trying to find all nilpotent elements of Z_n

So obviously 0 is a nilpotent element, so assume a is some non-zero nilpotent element

Then we have that a^t(n) = 1 mod n by Euler's thrm. => a^(t(n) * k) = 1 mod n for all k

Wait, my bad. I answered my own question by writing it out. Sorry y'all.

[rugged locust]

That is not true, though; the Euler-Fermat theorem explicitly only works when you assume gcd(a,n)=1.

For instance Z_4 has two nilpotent elements : 0,2

[lament gyro]

Ye, I know. That's what I meant by I answered my own question.

Didn't specify cos I didn't realise I needed to lol

[wooden glen]

See also https://en.wikipedia.org/wiki/Radical_of_an_integer

[chrome meadow]

Can anybody check if my reasoning is valid for this proof
I'm proving that (-a) | b given that a | b.
What I've written is, "if -a | b then b = -a × c. Because b > 0 it follows that c < 0, so b = -a × -c". Is this complete or is my reasoning lacking somewhere

[ripe scaffold]

the this | that operator doesnt care about positive/negative, only that that = this * an integer
its not restricting you to positive integers only, so you dont need to care about signs
so given that a | b, that means b = a times c, so you can then immediately say b = -a times -c without needing to care about signs and youre good

[obtuse quartz]

hi, sorry if it's a misfit to this channel.

I have a specific problem where, for given y, I want to chose x such that xy-3 is a square of an integer (or more likely to be a square).
basically I want to reduce number of x's before finding such a number, without trying all (0 <= x < y is all I need to check) candidates.

[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

[carmine tide]

My first instinct is to spam mod contradictions

Ex. Because all squares are either 0 or 1 mod 4, we can exclude all x where xy is 1 or 2 mod 4

[obtuse quartz]

good idea, I think I know how it works. thanks.
for what I'm doing tho knowing how much I can reduce will be useful too.
let's say I have a pre-computed table of if it can be a square for all values mod p for prime p.
for randomly selected values, how much are gonna filtered as "non-square"?
should I make the modulus some prime powers like p^k? or try something mod abcd where all factors are distinct primes? etc.

thank you for quick response btw, I'm willing to learn more.

[wooden glen]

How large is your y? It might be feasible simply to check all k<y/2 to see whether k²+3 is a multiple of y.
(Once you have found such a k, y-k will also work, because k and y-k has the same square mod y.

[obtuse quartz]

It's pretty big, to the point I'd like a less naive approach
I think k has at least 2^32 patterns or something

[wooden glen]

Wait, if you only want x<y, then you only need to check k up to sqrt(y) or so.

[carmine tide]

uhhh iirc there’s (p+1)/2 quadratic residues mod p for prime p

You may also want to filter mod powers of 2

Then amongst the remaining numbers, maybe you can find their p-adic evaluation for small p

If any of them are odd, then it can’t be a square

[prime gust]

I have seen this proof in math stack exchange on how many quadratic residue mon n are there for n=p1,...pk
I just dont understand the step he does here from getting that there are 2^k solutions simply saying there are phi(n)/2^k quadratic residues

[rugged locust]

i would like to highlight that the post is explicitly definiting a quadratic residue to be coprime to n, which is not the conventional definition. For instance, 4^2 = 4 mod 6 is a noncoprime quadratic residue mod 6. So the result is saying that there are phi(n)/2^k coprime quadratic resides mod n

[rugged locust]

consider the function f: A->A where f(x) = x^2.
then the # of QRs in A is exactly f(A).
So if you want to find # of QRs you can just calculate the size of f(A), and since f is 2^k to 1 |f(A)| = |A/2^k| = phi(n)/2^k

[plush dawn]

How to Prove that there is no integer between 1 and 2.

[wooden glen]

Depends almost entirely on which facts (or axioms) and definitions you have to prove it from.

[plush dawn]

Well ordering principle

Can we use it?

[rugged locust]

well, first things first, what is your definition of the integers?

[wooden glen]

And then, what is your definition of the ordering relation that the word "between" presumably refers to?

[plush dawn]

Z={0,±1,±2...} all positive and negative number included0

[rugged locust]

that's not a definition

what do you mean when you say 2? what do you mean when you say ±?

[plush dawn]

Could you please answer it..and dont know about it.

[rugged locust]

because otherwise it just follows from that. You define Z={0,±1,±2...}, so there is nothing between 1 and 2 by construction

[plush dawn]

Yeah thats correct..that means there is no specific proof of this.

[rugged locust]

again, it's a question of how you're defining the integers

[plush dawn]

Is there any other way of defining integers..

[rugged locust]

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

[left fable]

so just a lesson here but in questions like no integers between 1 and 2, when someone is asking you questions you think are dumb like what are integers? you should take a step back and before you respond know that people answering know a lot more than you. theres a reason theyre telling you certain things

it only seems obvious because you know much less

1 is an integer, 2 is an integer, 1000 is an integer, and so is -9. that does not say there isnt one between 1 and 2. it only says you wrote a bunch of integers

you need a definition down to a very axiomatic system to explain why "2" whatever that means as a math symbol comes after "1" and nothing is inbetween

for example what if i wrote the set of all integers are {0,1,-1,-2,-3,-4,...}?

this is certainly correct, but of course its not a good way to write out all the integers. what about +2, +2? but i didnt ommit them im just writing all the negative ones first.... and here you have a problem. when do i include 2?

so i wrote all of the integers, yet i never wrote "2", so does 2 not exist?

of course it does

just because you didnt write an integer between 1 and 2, does not mean it doesnt exist. thats what you want to prove though

you need fundamental axioms, not just "i know everything this question is obvious and dumb" attitude

[wooden glen]

I think you're being a little uncharitable towards the OP there.

It does sound like they're not aware of how a key role of definition is to support proofs instead of simply to tell the listener which numbers we call "integers".
But I don't see them calling anything "dumb" or displaying the kind of arrogance you seem to be arguing against.

[tough edge]

my brain is lagging

if i have 4 unknown numbers, which i know are each one of two options, and im summing them, theres no combinatorics right? i just do case by case (how many option 1s)

[livid raft]

Hi everyone, I am looking for distinct solutions of the form (a, b, c) to the following equation:
(a*b) (mod c) = (a+b) (mod c)

I have come across one non-distinct solution, which is of the form (c, n*c, c), for some naturals c, n

[rugged locust]

by the chinese remainder theorem, it suffices to solve the equation when c = p^k for some prime p

[plush dawn]

How to prove there is no number which are prime but not irreducible

[rugged locust]

what is your definition of prime and irreducible?

[plush dawn]

n belongs to N is irreducible if n=ab then a=1 or b=1

[rugged locust]

what about prime?

[plush dawn]

P>1 is irreducible if a divides p and b divides p then ab divides p

[rugged locust]

this fact follows immediately from the Fundamental theorem of arithmetic, but here's a proof that doesn't use that:

Suppose p = ab where p is prime.
Further suppose for a contradiction that a,b are both not 1.
Then as p is prime p has to divide, let's say WLOG a.
Then a = np for some n, and p = npb.
but then dividing from both sides we get nb = 1, and so n=b=1, which is a contradiction.

[mossy owl]

oh ffs determining whether there are integer solutions for ax^2+by=c (where a b and c are given and x and y are the variables) is already np-complete

how does anyone solve diophantine equations

[rugged locust]

there is no general method, that's the fun part

[loud maple]

Look up Hilbert's tenth problem

[livid raft]

Thank you for responding! I must admit my number theory knowledge is basically non-existent, I have to learn what the Chinese remainder theorem is.

A follow up question, why would this be an equivalent statement?

[rugged locust]

That is essentially the statement of the Chinese reminder theorem

That if n = p1^n1 … pk^nk is the prime factorisation of n, then the set of solutions to a problem mod n is exactly the same as the set of solutions to that problem mod pi^ni for all i

[livid raft]

So (mod 10) would be equivalent to solving for (mod 5) and (mod 2)? I will search this up in more detail soon I am slightly busy atm

[rugged locust]

Yes

[livid raft]

Ah okay

The larger idea in which I am posing this problem is in the context of rings. More specifically, let R be a ring and let D = {r in R: r*r = r+r}

I wanted to know what D could look like for different rings R. If R was the reals then D = {2}

[rugged locust]

oof, that sounds like an impossible problem

in PIDs I believe the CRT still holds and you can do something similar

but in generality I have no idea

oh wait, you mean a=b=r?

[rugged locust]

in that case, you solve and get that r(r-2) = 0.
so if your ring is an integral domain then r=0 or r=2.
if your ring has zero divisors, then r, r-2 belongs to the pairs of zero divisors, and your problem reduces to finding all the zero divisors
and if the ring is noncommutative then the problem reduces to finding all the left and right zero divisors, depending on if you start with 2r or r2

[mossy owl]

wow

[naive heart]

If anyone is up for a read, here's my attempted proof at proving Goldbach via modular seiving. Surely I've made a mistake but unfortunately I don't see it yet !!

https://www.researchgate.net/publication/392194317_On_the_Impossibility_of_a_Goldbach_Counterexample_via_Modular_Sieving

[patent acorn]

Thus, the failure of the Goldbach conjecture for E is equivalent to the condition [E/2, E] ⊆ S.
...no it isn't (or at least you definitely haven't proven that)

that condition is impossible, because E - 1 is an element of [E/2, E] and isn't an element of S

[wooden glen]

Congratulations, you've just proved Goldbach!

[patent acorn]

i think the deeper problem here is that you're not really being clear about what claims you're even making

like i looked through the rest of it and i am not convinced that there is essentially any correct reasoning in this "proof" at all, but i'm not sure how to identify any particular problem because i can't even figure out what any of it is supposed to be proving

[patent acorn]

well yes i got that the point of the entire thing is to prove goldbach's conjecture

but that doesn't help with following each individual step

[naive heart]

Which step

[charred roost]

I think some symbols disappeared when you copy-pasted this text (from chatgpt?)

[naive heart]

Ahh okay wait

.... To formulate a counterexample, a set S is defined to contain only composite numbers, thereby obstructing all potential Goldbach pairs. A modular sieve is constructed to replicate the exclusion pattern of S, targeting specific nonzero residue classes modulo small primes. The system is then translated by a carefully chosen K such that the sieve eliminates values in the zero residue class modulo each prime. For such a sieve to block all shifted primes, those primes would need to occupy a single nonzero residue class modulo 3. However, this scenario is ruled out by the equidistribution of primes among all reduced residue classes. A contradiction is thus obtained, invalidating the assumption of a counterexample.

[charred roost]

So am I correct in saying this is from chatgpt?

[naive heart]

Yeah

I'm just writing quickly cos I'm on the move

The proof is mine

If that's what your implying ?haha

Attempted **

Right right

[abstract ferry]

!nogpt

[rotund gust]

Please do not trust ChatGPT or similar AI tools for mathematical tasks, as they often generate output which "sounds correct" but has numerous factual or logical errors. Use of these AI tools to answer other people's help questions is strictly against server rules (see #rules).

[naive heart]

Sorry I'm new here

[abstract ferry]

this is regardless of you are new to here nor mathematics

[naive heart]

Okay mate

[charred roost]

What do you mean the proof is yours? Do you know what a modular sieve is, or what a reduced residue class is, or is that chatgpt speaking?

[naive heart]

Yes of course I do I was literally just using gpt to write that comment cos I was on the move!!

I've been working on this for a while.

[charred roost]

Okay, what is a modular sieve?

[naive heart]

I constructed a sieve using a mod P residue classes to cover the composites

And then I translates the sieve

By a K

...

Please stop

This is rude

What else do you want

[patent acorn]

...he didn't ask what you did, he asked what a modular sieve is

[naive heart]

Ita a system of modulii that sieves numbers in some way

[charred roost]

Wait, who are you talking to? 💀

[patent acorn]

that's really vague

if that's all you know about what a modular sieve is, then you do not know what a modular sieve is

[naive heart]

Oh for goodness sake

Right I'm not playing. Get a life both of you

[abstract ferry]

there are prerequisites but if you cant describe a thing in very formal, understandable way
or its properties how does that say you know something lmao

you said it is a moduli that sieves numbers in “some way” but what is such a way

[weak torrent]

perhaps this is the famed modular sieve https://www.youtube.com/watch?v=zr2v2R7Z1j8

[barren locust]

:0 your into modded?

[weak torrent]

i looked up “modular sieve” and this was one of the top results

[lime trout]

lmao

[naive heart]

Language is not the same as understanding. there are millions of people that cannot express themselves in formal language but they are many fold more intelligent than you...

[loud maple]

I'd rather live my life focusing on those claims about which people are able to communicate their understanding than worry about people who are 'many fold more intelligent' than me but for whatever reason lack a means to communicate with me.

[naive heart]

Thanks to an actually friendly cough user on Reddit I have now edited the proof. I had made a fairly big error in the set up where I was implying the initial sieve covered compsoites, which was very confusing, when it was meant to be primes Q [E/2, E] Thankfully the translated sieve still seems to act on the zero residue prime classes , and create a contradiction in the same way. As the primes Q are all forced into one residue class ... Not all prime numbers [E/2, E]can sit in one residue class mod prime due to equidistribution .

[naive heart]

Sure but never be dismissive before you've even smiled

It's the kind of "say it to my face like that".

[abstract ferry]

writing about things and then publicating ur works are all about communication.
if you cant communicate with people well, how do you say ur doing a publication, or how even they know if you ever understood it

[naive heart]

Nope this doesn't mean you can be rude still...be respectful. Talk to people here as you would to someone on the street...

[loud maple]

I don't think asking someone to explain what a modular sieve is can be called rude, when the person in question claims to have produced original work using it.

[naive heart]

This isn't what he was doing. He was being snyde and sarcastic and impmying I didn't know. He didn't say, excuse me , would you mind explaining what a modular seive is.

Cmon guys not rocket science

Implying *

[loud maple]

If you claim to solve long-standing open problems, prepare to be grilled.

[naive heart]

Noo even still....

[naive heart]

I will be be grilled nicely thanks

[compact swift]

man the fuck going on here

[supple saffron]

so i was messing around,right

and in a problem i recognized that if you just do nx-n its just n(x-1)

but im wondering,can you have an nx-c=n(x-c) for what c

[loud maple]

What you've written boils down to nc=c

[potent raft]

Yoo I found new formula now and try if it get many prime and see if it works, the quadratic formula is 6n²-42n+103

And I think it stop at n=34

[low halo]

So I’m taking number theory this coming fall

And the intro is all about PEANO

Is this considered elementary?

Description:Prime numbers, the unique factorization property of integers, linear and non-linear Diophantine equations, congruences, modular arithmetic, quadratic reciprocity, contemporary applications in computing and cryptography.

[rugged locust]

yeah that looks standard

the class itself will probably be skipping the peano part

it's not relevant to number theory

[low halo]

Okay

So which type of proofs this subject matter focuses on?

Induction or more direct?

[rugged locust]

proofs are proofs

when I am building a house you do not ask if I need more nails or screws

you just give me both

[sacred junco]

Hey

You know that thing

With exact formula for harmonic

And euler masceroni

Like

H(n)=log(n)+(euler masc)+(some exp tending to 0 as n increases)

Chatgpt wasnt very helpful

But when was this found out

And how

This isnt obvious right?

[long lion]

not sure when it was discovered

[long lion]

but the how is you just partial summation it

https://en.wikipedia.org/wiki/Abel's_summation_formula

[sacred junco]

Cool

Never heard of this

Choosing the right function also seems hard

Or like lucky

Whatever helps you integrate

[long lion]

i mean u pick 1/x lol

differentiate 1/x, and ur sequence is just a_n = 1

[sacred junco]

Oh wait

[sacred junco]

I meant in general

Like choosing to rewrite a partial sum as the product of these two things

[long lion]

oh i mean it's like a really common thing in analytic NT

so you get more familiar with it

the sequence will usually either be a_n = 1 or a_n = indicator of primes

[sacred junco]

Oh

[unique cypress]

It's a product of messing around with asymptotic formulas regarding average sums that are "convenient" to use in number theory

You can check Apostol's analytic number theory book. He covers the basics there

[sacred junco]

how can i show that $(b-a)^2+(b^4-a^4)^2$ is a perfect square only if $a=b$?

[sterile pumice]

Cobain

[loud maple]

(b-a)²+(b⁴-a⁴)² = (b-a)²(1+(b+a)²(b²+a²)²)

For the whole expression to be a perfect square, if b-a≠0, then 1+(b+a)²(b²+a²)² must be a perfect square

[sacred junco]

i just realized im half asleep

thanks anyway

[coral merlin]

I see. I tried that

I could see how 1+x² would result to a perfect square

wait what does perfect square mean

are they the numbers like 1, 4, 9, etc?

[sacred junco]

if some numbers a perfect square then there exists an integer such that the square of it equals that number

[sacred junco]

1+x^2 is never a perfect square if x is a natural number or some integer thats not zero

[coral merlin]

oh ok

[sacred junco]

since if there does exist one then $k^2=1+x^2$ which factors to $(k+x)(k-x)=1$ and the only factor of 1 is itself

[sterile pumice]

Cobain

[coral merlin]

oh yea i see. true

[grave veldt]

Hardy has amazon account

[supple saffron]

Do y’all have tips for formulating proofs in textbook exercises

[regal summit]

read through it and look out for accidental handwaviness

if ur proving something for the first time you should put effort into formulating it with as much relevant detail as you can

[supple saffron]

What do you mean handwaviness

[regal summit]

sometimes youll phrase something and realize you left some detail out because you thought it was more obvious than it actually is

i do this all the time

sometimes ill phrase something and think its obviously when subconsciously im actually just not comfortable with writing it out with as much rigor as it demands

[supple saffron]

Ok

[hot cipher]

How does one proof that equality c holds for every integer

[charred roost]

Work modulo 7 and 5, then combine them

(the fast way to solve this is to see that the Carmichael lambda function of 35 is 12)

[hot cipher]

I have no clue what ghe carmichael lambda function is lol

[charred roost]

Lol, forget about that, it's just a teaser of future attractions 😅 Just try to form two congruences and see if you can combine them to a congruence mod 35

[loud maple]

Euler's theorem for 5 and 7

[hot cipher]

Yes i did so
I kinda did something very stupid when i first tried it so thats why it didnt work

[charred roost]

Doing something stupid is the best way to start 💪

[supple saffron]

😭

[unique cypress]

Did you try the hint?

[supple saffron]

number theory got me fcked up

i can't be doing these proofs bro 😭

i aint never done a proof in my life

[worn folio]

What you working on

[supple saffron]

The exercise is to prove that recursive functions are uniquely determined for all f(n) that’s a positive integer

[worn folio]

Sounds like induction

[plain trail]

Can you reduce the expression (a + 1)(a + 2)(a + 3) ... (a + n), where n is a positive integer, to a simpler form?

[carmine tide]

$n!\binom{a+n}{a}=\frac{(a+n)!}{a!}$

[sterile pumice]

Civil Service Pigeon

[stuck mulch]

you can factorize 35 and then do it seperately

we know that a^4=1 mod 5 for all a, so a^13=(a^4)^3*a=a mod 5 and something similar holds for mod 7

[elder cloud]

Prove that there is no rational number whose square is 12

Let $r \in \mathbb{Q}$ with $r^2 = 12$. Write $r=m/n$, where $m,n \in \mathbb{Z}$ are coprime. Then $m^2 = 12n^2=3(2n)^2$. We see that $m^2$ is divisible by $3$, hence $m$ is divisible by $3$ so $m^2$ is a multiple of $9$. Thus $(2n)^2$ is a multiple of $3$, so $2n$ and thus $n$ are multiples of 3. So $m$ and $n$ share a divisor, which contradicts $m,n$ being coprime. Thus $r$ is irrational.

[sterile pumice]

heavenly_lamb_61155

[elder cloud]

Is my proof correct ?

[long lion]

yh looks fine

[rugged locust]

Better yet, x^2-12 is irreducible by Eisenstein with p = 3

[long lion]

lmao

[rugged locust]

But yeah there isn’t much to it lol

[sullen jewel]

in your country, is sequences a lesson in the curriculum of a 10th grader?

[stuck mulch]

Here's a cool combo/nt problem: Given sequence $a$ such that $a_1=a_2=a_3=1$, and $a_{n+3}=a_{n+2}a_{n+1}+a_n$. Prove that for every natural number there exists a term in $a$ that is divisible by it.

[sterile pumice]

buboblakistoni

[left fable]

small thing, not sure if others agree

"we see that m^2 is divisible by 3 hence m is divisible by 3" on its own isnt enough, you need to say since 3 is a prime (and possibly refer to a theorem)

12 divides 6^2 but 12 does not divide 6

a little pedantic but still important imo

[elder cloud]

Ah i see
Does it work for higher powers? Like if p is prime, and m^k is divisible by p, then m is divisible by p?

[pine brook]

yes

try it using induction

for example, for k=3, you have p|m^3 implies p|m or p|m^2. If it's the first then done, if it's the second, then p|m^2 implies p|m or p|m. In both cases we are done.

[left fable]

just to add more to ^ comment, a|bc means a|b or a|c if a is prime. set "a" prime, and "b=c" to get p | b^2 then p | b if p is prime. thats where this comes from. in class, or books, or online youll see it "Euclid's Lemma"

so in your original proof, i think you should say since 3 is prime and using euclids lemma (so 3|m^2 => 3|m) is properly cited

so now you have name, proof, higher powers

something to think about. if a^3 | b^2, does a|b?

what about if a^2 | b^3?

[pine brook]

oh i forgot to completely mention your first line... I inherently just take that as the definition of prime ;-;

[stuck mulch]

yes

[stuck mulch]

no, take a=2^4, b=2^3

[echo shuttle]

"Let a divide c and b divide c. Show that if a and b are relatively prime, then ab divides c"
Is there away to prove this without using the fundamental theorem of arithmetic? I want something more elegant and less overkill. I feel like I should use Euclidean division and bezout's lemma, but I don't know how.

[loud maple]

Why is the fundamental theorem of arithmetic "overkill" here?

[echo shuttle]

I know this sounds silly, but I'm simply not a fan of using the fundamental theorem of arithmetic for proofs

It's a weird personal thing

[pine brook]

Bezout should be enough

[echo shuttle]

So we have ap = c, bq = c and as + bt = 1

Just a hint on what to use and how to start would be enough

[pine brook]

Multiply throughout by c

The use the first two relations you wrote

[echo shuttle]

In the Bezout lemma identity?

[loud maple]

Ah

[pine brook]

Yup

The fundamental theorem of arithmetic is really strong. I also try to avoid it as much as possible

[pine brook]

Any luck?

[echo shuttle]

I have ||(as)(bq) + (bt)(ap) = c|| which becomes ||ab(qs+pt)=c||. So, ab divides c.

[pine brook]

Yup

Nicely done

[echo shuttle]

Thank you

[pine brook]

This shows that the result is true in a bezout domain, not just a ufd

So really, FTA is overkill

[echo shuttle]

What is a bezout domain and what is a ufd?

[pine brook]

Ufd is a unique factorization domain. So basically good enough rings (integral domains) where every element can be factorized uniquely (upto units). For example Z.

A bezout domain is one where the sum of two principal ideals is also a principle ideal.

The main thing is, there are things that are bezout domains but not ufds (for example, the ring of all algebraic integers). The proof goes through for them as well.

You can look them up to get a better understanding :)

[echo shuttle]

Could someone check if this proof is correct?

[pine brook]

Seems okay

[echo shuttle]

I like the statement, it's pretty neat. I think it implies that (n-1)! is always equivalent to either 0 or 1 mod n, depending on whether n is prime or composite

[pine brook]

Wilson essentially gives an equivalence. (n-1)!=-1 mod n iff n is prime.

[left fable]

n=3 => (3-1)! = 2! = 2 is not 1 mod 3

why is (n-1)! = nq+1 for some q if n is composite?

n=5 ==> 4! = 24 = 5(q)+1, what is q?

[left fable]

^ did i miss something?

oh im stupid, i read it backwards

is there any example at all when its even true?

like for what n is (n-1)! = 1 mod n

[echo shuttle]

n=2. I think the result I proved in combination with wilsons theorem could be used to prove that's only possible case

[left fable]

yea its the only case for trivial reasons

[echo shuttle]

Since we need -1=1 (mod n)

[left fable]

the same reason soooo many theorems use odd primes 😄

imo this is a nothingburger, its never true except yea p=2

and thats not a prime reason, thats just a #2 reason

no numbers less than it

[echo shuttle]

I never imagined 2 as being "trivial" member of the primes, but you do have a point

[stuck mulch]

-1 when n is prime

2 for n=4

and 0 for everything else i think

[quaint thorn]

hello, are you still looking for a study partner?

[rough acorn]

i'm under the impression that the division algorithm doesn't strictly imply (n-1)! = nq+1, for some integer q, rather it implies (n-1)! = nq+r for some 0=<r<n. (and integer q) Am i being silly?

[echo shuttle]

That is correct. We subsequently get r=1 from the fact that (n-1)! mod n = 1.
This turns 0<=r<n into 0<=1<n. Obviously 0<=1 so we can scrap that side of the inequality, and 1<n is given in the questionnaire so we can scrap that as well.

[rough acorn]

Oh, makes sense

[fathom ridge]

can i get help proving for fibonacci numbers (n choose 1)f_1 + (n choose 2)f_2 + ... (n choose n-1) f_n-1 + (n choose n) f_n = f_2n?

strong induction is getting me nowhere 😭

it looks kinda like binomial theorem maybe but i have no clue how that would be relevant here

no generating functions since thats a later chapter

how do i prove ts 💀

[rugged locust]

Think about how you can decompose f2n into a sum of f1 through fn

[fathom ridge]

Do I just recursively use the Fibonacci relation?

[rugged locust]

Also, are you missing a (n choose 0) f_0 term at the start?

[fathom ridge]

Uh maybe

Probably

[rugged locust]

Because the sum doesn’t look right without a n choose 0 term

[rugged locust]

You still use induction

If you want another hint, think about it like this

Try and understand what I’m trying to communicate with this image lol

I’ll draw a better one in a bit

@fathom ridge

[fathom ridge]

hmmmmmmm

ok i think i get what ur getting at

it's like 2 sequences that r overlapping on the same fibonacci numbers that becomes like one bigger one or smth

[fathom ridge]

also no apparently not

i mean at n=1 youd get 2 when you should get 1

or im acc not sure what the 0th fibonacci number is considered

but like yea

[rugged locust]

I’m pretty sure it means f0 = 0 then

[fathom ridge]

yea ig f0 = 0 so that term is js ignored

[rugged locust]

Because n choose 0 has to show up

You’ll see why when you do the induction

[fathom ridge]

ok can get a further hint on how to relate f2n to fn im js getting weird stuff

[rugged locust]

So suppose we have managed to split F_2n into a sum of some middle numbers

Let’s say a sum from F_i to F_j

Well the first goal would be to keep spitting it down further until the biggest term is F_n

Does that make sense

[fathom ridge]

yes

so u js like keep splitting

and i think the coefficients are also fibonacci numbers?

[rugged locust]

So now, given a sum from F_I to F_j, how do you move it down a term?

[fathom ridge]

decompose f_i ?

[rugged locust]

You move it once back, and then separately move it twice back, and add their sum

That’s just from looking at the definition of Fibonacci numbers

And that’s how you reduce the sum up to k into a sum up to k-1

[fathom ridge]

yea but it gets like messy when u repeat it a bunch

[rugged locust]

So now the goal is to inductively show that you get n choose k every time you do this once

[fathom ridge]

wait hmm

what dose that mean

😭

[rugged locust]

Well ok

So it’s
1
1 1
1 2 1
1 3 3 1

When you push the indices back

Those are the coefficients, and you are just overlapping the previous one with itself in the way I described

[fathom ridge]

what r we inducting on

where r the binomial coefficients coming from

[rugged locust]

When you push the maximum index in the sum from 2n back to n

[fathom ridge]

cause rn the thing id wtp is f_2k+2 = sum from i=1 to k of k+i choose i F_i

[fathom ridge]

Why do we get binomial coefficients

[rugged locust]

There’s actually a very nice reason why this happens but I’ll explain that after you’ve proven this

Because the explanation takes longer

[fathom ridge]

ok

i see what ur tryna say tho this does look like an easier way to approach the problem

i dont rly see how its induction yet but maybe once i work ts out itll become clear

but like rn as i keep going im getting fibonacci coefficients

like f_2k = f_2k-1 + f_2k-2 = 2f_2k-2 + f2k_3 = 3f_2k-3 + 2f_2k=4 = 5f_2k-4 + 3f_2k-5

yk

[fathom ridge]

oh u like break apart all the terms at each step?

and it becomes pascals traingle or smth??

[rugged locust]

Ignore Pascal’s triangle (although that does give a neat visual proof)

Just prove via induction that the coefficients at each step are exactly n choose k

[fathom ridge]

im sry i thin kim still a little confused on the process

from one step to the next does every term become broken apart?

cause i got different coefficients than you

[rugged locust]

Yes

[fathom ridge]

o ok

yea i was only breaking biggest

what do i induct on

[rugged locust]

That’s not good enough

We want to reduce the biggest term from 2n down to n

[fathom ridge]

but how does induction happen here

like what do i assume in the inductive step

[rugged locust]

We want to show that the binomial expression is preserved

Every time we reduce the maximal index

[fathom ridge]

hm

so it's just like assume the current step is expressed binomially, prove the next step is?

[rugged locust]

Yes

[fathom ridge]

ok

sry i gotta go eat dinner ill return with more thoughts in like 30 mins

ty for help

[fathom ridge]

ok yup i worked everything out ty again

[obtuse quartz]

Hey so I'm studying about pseudoprimes, and I have a weirdly specific question,
Can there be any overlap between carmichael numbers, and lucas-carmichael numbers?

In case definitions vary, here it is:
squarefree composite n is carmichael numbers IFF for any prime p|n, it's the case that (p-1)|(n-1) is also satisfied.

squarefree composite n is lucas-carmichael numbers IFF for any prime p|n, it's the case that (p+1)|(n+1) is also satisfied.

[pine brook]

That is unknown :(

[obtuse quartz]

ugh, thank you for the info btw!

[elder cloud]

how did they deduce b from a

[pine brook]

If this holds for any b, then you just replace a=b^n, then rename a to b.

[elder cloud]

they say fix b>1 it still works like that?

i think u can just plug in b^1/n for (a) right? since b>1 => b^1/n > 1

[pine brook]

Yup

[pine brook]

That means it holds for any b>1. So yes

[hot cipher]

find x1,x2,x3 for which the equation hold

im stuck

like i can go calculate 2^16 mod 105 but im supposed to do this without a calc

[patent acorn]

105 = 3 * 5 * 7

[hot cipher]

yes i know that
but then using the chinese theorem idk english name
i will get 1 + 105z as solution

[hot cipher]

with z an integer but then i would still need to know which number would be an exact cubic

i tried to use congruence of euler thats how i got 2^48 = 1 mod 105

[patent acorn]

(chinese remainder theorem)

[hot cipher]

ah thanks

[patent acorn]

well that's what you get if you put in x = 1 mod 3, x = 1 mod 5, x = 1 mod 7

but there are two other solutions

[hot cipher]

OOOOOH

wait

can i put in

ok ehm nvm

let me think

nope i dont get how to get the other solutions

[hot cipher]

is there a different set of equations?

how do i find those

[patent acorn]

well from x^3 = 1 mod 105 you know that x^3 = 1 mod 3, x^3 = 1 mod 5, x^3 = 1 mod 7

[hot cipher]

yes i get that

[patent acorn]

so you can just solve each of those separately

[hot cipher]

yeah that gives 1+3k
1+5k
and 1+7k

[patent acorn]

nope

[hot cipher]

huh

[patent acorn]

those are all valid solutions but they're not all of the solutions

[hot cipher]

uuuuuh

let me cook

[hot cipher]

ok i think i know what to do but idk how to do it
cuz these solutions are for the equation x = 1 mod 3 but we got x cubed so we also need to include the cubic roots of 1+ak but idk how to find those perfect cubes

or am i totally wrong now

OH WAIT

ok nvm

istg i had modula maths
imma eat lunch

[patent acorn]

well you can just take each number, cube it, and see if you get 1

0^3 is always going to be 0 which isn't 1 so you can skip that

for mod 3, 1^3 = 1, 2^3 = 8 = 2 which isn't 1, so x = 1 is the only solution
for mod 5, 1^3 = 1, 2^3 = 8 = 3 which isn't 1, 3^3 = 27 = 2 which isn't 1, 4^3 = (-1)^3 = -1 which isn't 1, so x = 1 is the only solution
for mod 7... well you should get the pattern by now, i'll let you fill in this one

[hot cipher]

Yeah i had finally figured ut out
2 and 4 also work as solutions

But is there no trick for it? Just brute force calculate all the cubics of the numbers below it?

Ok now i got it

Now i need to check 1+15k mod 7 = 2 for which k

So 16 works

And 46 we get from 1+15k mod 7 = 4

So the three solutions are 1,16,46

Omg that makes much more sense now

Thank you

[silent bear]

So I made this triangle where first I assign 1/2 -> 1, 1/4 -> 2, 1/8 -> 3 and so on. And then I assign any fractional number z the possibly smallest sum of the integers that are assigned to 1/n's whose total sum is z. For an instance 3/8 -> 5 because 3/8 = 1/4 + 1/8, 1/4 -> 2, 1/8 -> 3, 2+3=5. It's true 3/8 = 1/4 + 1/16 + 1/16 but that does not keep it miniamal.

What name does this actually have and what interesting properties can easily be found from this?

[silent bear]

I did some digging and it's A359042

(OEIS)

[faint sierra]

what i can immediately see here is that, for a fraction 1/n, the result z will be the power of 2 of n, assuming n's only prime factors are 2's. this would mean that 1/32 will yield 5, 1/64 will yield 6, and so on. if you want to calculate, say, 1/3, then you may realize that 1/3 cannot be constructed using 1/n, where n's only prime factors are 2's. this is simply because 1/3, when written as an egyptian fraction expansion, is also 1/3. if you would have, say, 2/17, the egyptian fraction would be 1/9 + 1/153.

[silent bear]

Riight
I am gonna test what funny stuff would happen if I give 1/p natural numbers or really for any given subset of natural numbers 1/s for s in the subset
My ex also proposed assigning 1/n's primes, and then instead of sum, go with product to see what other funny shit would also happen
I'll do it at least after this week which would be finally the summer break for me

[obtuse quartz]

im studying about proving primality
and well this is a fun topic!
it's known that it's easy to do so, if p+1 or p-1 is easy to factor. (say p is the number you're trying to prove primality)
because if p is prime a^(p-1) = 1 (mod p)
and using its quadratic extension for example, the order becomes (p^2-1) = (p-1)(p+1). and I think that's where the p+1 comes from. got it.
you don't immediately see which is "better" to find some kind of large primes, like ones in GIMPS or PrimeGrid or w/e
so I run my code and ones that p+1 is easy to factor seems more likely to be a prime (than p-1 being easy to factor)? at least for primes of my interest?
for example

[p-1 is easy to (partially) factor]
2^n + 1 is a prime when (n = 1,2,4,8,16)
4^n - 2^n + 1  is a probable prime when (n = 1,2,4,32)
4^n + 2^n + 1 is a probable prime when (n = 1,3,9)

[p+1 is easy to (partially) factor]
2^n - 1 is a prime when (n = 2,3,5,7,13,17,19,31,61,89,107,127,521,607,1279,2203,2281, 3217,4253,4423)
4^n - 2^n - 1 is a probable prime when (n = 2,4,5,9,10,18,38,45,50,57,108,161,208,224,225,240,354,597,634,1008,1080,1468,1525,1560,3298,3329,3846,4129)
4^n + 2^n - 1 is a probable prime when (n = 1,2,3,4,6,10,16,24,26,35,52,55,95,144,379,484,939,1284,1300,2651,3644,3979)

and n was tested up to 5000.
Q: is there a reason that the top list looks a lot more sparser?

it's not only sparse, but it looks like the list "stops" - in a sense that I don't think there are more of them.

[pine brook]

Seems like you found the 5 known fermat primes (2^{2^n)+1, note that that list has only powers of 2 and that is not a coincidence) and some of the mersenne primes (2^n-1, note that this list has only primes, not all though like 11 is not there)

I can't comment on the others yet, haven't checked really. But it might be related to the fact that we know only 5 Fermat primes but a lot of mersenne primes

[pine brook]

About the fermat primes, we don't know if there are more. I think we can say similar statements about the others too.

[obtuse quartz]

Ok, ty for comments!
Made some things clear about 2^n ± 1 but not entirely sure about others still

[raven kayak]

hi, can anyone give me a hint please. I tried to prove that number is a Liouville number but i don’t if it is correct

[rugged locust]

||think about base 2||

[chilly thistle]

This might be a simple question. But can an irrational number ever be rational in a different base. How about a rational number becoming irrational in a different base. Seems that the answer to both of those is no but I wouldn’t know how to go proving that

[rugged locust]

no, but that's assuming the base itself is also rational

but in general irrationality is something that is not dependent on how you choose your base (assuming you are choosing "nice" bases)

[chilly thistle]

Fair enough. So the assumption breaks down in an irrational base then? Eg pi in base pi

[chilly thistle]

Yeah fair enough

Ai overview lied to me once again ahaha

Not that I’m overly trusting with it, especially with math questions

[patent acorn]

honestly in terms of terminology i'd say, no, a rational number is rational and an irrational number is irrational

it's not "rational in a base" because the property of a number being possible to write as a ratio of two integers doesn't mention a base at all

[chilly thistle]

Yeah that makes sense

[rugged locust]

an interesting question instead would be to ask if "rational if and only if the decimal expansion is finite or periodic" holds true in general rational bases. and the answer is indeed yes, as one would expect

[patent acorn]

if you mean the equivalent property of having an eventually periodic decimal expansion, then yeah i think that's equivalent to being rational in all rational bases, and in irrational bases you definitely get weird stuff (because like, "10" would be irrational)

[wooden glen]

It's pretty off the beaten path to consider positional systems with non-integer bases in the first place, though. Never mind the rational/irrational distinction; arithmetic becomes super weird.

[raven kayak]

so as it’s decimal expansion is not periodic, because you got a bunch of zeroes, the number it’s irrational ?

[rugged locust]

well, binary expansion

[raven kayak]

sorry i don’t get it

[wooden glen]

Your explanation was correct (if a bit informal), except you should have said "binary expansion" instead of "decimal.expansion".

[desert wave]

is anybody active

bro mobody

[stuck shore]

#chill

[desert wave]

ok

i'

im tired

[frank matrix]

Can someone help explain all but the last step

[unique cypress]

How can you rewrite the sum?

[frank matrix]

Which sum

[unique cypress]

The one down

Sum of logs is equal to?

[frank matrix]

Of course it’s the product but I don’t see how that helps

Maybe there’s a combinatorial interpretation to why ${2n \choose n}$ is divisible by every prime between n and 2n

[sterile pumice]

aNDY

aNDY

[unique cypress]

just write them down lol

Every prime in the interval (n,2n] appears in the numerator

[frank matrix]

Oh duh

I see now

The primes in the interval can’t be divided by n!

[unique cypress]

yeah so you get that the product <= the binomial

[frank matrix]

So each must be a factor of the binomial coefficient

[unique cypress]

Do you see how do you get O(n)?

[frank matrix]

yeah that’s just stirling

[unique cypress]

Cool

How about the first sum?

[frank matrix]

Digesting

[placid stratus]

does anyone know the state of the art for finding goldbach pairs

i found an approximate linear method

[unique cypress]

[placid stratus]

for some n=p+q, 1.85 * nth(largest_prime_divisor(n)) ~ nth(p > q)

so finding a goldbach pair for any given n is a quick lookup if you have a table of primes

the relationship itself is quite interesting. why should the prime indices have a linear relationship?

[frank matrix]

Nah haven’t gotten it yet

[vestal light]

First try to understand the sum $S(n)$ of $log(p)$ over all primes less than $n$, by breaking it up into the sum over those between $n$ and $n/2$, those between $n/2$ and $n/4$, those between $n/4$ and $n/8$, etc. and summing the convergence series. Then notice that the relevant sum at the start may be written as $S(n) + S(\sqrt{n}) + ...$, where you have at most $log_2(n)$ terms in the tail of that sum

[sterile pumice]

Nathaniel Kingsbury-Neuschotz

[left fable]

if you want another one, see if you can show $\sum_{k=1}^{\infty} \frac{1}{10^{k!}}$ is irrational. also fun thing this is also transcendental and "almost all" numbers are transcendental. thats irritating for intuition.

[sterile pumice]

rochambo

[frank matrix]

I was thinking that, but what about the different coefficents on log p

[vestal light]

WDYM by different coefficients? The fact that you sum for every prime power less than n, not just every prime less than n?

Note that I define S(n) to be the sum only over primes, and I handle the remaining terms (higher prime powers) in my last couple of sentences

[tranquil shoal]

ok so i was looking at this example problem. Why is that step justified?

is related to the inverse operatoin

[pine brook]

If you multiply 10 on both sides, then the LHS becomes 100, which is 1 mod 11.

[wooden glen]

Note that the 2 at the end is the same 2 they already had at "2 + 10a10 = 0".
Instead of multiplying by 10 they could just have added a10 on both sides. The 11a10 on the LHS disappears since 11=0, and we immediately get 2 = a10.

[frank matrix]

ah I see

[left fable]

just to add another perspective, using 10=-1
10a = 9 (mod 11)
(-1)a=9 (mod 11)
a = (-1)9 (mod 11) multiply both sides by -1
a = (10)9 (mod 11)

so either multiply both sides by 10 to get 100 = 99+1 = 1 mod 11
do what i wrote above using 10=-1
do what tropo said about just add a to both sides so 10a + a = 11a = 0

[solid garden]

James's number theory thread

[wild spruce]

Hello, I would be going through this course page in the thread https://ocw.mit.edu/courses/18-781-theory-of-numbers-spring-2012/

If interested, do join :)

[placid stratus]

is anyone here into vibe proofs

[pine brook]

Wdym?

[placid stratus]

i might've just proved that 2p' always has a sum p+q

[pine brook]

Sure, go on

I am hoping p and q are primes and p' is not necessarily a prime, right?

[placid stratus]

p' is always prime

it may generalize but it's still interesting

[pine brook]

Then 2p'=p'+p'

[patent acorn]

well- yeah

[placid stratus]

oh, but p and q are unique

so it's a goldbach pair

[patent acorn]

well they aren't unique in general, 2*11 = 22 = 3 + 19 = 5 + 17 so there are multiple (p,q) pairs

[pine brook]

Goldbach does not claim to be a sum of two different primes

6 is 3+3 for example

[patent acorn]

hang on no this example doesn't work lol

i am too sleep deprived for this

fixed it

[pine brook]

Get some good sleep

[placid stratus]

i think it's still progress and interesting, if my result works they have to be unique

[pine brook]

Go on go on

[placid stratus]

the starting idea is that every n has some greatest prime factor k, and if you consider this in reverse, every k has some smallest n

empirically you get a linear relation between k and max(p,q) for n smallest

you can define a lower and upper bound for where the smallest n will fall to explicitly define that relation

[patent acorn]

for a prime k, wouldn't the smallest n that has k as its largest prime factor be... k

or if you exclude that then it's 2k

[placid stratus]

yes, and that is very handy

so the slope is about 1.85 between prime indices of k and max(p,q)

and you can bound it as [2-log2/logp_k, 2+log2/logp_k]

this comes from pnt and min and max reasoning about p and q

if we then consider some starting point where we know every k has a goldbach pair, we can reason inductively from there

if we suppose that the next k does not have a goldbach pair, we can show a contradiction

[patent acorn]

...how

[placid stratus]

deriving the gap and showing it contradict's nagura's

if no goldbach pair exists then that implies 2p_k-p_i=q_i is always composite

[patent acorn]

ok so how do you get a contradiction from that

[placid stratus]

take it easy on me and let me type, i'm taking painkillers and ignoring a headache

there are k such values, and they're all composite

2p_k-2 is the largest, 2p_k-p_{k-1} is the smallest

so we get a prime gap of (2p_k - 2) - (2p_k - p_{k-1}) = p_{k-1} - 2

nagura's says the gap is at most p_k - 4/5p_k

[patent acorn]

...by a "prime gap" do you mean that all of the numbers in that range are composite?

[placid stratus]

yeah, that has to be true if a goldbach pair doesn't exist

[patent acorn]

why?

if you want a more concrete question, why does the nonexistence of a goldbach pair imply that 2p_k - 9 is composite?

(for sufficiently large k obviously, so that 9 < p_{k-1})

[placid stratus]

9 should be prime, but gimme a sec

[patent acorn]

9 isn't prime, it's 3 * 3

[placid stratus]

i know but we're only checking primes

[patent acorn]

no

you said that "prime gap" means all of the numbers in that range are composite

and 2p_k - 9 is a number strictly between 2p_k - 2 and 2p_k - p_{k-1}

(for sufficiently large k)

[placid stratus]

it is, but p_i must be prime

[patent acorn]

i don't know what you mean by p_i in this context

[placid stratus]

when i write p and q, they must be prime

[patent acorn]

i'm responding specifically to your claim that there is a prime gap between 2p_k - 2 and 2p_k - p_{k-1}

anything outside of that is irrelevant

and you defined "prime gap" as meaning that every number in that interval is composite

so my question is why 2p_k - 9 is necessarily composite

and if that isn't necessary, then why is there a prime gap of that length

[placid stratus]

okay, let's arrive there from the beginning

[patent acorn]

actually let's not do that

[placid stratus]

if a goldbach pair exists then there is some 2p_k =p_i+q_i

[patent acorn]

you should be able to look at the concrete claims that i'm claiming you made and at least tell me which of them you're actually making

[placid stratus]

p_i and q_i are strictly less than p_k

so there are k-1 candidates to try

[patent acorn]

you don't need to explain the entire proof again

[placid stratus]

if 2p_k - p_i is always composite, there is no goldbach pair

ohhh

this skips values though doesn't it

so the run of values 2p_k-p_i for i<k will be composite

but there are values between them and whether they're prime, idk

[patent acorn]

exactly

[placid stratus]

well, at least i think it's interesting to show the existence of the 1.85 band

any issue with that reasoning? it must be composed of the smallest n values per k if it exists, every 2p_k implies a new k value and fills it (so there are no gaps), and its existence is inferred from the bounds

and it is still true that each 2p_k-p_i would be composite without a goldbach pair for k

perhaps there is another avenue of reasoning to consider

[placid stratus]

i guess this defines a goldbach prime gap

perhaps nagura's can be adapted

any ideas for showing a [n,f(n)] bound for goldbach primes?

[placid stratus]

hm, i found another interesting angle

assuming goldbach's fails for some p_k implies a certain count of composite values

there is a limit on how many p_k can fail before you overcount composites

so goldbach's can only fail for some finite quantity of 2p_k

(with enough failures, it would imply too many composites in the lower range starting from 0)

[placid stratus]

another idea: all the complements implied by 2p_k no goldbach must be smooth up to the greatest prime less than 2p_k

[placid stratus]

okay, progress

as we consider larger n whose largest prime factor is k, i.e. ck for c > 2, the complements defined by (p_k, c*p_k) grow, and must be fit into the same range (0, p_k) by mirroring. eventually, this defines more complements than k smooth numbers, yielding a contradiction

so every k has some minimum n after which there exists at least one goldbach pair

the joys of vibe math.. ask for the same plot, get two different results

[placid stratus]

regardless of which graph is correct, the reasoning is solid i think

i need a nap

this is close to proving strong goldbach

[placid stratus]

i realized an error in my nap but also a fix

the actual intervals should be, uhh, (0, c * p_k) and (c * p_k, 2c * p_k)

but it's amendable because the prime count in the left interval grow asymptotically faster than the prime count in the right interval

so for a large enough k, there is always a c that implies an overcount of composites in the right side

[placid stratus]

mm, never mind

[placid stratus]

honestly maybe i should write a little paper about the results already because it does show that goldbach's is actually quite profound and interesting

the linear relation is between constructing composite numbers using prime factors and building prime numbers using prime summands

and if goldbach's is true, the relation is proven

so this would prove, at least, that the conjecture is deeply interesting

that is to say, given any subset of primes, it's in a class of linearly related subsets determined by goldbach pairs

so you can iterate infinite classes of ksmooth spaces by goldbach pairs

this makes some primes quite a lot more interesting than others

break time

[abstract ferry]

<@&268886789983436800>

why are there so many

[tardy talon]

So, I was working on a problem to find the number of trailing zeroes in $n!$.
I started reading about it and stumbled on Legendre's formula for finding the highest power of $p$ that divides $n!$
$$\nu_p\qty(n!) = \sum_{i=1}^{\infty} \left\lfloor\dfrac{n}{p^i}\right\rfloor$$
I understand that I need to find $\text{min}\qty(\nu_5(n!), \nu_2(n!))$, but this line from wikipedia confused me

The formula actually counts the number of factors 5 in n!, but since there are at least as many factors 2, this is equivalent to the number of factors 10, each of which gives one more trailing zero.

Why are there at least as many factors of 2?

[sterile pumice]

garamgaramsamose

[tardy talon]

oh wait nvm it makes sense, i am stupid

[jovial smelt]

When you're trying to figure out how many trailing zeroes are in n!, the key is realizing that each trailing zero comes from a factor of 10 and 10 is just 2 × 5. So, for every pair of 2 and 5 in the prime factorization of n!, you get one trailing zero. Now, here's the trick: 2s are super common because every even number contributes at least one, while 5s are way rarer since only multiples of 5 add a factor of 5. That’s why we usually just count how many times 5 appears in the factorization of n! (using Legendre’s formula), and not worry about 2s there are always more 2s than 5s, so 5s are the bottleneck. That line from Wikipedia just means that since 2s are always more abundant, the number of 10s (and therefore trailing zeroes) is completely determined by how many 5s are in there.

[wild spruce]

this is what I have done so far

any inputs?

[pine brook]

b+|b|\ge 0. It can be 0 as well. But S only has those b+xa such that b+xa>0. So this does not show that S is non-empty. You have to tweak your choice of x a little.

I would suggest using euclid's division lemma to do this quickly (which hides the well ordering inside the proof of the lemma).

[wild spruce]

I did

|b| + 1, right?

[tight mountain]

if $\frac{a^2+1}{ab+1}$ is an integer (a,b integers and greater than zero), is a=b?

[sterile pumice]

poka luka wan

[tight mountain]

it feels obviously true but I can't think of any proof for some reason

[long lion]

if a^2 + 1 has a 1 mod a factor, then it must have at least 2

but the smallest 1 mod a factor not 1 is a+1, and (a+1)^2 > a^2+1

[split sail]

are you still on the problem?

[tight mountain]

why does a^2+1 having a 1 mod a factor imply that it has at least 2?

[split sail]

since b can't be bigger than a (trivial), you have to prove that in fact b can't be smaller than a and therefore it must be equal. I did it by adding convenient factors to the numerator.

[long lion]

as in like say (ab+1)(qa+r)= a^2 + 1, then r=1

[upper mural]

hey yall, is this a good time to ask what a trailing zero is?

[west glade]

eg 720 has one trailing zero and 4961000 has three trailing zeros

[tight mountain]

looking at $\frac{a^2+b^2}{ab-1}$ (integer solutions, a>0, b>0). why is it always 5 (e.g. a=1, b=2 leads to 5)?

[sterile pumice]

poka luka wan

[tight mountain]

every integer solution with 0<a,b<100000

[tight mountain]

nvm solved it

[ocean flame]

Hi! Are there any lists of unsolved problems related to Pythagorean triples? I know at least two: 1) Are there infinitely many Pythagorean triples where all sides are triangular numbers? 2) Are there infinitely many Pythagorean triples where one leg and hypotenuse are primes?

[surreal crescent]

not precisely on pythagorean triples, but perhaps related. the problem of determining whether N can be the area of a right triangle with rational side lengths

[ocean flame]

Interesting. Thanks

[upper mural]

this is a stupid question but im really curious, can it be proven that if the sum of all digits of a number is divisible by 3, then the number itself is also divisible by 3?

forgot to add; if yes, how? lol

[rugged locust]

I'll just do the 3 digit case, you can generalise it to the rest.
Suppoes that "abc" is a 3 digit number such that a+b+c is divisible by 3.
Then "abc" = 100a + 10b + c = (99a + a) + (9b + b) + c = 3(33a + 3b) + (a+b+c), so "abc" is divisible by 3

[charred roost]

It's easier to prove if you know modular arithmetic: it boils down to the fact that 10 = 1 (mod 3).

If (x_1, ..., x_k) are the digits of a number n in reverse order, then n = x_k * 10^(k-1) + ... + x_2 * 10 + x_1 = x_k + ... + x_2 + x_1 (mod 3), so n and its digit sum have the same remainder modulo 3

[rugged locust]

I considered explaining it that way but then i realised i didnt want to deal with the question of "what is modular arithmetic", so good luck lol

[charred roost]

Lol, I think I also want to back out of that explanation 😅 kinda hard to explain when typing on a phone

[junior swallow]

Does a(2x + 3y) + b(x - y) = x have any integral solutions for a and b

[rugged locust]

are x and y variables?

or are they fixed numbers as well

[junior swallow]

They're just basis elements of a free abelian group G, I'm trying to prove this problem

[rugged locust]

in this case you just solve the linear system in Q

and by Gauss's lemma it will give you a solution in Z

[junior swallow]

Oh I lowkey forgot that lol

[upper mural]

honestly thats simple and beautiful

[junior swallow]

Do you know where I can find an exact statement of this theorem? I tried googling it but I just got the product of two primitive polynomials is primitive

[upper mural]

you read me well

[rugged locust]

there are a few equivalent forms

let me pull up my notes, but the version of it that you're looking for here roughly tells you that if you have an integer polynomial, then solutions in Q correspond to solutions in Z

[junior swallow]

Oh okay thanks

[rugged locust]

If f(x) is a polynomial, define the content of f(x) to be the gcd of all of its coefficients.
A polynomial is said to be primitive if its content c(f) = 1.

• Gauss's lemma (version 1).

The product of two primitive polynomials is primitive.

• Gauss's lemma (version 2).

c(fg) = c(f)c(g)

• Gauss's lemma (version 3).

If D is a UFD with F the field of fractions of D, such that f = g1g2 for some f(x) in D[x] and g1,g2 in F[x], then there exists scalars c1,c2 in F such that c1g1, c2g2 in D[x] and f = c1g1 c2g2.

essentially, it tells you that factorization of polynomails in the field of fractions can always be "normalised" into factoriation of polynomails in the base ring

actually, wait, is it even needed here?

[rugged locust]

lmao you don't need Gauss's lemma, you just solve the linear system

my bad

[delicate vortex]

I'm assuming here that the idea is to argue either that at least one factor is not irreducible, or that we have equality up to units. I am having difficulty proving either of these in practice. For the first one for example, I don't think 5 +/- sqrt(3) is an associate of 2 or 11, so I should be arguing that e.g. 2 or 11 is reducible. If 2 is reducible, then there should be an element of Z[sqrt(3)] with norm 2, but I cannot find any with coefficients <100, similarly for elements with norm 11. Am I missing something?

[pine brook]

2=-(1+\sqrt 3)(1-\sqrt 3)?

[delicate vortex]

ah true thanks, I forgot we could also solve for -2

[pine brook]

all good

[livid raft]

What if you took a=0 and b to be any other integer? You would still obtain the integer 1 but clearly a does not equal b.

[pine brook]

a and b are given to be > 0

[livid raft]

I am blind

[vestal yacht]

sorry, I don't know if this is the right place to ask, I want to know some number theory book recommedations?

[ocean flame]

Maybe #book-recommendations is more appropriate channel. By the way, now I read "Number Theory:
In Context and Interactive" by Karl-Dieter Crisman. It is free and has pretty good interactive web version. I don't have any previous number theory experience so this book is good for me

[junior swallow]

Uh wait is it even possible to write x and y as linear combinations of 2x + 3y and x - y with coefficients in Z

Am I trippin

ok maybe chat gpt is wrong

Well if I say a(2x + 3y) + b(x- y) = x and compare coefficients, I get a = 1/5

[wooden glen]

No -- the sum of the coefficients of x and y will always be 0 modulo 5.

[surreal crescent]

Oh that’s nice

[upper mural]

I wanna ask a potentially stupid question. why are primes so important? to the point where a ton of research has been done centered at them. As a newbie to number theory, my only conclusion would be because they represent the perfect chaotic system, but that may be a very stupid conclusion lol

[vestal anchor]

I guess at a basic level cuz primes are the multiplicative "building blocks" of the integers: by the fundamental theorem of arithmetic, every positive integer is uniquely factorisable as a product of prime powers. So for any sort of (multiplicative) question about the integers it is usually useful to break it down and consider it for primes. (But also just because they're very interesting to study lol)

[rugged locust]

divisibility works the best with primes

as a very basic fact, in general if a divides b^2 that does not mean a divides b

but if you can't say something as simple as that it's nigh impossible to prove anything about diophantine equations

but if you restrict yourself to primes, then it does become true

[wild spruce]

Okay so I will lay out what my approach has been so far...

I computed n(a, b) for some specific instances of a and b and was able to notice a common pattern

which is...

$n(a, b) = ab - (a + b)$

[sterile pumice]

James

[wild spruce]

Now I think I need to go about proving the claim that n(a, b) can't be represented as ax + by with x, y \in N+ and that every greater integer can be represented in such a way

I think for the former contradiction should suffice?

and for the latter, I am thinking along the lines of induction maybe (not very sure about this)

[rugged locust]

what happened to the thread?

[wild spruce]

it's there i believe....i just posted here to get some visibility

[mint stone]

Definitely you should learn McNugget theorem
https://artofproblemsolving.com/wiki/index.php/Chicken_McNugget_Theorem

[wild spruce]

Funny name lmao

[delicate vortex]

I think there's just a bit of logic I don't understand here for the last inclusion. I computed all relevent quantities: we have $Tr(\theta) = 3u,$ $Tr(\delta \theta) = 3dw,$ $Tr(\delta^2 \theta) = 3dv,$ and $N(\theta) = u^3 + dv^3 + d^2w^3 - 3duvw.$ Clearly $\mathbb{Z}[\delta] \subseteq \mathcal{O}_K,$ but I don't see exactly what to do with these quantities to prove that $\mathcal{O}_K \subseteq \tfrac{1}{3} \mathbb{Z}[\delta}.$ I know that if $\theta \in \mathcal{O}_K,$ then $Tr(\theta), N(\theta) \in \mathbb{Z},$ but I am not making much more progress.

[sterile pumice]

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

[long lion]

this belongs in #advanced-number-theory btw, this channel is more for like basic stuff i.e. bezout crt etc.

but as for ur question, recall that the trace and norm of an algebraic integer are (rational) integers

so the goal is to use ur expressions for Tr(theta), Tr(deltatheta), Tr(delta^2theta) and N(theta) to deduce that u,v,w are in Z/3

[mint stone]

Yes, I have a proof. View your equation 10^k x +y=(x+y)^2 as a quadratic equation in x with fixed y. If there is one positive integer solution to it then the other solution is also a positive integer. Both x1, x2<10^k. Then reduce them mod 9. The discriminant mod 9 equals 7, so one of the solutions is always x=-y (mod 9). So, x+y is divisible by 9 and by 5. Thus, (x+y)^2 is divisible by 2025.

[idle fractal]

I just need to prove that for odd k there are no numbers divisible by 5.

[idle fractal]

I would only have to prove this, I know from a computer program that this is the case, but the mathematical proof is missing

[mint stone]

You won't prove this bc it's not true

say x=8784160, y=588225, k=7

[quiet tree]

Anyone online

[west glade]

no, everyone is offline

[quiet tree]

https://www.reddit.com/r/askmath/s/vkI6MG0Hw6

[quiet tree]

Noone can prove this

[prisma folio]

This looks false

13^3 - 13 = 3^7 - 3 = 2184.

[quiet tree]

That was fast, did U use wolfram alpha or smtg

[prisma folio]

No, there is an OEIS sequence and a paper about these

Michael Bennett, On some exponential equations of S. S. Pillai, Canadian Journal of Math. 53 (2001)

And

https://oeis.org/A057896

[quiet tree]

What does the paper really say?

That there are finite counterexamples?

I never read a paper before

[prisma folio]

No, it just says that there are at most two solutions if you take some c and a, b >= 2 and want to find x, y so that a^x - b^y = c. OEIS linked the article, I haven't read it, not sure if it states anything directly about the counterexamples you ask for

But just check OEIS, they give two examples

One of them is of the form you are looking for which I wrote down

[quiet tree]

I see, thanks