elementary-number-theory

[torn escarp]

sounds similar to the post correspondence problem, I'm gonna guess it's undecidable with the hope someone proves me wrong

[idle steeple]

What does this mean?

For what it's worth I wrote a program that I think gives the answer in python, it seems to work

def isproduct(number, list_of_factors):
    for n in list_of_factors:
        for m in list_of_factors:
            a = max(n, m)
            b = min(n, m)
            if a % b == 0 and a != b:
                current_factor = a // b
                if current_factor not in list_of_factors:
                    list_of_factors.append(current_factor)
    for factor in list_of_factors:
        while number % factor == 0:
            number = number // factor
    return number == 1

Assumes that 1 isn't in the list of factors

[torn escarp]

your function doesn't seem to work, isproduct(4, [6,10,15]) returns false but 4 = 6*10/15 is true

[idle steeple]

Ohh yeah you're right

Damn it's trickier than I thought on first read

[torn escarp]

you can think of the post correspondence problem as being a kind of simple problem with given a set of dominos with letters on them, and trying to match them up to make the same word on top and bottom

the observation I'm saying is it's sorta similar except it's prime numbers in numerator and denominator and the letters commute, and we're not exactly making the words match exactly, we're trying to match the given number

so it might not be undecidable but I wouldn't be surprised if it turned out to be equivalent or something cause it's sorta similar and deceptively simple sounding

idk it was just a quick guess after looking at it for 3 seconds so don't look into it too much lol

[idle steeple]

thanks for the rundown

[leaden swan]

I was thinking you could reduce this to a Z-module membership problem

Enumerate all the different prime factors in N. Let the count of all the distinct prime numbers be k. Consider \mathbb{N} ^k

Reduce a number to $N^k$ as
${p_1}^{q_1} {p_2}^{q_2}...{p_k}^{q_k} \mapsto ({q_1},{q_2}...{q_k})$

[sterile pumice]

JohnDS

[leaden swan]

Similarly reduce your X to this form. If you can't reduce it,it means you can't obtain it trivially

Otherwise ,Check if X is in the span of those generators(all the numbers in N)

That can be done with Smith Normal form because this corresponds to finding a solution to a system of linear equations over Z

I have no idea how you will do this part computationally but that's how you do it mathematically

[leaden swan]

Sorry this N should be $\mathbb{N}$

[sterile pumice]

JohnDS

[leaden swan]

I think this could have been PCP but a finite set of \mathbb{N} being reducible to \mathbb{N}^k prevented that

[leaden swan]

@sacred junco you saw this right?

[sacred junco]

<@&286206848099549185> any clue how to solve this

[stiff timber]

it would be better if you show what you already know, so that we know where to start with

[elfin condor]

lol I think this problem solves itself, just plug some jawns in and see where the algebra takes you

[wicked patio]

I need to prove that there exists a prime number between n^2 and (n+1)^2 for all positive n. I have already bruteforced the theorem, and it appears to be correct.

Can i get a hint? (Thank you)

[inner anchor]

https://en.wikipedia.org/wiki/Legendre's_conjecture

[formal minnow]

wow lol

[wanton torrent]

anyone acquainted with vigenere cipher?

[wanton torrent]

I don't understand how he built the system of Betas

This is the exercise, I don't understand how to do (b)

Note that the length of the key is 4

[abstract quail]

Hi guys, could someone help me with this exercise

[frigid path]

https://media.discordapp.net/attachments/925630045777715250/972012026568265748/IMG_0906.jpg

[inner anchor]

you can interpret the second condition using eulers criterion and then use quadratic reciprocity to find to which residue classes 2p+1 must belong mod 5

i think after that its just brute force

[silver berry]

what is the contradiction here? (the proposition was about how g is a primitive root mod p iff for all q s.t. q is a prime factor of p-1, g^ (p-1/q) is not congruent to 1 mod p)

[sacred junco]

can someone explain how passing the lucas test proves n is prime

idk any group theory

but i get that a is the order of n-1 for every a

how does that prove n is prime though

also why use n-1/q instead of q. Since n-1/q is just the complementary divisor

[stiff rivet]

(Z/nZ)^* consists of all elements in {1, ..., n-1} coprime to n
so if the order of that group is n-1, then n must be prime

you can use q

[sacred junco]

so the conditions holding true implies phi(n)=n-1 and that implies n is prime

[sacred junco]

im still wondering why they used n-1/q

is it to highlight q divides n-1

[stiff rivet]

yes

no idea, it doesnt matter

you just have to test the divisors of n-1

[sacred junco]

yeah

Also

Any idea why pollard's rho method for factorization works

[leaden swan]

A question about that notation,what does [z]_{\phi_p(z)} mean? I know Z_q[x] but this is new to me

You know
$\sum_{i=0}^{p} x^i = \frac{\left(1-x^{p+1}\right)}{1-x}$?

[sterile pumice]

Drake

[leaden swan]

If you differentiate this you get \sum_{i} i x^{i-1}

So it feels like the expected solution is to find a closed form for the sum and then manipulate that somehow to show it's a unit

Or maybe you can use this to demonstrate x will be nonzero

[sterile pumice]

Scip

[leaden swan]

This is called the discrete logarithm problem

There are different techniques to solve discrete logarithm (like baby step,Pollard rho). You can look those up

https://crypto.stanford.edu/pbc/notes/crypto/factoring.html

[exotic valve]

Thanks! Wanted to update my example to replace GF(169) with GF(23) where 2 generates a subgroup of order 11 fwiw

[leaden swan]

You can't exactly solve the discrete log problem efficiently in the general case

Like there are cryptosystems built around that

[calm pelican]

You could say 2^n = 169x + 8

[abstract quail]

Hi guys
Could someone send me this demo or where I could look at it please.
"how many positive integers have an odd number of positive factors".

[leaden swan]

Infinite

A positive integer has a odd number of factors iff it's a square

Check out the relation between prime factorization and no of factors

After that it becomes really obvious to see that

@abstract quail

https://www.programming9.com/tutorials/competitive-programming/364-check-if-a-number-has-even-or-odd-number-of-factors
If you really want a website

[wheat tinsel]

Given any natural number n there exists a polynomial P such that P(x) is prime for all natural numbers 0<x<n.

Is there something known about this?

Seems true to me

[wild lotus]

Is it required that P has integer coefficients?

[wheat tinsel]

Uhm yes

But I don't see how it would be much different with other coefficients

[wild lotus]

Well you could just take P(x) = (x-1)(x-2)...(x-n) + 2 right

Maybe try distinct primes?

[wheat tinsel]

Uhm yeah true

[inner anchor]

you can just do lagrange interpolation

[wild lotus]

Yeah but then the polynomial won't necessarily have integer coefficients

[wheat tinsel]

Or maybe require it to have as lowest degree as posible

[wild lotus]

Yeah

[wheat tinsel]

I wonder if degree 1 suffices (obviously degree 0 is trivial). It would be something like 2ax+b, where a and b would need to be carefully chosen. I have no idea to be honest

b being odd of course

[modest kestrel]

here i would need to find an element of order 9 in F_37, so they use a primitive root 2 and raise it to the power 37-1 and divide by 9, but why is that?

[sacred junco]

they just constructed an element such that its order is 9

when you raise it to 9th power you get that it is 1

[modest kestrel]

ah yes got it thank you

[leaden swan]

Well if it were m^2 you first need to find a solution using that mod m solution

If m is prime this is easy, otherwise that would be a lot of work

Yea

Well The exact statement is Z_m*n is isomorphic to Z_m X Z_n if m and n are primr

Well anyway you can explicitly construct a bijection (CRT doesn't help you with this,it just tells you this bijection exists)

Let a be inverse of n in mod m and b be inverse of m in mod n,that is
$an=1 \mod m \
bm=1 \mod n$

[sterile pumice]

Drake

[leaden swan]

Then Consider
$p=(xan+ybm) \mod mn\$
Then p satisfies
$\p=x \mod m \
p= y \mod n\$

[sterile pumice]

Drake

[leaden swan]

Because write
P=(mn) q + r where r is the remainder when (xan+ybm) is divided by mn.
This implies
p mod m=r mod m = xan mod m =x mod m

Similarly for mod n

Well TL;DR you can explicitly find a c such that x=c mod pq is equivalent to x=a mod p and x=b mod q

Chinese remainder in the general case is not very powerful compared to over Z

If you are interested,you can do these exercises on CRT

[leaden swan]

No? p=5 and x=3 mod 5 satisfy that

[fluid coyote]

I need help finding all integer solutions to the equation $51x=4\quad \text{mod}, 110$ as well as find those integers $x$ which also solves the equations: $x=7\quad\text{mod}, 13$ and $6x=5\quad\text{mod}, 7$. I know its not supposed to be that difficult but for some reason I'm still having trouble with it. Can anyone help me with this?

[sterile pumice]

Ursus1234

[leaden swan]

so you want to solve
$\51x = 4 \mod 110 \
x = 7 \mod 13 \
6x = 5 \mod 7$?

[sterile pumice]

Drake

[leaden swan]

which is
$\x= 54 \mod 110\
x = 7 \mod 13\
x = 2 \mod 7$

[sterile pumice]

Drake

[leaden swan]

@fluid coyote ?

[fluid coyote]

holy moly, it's been so long since I've worked with this modulus, I've totally forgotten everything.

why is $51x=4$ the same as $x=54$ mod 110?

[sterile pumice]

Ursus1234

[leaden swan]

multiply with inverse of 51

[fluid coyote]

how do I know what that is?

[leaden swan]

I mean is this hw

If not,I would just use python

[fluid coyote]

not homework, just preparation for exercises

[leaden swan]

Algorithmically it's extended euclidean

[fluid coyote]

Im just so frustrated that I couldnt understand so I would get just a little bit better understanding before class exercises

[fluid coyote]

yea, and I've tried to follow an example from the lecture notes, but somehow Im still lost...

[leaden swan]

https://cp-algorithms.com/algebra/extended-euclid-algorithm.html

This is unironically super good

[fluid coyote]

thanks Ill check it out, maybe I just need another explanation

[wanton torrent]

Take n any positive integer

is there any function that gives us all pairs (x,y) such that gcd(x,y,n) = 1

with x,y in Z_n

[leaden swan]

Isn't that easy,Let A be the set of numbers coprime to n in Z_n

Then your set is (Z_n x A) U (A x Z_n)

[wanton torrent]

Is there any already known function that gives us the number of elements?

in that set

like phi(n) is the coprime with n

[leaden swan]

|A| is phi(n)

So it's 2 n phi(n)

[wanton torrent]

nooo, there would be double counting

[leaden swan]

Wait,mb

Yea

I guess isolate into cases and check

Counting won't be hard

[wanton torrent]

and for a big n ? o:

[leaden swan]

This is not quite correct

gcd(x,n) can be >1 and gcd(y,n) can be >1 but gcd(x,y,n) can be 1

[atomic dagger]

Need some one to help me on math on friday will pay 25$ for 32 questions dm plz for Friday

[wanton torrent]

like what

[leaden swan]

n=12

x=2

y=3

[wanton torrent]

yep

[fluid coyote]

I know finally understand. I also made some mistakes in my calculations and that didn't really help either.

[fluid coyote]

so now that I'm here, how can I find the integer solutions for all 3?

[leaden swan]

That seems like a weird conclusion.
If p=7 , 2 satisfies x^2+3=0 mod 7 and x^3=1 mod 7

You can't say anything more if you don't know anything about p
@sacred junco

Maybe you assumed like p is of form 4k+1 or something in class?

Well This should be a correct proof for that

Yea,The if is fine ig

Actually this feels weird compared to just applying Lagrange

With group theory lang ,The if statement is just order of element divides order of group

If x^2+1=0 mod p then x^4=1 mod p ,i.e., ord(x)=4

So 4 divides p-1( order of (Z/pZ)^x) and you are done

So you are telling me you are doing this before lagrange?

No

x^2+1=0 mod p worked nicely because x^4=1 mod p

[leaden swan]

$x^3+3x=0 \mod p \
3x^2+9=0 \mod p\
(x+1)^3=-8 \mod p\$

This could be usedul

[sterile pumice]

Drake

[leaden swan]

-2 is invertible in mod p so this gives you a y such that
y^3=1 mod p

@sacred junco

Your y is $- \frac{x+1}{2}$

[sterile pumice]

Drake

[leaden swan]

np

[sterile pumice]

Kraft Macaroni

Kraft Macaroni

[low yacht]

But I'm not getting 1s as the numerator

instead I have 6s all over the place

[sterile pumice]

Kraft Macaroni

[fervent crest]

Hmm I remember for square roots the continued fraction is periodic so at least you can calculate the continued fraction in finitely many steps

[wooden glen]

Which procedure (or train of thought) are you following that gives you those sixes?

A simple procedure that often suffices is to use a calculator: compute sqrt(22), then alternately subtract the integer part and take the reciprocal. Note down the integer parts you subtract, and continue until you spot a repeating pattern.

Then write down the continued fraction with that pattern, derive the equation for its fixed point. Simplifying it always gives a quadratic equation which ought to have sqrt(22) as its root.

[abstract quail]

What do you guys think of the demo?

[wooden glen]

If x+y=0 then 0=0. I believe that.

(Of course 0=0 tends to be true even on days where x+y is not 0, so perhaps we haven't learned much. But complaining about that would just be ungrateful).

[wheat tinsel]

Would it make sense or would it be interesting to ask for (non-trivial) integer solutions to equations like x^pi+y^pi=z^pi ?

[wooden glen]

It makes sense to ask, but (a) it would surprise me if there are any, (b) even if there is a solution, verifying that a claimed solution works looks like it would be very hard.

[sacred junco]

there is no way there are any solutions

[fervent grove]

sorry I'm a few days late
there is a very efficient algorithm to compute the continued fractions of quadratic irrationals; see S5.1 of https://www.math.canterbury.ac.nz/~j.booher/expos/continued_fractions.pdf

[fervent grove]

also, as an aside: for numbers larger than 22 (which do come "in practice") it does not suffice to use a calculator and take floors of things because calculators use floating point arithmetic, and often the rounding done will make later terms of the continued fraction come out incorrectly (!)

one of the amazing things about the super magic box algorithm (from S5.1 above) is that (after a little practice) it can actually be done by hand at comparable speed or faster than someone with a calculator using the "reciprocal and floor" technique

[crisp escarp]

I wrote a simple CUDA solver in python for this. It doesn't look like there are any integers even close to it, but so far I've only checked the first 10000 or so

[sterile pumice]

Anton.

[west glade]

can you use stuff like fermat/euler?

or do you actually need to calculate 3^341 mod 341 by hand

[wheat tinsel]

341=31*11. Try working mod 31 or mod 11 and use FlT. Numbers get smaller.

[still fox]

showing 3^20 ≠ 1 mod 341 is enough

because the order of 3 mod 341 divides phi(341) = 10*30 = 300, but GCD(300, 340) = 20

of course you have to check that 3^d is not 1 mod 341 for all divisors of 20

so you can take the path: 3^1 -> 3^2 -> 3^4 -> 3^5 -> 3^10 -> 3^20 by squaring and multiplying by 3

i think that's as fast as you can get if you have to do it by hand

[north orbit]

Find all integers k between 1 and 500 such that 2^k + 1 is divisible by 101

given that 2 is a primitive root of 101

So I started with 2^k = 100 (mod101)

k ind(2) = ind(100) (mod100)

k = ind(100) (mod100)

How would I find the index of 100 base 2 by hand?

[west glade]

if 2^x=100=-1 mod 101, then 2^(2x)=1 mod 101. but you know that 2 is a primitive root, so can you use that?

calculating the index is pretty hard in general. there are some algorithms like baby step giant step but nothing easy

[burnt stirrup]

hey

I want to learn number theory for AMC 12

give me tips

[stiff rivet]

you look at the prime ideals in that ring, any of those, say P, will lie over a prime ideal of Z; that is P \cap Z is again prime in Z and therefore generated by a prime number
now the behavior of P depends on how the ring extension looks like: you have Z[sqrt(a)] = Z[x]/(x^2 - a) and by the correspondence theorem, the prime ideals in Z[sqrt(a)] correspond to prime ideals in Z[x] containing x^2 - a
it follows that the prime ideals in Z[sqrt(a)] must contain x^2 - a and a rational prime p, thus contain the ideal (x^2 - a, p)

if now a is a quadratic residue mod p, say b^2 = a mod p, then (x-b, p) and (x+b, p) both contain (x^2 - a, p) (they are in fact maximal)

then we say that the prime p splits

the case you asked about corresponds to a not being a quadratic residue mod p: in this case x^2 - a is irreducible and the ideal (x^2 - a, p) turns out to be prime

there is also the case that p divides a and in this case the ideal (x^2 - a, p) = (x^2, p) is contained in (x, p)

anyways, the short answer is you can tell by looking at the jacobi symbol

this phenomenon is called "splitting of prime ideals" (the first case is called a split prime, the second an inert prime and the third ramified) @sacred junco

[fluid coyote]

Im having trouble with following exercise: Let $p>3$ be a prime and $a$ a primitive root mod $p$. Show that $-a$ is a primitive root iff $p=1$ mod 4

[sterile pumice]

Ursus1234

[fluid coyote]

<@&286206848099549185>

I thought since $a$ is a primitiv root mod p that for a generator $g, a=g^u$ where $u$ and $p-1$ are coprime and then assume the same for -a and use that

[sterile pumice]

Ursus1234

[fluid coyote]

but not sure if that is correct or how else I should go about it

[idle steeple]

This is a very interesting question which spawns a lot of interesting mathematics. It sounds like you want to read into some algebraic number theory. It would take too long to develop the maths to explain everything but p in Z is not prime in Z[i] iff X^2+1 is reducible mod p iff X^2+1 = (X+a)(X-a) for some a mod p iff a^2=-1 is soluble mod p iff p = 1 mod 4, so p factorises iff p = 1 mod 4, and p remains prime iff p = 3 mod 4(you already knew this).

[fluid coyote]

haha, I thought you were gonna respond to my question. I was waiting in anticipation 😅

[idle steeple]

This reasoning works for rings of the form Z[sqrt(d)] where d != 1 mod 4, so you can study X^2-2 and X^2-7 to answer your other examples. You can't answer your question for Z[sqrt(5)] in this way. This is because Z[sqrt(5)] does not have unique factorisation of prime ideals, what you want to study is actually Z[(1+sqrt(5))/2] which are the "integers of Q(sqrt(5))" in some sense that can be made precise

https://zb260.user.srcf.net/notes/II/nf.pdf

Ramification of rational primes (aka finding out whether primes in Z remain primes in more general integer rings) in general is covered by Kummer-Dedekind theorem in chapter 9 of these notes, but this is aimed at third year undergraduates with some algebra under their belt so it might be a bit heavy. You asked an interesting (but difficult to answer) question and I highly recommend reading into this topic, it's one of my favourite courses in undergrad maths

[idle steeple]

Ahh sorry about that, I just happen to be revising this topic hence why I posted a lengthy reply

[inner anchor]

If a is a primitive root, use the multiplicativity of the legendre symbol to conclude that you must have p = 1 mod4

[fluid coyote]

Im not sure I quite know how to use the legendre symbol

[inner anchor]

Do you know eulers criterion for quadratic residues

[fluid coyote]

I know the definition of quadratic residue

but not eulers criterion

[inner anchor]

Then its probably overkill

Lemme try to think of something else

[fluid coyote]

its not in my lecture notes

[inner anchor]

Have you been given any properties of quadratic residues

Or do you just know the defn

[fluid coyote]

oh I missed it. I found eulers criterion

[inner anchor]

Cool

Try to use that then

[fluid coyote]

yea, Ill try. This is the first exercise using that, so maybe I will be back with some more questions...

[inner anchor]

Sure

[keen urchin]

It can be proved using quadratic reciprocity law

[haughty ivy]

i don't see how the problem has to do with quadratic residues

[wooden glen]

Since a is a primitive root, a^((p-1)/2) == -1 (because it is a root of x²-1 that is not 1, and Z/p is a field). So the question is whether -a == a^((p+1)/2) is a primitive root, which it is iff (p+1)/2 is coprime to p-1 ...

(Not sure why the exercise assumes p>3 -- the argument I've started here seems to work perfectly well for p=3 too).

[native monolith]

anyone know what the rules are for arctan of rational and irrational numbers ? or if they exist?

[wooden glen]

This is more #geometry-and-trigonometry. However: the only rational numbers whose arctangents in degrees are rational are -1, 0, and 1.

The arctangent in radians of a nonzero rational is always irrational, and even transcendental according to the Lindemann-Weierstrass theorem.

[native monolith]

alright ty

Is there anything about irrationality when inputted into arctan? @wooden glen

[wooden glen]

Not really. The arctangent of an irrational number may be either rational or irrational.

[native monolith]

Because computing a certain function and proving it's differentiable you can show there exists a $c\in (0,1)$ such that the $\sum_{k=0}^{\infty}\frac{(-1)^k \cdot c^{2k}}{2k+1} = G$ where G is the Catalans constant. But this is just $\frac{arctan(c)}{c}$ and if I could show for each case c rational and c irrational that this produces an irrational number then it would prove G is irrational which I don't think has been done yet

[sterile pumice]

Max..

[native monolith]

thought so

but if for c irrational (which c is more likely to be) it's unknown what arctan(c) will be looks like it's a dead end rip

[torn escarp]

problem with this approach is this has nothing to do with Catalan's constant

what's stopping you from picking any number on the RHS?

[native monolith]

Yeah I was thinking that as soon as you said the original thing

shame but oh well might be another route rather than this cheap routing using a similar technique to lambert

Pretty pointless statement

Someone solved a long standing problem using elliptic curves... pi has been proved irrational using integrals and a simply constructed function

Just because the problem and the technique have been around a long time doesn't mean the solution to the problem isn't using that technique

[torn escarp]

your way of proof could be generalized to show why it is broken in a more severe way

because you don't even know if c is rational or not

for instance f(x)=x would satisfy the same requirements as a special case

obviously there's a c such that f(c)=G

and f maps rationals to rationals and irrationals to irrationals

[native monolith]

The thing is I wasn't looking at general c I was looking at whether if I knew c was rational or irrational would it make proving G irrational simpler, don't think I explained this well.

[torn escarp]

this doesn't prove that G is irrational it just puts us in a position of having some other c which we then need to determine is rational or irrational

[native monolith]

Yes I know that now, that's why I asked if it would help

Because potentially proving the irrationality of c couldve been a more doable activity

Not saying it was lol

I mean pi^2 is proven irrational and it has a similar definition

(To the original definition of G)

You can also define catalans constant in multiple ways using power series, endpoints of functions and integrals

Lots of stuff to be played around with... thanks for your information on arctan @torn escarp 👍

[torn escarp]

you're welcome 😎

[native monolith]

Also probably differential equations and infinite fractions but I haven't looked at these yet in this context so can't say yet

[torn escarp]

expand it out and equate the coefficients on both sides

[west glade]

well in particular it would have a root. just show that it doesn't

[torn escarp]

you can do brute force check that way or use quadratic reciprocity

[west glade]

probably easier to calculate 4 squares than use quadratic reciprocity

[torn escarp]

definitely

[west glade]

2 if you are not counting 0^2 and 1^2

[wanton torrent]

I must show 645 is pseudoprime for base 2

[sterile pumice]

mns

mns

[wanton torrent]

I tried dividing 646 by 336 but it isn't an integer

[rancid aurora]

@wanton torrent u mustve done the prime factorization wrong

when using euler fermat theorem

[wanton torrent]

to calculate phi(645)? It is indeed 336

uh

I didn't understood sorry

[rancid aurora]

this is the best definition for what your proof is supposed to be

when using fermat theorem in this case, you are saying that 645 and 2 are relatively prime (1 is the only common factor) and it can shown using the theorem as a direct proof

in this case the prime number is 2, your base and the other integer is 645, your exponet

then you should get

leaving you with

where x = 2

proving that 645 is a pseudoprime of 2

@wanton torrent

[wanton torrent]

Oh nice yeah

Thanks!!

[rancid aurora]

your gonna have to figure out how to show that 2^154 is congruent to 1 mod 645

[sterile pumice]

CuriousTalon

[leaden swan]

Well in this case yea,All the linear polynomials are distinct.

Because
For (a,b) != (c,d) ,
ax+b=cx+d => there exists (e,f)!= (0,0)
such that ex+f = k(x^2+3),which is not true since gcd(1,5)=1(1 here is coefficient of x^2)

@sacred junco

[fervent crest]

Pi divides (2p_1…p_r) because it’s literally in the product, then if P_i divides two numbers then it also divides their sum

[leaden swan]

To understand this,try finding the number of elements in
$Z_6[x]_{2x^2+1}$

@sacred junco

[sterile pumice]

Drake

[leaden swan]

The answer is ||There are only 9 elements||

[wooden glen]

Huh? Does that subscript notation not mean (Z/<6>)[x]/<2x²+1>?

If it does, then I'd expect there to be infinitely many elements in the quotient, since all x^n would be distinct.

Whoops no, I see.

3(2x^2+1)=3 so it all collapses to mod 3.

[wanton torrent]

Hello

We have $(-1)^{2^{2^n-n}}$. Can we simplify this ugly thing?

[sterile pumice]

mns

[leaden swan]

2^n-n is never 0

So this simplifies to (-1)^(even)=1

[wanton torrent]

yeah I saw that, so it basically is one

all that

[leaden swan]

Yes

[wanton torrent]

Thanks

[pale fjord]

Prove that there exists infinitely many positive integer $n$, satisfies: there exists a positive integer $k$, such that $n<10^k$ and $10^{k}|2^{n}-n $.

[sterile pumice]

erictheeonicpizhao

[wooden glen]

Looking at it modulo 2^k gives 2^k | n. In particular 2^k <= n < 10^k, so it suffices to show that there are infinitely many (n,k) pairs. That means we could also attack it from the "infinitey many k" end.
Beyond that I'm getting nothing, though.

[wooden glen]

The only pairs of (n,k) with k<=5 that satisfy even just 5^k | 2^n-n are: (3 + 20m, 1) and (297 + 2500m, 4) for any m>1 -- but none of these can also satisfy 2^k | 2^n-n.

Wait, that doesn't make sense.

Those are solutions allright, but not the only ones.

(3,1) and (297,4) are the only ones with n < 4·5^(k-1) and k <= 5, but the reasoning that led me to think that bound for n was relevant is rubbish.

I've found these base solutions for 5^k | 2^n-n with k<=4:```
(16,1) (36,2) (236,3) (1236,4)
(17,1) (97,2) (297,3) ( 297,4)
(14,1) (34,2) (434,3) (1434,4)
( 3,1) (83,2) (283,3) (2283,4)

And for each (n,k) we also add any multiple of 4·5^k to n to get more solutions. That ought to be exhaustive.

[supple palm]

do any of those also satisfy 2^k | 2^n - n or is there still nothing on that front

[wooden glen]

Still checking -- I thought I had a CRT argument for that, but it turned out to be bogus.

[supple palm]

this seems like a very interesting problem but i am rather stuck.

i am not entirely convinced that there are infinitely many solutions in the first place.

[wooden glen]

I've yet to convince myself there's even one.

[supple palm]

hah, yeah

[wooden glen]

Oh, wait: (36,2) is a solution.

[supple palm]

oh wow

well there we go

[wooden glen]

(736,3) too.

And (8736,4). This begins to look like a pattern.

[supple palm]

it does, but it is not at all clear to me how to get from one to the next

[wooden glen]

(48736,5)

[supple palm]

i think i have a thought

if you reduce (2^36 - 36)/100 mod 10, you get 7

[wooden glen]

At each step we have (n,k) such that n is a multiple of 2^k (which easily implies 2^k | 2^n-n) and 5^k | 2^n-n.
Suppose we try (n,k+1). That most like won't work, but we can fix it up in two steps:
Let n' = n+j·4·5^k for some j. Then 2^n == 2^n' (mod 5^(k+1)) due to Euler's theorem. So by choosing j appropriately between 0 and 4 we can make 2^n'-n' == 0 (mod 4^(k+1))

[supple palm]

likewise with with 736 you get 8

[wooden glen]

Hmm, that sounds like it may be more promising that the hodgepodge I've thought up, but let me continue the explanation for completeness.

[supple palm]

[wooden glen]

Also 2^n-n mod 5^(k+1) is periodic in n with period 4·5^(k+1), that being the least common multiple of the totient and the modulus. So if we can add some multiple of 4·5^(k+1) to n, we won't lose the match mod 5^(k+1), but can get n to be a multiple fo 2^(k+1).

This is always possible since n' was already a multiple of 4, and 5^(k+1) is invertible modulo 2^(k-1).

So how much do we need to add in total to the n of (n,k) to get one that works with k+1?

At most 4·4·5^k to fix up modulo 5^(k+1), and then less than (2^(k-1)-1)·4·5^(k+1) for fix up modulo 2^(k+1).

The sum of these, divided by 10^k is bounded by 2^(4-k) + 10*(1-2^-(k-1)).

Hmmm, I had hoped that would always be < 9·10^k, but these estimates are not precise enough for that.

At least it looks like heuristically the new n ought to be less than 10^(k+1) most of the times.

Especially since we can start with the intermediate n that worked mod 5^k in the previous step, and that grows asymptotically strictly slower than 10^k.

[wooden glen]

If we can figure out why this seems to work, it will probably be a much nicer argument.

[supple palm]

i think it would be, but i think you have to do some modular arithmetic magic with 2^((2^n - n)/10^k) and im not sure how

(fwiw this also works to get 48736 and the next term, 948736)

so im reasonably confident that im on the right lines

[wooden glen]

Yeah.

Let's see. When k is large enough, 2^n-n mod 10^k is periodic in n with period 10^k -- namely, this period holds both modulo 2^k and modulo 5^k since phi(2^k) and phi(5^k) both happen to be divisors of 10^k.

So adding a multiple of 10^k to n cannot change the lower k digits which we already know are zeroes.

[wooden glen]

Your observation suggests we should try to prove $$2^{n+10^k} - (n+10^k) \equiv (2^n - n) - 10^k \pmod{10^{k+1}}.$$ First, several terms cancel to leave $$2^{n+10^k} \equiv 2^n \pmod{10^{k+1}}.$$ This is obviously true modulo $2^{k+1}$ since $n\gg k$, so we just need to check $$2^n 2^{10^k} \equiv 2^n \pmod{5^{k+1}}.$$ But this is true, since it happens in the \emph{multiplicative} group modulo $5^{k+1}$ whose order is $\varphi(5^{k+1}) = 4\cdot 5^k$ and $10^k$ is a multiple of that as soon as $k\ge 2$.

[sterile pumice]

Troposphere

[wooden glen]

Ah, much nicer!

[supple palm]

this is perhaps my tiredness showing, but where does the first line come from?
in my working i was trying to show that
$$ 2^{n+a} \equiv n + a \mod{10^{k+1}}$$
where
$$ a \equiv 2^n - n \mod{10^{k+1}}$$

[sterile pumice]

twiceshy

[supple palm]

given that
$$ 2^n \equiv n \mod{10^k}$$ of course

[sterile pumice]

twiceshy

[wooden glen]

The first line essentially says "to decrease the last digits of 2^n-n by 100..00, just add 100..00 to n".

[supple palm]

i am perhaps being very silly in my tiredness aha

[supple palm]

right, i follow that

[wooden glen]

We could also write $$2^{n+10^k j} - (n+10^k j) \equiv (2^n - n) - 10^k j \pmod{10^{k+1}}$$ (and then my argument above, mutatis mutandis) to do the correction in one go, where $j$ is the remainder from your observation -- that is, the above equation together with $$ 2^n - n \equiv 10^k j \pmod{10^{k+1}}$$ gives us $$2^{n+10^k j} - (n+10^k j) \equiv 0 \pmod{10^{k+1}}.$$

[sterile pumice]

Troposphere

[supple palm]

ah! there we go.

well, thank you for your hard work here.

i think it's time for me to hit the hay.

[frozen patio]

so i was thinking about the statement "every natural number is written as a unique product of a square and a squarefree number"

is it equivalent to the fundamental theorem of arithmetic?

[frozen patio]

i think it is

[stiff rivet]

both of those statements are just true so im not sure what you mean by equivalent

[wooden glen]

It's easy to prove that from the fundamental theorem of arithmetic, but it's not clear how you would go the other way without essentially proving the fundamental theorem from scratch anyway,

[frozen patio]

well, you can write any product of prime powers as a unique square/ squarefree pair of terms . so two different such products would have different square and or squarefree parts leading to a contradiction

[wooden glen]

Is that suposed to be an argument for the fundamental theorem?

How does it establish, for example, that a square-free number cannot be written as a product of (distinct) primes in two different ways?

[frozen patio]

hmm

so this number would have two factorizations like n = p1 x p2 x pi = p1' x p2' x ... pj'
then we could square it and have
n^2 = p1 x .... pi x p1' x ... pj' . if there are factors unique to each factorization (say p3, p3' and p5'), their product would be a squarefree number. so n^2 = a^2 * (p3,p3',p5'), violating the assumption.

[wooden glen]

Hmm, perhaps you can get through that way.

[frozen patio]

it does sort of feel like begging the question

[frozen patio]

and we could argue that a product of distinct primes is squarefree based on euclid lemma

here's another way to present the argument:
assumption: every number is written as unique product of a squarefree number and a square.

let x be the smallest number with 2 different factorizations: p1^a1 x p2^a2 ... = p1'^a1' x p2'^a2' ....

now write each a using division by 2 and euclid algorithm: p1 ^(2y1 + r1) * p2 (2y2 + r2) * ....
separate the quotients and the remainders to get square and squarefree parts.
p1^2y1 x p2^2y2 .... x p1^r1 x ...

so you get. square1 x squarefree1 = square2 x squarefree2. since these are unique it must be that either square1=square2 has two different factorizations, or squarefree1=squarefree2 does. either way we get a smaller number than x which is a contradiction

[wooden glen]

Unless the square or the squarefree is 1.

[frozen patio]

true

is that a fatal flaw tho

[wooden glen]

Dunno. Whether flaws are fatal or not is a squishy question when we know the conclusion is true anyway,

[frozen patio]

alright. hear me out.
if the squarefree is 1: take the square root of both sides to get the contradiction.

if the square is 1: from euclid lemma we can argue that it again leads to contradiction

[frigid path]

Is there any handout kinda thing for mod $p^k$ where p is a prime.

[sterile pumice]

dEePaNu1729

[frigid path]

especially mentioning the properties of this modulo

<@&268886789983436800> cud u plz change my name to this ದೀಪನು

sorry to ping u guys

[elder bobcat]

sure

[frigid path]

thank you bro

[fluid coyote]

Let $p$ be a prime and assume that $p=1$ (mod 5). How do I show that $(\mathbb{Z}/p\mathbb{Z})^*$ has an element of order 5. I thought any primitive root mod $p$ would have order $\varphi(p)=p-1$ and you couldnt have a higher order mod $p$...

[sterile pumice]

Ursus1234

[leaden swan]

That's a group of order 5p

So there's an element of order 5 by cayley's theorem

[fluid coyote]

if $p=1$ (mod 5) and $c$ is an element of $(\mathbb{Z}/p\mathbb{Z})^*$ with order 5, how can I show that $p, |, (c^{-2}+c^{-1}+1+c+c^2)$?

[sterile pumice]

Ursus1234

[inner anchor]

use the formula for a geometric sum

[fluid coyote]

do you mean something along the lines of $c^{-2}+c^{-1}+1+c+c^2=c^{-2}(1+c+c^2+c^3+c^4)=c^{-2}\cdot \sum_{k=0}^4 c^k=c^{-2}\Big(\frac{1-c^5}{1-c}\Big)$?

[sterile pumice]

Ursus1234

[inner anchor]

yes

what can you say about the fraction now

mod p

[fluid coyote]

ehh I'm, not quite sure. It confuses me that its mod $p$ when $p$ it self is 1 (mod 5)...

[sterile pumice]

Ursus1234

[inner anchor]

that doesnt matter here

c is an element of order 5

what does that mean

[fluid coyote]

ahhhhh

$c^5$ is the neutral element or 1

[sterile pumice]

Ursus1234

[fluid coyote]

do you just get 0 then mod p?

so p divides c^-2+c^-1 and so on

[inner anchor]

yes

[fluid coyote]

well ok then. thank you

[inner anchor]

np

[jolly frigate]

Given that 17x+3y is divisible by 61, prove that 8x+5y is divisible by 61

1 million dollar question

[west glade]

17x+3y=0 mod 61. multiply both sides by 18. then x=7y mod 61. finally 8x+5y=56y+5y=61y=0 mod 61

18 here because it is the multiplicative inverse of 17 mod 61

[jolly frigate]

Tnx

[jolly frigate]

@west glade and where did you get x=7y?

[west glade]

from simplifying after multiplying by 18

x+54y = 0 mod 61

x = -54 y mod 61

x = 7y mod 61

[jolly frigate]

oh 17*18 =1 ?

i see

[west glade]

mod 61

17*18=306=5*61+1

[jolly frigate]

yy i get it tnx

[sacred junco]

can anyone help me?

<@&286206848099549185>

[leaden swan]

Well do by induction

We know 3^{2^1} = 1 mod 4

That's your base caze

Now

$3^{2^n} = 1 \mod 4
\implies
3^{2^{n+1}}=({3^{2^n}})^2\mod 4=1^2 \mod 4 = 1 \mod 4$

[sterile pumice]

Drake

[leaden swan]

So 4 cannot divide that expression

@sacred junco

[sacred junco]

How to have that?

[leaden swan]

Just add 1 and you get that expression will always be 2 mod 4

[sacred junco]

Ah

I get it

tksss

[south sedge]

guys can you tell me what a –= b –= c mod(m) mean ?

[leaden swan]

$a \equiv b \equiv c \mod m$

[sterile pumice]

Drake

[south sedge]

yea what does it mean

[leaden swan]

Means that m divides (b-a) and (b-c) and (c-a)

Simultaneously

[south sedge]

can we tell it as (a-b) , (b-c) and (a-c) ?

[leaden swan]

Same thing

So yes

[south sedge]

ok

thanks man

[sacred junco]

with m,n,p all are integers

[sacred junco]

<@&286206848099549185>

[gentle gate]

What is the symbol with the three dots?

[sacred junco]

divisible

[gentle gate]

that's not the symbol..

|

this is the symbol

it's above the enter key

and below backspace

Anywahs

[sacred junco]

it's mean can be devide to ...

like 8 can be devide to 4

[gentle gate]

I know the meaning, don't worry

[sacred junco]

That symbol use in different case

[gentle gate]

huh?

like the factors?

[sacred junco]

like 4 | 8

[gentle gate]

8 ... 4

I see

[sacred junco]

yeahh

so help me plee

please

[sacred junco]

I came across this notation $[a]_n$. Does this mean a mod n or something else?

[sterile pumice]

Pencil

[karmic notch]

How long of a post is too long of a post here? Asking for a me. lol

Essentially I have an idea that occurred to me when I was reading a book and was wondering if this was the right place to post that idea/questions/observations

But when I wrote out everything I wanted to a text editor, it ended up being a bit long winded... I'm wondering if I should post this somewhere else, if I should segment the messages into smaller chunks, or just post the entirety of it all at once...

The post in question is about number theory, so, I figured I'd ask here

This would be the first time I try to post one of my ideas for evaluation by other math peeps, so I'm a bit nervous I think.

[stiff rivet]

you can post it but longer post will probably lead to less people reading it

might be worth considering to post on math stackexchange instead

[karmic notch]

Gotcha, I'll do that then, I can then post the link here once it's available. Thanks for the suggestion @stiff rivet

[karmic notch]

"Should 0 be considered a perfect number?": https://math.stackexchange.com/questions/4462895/should-0-be-considered-a-perfect-number

I'm interested in hearing people's thoughts on this.

[sacred junco]

I agree with JMoravitz; letting 0 be a perfect number or not does not change any results, so it is not significant enough to really get people to care.

[torn escarp]

sure let's say 0 is, then -1 is the corresponding mersenne prime

🤣

[leaden swan]

Actually nvm it doesn't work that eay

[torn escarp]

I was thinking more in terms of the 2-adics and pretend $\lim_{p \to \infty} 2^{p-1}(2^p-1) = 0*(-1)$ and then going to the formula $\lim_{p \to \infty} \sigma(2^p) = 1+2+2^2+\cdots = \frac{1}{1-2} = -1$ with $\lim_{p \to \infty} \sigma(2^p-1) = \sigma(-1) = 1+(-1) = 0$ (because it's prime duh... lmao)

[sterile pumice]

Merosity

[torn escarp]

therefore $\sigma(0) = \sigma(0*(-1))=-10=20$ lmfao

[sterile pumice]

Merosity

[torn escarp]

I once read in a book that conway argued -1 should be prime, so obviously this is just that totally legitimate thing yes

[sacred junco]

Like why would -1 being prime help though

[torn escarp]

it wouldn't, this is a giant shitpost pretending to argue -1 is a mersenne prime lol

[sacred junco]

Stoopid

[karmic notch]

I never actually made that claim, instead I asked to relax the restriction that the power we use be a prime to show that it would still fit the overall form of the even perfect numbers.

I never mentioned the mersenne primes in the entirety of that post, the only time I mentioned primes at all was to outline the above relaxing of restriction.

[karmic notch]

Never made this claim either...

[karmic notch]

Never made this claim either...

[torn escarp]

it's true, I made all the claims lol

[karmic notch]

Yeah, I only realized a short while ago that the shitpost you were referring to in one of your later posts was your series of posts, and not necessarily mine... I'm new to the community, so I hadn't expected someone to go to great mathematical lengths for the purposes of a joke, lol

[torn escarp]

haha it's all good 🤣

sorry for the confusion

[abstract quail]

guys, help with this exercise please
If ∅ is considered as a relation of A in A, is it reflexive? is it symmetric?
is it antisymmetric?
is it transitive?

I know it is reflexive because emptiness is related to itself, emptiness.
symmetrical it cannot be because it cannot be related to any other element besides itself.

[leaden swan]

Is A an empty set?

[abstract quail]

we will call A as an empty set

(?)

so it says (spanis), sry

[leaden swan]

The definitions are $\$
1)Reflexive:\ $(\forall a) a \in A \implies aRa\$
2)Symmetric:\ $ (\forall a,b)aRb \implies bRa\$
3)Antisymmetric:$\ (\forall a,b)aRb \land bRa \implies a=b\$
4)Transitive: $\(\forall a,b,c) aRb \land bRc \implies aRc$

[sterile pumice]

Drake

[leaden swan]

So The null relation is vacuously symmetric, Antisymmetric and transitive

Reflexive if A is null set

[abstract quail]

ye

[abstract quail]

I understand a little of the definitions
but I don't understand your abstract thinking
about it

[abstract quail]

look https://foro.rinconmatematico.com/index.php?topic=51067.0

[fluid coyote]

Im having a difficult time understanding this example
how do they establish the 3rd equality?

[inner anchor]

quadratic reciprocity probably

[fluid coyote]

yea, I think I found out why since $541=83\cdot 6+43$

[sterile pumice]

Ursus1234

[fluid coyote]

can I maybe ask you another question about this quadratic reciprocity?

if $p$ is a prime and $p=1$ (mod 5) why is it that from quadratic reciprocity that $\bigg(\frac{5}{p}\bigg)=1$?

[sterile pumice]

Ursus1234

[fluid coyote]

I get $\bigg(\frac{5}{p}\bigg)=(-1)^{(5-1)(p-1)/4}\cdot\bigg(\frac{p}{5}\bigg)=1\cdot\bigg(\frac{p}{5}\bigg)$

[sterile pumice]

Ursus1234

[fluid coyote]

how is that 1?

[inner anchor]

what is (p/5)

i.e. is p a quadratic residue modulo 5

[fluid coyote]

no how can it be that if p is a prime

[inner anchor]

what is the definition of a quadratic residue

[fluid coyote]

an integer a is quadratic residue mod p if there exists y such y^2=a (mod p)

a can not be 0

[inner anchor]

yes

so is there a integer x such that x^2 = p mod 5

note that p = 1 mod 5

[fluid coyote]

I was thinking that 9^2=81=1 mod 5

but 81 is not prime...

[inner anchor]

why do you care for the primeness of the number

[fluid coyote]

because p is a prime

im probably confusing myself an going off track...

[inner anchor]

you are

look at your definition again

lets put in our numbers into it

an integer p is a quadratic residue mod 5 if there exists y such that y^2 = p mod 5

so the only thing that matters is what p is mod 5

[fluid coyote]

so would this be a reason why p is quadratic residue?

[inner anchor]

yes

[fluid coyote]

but why does it then say in the problem that p is a prime

when does that come into play?

[inner anchor]

in using quadratic reciprocity

also the legendre symbol is only defined for prime moduli

[fluid coyote]

hmm yea okay

so this is till true $\bigg(\frac{5}{p}\bigg)=(-1)^{(5-1)(p-1)/4}\cdot\bigg(\frac{p}{5}\bigg)=1\cdot\bigg(\frac{p}{5}\bigg)$

[sterile pumice]

Ursus1234

[fluid coyote]

and then since $\bigg(\frac{p}{5}\bigg)$ is quadratic residue so is $\bigg(\frac{5}{p}\bigg)$?

[sterile pumice]

Ursus1234

[inner anchor]

yes

[fluid coyote]

thank you

[inner anchor]

np

[abstract quail]

$\text{Show that is a relation R defined on A}\
\text{(a) It is symmetric in A if and only if }R=R^{-1}\
\text{(b) It is antisymmetric if and only if } R\cap R^{-1}\subseteq \bigtriangleup_{A}$

[sterile pumice]

Aylou-210

[abstract quail]

Hi guys, could someone help me with this exercise?

$\text{We know that R is symmetric in }A \left( \left(\forall x \right) ,y\in A \right)\left( xRy \longrightarrow yRx \right)\
\text{Then we have to }R=R^{-1}$

[sterile pumice]

Aylou-210

[opal linden]

Is there a generalization for sum of the individual digits of the product of any number and 9 is 9 for any number besides 9?

[torn escarp]

do you mean how when you have a number written in base 10, it's divisible by 9 when its sum of digits is divisible by 9?

this type of trick will work for numbers written in base b and looking at its sum of digits to test for divisibilty by b-1

[opal linden]

Yhea

[opal linden]

Is there a theorem or something for this?

Are there any other modular behaviors besides just b - 1?

[torn escarp]

basically the proof is just writing out the number in base b and reducing mod b-1

$$\sum_{k=0}^n d_kb^k \equiv \sum_{k=0}^n d_k \pmod{b-1}$$ since $b=1 \mod b-1$

[sterile pumice]

Merosity

[jaunty cape]

Can you simplify the calculation of the modular inverse of a modular inverse of a modular inverse .. and so on?

So basically a simplified way to calculate n = n^-1 % p multiple times in a row

[leaden swan]

Why would you do that multiple times in a row

Extended Euclidean is good enough if you want speed
@jaunty cape

[jaunty cape]

I've been given a task to simplify this

I figured out that x ** k % y = x ** k + 1 % y - 1 , but not sure how that helps me

[fervent crest]

The inverse of the inverse is the original number...

[jaunty cape]

oh... i just noticed, thanks

[silver oak]

sorry

[somber lagoon]

?

It’s fine post here, that is from number theory

[silver oak]

i know, just getting agitated

[somber lagoon]

I see

[silver oak]

@somber lagoon i don't understand

like, how do you know it has 8 elements, that's circular

if it has 8, then yeah, you map remainders to actual numbers

oh you said injective, so you still can

no, that's not what injective means

this "set of equivalence classes" has 2^n elements or less, and we're trying to prove it has 2^n, am i wrong?

[somber lagoon]

No

I constructed a map from

Z/(2^N)Z to ({number of length N in 10-adic made up with 0,1}+Z)/(2^N)Z

Mapping the equivalence class of Σa_k 2^k to equivalence class of Σa_k 10^k

Where a_j are all 0 or 1

This is well defined and injective

And clearly is surjective

[somber lagoon]

We know Z/mZ has m elements, we are not proving it we know it already

[silver oak]

ok, it's not something easy but obfuscated, got it

[robust dirge]

Hi, I posted something in the math help channels, which got no replies in four hours; the thread has long been closed since. The question seems related to Diophantine approximations. Am I allowed to post it here?

[stiff rivet]

yes

[robust dirge]

Denote $\text{frac}(x)$ where $x \in \mathbb{R}^+$ to output the fractional part of $x$; in other words, $\text{frac}(x) = x - \lfloor x \rfloor$. Prove that $\inf{n \in \mathbb{N}^+ : \sqrt{3}n,\text{frac}\left(\sqrt{3}n\right)} = 1$

[sterile pumice]

_gmz

[formal minnow]

does anyone have any advice for proving things relating to lcm and gcd? i really suck at it and i want to be able to handle all the abstract algebra stuff that depends on lcm and gcd

[torn escarp]

I guess the main things to know and understand are the euclidean algorithm, extended euclidean algorithm, and gcd(a,b)lcm(a,b)=ab at least for starters

maybe if you have some examples of problems in particular you could show, that might help give an idea what you mean better

[main ermine]

could someone help me understand 2. ?

i don’t really understand what the equivalence classes in Z/nZ are

could someone help me understand i know that the equivalence classes of $a \in \mathbb{Z}$with respect to congruence modulo n is the element $\bar{a} \in \mathbb{Z}/n \mathbb{Z}$

[sterile pumice]

sean

[main ermine]

but then the equivalence classes of Z/nZ

i don’t even know what equivalence relation it’s talking about on Z/nZ

[leaden swan]

The equivalence relation is
$\aRb \iff a \equiv b \mod n$

[sterile pumice]

Drake

[leaden swan]

@main ermine

[leaden swan]

Well Z/nZ actually means the set of equivalence classes of Z under that equivalence

Each element in Z/nZ is an equivalence class

[main ermine]

yeah i figured it out

one more question, how is this division in modular arithmetic defined?

could someone lead me to a proof of it or smth?

i'm not really sure where that comes from

[leaden swan]

#precalculus

[formal minnow]

it’s not here

e divides a and b, therefore a/e and b/e are integers

gcd(n,e) divides n by definition, so n/gcd(n,e) is an integer

[full crescent]

how do those implications arise?

[torn escarp]

chinese remainder theorem

[full crescent]

ohh caues 2 and p are coprime

tyty

[torn escarp]

yup yw 😎

[full crescent]

wait im still confuesd

sry

like for the 4th implication

how would i go about finding the inverse?

nvm

[scarlet geode]

all my homies hate fermat

[patent escarp]

well I guess ill take another crack at asking a problem here. I want to find all nontrivial integers x, y, and z (not x=y, 2x=y, or an integer multiple of an existing solution) such that $\sqrt{\left(2xy\left(x-y\right)\right)^{2}+\left(z^{2}\left(2x-y\right)\right)^{2}}$ is an integer. This is not an easy problem in the slightest as nothing I do to it has made it budge. I do have a life of a lot of solutions (found through brute force) so I know they exist, I just don't know the fastest way to find them.

[sterile pumice]

Chixen

[patent escarp]

forgot to also add that trivial includes x, y, or z being zero. Positive integers only too.

a few examples include (1,4,3), (1,3,4), (1,7,4), (1,15,7), and for a big one: (99,77,36)

(18,25,35) is the best solution I've found so far because for what I'm using it for it's the only one that has fully worked.

[patent escarp]

Still wanting help with this

[patent escarp]

This problem is equivalent to finding rational points on the 3d quartic curve $\left(2xy\left(x-y\right)\right)^{2}+\left(z^{2}\left(2x-y\right)\right)^{2}-1=0$

[sterile pumice]

Chixen

[haughty coral]

I think I may have found a similar but better approximation for gauss’s prime counting function

Gauss’s approximation is

$\frac{x}{\log(x)}$

[sterile pumice]

Adeline

[haughty coral]

Mine is $\frac{\frac{x}{\log(x)}}{1.95}$

[sterile pumice]

Adeline

[haughty coral]

I haven’t proven anything all I know is it might be a better approximation

I’ve tested up to 300 and it looks promising

[inner anchor]

Its worse

It might be alright for small x but it will be worse for sufficiently large x

[fervent grove]

amusingly, if I remember correctly x/(-1+log x) has a better error term than x/log x

[patent escarp]

I would still like some help with my stuff

Well if you scale every variable in the expression by $a$ you get $a^{3}\sqrt{\left(2xy\left(x-y\right)\right)^{2}+\left(x^{2}\left(2x-y\right)\right)^{2}}$

[sterile pumice]

Chixen

[patent escarp]

so not every integer solution scales nicely to a rational solution on a 3d curve

or in other words not every integer evaluation to the expression has a rational (x,y,z) (assuming there isn't one for every evaluation already)

but every rational solution on the 3d quartic curve $\left(2xy\left(x-y\right)\right)^{2}+\left(z^{2}\left(2x-y\right)\right)^{2}=1$ does map nicely to an integer solution to $\sqrt{\left(2xy\left(x-y\right)\right)^{2}+\left(x^{2}\left(2x-y\right)\right)^{2}}$.

[sterile pumice]

Chixen

[patent escarp]

I guess I could then solve for z and try to find rational sultions to that

Right?

Given that $\left(x,y,z\right)$ is a rational solution to $\left(2xy\left(x-y\right)\right)^{2}+\left(z^{2}\left(2x-y\right)\right)^{2}=1$ and $a$ is a common denominator of x, y, and z, $\sqrt{\left(2\left(ax\right)\left(ay\right)\left(\left(ax\right)-\left(ay\right)\right)\right)^{2}+\left(\left(az\right)^{2}\left(2\left(ax\right)-\left(ay\right)\right)\right)^{2}}$ will be an integer.

[sterile pumice]

Chixen

Chixen

[patent escarp]

I gotta test this out

I guess it could help find counterexamples but wouldn't help in proving the conjecture if it is true.

Now the problem is just rational solutions to $\sqrt[4]{\frac{1-\left(2xy\left(x-y\right)\right)^{2}}{\left(2x-y\right)^{2}}}$

[sterile pumice]

Chixen

[patent escarp]

I'm getting somewhere

[pine cave]

so my abstract algebra textbook had a very interesting problem (it's relevant to cyclic groups), that at a glance looked very difficult until i thought about it for a minute and realized how trivially easy it was: "compute the last digit of 1238237^18238456".

so inspired by this i went about doing some fucking around with general examples of this problem, and i discovered some interesting theorems, and i have a relevant interesting conjecture i don't yet know how to prove or disprove, though i am sure i'll learn how eventually

the conjecture is "consider higher order iterations of exponentiation x^[z]y (e.g. tetration x^[2]y, pentation x^[3]y) in bases p. the possible rightmost (i.e. smallest) digit of the full expansions of x^[z]y for any natural x z and natural y > 1 exhausts all available digits in base p if and only if p is prime."

i don't really have any motive for sharing this other than i thought it was a fun thing to think about and thought other people might think so too

[desert sonnet]

can u elaborate on wut u mean by "consider higher order iterations of exponetiantion"

cuz even with the examples i still don't really get wut u are saying

[pine cave]

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

x^[z]y here represents x^[z-1]x^[z-1]....x with y copies of x

[hollow slate]

Woke up today thinking about this problem:

Take any integer, i.e 57

now half it, taking the integer part if odd and repeat until reaching 1.

This clearly takes roughly log_2(n) steps, but will be slightly faster because of odd numbers - this will more strongly affect at small numbers because -1/2 is more significant to its binary logarithm.

This would mean that the offset averaged over all n should converge as the effect diminishes (probably exponentially too?)

The question: what is the value and form of this offset?
something like log_2(n) - k?

idk if it fits in number theory per se, but i dont really know where else it'd go :3

[leaden swan]

Wdym roughly it's always $\floor{\log_2{n}}$

[sterile pumice]

Drake

[leaden swan]

@hollow slate

So you want something like
$\lim_{n->\infty} \frac{\log_2{n}-\floor{\log_2{n}}}{n}?$

[sterile pumice]

Drake

[torn escarp]

I don't think I understand the algorithm, are you doing floor(x/2) at every step of the way? I guess I don't get what you mean by offset or what would be faster

[hollow slate]

tbh this is what happens when I'm not properly awake yet lol. Yeah I'm doing the floor each step. I guess what I was attempting to get at was that the powers of 2 all take log_2(n) steps exactly but the rest need the floor - so what would be needed to create a smooth function? (one that passes through the middle of the steps rather than grazing the steps as with log_2(n))

[hollow slate]

you're absolutely right, but what would it be without the floor?

[wooden glen]

What are you trying to achieve here?

$\log_2(n)-\frac12$ will approximate your function with the smallest \emph{absolute} error, but I'm not sure that is what you're going for ...

[sterile pumice]

Troposphere

[torn escarp]

I am kind of interpretting it as asking how many times you'll have to floor when dividing by 2 on average

[hollow slate]

yeah this is what I'm looking for

https://www.desmos.com/calculator/uhfiiqsuv0

[wheat prairie]

Can someome point me to a proof of the following fact: If $n\vert l$ such that $n<l$ and $\varphi(n)=\varphi(l)$, then $n$ is odd and $l=2n$, where $\varphi$ is the euler function

[sterile pumice]

ShiN

[fervent crest]

I think you can prove it by writing down a prime factorization of n and l

Yeah so write $l=np_1^{r_1}\cdots p_k^{r_k}q_1^{i_1}\cdots q_j^{i_j}$, where $p_i,q_i$ are primes and $p_i$ are in the prime factorization of $n$ and $q_i$'s are not. Then \begin{align*}
\varphi(l)&=\varphi(np_1^{r_1}\cdots p_k^{r_k})\varphi(q_1^{i_1}\cdots q_j^{i_j})\
&=np_1^{r_1}\cdots p_k^{r_k}\prod_{p|n}\br{1-\frac1p}q_1^{i_1}\cdots q_j^{i_j}\br{1-\frac1{q_1}}\cdots\br{1-\frac1{q_j}}\
&=\varphi(n)p_1^{r_1}\cdots p_k^{r_k}q_1^{i_1}\cdots q_j^{i_j}\br{1-\frac1{q_1}}\cdots\br{1-\frac1{q_j}}
\end{align*}
So by canceling $\varphi(n),\varphi(l)$ on both sides we get $1=p_1^{r_1}\cdots p_k^{r_k}q_1^{i_1}\cdots q_j^{i_j}\br{1-\frac1{q_1}}\cdots\br{1-\frac1{q_j}}$ or $q_1\cdots q_j=p_1^{r_1}\cdots p_k^{r_k}q_1^{i_1}\cdots q_j^{i_j}\br{q_1-1}\cdots\br{q_j-1}$ and so $p_i$'s don't exist and $q_i$ must be 2 and $j=1$ and $i_1=1$ so $l=2n$ where $2$ doesn't appear in the prime factorization of $n$

[sterile pumice]

Whoever

[fervent crest]

@wheat prairie

[wheat prairie]

I see

thank you!

[torn escarp]

I like whoever's proof cause it's clear what's happening but wanted to try to see for fun if I could prove it without writing out all the prime factors here's what I came up with

[sterile pumice]

Merosity

[rough field]

@sudden spoke the unicity you asked about a2ⁿ and so on is easily provable with induction. If you want help, ask in a help channel and ping me

[tender cedar]

I wrote a proof but I'm not sure if it's correct.
Goal: prove that ideal $I \subset a\mathbb{Z}$, where $a$ is the smallest positive integer in $I$.

Take any $b \in I$. Since $I$ is closed under integer multiplication we know that $ba \in I$.

We also know that $gcd(b,a) = gcd(ba,a) = a$. So $b=an$ for some $n \in \mathbb{Z} \implies b \in a\mathbb{Z}$

[sterile pumice]

sam

[tender cedar]

I suppose it's that last step, gcd(b,a) = gcd(ba, a) that im not sure is correct

seems really iffy

[west glade]

It's wrong. 1=gcd(3,2) but gcd(6,2)=2

You'll have to use division with remainder for your proof

[tender cedar]

oh yeah I mixed up two propositions

[wheat tinsel]

Does "the sum of the positive integers not exceeding n" mean 1+...+(n-1) or 1+...+n ?

I suppose its the first one but I have no idea how to do it

[leaden swan]

Latter

If n+1 is prime , the product will not have a factor of (n+1) and hence is not divisible by the sum which does have a factor of (n+1)

If n+1 is composite ,well you can just factorise and match with those terms in the product

Ergo n(n+1) divides the product implies n(n+1)/2 divides the product

[wheat tinsel]

Is there a non tedious way to prove that n^2-81n+1681 is prime for all n=0,...,80 ?

simply using elementary tools

[west glade]

well you can write it as t^2+t+41 to t=n-41. then you have to show that t^2+t+41 is prime for t=-40,...,39 of which you can find some proofs online. whether you count them as elementary, dunno

[wheat tinsel]

Oh thats nice

Well the most elementary thing is to see whats the maximum value, say n, and then we only have to worry about primes less than sqrt n

But thats tedous

[tender cedar]

Can someone give me a light hint for the following proof: Show that every integer on the form 4n+3 has a prime factor of the same form.

[strange grail]

Suppose all of the prime factor of that number is 4k+1 form so ...

[tender cedar]

This is using the fact that all primes are either 4k+1 or 4k+3 then yeah?

[strange grail]

Yes

[tender cedar]

I havent proven that one yet

Ill start there then

[grave carbon]

How would I find an integer, where $13^n + n^{13}$ is a prime number?

[sterile pumice]

beeswax

[grave carbon]

I saw this on Twitter, and I thought it would be fun to recall some number theory stuff from a year ago

[robust dirge]

I believe there are none

[grave carbon]

Why is that?

I was thinking it is unlikely, but idk why

[robust dirge]

Firstly, notice n must be even, since 13 > 2

and 1 isn't a prime

[grave carbon]

Wait, why does 13>2 imply n is even?

[robust dirge]

Next, consider mod (n + 1): let n = 2k (since it's even), and so 13^(2k) + (-1)^13 (mod n + 1) ≡ (13^k + 1)(13^k - 1) (mod n + 1)

Hold on I thought I had a solution that didn't require Fermat's little theorem

[robust dirge]

13^n + n^{13} > 2, so in order for it to be prime it must be odd

[grave carbon]

And for that to be odd, n needs to be even?

[inner anchor]

Im not sure how the statement follows

9 doesnt divide 13^8 + 8^13

[robust dirge]

if n + 1 is prime we're done, by FLiT

[inner anchor]

If n+1 is prime then your idea works yeah

[robust dirge]

3 does though

but yes, not exactly great

[inner anchor]

If it isnt prime then you should just be able to look at some prime factor of n+1

[grave carbon]

Are we still trying to prove that there exists no such integer n?

[wooden glen]

Wait, just because the number factors modulo n+1 doesn't mean it's actually composite. Am I missing some implication of this?

[misty nova]

PLEASE, READ THE ENTIRE QUESTION. I've asked this on the help channels and no one was able to help me

I'm writing a short paper where I analytically prove a few theorems of elementary arithmetic about the divisibility relation n | m \↔️ ∃p(m = np), prior to introducing division with remainder and/or its related algorithms, as a proof of concept for a friend. right now I'm trying to prove a lemma of Euclid's lemma, to in turn prove the uniqueness part of the fundamental theorem of arithmetic

the lemma is that, given nonzero integers m,n,p,q where p,q are coprime and mq = np (i.e. m/n = p/q), there is an integer k such that m = pk and n = qk* (i.e. m,n are multiples of p,q by the same integer). I know that, if q | n, then the theorem follows (because then n = qk for some k, in which case mq = pkq, and so m = pk and p | m, and conversely), so in turn I just have to prove that q | n (or p | m), but I don't know where do I even begin

so far I've proven that divisibility is a pre-order over the nonzero integers having 1 as a minimal element over the positive integers, that every composite number is a product of primes (though not the uniqueness of this product, of course), and that the integers resulting from the division of m,n by their gcd are coprime (i.e. that if m,n are nonzero, and if m = gcd(m, n)p and n = gcd(m, n)q, then gcd(p, q) = 1)

[runic token]

m = pk and n = qp
?

[misty nova]

n = qk*

thanks for pointing that out

[runic token]

i think you are overthinking this

we have $\frac{m}{n} = \frac{p}{q}, m,n > p,q$. it then naturally follows that we have an integer k due to this: $\frac{m}{n} = \frac{p}{q} \cdot \frac{k}{k}$.

[sterile pumice]

valley

[runic token]

or, well, i am 99% sure that works

[misty nova]

as I've said in the statement of the question above, I'm trying to prove this and other theorems prior to introducing division, from the definition of the divisibility relation alone

this is trivial if you consider fraction multiplication, but I'm not considering fractions in the first place

[runic token]

omg i forgot fractional multiplication was division

fuck me

lmfao

could you use that because q is a factor of np, and p and q are coprime, q must be a factor of n

i think this works from what you have and doesn't require division

[misty nova]

that's Euclid's lemma

again, as I've already said in the question above, I'm trying to prove this theorem as a lemma to Euclid's lemma

I'm sorry for pointing that out so harshly, but about 5 people across 2 different servers and 2 different social media platforms have "answered" me in the exact same way, appealing to Euclid's lemma in some way or another

and I've made sure to point out I've already ruled out this proof in the statement of my question, every single time

[runic token]

nw

do you have bezout's identity?

[misty nova]

not without the division with remainder algorithm

[runic token]

hmmmmm

[misty nova]

I've already stated above what I have proved so far as well

• divisibility is a pre-order over nonzero integers having 1 as a minimal element over the positive integers
• every composite number has a least non-trivial factor which is prime, as well as a (possibly not unique) prime factorisation
• given nonzero integers m,n having d as a gcd, if there are p,q such that m = pd and n = qd, then p,q are coprime

[runic token]

i thought i had a funny induction proof but i still need division to finish it

damn

and every other one i can think of is circular

oh wait

i think i have one

[misty nova]

👀

[runic token]

okay so i didn't wanna give you another wrong proof so i went over it again and it uses something i think you don't have :/ damnnn i rly thought i had something here

i might just look this up this is painful

[misty nova]

it's fine as long as it doesn't appeal to the division with remainder algorithm or anything that presupposes it, or to a theorem I'm already trying to prove (i.e. Euclid's lemma or the uniqueness of prime factorisation)

[runic token]

it uses euclid's algorithim

specifically a = bc + r

[misty nova]

yeah, that won't work

[runic token]

i went looking on the internet and i found a really fucking nice proof

and i think it works for you

uhhh do you want it? or would you prefer hints to figuring it out

[misty nova]

I also searched for a proof of this theorem or anything similar to it, and I found nothing

so I'd like to see the proof you found, if it isn't one I've seen already

[runic token]

Call a triple (p,a,b) of positive integers "bad" if p is prime and p∣ab, but p∤a and p∤b.

Suppose that a bad triple exists. Among all bad triples, consider those in which p is minimal. Among all such triples, choose one in which a is minimal.

Note that a<p, since otherwise (p,a−p,b) would also be bad, violating the minimality of a. Also, a>1, since otherwise p would divide ab=b.

Let q be the smallest divisor of a such that q>1. (Notice that a is such a divisor, so q exists.) Clearly q is prime, since otherwise it would have a divisor r with 1<r<q and then r would be a smaller divisor of a.

Let a=qt. Since p∣ab, pc=ab=qtb for some positive integer c.

We now consider two cases:

1. If q∣c, so c=sq for some positive integer s, then ps=tb.

Since t∣a, p∤t; so (p,t,b) is bad, violating the minimality of a.

2. If q∤c, then (q,p,c) is bad, violating the minimality of p.

In either case, we have a contradiction. Hence there are no bad triples.
i think this one works

not 100% sure

[misty nova]

this works!

and it can be simplified, I think

[runic token]

originally due to someone called "dean thompson" :)

[misty nova]

if m,n,p,q are as in the statement of the lemma, then p | m is equivalent to q | n (for p | m means m = pk, and since mq = np, then np = qpk, so n = qk, and thus q | n) and p | m implies the theorem, so assume that p,q are the least integers as in the lemma such that ¬(p | m). first, p | mq since mq = np. second, q < p since otherwise p,q - p would be the least such integers. and third, either q | n, in which case p | m, contradicting ¬(p | m), or ¬(q | n), in which case q,p would be least such integers, contradicting q < p. thus no such p,q exist

there's no need to invoke q's least non-trivial factor

that's kinda brilliant

thank you very much @runic token

[runic token]

you're welcome!

sorry for all the false proofs and mishaps

and yeah this proof is absolutely beautiful

[grave carbon]

An interesting problem I saw online: are there finitely many primes p, such that there exists an n where the following is prime:

n^p + p^n

[runic token]

i bet this is either open and on the level of goldbach's or incredibly easy and simple

[sturdy violet]

Well, its almost like Goldbach, adding 2 non-primes to get a prime

[smoky finch]

Anyone that knows how to solve this problem for integers?

I'm really stuck

[sturdy violet]

Ok so I might not finish this or at least answer later, but z could have something to do with -2 or 2

Because if ya expand the sum of those fractions you can work this out

So if z = ±2, we get 0 = z²(2y + 3x)

So 2y + 3x = 0, or 2y = -3x. Can't happen within the integers

[gentle summit]

can someone help with this? I am having a hard time to prove (1) and (2)

[smoky finch]

I got sort of the same

z > 2 or z<-2

So far I know that z²>=9, x²>=4, y²>=4

[smoky finch]

If I could determine an upper bound I could exhaustively check all the answers

[buoyant mason]

this will not be the most helpful answer ever but here is a really lazy upper bound on $x$ that still takes some work lol. I'm gonna consider $x,y, z$ to be positive integers since that doesn't really change the problem at all, other than the final answer. Let $x > 100$. Now we'll show there are no solutions for any $y\geq 2$.
\begin{enumerate}
\item Let $y=2$. Since $0<\frac{2}{x^2}<\frac{1}{5000}$, we can show that $\frac{3}{4}+\frac{4}{z^2}\geq 1$ or $\frac{3}{4}+\frac{4}{z^2}\leq \frac{4999}{5000}$ for all $z$. It's simple algebra to verify that $\frac{3}{4}+\frac{4}{z^2}\geq 1$ when $z=3$ or $z=4$, and that $\frac{3}{4}+\frac{4}{z^2}<\frac{4999}{5000}$ when $z=5$ and hence when $z\geq 5$ (by monotonicity stuff if ya know what I mean)
\item Let $y=3$. With $z=3$, $\frac{3}{9}+\frac{4}{9}<\frac{4999}{5000}$, and a similar inequality holds for any $z > 3$
\item If $y>3$, then the same inequality as above holds for any $z\geq 3$, which is good news
\end{enumerate}

100 is a really bad bound but you can pick something smaller and it should work

I was lazy and wanted to be sure it would work

you should be able to bound y and z in a similar way with cases

[sterile pumice]

Spring

[buoyant mason]

I thiiiink that's typo free now, but let me know if anything looks off

[smoky finch]

I think I get it

[wanton torrent]

Hey guys

there's a theorem that goes as follows: 2 is a quadratic residue for all primes of the form 8k - 1

so, for k = 6, it follows that x^2 = 2 mod 47 has two solutions

How can I find them?

(clearly 7*7 = 49 = 2 mod 47) but I wonder if there's another way without knowing this

thanks

[buoyant mason]

I think you can find them easily if you know a primitive root of the prime

oh uh actually I misread that as 8k + 1

[wanton torrent]

it also works for 8k + 1

2 is a quadratic residue for primes of the form 8k + 1 and 8k - 1 and is not a residue for 8k +3 and 8k + 5

[buoyant mason]

hm ok I'm not sure about the 8k - 1 case

[wanton torrent]

hum so how would you find x in x^2 = 2 mod 49

[wooden glen]

Even if you know a primitive root, you'd have to find a discrete logarithm of 2, which is a challenge of its own.

[wanton torrent]

how is this related with primite roots?

primitive

[wooden glen]

If g is a primitive root and you know that 2 == g^n, then n will be even and g^(n/2) is one of the square roots. But finding n can in itself be hard.

[wanton torrent]

hum interesting

[buoyant mason]

actually it's not hard when $p$ is of form $8k+1$. If $r$ is a primitive root of $p$, then the two solutions to $x^ 2\equiv 2\pmod{p}$ are $x=\pm (r^{7(p-1)/8}+r^{(p-1)/8})\text{ mod } p$

[sacred junco]

apparently there's an (fast?) algorithm for square roots modulo a prime https://en.wikipedia.org/wiki/Cipolla's_algorithm

[sterile pumice]

Spring

[wooden glen]

Ah, because g^((p-1)/2) = -1 and the a² and b² parts of the square cancel out. Nice.

[buoyant mason]

yep

not sure about the 8k-1 case though 😬

[fathom pumice]

Gauss's lemma application

For all primes of the form 8k-1, n is even

To prove it, it's just brute force algebra

[fervent grove]

your prime is 3 (mod 4), so you can just use 2^((p+1)/4)

this is efficient to compute by modular exponentiation by repeated squarings

for 1 (mod 4) primes, I think taking modular square roots is a little harder
I am under the impression that "in practice" one uses an algorithm like https://en.wikipedia.org/wiki/Tonelli–Shanks_algorithm

[sacred portal]

What exactly does this mean? Here we should perhaps mention yet another fact which is initially somewhat surprising.
Namely, in the prime numbers sequence $p1, p2,\ldots $, gaps between prime numbers can have an
individually determined length n. It is undeniable that under the n succession of natural numbers
$(n + 1)! + 2, \ldots ,(n + 1)! + (n + 1)$,
none of them is a prime number since in order, the numbers $2, 3, \ldots ,(n + 1)$ are comprised
respectively as real divisors. (n! means the product of the first n natural numbers therefore
$n! = n ∗ (n − 1) ∗ \ldots ∗ 2 ∗ 1)$.

[sterile pumice]

SXK

[buoyant mason]

maybe an example would help. Something it says is (letting n = 5) that 6! +2, 6! + 3, 6! + 4, 6! + 5, and 6! + 6 are all composite

because 2 divides 6! + 2, 3 divides 6! + 3, etc

[sacred portal]

Okay I get it now, thanks

[wanton torrent]

Yeah that’s on the next chapter

Thank you all!

[mossy sun]

yeah tonelli shanks mod prime and then hensel lifting and crt for other integers

so invoke tonelli shanks to find the set of all residues mod 7 which have x^2 = 2

then mod 7^2, any answer y will be of the form 7k+x for a residue x from before and an integer k. this is easily solvable

if you had more prime factors you need to use chinese remainder theorem on the answers to get candidates

[fervent grove]

(in practice, there are more efficient ways to do this Hensel lifting; if interested, search the keywords "Newton's method" and "Hensel lifting" together)

[patent escarp]

I have an interesting problem that if solved could seriously help on an unsolved problem in number theory. The problem is simply finding integer solutions to $\left(2xy\left(x-y\right)\right)^{2}+\left(z^{2}\left(2x-y\right)\right)^{2}=n^{2}$. I know that solutions exist and it's likely that there are infinitely many solutions as I've written a program to brute force some. Any methods I could apply to this? I've tried the obvious stuff and it doesn't work.

[runic token]

$\sqrt{\left(2xy\left(x-y\right)\right)^{2}+\left(z^{2}\left(2x-y\right)\right)^{2}}=n^{2}$

texit down?

[patent escarp]

i guess

[sterile pumice]

valley

[patent escarp]

whoops

mistyped

not that

I'll copy and fix

I have an interesting problem that if solved could seriously help on an unsolved problem in number theory. The problem is simply finding integer solutions to $\left(2xy\left(x-y\right)\right)^{2}+\left(z^{2}\left(2x-y\right)\right)^{2}=n^{2}$. I know that solutions exist and it's likely that there are infinitely many solutions as I've written a program to brute force some. Any methods I could apply to this? I've tried the obvious stuff and it doesn't work.

[sterile pumice]

Chixen

[patent escarp]

$\left(2xy\left(x-y\right)\right)^{2}+\left(z^{2}\left(2x-y\right)\right)^{2}=n^{2}$

[sterile pumice]

Chixen

[patent escarp]

I mean even some way to speed up computation time would help

[runic token]

if there are solutions then there are infinitely many of them

[patent escarp]

I know

[runic token]

since this is essentially a pythagorean triplet

[patent escarp]

yeah I know

[runic token]

what solutions do you have so far?

[patent escarp]

A lot

I look up to 100 for each one

This is just for gcf(x,y,z)=1 and the triplets are the (x,y,z) pairs.

also I removed any x=y, 2x=y, x=0, y=0, or z=0.

I didn't show the n values as they're trivial to find once you have (x,y,z)

[runic token]

you can multiply x and z by two to get a new solution i think

[patent escarp]

I know

[runic token]

so you already have infinite solutions?

and a method to find all of em?

[torn escarp]

what's the goal, proving there are infinitely many or just computing them or what

[patent escarp]

you can multiply the three values by and constant $a$ and $n$ by $a^{3}$ to get new solutions

[sterile pumice]

Chixen

[patent escarp]

computing them

[runic token]

you can compute a thousand solutions in a few seconds

if you have just one base solution

[patent escarp]

yes but I know if (x,y,z) doesn't work for what im using it for I'll know (ax,ay,az) also won't work

[torn escarp]

i don't get it, what's the point of computing them faster

[patent escarp]

to find more

[torn escarp]

why do you want more

[runic token]

what are you using it for

[patent escarp]

I found a way to transform solutions to this equation to near-miss magic square of squares.

magic squares where 6/9 values are perfect squaers

[runic token]

which unsolved problem are you trying to solve

[patent escarp]

The magic square of squares problem

at least for 7/9.

So far only one solution to this equation I've found works for 7/9 but the rest give 6/9

[torn escarp]

so by computing more of these, the more likely you are to find an example, makes sense

[patent escarp]

yeah

because the first example is so small

[torn escarp]

I'd try to write your formula in terms of pythagorean triples if I were you

[patent escarp]

I tried that already and I couldn't get anywhere

[torn escarp]

then work out what conditions that places

yeah I guess that's why you're coming here, I'll try later and see if I can find something maybe

[runic token]

have you tried factoring it into a complex form and seeing what that does?

adding i always helps, probably

[patent escarp]

How do you do that?

[runic token]

$a^2 + b^2 = (a+bi)(a-bi)$

[sterile pumice]

valley

[patent escarp]

huh ill try that

[runic token]

and maybe this lets you apply complex anal tools?

no idea

give it a shot tho

[patent escarp]

yeah I dont know where to go from here

given any rational solution you can easily get an integer solution. maybe I try something with that

I mean I already did but maybe you can try

ok an idea to get it to rationals

divide all variables by z

well I've simplified it

Given any rational solution $\left(x,y,n\right)$ to $\left(2xy\left(x-y\right)\right)^{2}+\left(2x-y\right)^{2}=n^{2}$, $\left(za,zy,z^{3}n\right)$ is an integer solution to the original curve. (where z is a common denominator of $\left(x,y,n\right)$)

[sterile pumice]

Chixen

[patent escarp]

and now it's a 3d curve

still quartic tho

let me test this

[runic token]

have you considered graphing the original curve in 3d btw

[patent escarp]

yes

actually a long time ago when asking this someone else did

ill find the message

#elementary-number-theory message

[runic token]

hm

actually a really neat lookin thing