elementary-number-theory

[buoyant mason]

so can’t be equal to 2036

helps a little bit…

[prisma folio]

Does this follow from x^2 + y^2 + z^2 = 0 mod 4?

[buoyant mason]

yea

[prisma folio]

What if x^2 = 2 mod 4 and y^2 = 2 mod 4?

And z^2 = 0 mod 4

[buoyant mason]

0 and 1 are the only squares mod 4

[prisma folio]

Ah

[buoyant mason]

0^2 = 0
1^2 = 1
2^2 = 0
3^2 = 1

[prisma folio]

Ok, so x^2, y^2 and z^2 need to be 0 mod 4

Meaning x, y, z need to be even

[buoyant mason]

so put another way x y and z are even

yea

[prisma folio]

Yeah

Ok now for each of x, y, z instead of 89 possibilities we have 45

Still a lot

[prisma folio]

Perhaps we can do some more modding so we can reduce the possibilities?

[buoyant mason]

it’s more like half of that btw

if you just solve it over the nonnegative integers the ones with negative numbers can be made from those

if (x,y,z) is a solution so is (-x,y,z) and (-x,y,-z) and such

and vice versa

[prisma folio]

Really? Somehow this doesn't feel right when looking at x + y + z = 78

[buoyant mason]

o

[prisma folio]

The squaring we did was just in the => direction

[buoyant mason]

i forgot the original question was not to solve x^2 + y^2 + z^2 = 2036 lol

i think what i said is still ok though?

[prisma folio]

This?

[buoyant mason]

like if we just want to find all solutions x^2 + y^2 + z^2 = 2036

yea

they won’t all be solutions to the original system

[buoyant mason]

but still ok to just look at this over the nonnegative integers

[prisma folio]

True, the solution set will be a superset of the one we're after (after also including (-x, y, z) and so on from (x, y, z))

So 23 possibilities for each of x, y, z

[buoyant mason]

not sure of a way to do it other than brute force :(
you could take cases on one variable (say x) and then check if y^2 + z^2 = 2036 - x^2 has any solutions with that theorem that tells you when a number is representable by a sum of two squares but idk how efficient that would even be

and when there is a solution(s) idk a good way to find but there is probably a way

[prisma folio]

Well atleast it's reduced down to 23 possibilities, thanks! Perhaps there isn't a way other than brute-forcing, since no general formula for diophantine equations exists

[wet vale]

there is a way to do this very quickly

[buoyant mason]

ya but sums of squares are well studied

[prisma folio]

What is it?

[buoyant mason]

snow

[wet vale]

by Vieta's, if
[ x + y + z = 78, \quad xy + yz + zx = 2024, \quad xyz = d, ]
then $x$, $y$, $z$ must be the integer roots of the polynomial
[ X^3 + 78X^2 + 2024X + d ]

[wet vale]

making the substitution $X = Y - 26$, you arrive at
[ Y^3 - 4Y - 17472 + d = Y(Y - 2)(Y + 2) - 17472 + d = 0 ]

oh i used Z in my working

oops

[wet vale]

quick inspection of Z(Z - 2)(Z + 2) tells you that in order for the cubic to even have 3 real roots, you require 17472 - d to be between -3 and 3

thats finitely many cases to check

[prisma folio]

How?

[wet vale]

i meant -x, -y, -z here obviously

,w graph y = x^3 - 4x

[sterile pumice]

Results provided by WolframAlpha

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

Requested by tearfox

[wet vale]

the cubic has turning points at 3 + a bit

[prisma folio]

Ah

[wet vale]

anyway 17472 - d must be divisible by 3

so that leaves you with 17472 - d = 0, 3, -3

[prisma folio]

Wait, why 3 + a bit? It's at -1 - a bit and 1 + a bit, no?

[wet vale]

i meant the y-coordinate in that graph

[prisma folio]

Ah

[wet vale]

the x-coordinate is quite irrelevant

[prisma folio]

Ok, so yeah, makes sense, 17472 - d needs to be between -3 and 3 because of that

[prisma folio]

Why?

[wet vale]

because Y(Y - 2)(Y + 2) is

[prisma folio]

Ah

[wet vale]

although i hope its visually obvious that d = 17472 is the only option

[prisma folio]

Yep

[prisma folio]

This is because we want integer solutions, right?

[wet vale]

yes

[prisma folio]

Ok, so d = 17472 and now Y(Y-2)(Y+2) = 0, so Y = 0, Y = 2 and Y = -2

X = Y + 26 and so X = 26, 28, 24

And then we get Z from x + y + z = 78

[prisma folio]

Thank you!

[wet vale]

no uh

X and Y are not x and y

[prisma folio]

Oh, X is from the polynomial

[wet vale]

the roots of Y(Y - 2)(Y + 2) = X^3 + 78X^2 + 2024X are -x, -y, -z

[prisma folio]

Ah

[prisma folio]

so x = -26, y = -28, z = -24

[wet vale]

thats the wrong way

Y = -2, 0, 2
X = Y - 26 = -24, -26, -28

[prisma folio]

Yeah

Those are the roots of the polynomial

[wet vale]

oh thats

thonk

i messed up the signs

so the roots are -24, -26, -28

and so x, y, z are 24, 26, 28

[prisma folio]

Ah

[prisma folio]

But (24, 26, 28) is not the only triple that solves this

,w x + y + z = 78, xy + yz + xz = 2024 solve for integer

[sterile pumice]

Results provided by WolframAlpha

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

Requested by kepe_5235

[prisma folio]

Ah

[wet vale]

i mean

theres no specific ordering

you can permute the roots

[prisma folio]

True, thanks a lot!

[prisma folio]

How did you think of substituting X = Y - 26, btw?

[wet vale]

its just centralising the cubic

[sacred junco]

hi, can you have negative factors of a number?

like for 25, -5 and 5 could both be factors of 25 right? I'm guessing the "regular idea" of factors exist on Z?

so is (-5) = 5 like do we treat this as the same over a certain ring?

sorry i mightnot have the perfect description here cuz i haven't done any ring theory

[west glade]

-5 and 5 are so-called associate elements. you have -5=(-1)*5 and -1 is a so-called unit in the ring Z

which means that there exists an integer k with (-1)*k=1 (so k=-1)

in Z this is still relatively uninteresting cause you only have +-k, but in other rings more things can be associate to each other

[sacred junco]

so wait would you call them "negative factors" over Z then?

considering they're the same to an extent (lack of my precise vocab ig)

cuz each positive factor has its "negative factor" as its associate element

i'm just curious cuz how do you respond to a "total number of factors" question for example

[west glade]

generally you only care about positive factors

because negative factors just dont add anything meaningful

[sacred junco]

so going back to a perhaps trivial question

the total number of factors of 2^3 * 3^2 is 12 right?

instead of 24

[sacred junco]

because i've seen a solution manual which said 24 but like yeah i agree with this so i was confused why they did that

[west glade]

well it will always depend on who you ask

for these types of problems I would only consider positive factors but in the context of a ring theory class I might include all of them

[sacred junco]

cool, thanks

[west glade]

but then you would also often just say one of each set of associate elements

[sacred junco]

yeah i see a stackexchange response

and they say (5) = (-5) over a ring ig

so technically it'd still be 12 right?

if u consider each as one

but yeah okay i guess it depends on context

[west glade]

the () is special notation which means ideal

[sacred junco]

no idea what that is tbh

[west glade]

it doesnt itself say anything about 5 and -5 being equal

they both generate a set (the set of all multiples of 5)

[sacred junco]

ohh

[west glade]

and in ring theory these types of sets are important

and because they both generate the same one, it often makes no difference whether you look at 5 or -5

cause actually you are interested in the set

[sacred junco]

so wait then if they both generate the same elements

cuz both sets would have all multiples of 5

since we allow negative multiples

then why is negative multiples a thing then?

even there it'd be positive integers based on what we just mentioned right?

[west glade]

well a multiple of 5 is a number of the form 5*k where k is an integer. it doesnt say anything about k having to be positive or negative

these additional restrictions wouldnt make sense over other rings

and it would also make other stuff just way less nice tbh

[sacred junco]

I see, let me think about this

and if i have any questions i migth get back

Thanks for now

[keen pagoda]

is the group of all numbers relatively prime to a less than a under multiplication isomorphic to the cyclic group of order phi(a)?

[still flare]

Usually not.

[keen pagoda]

that's sad

[torn escarp]

you might look into the carmichael function a bit

[keen pagoda]

also, is that thing that a² = 1 modb implying a = +- 1 modb also valid for b relatively prime to a or only b prime?

[keen pagoda]

ty

[keen pagoda]

ok probably not

damn it

[visual pewter]

I came up with this proof but can't finish because i can't prove c is a prime.. is there a way to do so or my proof is wrong..

Please ping me if you can help

[coral venture]

It is the right path

As a hint let a=7^7^k

Then c = (a^7+1)/(a+1)

[visual pewter]

Im sorry but i can't get how this implies c is never a prime );

I tried binomial but its not working too..

[coral venture]

it doesn't directly you have to do a lot of algebra

it's kinda a dumb problem

https://artofproblemsolving.com/wiki/index.php/2007_USAMO_Problems/Problem_5

here is a full solution

[keen pagoda]

uh weird question but is there a general way of knowing if the sum of two squares is a sum of three squares?

like a general classification like there is for pythagorean triples

[visual pewter]

I tried completing the square, difference of squares, modulo reduction but none of them worked..the best i got was that if a²+b²=x²+y²+z² then $$ x=2x_0 \vee 3x_0 \vee 4x_0 \vee 5x_0 \wedge y=2y_0 \vee... $$ and same with z.. which just increases the efficiency in hit and trial.. doesn't really help in generating a general way of solving it..

[sterile pumice]

ideal_37

[visual pewter]

Hey can anyone see though them once...

Ask me if you don't get the writting.. i can write it once more(with clear handwriting) if its not readable..

[patent acorn]

,rccw

[visual pewter]

and yeah q=2 does not change anything..

If the proof is correct then part 2 and 3 should follow form case 1 and 2 respectively...

[visual pewter]

i.e. the new $S_1 \wedge S_2$ are not changed..

[sterile pumice]

ideal_37

[visual pewter]

Ping me if you got something

[keen pagoda]

what does the wedge do?

anyways I think I got a handle on the specific problem I was trying to solve cus I got a very restrictive inequality

I'm actually in a bit of negation rn cus I'm thinking "damn that's so obvious, why would that problem be considered hard?" after spending days to find this idea out

[sterile pumice]

Adam

[visual pewter]

$ \wedge $ is used for "and"
$ \vee $ for "or"

[keen pagoda]

Oh it's just the logical operator

Thought it was like an advanced operation

[gilded breach]

This is about how the number of steps can be reduced in Euclid's algorithm by taking $|r_{k+1}| < r_{k}/2$

[sterile pumice]

Autumn

[gilded breach]

In the example they showed

12378 = 4.3054 + 162

3054 = 19.162 - 24

162 = 7.24 - 6,
24 = (-4)(-6)

I did it this way:
12378 = 4.3054 + 162
3054 = 162.9 + (-24)
162 = (-24).(-7) + (-6)
-24 = (-6).4 + 0

I was wondering why did they take 24 as a divisor instead of -24? Is there a rule to divide only the positive form of the remainder? And so they took it as a divisor? In the last step they take (-6) as a divisor instead of 6. I don't know when to take the positive or the negative

[west glade]

well they got 7, you got -7 as the quotient. so the signs just cancel anyway

often its just easier to think about positive numbers

[last tundra]

Given $p,q,r,s$ integers such that $ps-rq \neq 0$ how do you count the number of solutions of
\begin{align}
z_1^p = z_2^r \
z_1^q = z_2^s
\end{align}
for $z_1,z_2$ complex numbers in the unit circle?

[sterile pumice]

jfab

[last tundra]

Ok I reduced the problem to
finding the number of solutions $(x,y)$ of residues $\bmod ps-rq$ such that
\begin{align*}
px &\equiv ry \bmod ps-rq \
qx &\equiv sy \bmod ps-rq
\end{align*}
Could someone help me with this :(

[sterile pumice]

jfab

[torn escarp]

we're assuming pq,r,s are all integers?

[last tundra]

yes

sorry

[torn escarp]

raise (1) to the q power and you can make it in terms of just one variable by using (2). Then since it's nonzero divide through and you get (z_2)^{ps-rq}=1 and since it's algebraically closed you'd have to have exactly ps-rq solutions

hopefully I'm not being too reckless on that, I'm preoccupied atm but ping me if you have any questions

[last tundra]

raise to the q power or multiply by q

[torn escarp]

raise to the power

[last tundra]

which equation are you talking about

oh I get it

[last tundra]

no but wait

you get the two conditions

that $z_1,z_2$ are $ps-rq$ roots of unity

[sterile pumice]

jfab

[torn escarp]

yeah I see what you mean

[last tundra]

how do you conclude that $z_1$ is completely determined by $z_2$ is what I'm saying

[sterile pumice]

jfab

[last tundra]

what I did

[torn escarp]

I'm too busy at the moment but in a few hours I might be free

[last tundra]

was expressed $z_1$ and $z_2$ as $ps-qr$ roots of unity

[sterile pumice]

jfab

[last tundra]

and I transformed the problem

into this

[last tundra]

this

finding the number of solutions $(x,y)$ mod $ps-rq$ such that the system is satisfied

[sterile pumice]

jfab

[last tundra]

I'm pretty sure it works so I just have to count the number of solutions but I have no idea how. I noticed that the solutions form a subgroup but nothing else

so in particular the number of solutions must divide $(ps-rq)^2$. That's all I got

[sterile pumice]

jfab

[last tundra]

yeah no worries, thanks btw!

[torn escarp]

also when you say on the unit circle, you mean of finite order? might be possible to sneak in infinitely many solutions

[last tundra]

mm what? I don't think so for example if p=3 , s=1 , q=r=0 you solve for z_1^3 = 1 and z_2 = 1 so you have 3 solutions

in general you might have infinite solutions if p,q,r,s are not integers no? but if they are integers since we saw that they have to be roots of unity

then you have at most finitely many pairs to choose from

[torn escarp]

good point

[fading void]

Can someone help me following this last part?

I'm not quite sure what fact is being used...

[coral venture]

(n-1) choose (k-1) is an integer and gcd(n,k)=1, so when you multiply n/k on it and it remains an integer, that means the 1/k factor must have been "absorbed" by (n-1) choose (k-1), and so the n remains unscathed

[fading void]

Ahh that's a really nice way of putting it

[sacred junco]

I need help with number theory. I'm trying to figure out how to prove Law of Quadratic Reciprocity by assuming the truth of the following conjecture:

But I can't tell if the part of the question (not shown) that tells me to prove quadratic reciprocity might actually be a typo, and instead wants me to prove this conjecture using the law of quadratic reciprocity. Does anyone know if it is possible to prove the Law of Quadratic Reciprocity from the above conjecture alone + Legendre symbol manipulation? Thanks.

And if anyone has suggestions for how to proceed in this proof, that'd be great

Actually I might have figured this one out...let's see will delete this if so

[loud moon]

let f be a polynomial with integer coefficients in k variables such that only single-variable terms have a nonzero coefficient, for example x^2 + 3x, 2x^3 - y^2, but for example NOT x^2 + xy.

I've noticed that I can find reducible polynomials of this form for k =1 (obviously) and k = 2 (such as a difference of squares, and some other identities), but I've been completely unable to find any such polynomial for k > 2, I tried a limited brute force search and all of the polynomials I tried were irreducible.

is there some easy argument to show that none exist? rewriting it as a system of diophantine equations, heuristically it seems improbable that one would exist but perhaps there is some crazy counterexample

[loud maple]

Is there any particular reason why you're working with integer coefficients here?

[loud moon]

I want to be able to study these polynomials modulo an integer

[torn escarp]

interesting question, I feel like there should be a nice answer to this

you probably already know this, but without loss of generality you can use rational coefficients without causing issues, since you can always multiply through to make integers

[loud maple]

We're basically quotienting by the ideal generated by the set of all pairwise products of variables here right?

[torn escarp]

are we?

[loud maple]

This just came to mind lol, and I'm too sleep deprived to verify whether this is right myself

[torn escarp]

maybe, idk I'm about to head to bed soon too lol

[loud maple]

Lmao

[loud maple]

I found a relevant paper

1102706460.pdf

[loud moon]

nice find! that seems to answer exactly my question if I'm reading it right, there are no counterexamples. pretty cool

[slim parrot]

I had a doubt in one of the statements made here.
For reference, by the formula of $a^{m}$, they mean
$$a^m = p_{1}^{me_1}p_{2}^{me_2}\dots p_{k}^{me_k}$$
which is basically prime-power factorisation of a raised to the power m.

Here in the proof, they say that the product $a_1a_2\dots a_r$ is an mth power, which implies this product equals some $t^m$ ryt? and then as t has its prime power factorisation, each prime in t will have its exponent divisible by m, and so any $a_i$ will have some of those prime $p_i$ with the complete exponents of the $p_i$ 's with it.

The thing is that in the proof, they took the product $a_1a_2\dots a_r$ as a, they did say that a is an $m^{th}$ power but taking it as just a caused confusion earlier, here too they mean that a is some $t^m$ ryt?

[sterile pumice]

NightBaron

[blazing canyon]

Good day. How can I solve simultaneous congruences if the moduli are not relatively prime?

[coral venture]

prime factorize the moduli

[hot cipher]

how to proof that 2 groups are not isomorph?

like

the four group of klein and Z_4

(im to lazy to make the cayley table)

[patent acorn]

generally what you do to prove any two things aren't isomorphic is find a property that one has and the other doesn't

in the case of groups of order 4, one of them has an element of order 4 and the other doesn't

[hot cipher]

what are properties i could use for this apart from the orders of elements?

abelic would work i guess and uh what else?

[patent acorn]

well obviously there's the order of the entire group

but also like, any property, like you can look at properties of normal subgroups or something, or the size of the centre of the group, or...

[hot cipher]

alrighty

can ou tell me what the group $S^1$ is?

[sterile pumice]

you_are_me

[patent acorn]

...not without further context

[hot cipher]

let me take a picture

Here

for the permutation group we use a different notation so it isnt that one

[patent acorn]

...ah i see, it's the circle

so ${z \in \mathbb{C} : |z| = 1}$

[sterile pumice]

bee [it/its]

[patent acorn]

with the operation of multiplication

[hot cipher]

alright thanks big man

[hot cipher]

yo ok so there is a vague explanation of an inverse of a rest class in a certain ring

$[2]{2001}$ has as inverse $[1001]{2001}$ right? cuz $[2x1001]{2001}=[1]{2001}$

or am i completely misunderstanding this?

[sterile pumice]

you_are_me

[hot cipher]

the x is a multiplication sign

[patent acorn]

$[2 \cdot 1001]{2001} = [1]{2001}$

but yes

[sterile pumice]

bee [it/its]

[hot cipher]

oh ye i forgot how to get the dot lol thanks for telling me that too

[hot cipher]

how do you calculate $3^{302} mod 101$?

[sterile pumice]

you_are_me

[hot cipher]

there are like lots of theorems here but i dont understand

like wtf is the euler function and stuff

idk im so confused

[hot cipher]

ye no

still dont get it time to move on

if anyone knows then ping me

[still flare]

You should read Euler's theorem and come back to this question. In general it's a good idea to look at the content surrounding a question if you don't know how to tackle it.

[spare frigate]

hi, i need a reference for introductory nonlinear diophantines

any pdfs or lecture notes?

[quiet epoch]

Square and multiply would be a nice way. Split up the powers and reduce mod 101 on the way

————————————
„Determine a primitive root mod 17 and use it to find all solutions to x^4 === 1 mod 17.“

I got a primitive root 3 of 17 but I don't know how this should help me with this congruemce..😅

[weary rune]

if $a$ has order $k$ mod $n,$ then $a^h$ has order $\dfrac{k}{\gcd(h,k)}$

[sterile pumice]

elrichardo1337

[weary rune]

you know your primitive root has order 16, how can we finish?

[quiet epoch]

Maybe split up the ^16 into two ^4's?

[weary rune]

if $x^4\equiv 1\pmod{17}$ what can you say about the order of x?

[sterile pumice]

elrichardo1337

[weary rune]

||it's 1, 2, or 4||

then use the above fact to finish

[tawdry bramble]

You can write this as
\begin{align*}3^{302} \pmod{101} &\equiv 3^{100} \cdot 3^{100} \cdot 3^{100} \cdot 3^2 \pmod{101}\
&\equiv 3^{100}\pmod{101} \cdot 3^{100}\pmod{101} \cdot 3^{100}\pmod{101} \cdot 3^2\pmod{101}\end{align*}
From Fermat's little theorem you know that $3^{100} \pmod{101}$ is just $1$, while $3^2 \pmod{101}$ is 9, you get
$$1 \cdot 1 \cdot 1 \cdot 9 \equiv 9 \pmod{101}$$

[sterile pumice]

Rubix

[quiet epoch]

max val for order would be 4?

so order <= 4

[quiet epoch]

But how does the order contribute finding the concrete x's?

[quiet epoch]

and where does this formula come from?

[weary rune]

check any standard number theory text

I used Burton for my NT class

[weary rune]

incorrect, the order of x must divide 4

so the order of x is 1, 2, or 4

[quiet epoch]

Okey

[weary rune]

we can now proceed by casework

clearly if the order is 1

then x is 1

[weary rune]

or, using this result, we need gcd(h,16)=16, which obviously only occurs when h=16

(we take a to be our primitive root, 3)

if the order is 2, then we need gcd(h,16)=8

that is, h=8 and x=3^8=-1=15 mod 16

if the order is 4, then gcd(h,16)=4, so h=4 or h=12

and x=3^4 or x=3^12

that is, we have expressed all the solutions in terms of one primitive root

[quiet epoch]

So those 3 would be the only possible values for x, as their order divides 4?

ord(3^4)=4
ord(3^8)=2
ord(3^16)=1

[weary rune]

you dropped 3^12

so that’s four solutions total

[fading void]

hi this might be trivial, but can someone explain how this shows that (p - 1) | (n - 1)

we know n is carmichael and that p | n

[quiet epoch]

Ah i se.. but how should I come to check ^12 in particular? Is it just trying out until i got 4 solutions?

[weary rune]

I showed the method above, read back

[quiet epoch]

yes, but it's just some brute-forcing for the different powers of 3?

[weary rune]

no

[weary rune]

for small moduli like 17 this casework approach doesn't take long at all

[quiet epoch]

One last question 😅 : why do I know, that for powers of one primitive root I already get one solution?

I could search for another primitive root and do the same.. couldnt I?

Or is it, because this polynomial can only have exactly 4 solutions?

[weary rune]

you can take any primitive root and generate all the solutions

fundamentally it's bc of how the orders work

[quiet epoch]

huh

[coral venture]

This is partially true

It has at most 4 solutions

[quiet epoch]

so as soon as i got 4.. i can stop

[coral venture]

https://en.m.wikipedia.org/wiki/Lagrange's_theorem_(number_theory)

[quiet epoch]

it's just about finding 4

[coral venture]

Yes

[hot cipher]

Wait, is every element of $Z^X_{13},\cdot$ a generator?

[sterile pumice]

you_are_me

[hot cipher]

nvm i made a big oopsie

[still flare]

In general, a cyclic group has this property (that every nontrivial element is a generator) iff it has prime order or order 1. Noting the group of units mod 13 has 12 elements, this is impossible. In fact the only primes for which this works are 2 and 3.

[cunning shadow]

Does it not have 13?

or is this a different group than I'm thinking of?

[west glade]

you are thinking of Z_13. but Z_13^x is the group of units mod 13, which has 12 elements

[sterile pumice]

bjshnog

[foggy aspen]

I just found 2+2 guys!

[sacred junco]

Ideally, this would be in english and this goes in #linear-algebra anyway

[light prawn]

ζ(−k) = −Bk+1/k + 1
is this true

[torn escarp]

https://en.wikipedia.org/wiki/Riemann_zeta_function#Specific_values @light prawn

[light prawn]

doesn't contain a proof

[torn escarp]

that's a different question than this

[light prawn]

im extending the question

[torn escarp]

you'll have to learn some calculus and google a bit to find a suitable resource probably

[light prawn]

bruh you sure only calculus will suffice

[torn escarp]

I've walked through a proof of it myself

[light prawn]

mind posting?

[torn escarp]

idk, some analytic number theory book

[light prawn]

dang

[hot cipher]

What do they mean by S*S

S is a sub group of G,*

[west glade]

{s*t: s, t in S}

[hot cipher]

thanks

[hot cipher]

Let $p_1,...,p_n$ be all different uneven prime numbers and let $a=p_1 \cdot ... \cdot p_n$. Proof that for every $b \in Z$ with greatest common denominator of $a$ and $b$ equal to 1 the equation:
$$x^2= b ; \text{mod} ; a$$
Always has 0 or $2^n$ solutions in ${ 0,...,a-1 }$

[sterile pumice]

you_are_me

[hot cipher]

they use chinese remainder theorem which i understand

and then they say so we just have to proof that every equation has 2 solutions

and then we get 2^n solutions

but i dont understand that argument

OOOH WAIT I GET IT I THINK

nope i still dont get it

[coral venture]

what don't you get?

[hot cipher]

so i have to proof that the equation x²=b mod a has 2^n solutions or zero but im stuck on the 2^n part so like i got until the system using the chinese remainder theorem and then they say now it is enough to proof that each of these equations has 2 solution and thats where they lost me

[coral venture]

suppose we know that each of those equations has 2 solutions

[hot cipher]

i dont get it like if one of those equations has 2 solutions then that doesnt mean that that solution is of the original equation right?

[hot cipher]

they do i get how they proof that i dont get how tha fact that each equation having 2 solutions will result in 2^n solutions

[coral venture]

then for each of the equations we can pick one solution
each possible way of picking the n solutions gives rise to a system of congruences that has exactly 1 solution (by crt)
there are 2^n possible ways to pick the n solutions, hence 2^n solutions

[hot cipher]

huh but you pick an x?

and then try to find a solution of that system?

but x is supposed to be a solution to everything?

im soooo confused

[coral venture]

we pick the x (mod p_i)

[hot cipher]

still dont get it

this is the rest of the solution btw

i give up imma do something else

[quiet epoch]

Can someone help me with Solovay-Strassen test?
I computed the first term mod 31 but I don't know how to calculate JAcobi symbol (2/31) wouldn't i need to know that 31 is prime to use anything of the quadratic reciprocity law?

[hot cipher]

what does this notation mean?

K is a subgroup of G

[fleet bone]

basically any solution (a_1 mod p_1,a_2 mod p_2,...a_n mod p_n) that satisfies that is going to satisfy x^2=b as well this holds in converse direction as well

2 ways to choose each a_i

standard high school combi says 2^i ways to set (a_1 mod p_1,a_2 mod p_2,....,a_n mod p_n)

[charred roost]

I don't understand how this is a complete proof. It's not enough to show that each congruence has two solutions, you must also show that each solution mod p_i gives rise to a different solution mod a. For example, take p_1 = 5, p_2 = 7 and b = 4; then x = 2 is a solution both mod 5 and mod 7, but somehow they give rise to different solutions mod 35

[charred roost]

nvm, I got it

[hot cipher]

how do you solve this?

i used chinese remainder theorem

now im stuck

[charred roost]

How exactly did you use it? And where are you stuck?

[wicked mountain]

.

[slate juniper]

yooo the last two digits of 76^n always seem to be 76

is this true? how does one prove this?

[coral venture]

Notice 76^2 = 76 (mod 100) and it follows from induction

[slate juniper]

oohhh damn! nice

[unkempt void]

By the same reasoning this occurs for all a with a^2 = a, called idempotents, and since Z/100 = Z/4 x ZA/25 and neither of these rings has any nontrivial idempotents, the idempotents of Z/100 are precisely stuff which is 1 or 0 mod 25 and 1 or 0 mod 4 which gives us only 0,1, 76, 25

(indeed 25^2 = 625)

So I guess 76 is kinda special in that respect, nicely observed

[unkempt void]

This method will then generalise to any n instead of 100 ofc

[torn escarp]

<@&268886789983436800>

[crude thicket]

Proof: $$(l+m)+n=l+(m+n)\hspace{.5cm} \forall l,m,n \mathbb{N}$$

Using induction over m:

Start: m=0
$$(l+0)+n=l+n=l+(0+n)$$

Assume:
$$\exists m \in \mathbb{N}:(l+m)+n=l+(m+n)$$

Step:m+1=m*

$$(l+m^)=(l^+m)+n$$ (Definition)\
I dont get this step and the following one.
$$=l^+(n+m)$$
$$=l+(m+n)^$$
$$=l+(m+n^)$$
$$=l+(m^+n)$$

[sterile pumice]

Benschko

[glossy turtle]

$$(l+m^)+n=(l^+m)+n$$ (Definition)\
$$=l^+(n+m)$$
$$=l+(m+n)^$$
$$=l+(m+n^)$$
$$=l+(m^+n)$$
Since you defined $m^* = 1+m$, similarly $l^* = 1+l$ so you can replace $ l^*$with its value and you get

$$l+(m+n)+1 $$
If you add it to the bracket it becomes
$$l+(m+n+1) = l+(m+n)^$$
Or you can add 1 to either of the two in which case it would be
$$l+(m^+n) $$

[sterile pumice]

Taaha_Tariq

[glossy turtle]

I may have changed the terms but you get the idea. Right?

[prisma folio]

What are some generally useful ways for solving diophantine equations?

[coral venture]

Factoring, modular arithmetic, bounding, thinking about prime factorisations, infinite descent and in general recursive constructions

Diophantine equations are usually very unique though and there isn't a general way to solve them

You just have to try a lot of things until something sticks

[unkempt karma]

9696996 and 6661661161 are perfect square numbers

[viral patio]

Guys thats the question x²+3y = 200 How many solutions are there in integers?

Pls

[coral venture]

Take the equation mod 3

[viral patio]

Thanks a lot

[viral patio]

u can translate it in turkish but ı thınk everythink clearly

[torn escarp]

solve in integers?

for 25 you can use the same type of trick Daniel showed you

show your attempt to solve these

[viral patio]

but ı found contradiction for both question is it correct

@torn escarp

[torn escarp]

what contradiction did you show

[viral patio]

For (example 25) ı take mod 4 so x²=2 (mod 4 ) but x² can be only 0 or 1 so ıt cant be 2 for mod4 so its condradiction

İs it correct

@torn escarp

[torn escarp]

yup

[viral patio]

Thanks for help bro👑

[viral patio]

1. For how many integers n; n3 + 4 number
   divisible by n2-n+1

[torn escarp]

!showwork

[rotund gust]

Show your work, and if possible, explain where you are stuck.

[viral patio]

what do you think

@torn escarp

[viral patio]

sorry ı understood

[trail inlet]

Can someone help me solving it?

[bold badge]

i have a solution but this channel is too small to contain it

😔

[weary rune]

[gilded breach]

I write in book margins imagining I'm Fermat

[full nimbus]

easy stuff

[viral patio]

For how many different values ​​of the integer d, each of which is divisible by d and whose sum is 999? How can 49 positive integers be found?

[torn escarp]

this doesn't quite make sense

what are you summing, divisors of d including d itself?

[viral patio]

For example d=1 we can found 49 number

Think of it as adding multiples of d

[viral patio]

And if someonre prove it send me pls

[torn escarp]

so for d=1 you have 998+1, 997+2, 996+3, ... right

[viral patio]

No for example 1+1+1.....48 piece and the last piece951

İt can be

But its for d=1

How many d can we find

[viral patio]

Bro i look for on internet and its fermats last theorem and ı found a pdf

[torn escarp]

I don't understand what you're doing at all

[viral patio]

Think of a number d, we will choose 49 numbers that can be divided by d number and their sum will be 999.

Maybe its more clear

İf not its not an important

[torn escarp]

I see

stars and bars gives you a solution to the d=1 case, and it looks like it can be fixed up a little when d|999 (which is necessary) to make it work for the other cases

if you're not familiar with stars and bars, I'd suggest you learn that first and solve the d=1 case

[viral patio]

But the best option we can choose is 8

I think only 1 and 3

What about you

So 2 numbers

[torn escarp]

oh you don't actually care about counting the number of ways of doing this?

just if it's possible for at least one way?

[viral patio]

I care but ı don find anything so ı asked this channel

[torn escarp]

1, 3, and 9 will all be possible since 999/9 = 111 can be cut into 49 pieces

since 999=3^3*37 and 999/37=27 < 49 you can't do anything else there

[viral patio]

Oh yes correct

[torn escarp]

like I said, I just gave you a solution above, stars and bars

[viral patio]

And can ı ask one more question

[torn escarp]

you should probably work the solutions out to this first before moving onto another problem

[viral patio]

Okey thanks again

[torn escarp]

let me know what you get, and show your work

[trail inlet]

turke

y

[verbal cedar]

if we know nonnegative integers a,b exist such that

N=2^a-3^b

then is there a simple way to find them?

say 1909 for example

[patent acorn]

you can probably get some information with modular arithmetic

like if we look at it mod 4, 2^a vanishes, so it's just -(3^b) = 1909 = 1, 3^b = 3, so b = 1 mod 2

N = 2^a - 3 * 9^b

now look at it mod 9, 2^a = 1, so a = 0 mod 6

N = 64^a - 3 * 9^b

mod 64, -3*9^b = 53, 9^b = 25, ...ok yeah maybe this isn't the best approach, discrete logarithm is actually pretty hard

[torn escarp]

I don't think this is technically the discrete logarithm problem because you can use the p-adic logarithm to solve it, which is a bit simpler since it boils down to the same series as you'd use in R, but with convergence in Q_p

well I use "solve" loosely here lol

the main point is you can arbitrarily gain further exponents in either the 2 or 3 -adics with a simple algorithm

the same way as hensel lifting, to help make it clear the distinction between this and the discrete log

[crude thicket]

thanks for your help. now i got it!

[patent acorn]

oh right yes of course, the fact that it's mod a power of a prime does make it easier doesn't it

[torn escarp]

I doubt this is the most efficient way to solve this but I wrote a little gp program demonstrating a way to brute force it:

a=100; b=0; L=1/log(2+O(3^100)); for(B=0,100, A=lift(log(1909+3^B+O(3^100))*L); if(A<a,a=A;b=B)); printf("%d %d\n",a,b)

this outputs a, b in a few milliseconds as:
12 7

basically I'm approximating up to 100 digits in the 3-adics and then returns the approximation as an integer. The smallest integer is considered to be the likely solution since generically you expect the log to output an irrational number so won't truncate

this is kinda lame tbh relative to just regular brute force checking

[fading void]

Hey I'm looking at congruences and trying to understand how fractions work with respect to that, my goal is to say

$ \frac{a}{b} \equiv a b ^{-1} \pmod{ n}$

so far I know that we must have $ b \mid a $, is the only other necessary condition that $b$ has an inverse mod $n$ ?

[sterile pumice]

cuppajoeman

[fading void]

Suppose that $n = 7$ and $a = 3, b = 4$, in this case can we write
$$ 3 (4)^{-1} = \frac{3}{4} \pmod{ 7} $$
or is that wrong because $\frac{3}{4}$ is a rational?

[sterile pumice]

cuppajoeman

[fading void]

meant (equivalent not equal in the above)

[white lion]

yes it is incorrect we are working in the integers mod 7 not the reals or rationals

[fading void]

But in general the notation 1/4 represents the multiplicative inverse of 4, in whatever system right, so isn't that technically correct?

Like it's technically correct, but incredibly confusing, or is it actually wrong...

[white lion]

it's actually wrong

are you familiar with equivalence classess?

[fading void]

yes

[patent acorn]

i'd say you should clarify what it means if you were going to use that notation

but if you do clarify it then i don't really see a problem with it?

[fading void]

to be sure, it's a non-standard notation though?

[patent acorn]

yes

...well, depends on the context somewhat

i can imagine seeing division used to mean multiplicative inverse mod n if it's explicitly in the context of like, working in the ring (in the abstract algebra sense) Z/nZ

[white lion]

wait so are you trying to say that 0.75 is 3(4)^-1 mod 7?

or is it just the notation you're reffering to?

[fading void]

The reason why I ask, is because sometimes we do stuff like this:

$$3 * 4 \equiv 10 * 4 \pmod{ 7 } $$

and then we can do:

$$ \frac{3 * 4} {4} \equiv \frac{10 * 4}{4} \pmod { 7 }$$

so that

$${3 \equiv 10 \pmod{7}$$

[sterile pumice]

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

[fading void]

no just the notation

[fading void]

So my question is that these steps are acutally wrong right?

There's no intermediary "fraction step" it just goes from the first line to the last right

[white lion]

no these steps are correct

[patent acorn]

yeah that's correct

writing it as "/ 4" is somewhat unusual but there's nothing mathematically wrong here

[fading void]

Assuming we are using the notation right?

[patent acorn]

it's just another way to write "multiply both sides by 4^-1"

[white lion]

mod 7 is a finite field btw

[fading void]

No , the cancellation happened, inside of Q, not inside of the modular system

That's why I'm saying it's a problem

[patent acorn]

(you do have to check that 4^-1 actually exists but that's a thing with algebra over the reals too, it's the equivalent of "can't divide by 0" except in this case 7 = 0 etc.)

[patent acorn]

ok if that's what you intended then that sounds like it is just wrong

because it has to fail when you try to divide by something that doesn't have an inverse

$0 \cdot 7 \equiv 1 \cdot 7 \pmod 7$ \ \ $\frac{0 \cdot 7}7 \equiv \frac{1 \cdot 7}7 \pmod 7$ \ \ $0 \equiv 1 \pmod 7$

[sterile pumice]

bee [it/its]

[patent acorn]

if "0 * 7 / 7" is interpreted in Z/7Z, then it's an invalid division by zero

if "0 * 7 / 7" is interpreted in Q, then the issue is that two integers that are equal mod 7 might not be equal as rationals

or if you try to say they're "equal as rationals mod 7" then the issue is that that equivalence relation doesn't respect the operations on Q (namely dividing by 7)

[fading void]

So I think the answer to my question is that $$a b^-1 \equiv \frac{a}{b} \pmod{n} $$ where the fraction is interpreted as a rational iff $b$ is inverible mod $n$ and $b \mid a$ right?

[sterile pumice]

cuppajoeman

[patent acorn]

well that requires you to define what $a \equiv b \pmod n$ actually \textit{means} when $a$ and $b$ are rationals

[sterile pumice]

bee [it/its]

[fading void]

a and b are integers

a/b is a rational, but turns out to be an integer because b | a

[patent acorn]

ok fine, it requires you to define what $p \equiv q \pmod n$ actually \textit{means} when $p$ and $q$ are rationals

[sterile pumice]

bee [it/its]

[patent acorn]

these are different letters so we don't know in advance that they're integers

[fading void]

no because a / b is an integer

[patent acorn]

well no it might not be

[fading void]

b | a

[patent acorn]

you said "iff"

which means an implication that goes both ways

[fading void]

ah ok

is that too strong here?

[patent acorn]

which means we need an expression like $2^{-1} \equiv \frac12 \pmod n$ to be meaningful and in fact false

[sterile pumice]

bee [it/its]

[patent acorn]

so what does an expression like that mean

[fading void]

Yeah good point, probably just mul by the denom

a/b equiv c /d iff a d equiv c b

[patent acorn]

well in that case your statement is false, because $2^{-1} \equiv \frac12 \pmod n$ is actually true (for $n \neq 2$, if $n = 2$ it's not defined), but $2 \nmid 1$

[fading void]

ok, so we should weaken the iff

[sterile pumice]

bee [it/its]

[fading void]

thanks for the help with this btw

[patent acorn]

yeah i think basically the statement you want is just, if $b \mid a$ and $b$ is invertible mod $n$, then $a\cdot b^{-1} \equiv \frac ab \pmod n$, interpreting the right-hand side as division of integers/rationals

[sterile pumice]

bee [it/its]

[patent acorn]

the hypotheses imply that a/b is an integer so you don't get the problem with "what does putting a rational there mean"

[fading void]

I'm solving some exercises, and one of them asks us to prove that
$$\choose{2p}{p} \equiv 2 \pmod{p}$$

and I'm looking at something like:

$$\frac{(2p)!}{p!^2} $$

in a modular equation, so we know it's an integer, but it's representation is as a fraction

[sterile pumice]

cuppajoeman

[patent acorn]

$\binom{2p}{p} \equiv 2 \pmod p$

[fading void]

yes exactly

[sterile pumice]

bee [it/its]

[fading void]

it simplifies to
$$ \frac{(p + 1) \cdots 2p}{p!}$$

[sterile pumice]

cuppajoeman

[fading void]

So that simplification occurred in the realm of rationals right?

[patent acorn]

yes

mod p, p! is 0 so dividing by it doesn't make any sense

[fading void]

see, it got you too

that's not the multiplicative inverse in the modular system

it's the multiplicative inverse in Q

[patent acorn]

?

[fading void]

For example if p = 3, then (6 choose 3) = 10, which does make sense

[fading void]

there's a problem with that idea

[patent acorn]

yeah i know how binomial coefficients work, what are you claiming "got me"

[fading void]

you can divide by p!

[patent acorn]

yes you can, in Q

you can't mod p

[fading void]

yes

[patent acorn]

which is why we evaluate the binomial coefficient in Q

[fading void]

sorry I don't get this then

because we're doing it in Q

[patent acorn]

that's me giving the reason why we didn't evaluate it mod p

i.e. that's how you can tell that we must have done it in Q

if we had done it mod p, it would not have worked, therefore we didn't

[fading void]

Right, following now

I thought you were saying there was a problem with what I wrote, but I see what you're getting at

So far we have

$$\binom{2p}{p} \equiv \frac{(p + 1) \cdots 2p}{p!} \pmod{p}$$

[sterile pumice]

cuppajoeman

[patent acorn]

yep

(well we don't really need the "equiv mod p" those are just equal, as integers)

[fading void]

yes, equal as well

[patent acorn]

probably the next step is to cancel the other factor of p

the $p$ in $p! = p \cdot (p-1)!$ with the $2p$ on the top

[sterile pumice]

bee [it/its]

[patent acorn]

and then we can start looking at it mod p because all of the factors of p (aka 0) will be gone

[fading void]

Right, so we get
$$\binom{2p}{p} \equiv \frac{(p + 1) \cdots 2p}{p!} \equiv \frac{(p + 1) \cdots (2p - 1) 2}{(p - 1)!} \pmod{p}$$

[sterile pumice]

cuppajoeman

[fading void]

also just equal as rationals

You see here I start getting a little confused, because by wilson we know that (p - 1)! is equivalent to -1, and I wanted to use that, but I'm sure I can because it's in the form of a rational...

[patent acorn]

(that's actually overkill here, we don't need wilson's theorem)

well, now the numerator and denominator both don't have a factor of p

[fading void]

Ok

[patent acorn]

so it's actually fine to reinterpret the division as being division mod p

[patent acorn]

(the only reason we couldn't do that earlier is that we would have ended up dividing by zero)

[fading void]

are we using the above fact?

[patent acorn]

yep

[fading void]

ahhh, ok finally I get this

[patent acorn]

and also the fact about primes that a number is invertible mod p iff it's not divisible by p

[fading void]

Right

so since we know that p does not divide (p - 1)! then we know that (p - 1)! has an inverse right?

[patent acorn]

yep

[fading void]

and then we know that p + i is congrueng to i, so we can then replace each (p + 1) ... (p + p - 1) with (1) ... (p - 1), which is (p - 1)! get cancellation and it leaves 2

[patent acorn]

yep

[fading void]

very cool

[fading void]

This is a cool fact

thanks for that

[echo light]

Hello. I have some trouble to show some results used in a paper. It seems at first look that it is an elementary problem, so i post this there. I have a polynom f(T) with all his coefficients integer. I define g(T)=f(AT+B), with A,B integer. How can i show that if a prime divide f(n) for some n in Z, p divide g(m) for some m in Z (p not dividing A)? All help would be appreciated, it is probabely not to difficult but i bug on this..

[torn escarp]

It's false. For instance take f(T)=T then 3 divides f(3). But now pick g(T)=f(3T+1) = 3T+1 and this is never divisible by 3.

[echo light]

Yeah but 3 divide A in this case

It is mayby not clear in my msg, but I take P prime dividing f(n) for some n, and not dividing A as defined in the last msg

However I am actually indeed not sure that the result is true. The result used in the paper is more precisely that the set of prime dividing f ( I. E there exist n such that P divide f(n)) is the same as the set of prime dividing g with a finite number of exceptions

[torn escarp]

doesn't look like you mention any restrictions on A,B except that they're integers

any other constraints or can you just send the paper or screenshot of it

[deft haven]

Is it okay to use a calculator when studying number theory? Would you miss out on useful intuitions?

[wooden glen]

Yes, calculator use is fine, as long as you don't need to rely on it for arithmetic with one or two digit results ...

[deft haven]

Thanks

[echo light]

Again, the real result used seems to be that : The set of prime divisors of f(T) and f(AT+B) coincides except at finitely many places. It is trivial that that prime divisors of f(AT+B) are prime divisors of f(T) (p |f(An+B) so p|f(m) with m=An+B). So we just have to show that, with finitely many exception, a prime divisors of f(T) is a prime divisors of f(AT+B). My conjecture is that, for every prime divisors of f(T), excepts those who don't divide A, divide f(AT+B).

I actually just have the paper in physic format but here is a of where it is used:

[torn escarp]

what you originally asked and what the lemma are saying are different things

[echo light]

No, i talk about what appear in last ligne of the proof of lemma 3.3

He want te replace f(T) with 1/df(AT+B) given by lemma 3.2 But to to be allowed to this, f(T) and 1/df(AT+B) have have the same set of prime divisors with finitely many exceptions. As the 1/d doesnt play any role, i direclty took f(AT+B)

And yeah, A, B aren't really random there, but he reuse some kind of similar arguments multiple time, replacing f(T) with f(mT), and replacing f(T) with f(p_0...p_rT+r)

[echo light]

okej, so actually i figured out how to proove this

[barren dock]

i'll be 100% honest, i don't really have an exact NT problem to discuss here, but i've got small ideas/concepts that i'm hyperfixated on

mostly recurrence relations, and the interactions between different arithmetic functions

i've put some focus into recurrence relations of the form $a_{n+1} = f(a_n)$ where $f$ is some recurrence relation but i haven't really done much with the concept

[sterile pumice]

nonpost

[coral venture]

Nice

Good luck in your journey

[wanton heath]

tell us about the interactions

you mean something like the Dirchlet product?

[barren dock]

a bit of the Dirichlet convolution, yes.

[wanton heath]

nice

and for what purpose

why these concepts specifically

[barren dock]

well i learned about them and i got hyperfixated on them. for weeks i've been fixated on arithmetic functions and their properties

[wanton heath]

nice

[barren dock]

one of the big things that intrigues me with number theory (or studying any ring tbf) is the way that addition and multiplication interact with each other

i find that a lot of arithmetic functions seem to revolve more around multiplication than addition (take for example, the multiplicative and/or additive functions)

it makes me wonder how addition can be explored when it comes to its interaction with these arithmetic functions

i ask myself questions like: can you find anything interesting about say, $\sigma_0(n + 1)$ in terms of $n$ and $\sigma_0(n)$?

[sterile pumice]

nonpost

[barren dock]

things like this intrigue me to no end

[coral venture]

That is interesting

Have you found anything

Intuitively I don't think it's likely because divisors are about prime factor distributions and those are essentially unpredictable under addition in such general terms as this

[sacred junco]

I'm working on a number theory problem rn

Prove that if p is a prime and n is a positive integer, then the equation x(x+1) = (p^2n)y(y+1) has no solutions in positive integers x, y.

I think the fact that [x * (x+1) ] / [ y * (y+1)] is an element of the natural numbers is key

[barren dock]

i haven't looked into the question i had just mentioned, but i did find that the recurrence relation $$a_{n+1} = \sigma_0(a_n)$$ will eventually hit a fixed point for any initial value

[sterile pumice]

nonpost

[coral venture]

this is a cool idea

Have you looked at $\sigma_1$?

[sterile pumice]

Daniel

[coral venture]

although that evidently only becomes constant if the initial value is 1

[patent acorn]

it's a completely open problem how many $n$ there are such that $2^n + 1$ is prime

[sterile pumice]

bee [it/its]

[patent acorn]

five are known, and it's suspected that's all of them, but we don't even know if there are infinitely many

so yeah probably you're not going to get much

[barren dock]

never knew

i'm kinda too stupid to figure out how exactly that ties in with what i'm talking abt but cool nonetheless

[patent acorn]

well we know a lot about the divisors of 2^n

but then we can't answer even very basic questions about the divisors of 2^n + 1

[barren dock]

ohhh i get ya now

[torn escarp]

idk about that, we know a few things like if n is odd then 2^n+1 is divisible by 3

[barren dock]

oh wow

[barren dock]

i trust you 100% on that but i'm gonna try and prove it myself just cause

[torn escarp]

well idk what the context is here for what bee is telling you, didn't read what you were talking about here

but the fact I said stands on its own at least

in fact we can prove a much stronger result that n must be a power of 2 to be prime

[barren dock]

the context was me saying something along the lines of "i wonder if you can write $\sigma_0(n+1)$ in terms of $n$ and $\sigma_0(n)$"

[sterile pumice]

nonpost

[torn escarp]

since n and n+1 are relatively prime but sigma_0 is a multiplicative function, that's probably not worth thinking about

[barren dock]

you're probably right that it's not worth giving the light of day but for me, that's kinda the fun stuff in NT – the seemingly basic questions that you just can't crack (also n and n+1 are coprime? never knew)

[torn escarp]

you could save yourself from banging your head against the wall if you learned just a little bit of basic NT

Silverman's Friendly Introduction to Number Theory is what I recommend as a fun book

gcd(n,n+1)=1 follows from the euclidean algorithm btw

[barren dock]

i've done fairly basic NT (i suppose) for a while, it somehow never came to me that n and n+1 are coprime until you said it

not once crossed my mind

[torn escarp]

also as a hint for this problem, fermat's little theorem should help

[torn escarp]

hint for this problem: use the geometric series

[barren dock]

i somehow proved in this in my head while completely forgetting about fermat's little theorem (making a simple problem a fair bit more complicated than it needed to be), i thought "well, the multiplicative group of Z/3Z is isomorphic to C_2 and 2 would of course be the element that isn't the identity so it has to be of order 2. if it's of order 2 then raising it to an odd power would just give it back, so in terms of the isomorphism, an odd power of 2 would be congruent to 2 (mod 3) so adding 1 would give 0, making it divisible by 3" instead of using the theorem i already knew that made the problem trivial

[torn escarp]

lol yikes

I guess for what it's worth it's good to have fermat/euler's thms and see how they're really special cases of lagrange's theorem from that perspective

[orchid steppe]

which is 2

[sterile pumice]

rnicol02

[coral venture]

not if the starting value is 1

then it's 1

[sacred junco]

Am I on the right track

I didn't solve the problem yet

Maybe I'll work on it later today

[sacred junco]

Yes

[torn escarp]

I'm thinking I'd use the fact that consecutive numbers are relatively prime to sort out how the pieces on either side of the equation can be equal

but that kinda boils down into a lot of annoying casework, probably a better approach

[flat scarab]

i posted a question in groups-rings-fields, that might be better suited for here: https://discordapp.com/channels/268882317391429632/496784958430380033/1259802530280640554

i put it there, because i found it in an abstract algebra book, but it's actually about modular arithmetic

[flat scarab]

I am struggling with this simple existence proof for the fundamental theorem of arithmetic. I don't understand how we can assume a, and b are prime or a product of primes.

Here is my attempt to explain it to myself, let me know if the notation doesn't make sense:

If we "let S be the set of integers greater than 1 that are primes or products of primes", how do a, and b seem to magically appear in that set?

I know that a and b are less than n, but how do we know a and b are primes or products of primes?

The proof also says "since we are assuming that both a and b belong to S", but I didn't see any previous statement that we made this assumption.

[coral venture]

The proof assumes that every integer less than n is in S. a and b are less than n, so they are in S. By definition, any integer in S is either prime or can be written as the product of primes, so a and b are either prime or the product of primes.

[flat scarab]

still dont understand, we are just assuming that a and b are primes?

how do we know a and b are primes?

[coral venture]

Nowhere was this said

We're assuming that every number less than n is either prime or the product of primes

a,b are less than n, so they are either prime or a product of primes

[flat scarab]

ok, i understand that we are assuming those integers which are less than n are either prime or a product of primes, thus a and b are either prime or a product of primes based on that assumption, but how are we proving that the assumption is true?

i am struggling with the second principle of mathematical induction

[coral venture]

We aren't proving that the assumption is true

That's the point of induction

[flat scarab]

this is not making sense to me yet

essentially it says, n is an element of the set since a and b are either primes or products of primes... i mean, of course this is true if a and b are elements of S, but how do we know that a and b are elements of S? just because they are less than n?

[coral venture]

Yes, because they are less than n

[flat scarab]

this is just way over my head, it's like how can we just assume that?

[coral venture]

That's how induction works:

1. show a base case is true
2. show that if it is true for k < n then it is true for n
3. then it's true for all natural numbers

[coral venture]

Imagine you want to prove that it's possible for you to climb a ladder. To do this it is sufficient for you to prove that

1. you can get on the first step of the ladder
2. when you are at a step, you can go to the next step
   If you can prove these two things, then you have proven that you can climb the ladder, by induction.

[flat scarab]

appreciate your patience in trying to help me wrap my head around this

i guess my misunderstanding must be with the initial statement, that we are stating that S is a set of either primes or products of primes, and that the same set S also includes all integers less than n

how can such a thing be stated?

[flat scarab]

and I think I understand this, it's like, you don't need to prove you can climb every rung

[coral venture]

Yes exactly

That's the idea of induction

[flat scarab]

the problem for me: if it's less than n, it's a product of primes or a prime

thats the thing we're trying to prove!

[coral venture]

You can go from step n to step n+1, and you can get to step 1.

[coral venture]

No, you're trying to prove that any positive integer is a prime or a product of primes

This is not the same, because you're right we can't just assume that S consists of all integers, that would be circular.

[flat scarab]

yes! i think you understand my confusion

[coral venture]

So, the key is that we don't assume S consists of all integers, we assume it consists of all integers less than n. Then we prove that given S contains all of these, S must also contain n. Because we know S contains 2, we can then conclude it must contain 3, and therefore 4, and therefore 5, etc.

[flat scarab]

we assume that it consists of all integers less than n, but we never SHOW that it contains all integers less than n?

maybe a different example would be better

maybe there is some simple proof i can look at and then i can come back to this one

[coral venture]

Yes this is the key idea in induction; that it isn't necessary. Like in the ladder example, you don't have to show you can climb all the way to the n'th step. You just need to show you can go from n to n+1 and you can get on the first step.

[flat scarab]

ok, then maybe go back to the a and b for a second

[coral venture]

there are many proofs by induction, you can probably just google "proofs by mathematical induction"

[flat scarab]

when we say n must = a * b

i was able to understand the first principle of mathematical induction after a few examples

the second one is just giving me a really hard time

i think the second one must be the first one, but in reverse, kind of?

[coral venture]

The second one is basically the same. In the first principle we assume that it's true for just k and show that it's true for k+1. In the second principle we assume that it's true for all k < n and then show that it's true for n.

[flat scarab]

where im stuck is the n = ab, a, b \in S

[flat scarab]

yeah its actually more the same as the first principle, not the reverse

[coral venture]

This is because if n=ab, then a and b are less than n. And we assumed every integer less than n is in S.

[flat scarab]

if we didn't make that assumption, then how can this work?

[coral venture]

It can't

[flat scarab]

this is probably very obvious to everyone else

[coral venture]

You need to assume it's true for k < n

[coral venture]

Nah induction is probably one of the most conceptually challenging ideas when starting out proof-based maths

Everyone I know including myself struggled with it

[flat scarab]

yeah i dont want to just regurgitate the steps, i want to gain a deep understanding

im not saying thats what you are doing, of course!

but yeah, i dont want to give up on this topic until i fully understand

how can we make assumptions and then make inferences based on assumptions? maybe my real question is, why and how does the second principle of mathematical induction work?

which I think @coral venture you stated with the ladder example

[coral venture]

Do you agree that the ladder example is true

Like that would be a fine proof in your mind

[flat scarab]

your ladder example makes perfect sense

[coral venture]

Induction is formalizing that intuition

Of going from one step to the next

The reason it "works" is because we assume it works (as an axiom)

[patent acorn]

(if it helps: you can derive the second principle from the first principle, by just doing induction on the statement "P(k) for all k < n" (where P is whatever it is you're trying to prove is true about all natural numbers))

[flat scarab]

then, using your same example, number 2, how do you know that you can get down to the rung below the one you're on?

[coral venture]

You don't

That's not part of the assumption

[flat scarab]

it's the thing you're trying to prove, not the assumption?

[patent acorn]

the way i think about induction is that it's basically saying, every natural number can be constructed by starting at 0 and then repeatedly adding 1

for any particular natural number, if you know how to "build" it like that by repeated +1, you can use that structure to "expand out" the proof

[coral venture]

In the ladder example I wanted to prove I could climb up to whatever step I wanted

[patent acorn]

like if you want to show P(5)

by the base case you have P(0)

and then by the inductive step you have P(0) -> P(1), and P(1) -> P(2), and P(2) -> P(3), and P(3) -> P(4), and P(4) -> P(5)

[coral venture]

Yes and in complete induction it's
P(0) and P(1) and P(2) and ... and P(n-1) -> P(n)

That's what the set S represents btw @flat scarab
All the integers in S are the ones for which we know they are either prime or the product of primes

[patent acorn]

you start from the "zero" case and then apply the "successor" case 5 times, because that's how you "make" the number 5 in the first place, that's what it is

[flat scarab]

hmm... maybe if you guys have a couple minutes we can do a quick call.

[coral venture]

I can't sorry

[flat scarab]

no worries!

[patent acorn]

i also can't, but also i think i'm probably faster at communicating through typing than i am through speech, so i don't really see what the point would be

[flat scarab]

ok, using this example, how can we build to the case where n = ab?

[patent acorn]

...well, that depends what n is

[flat scarab]

yeah thats my thought as well

n can be prime, or a product of primes

[patent acorn]

well induction is more saying "n is either 0 or 1 or 2 or 3 or 4 or 5 or 6 or 7 or 8 or 9 or..."

[flat scarab]

is "n can be prime or a product of primes" an axiom? or we are trying to prove this?

[patent acorn]

"n can be a prime or a product of primes" is what we're trying to prove

without induction, you could imagine a number that you can just keep splitting into factors forever, without ever hitting the prime numbers

but induction effectively says that that can't happen: if you take a natural number, and keep going down, you must eventually hit 0

[flat scarab]

you mean like, if you keep dividing, you would eventually hit a prime greater than or equal to 2?

[patent acorn]

no i mean you never get prime factors at all

[flat scarab]

im not sure there is a number you can divide forever

[patent acorn]

yeah there isn't

[flat scarab]

i mean there is

but it wouldn't be an integer

[patent acorn]

yep

and induction is basically how we know that we got just the natural numbers and not anything else

[flat scarab]

ok, so i think i am starting to understand

you take n, it becomes a * b

a is composed of c * d

either c is a prime or a product of primes

c = e * f

e is a prime or a product of primes

e = g * h

am i thinking right?

[patent acorn]

yeah pretty much

although the phrasing with induction is more analogous to a structure of like

we take 3, alright well that's prime

we take 4, that's 2 * 2, and we know we already did 2

we take 5, that's prime

6 is 2 * 3, we already did 2

7 is prime

8 is 2 * 4, we already did 2

[...]

n is a * b, we already did a somewhere up there

and you can see here the concept of getting to n just by doing +1 repeatedly

we have n steps, and each step refers to some of the previous ones

[flat scarab]

hmm... maybe it's more like this: n = a * b, n - 1 = c * d, n - 2 = e * f, ... you don't need to keep going

kind of?

[patent acorn]

i mean there's multiple different ways of looking at it

another equivalent phrasing of induction is that any nonempty set has a minimum element

and so we say, ok, suppose some number isn't a product of primes, then there's a smallest number that isn't a product of primes

[flat scarab]

well ordering principle?

[patent acorn]

and then if we decompose that into smaller numbers, we know those smaller numbers must be products of primes, because otherwise the number we started with wasn't actually the smallest one

[flat scarab]

so to wrap this all up, 1: we do the base case, 2: we can show n = a * b and we know that the numbers are either primes or they're not?

[flat scarab]

@patent acorn @coral venture is this question better for proofs-and-logic?

it is about elementary number theory, but i guess there is some overlap

[coral venture]

Yea

The number theory isn't the important part

[flat scarab]

is it possible to move it there?

[coral venture]

you can just re-ask your question

[flat scarab]

by the way, i still dont understand, but i did a few more examples, and they were very easy to understand, so maybe i am coming closer

[coral venture]

Also i think you will get more answers in #proofs-and-logic

This channel is (sadly) usually pretty dead

[flat scarab]

we will reignite it!

[lilac bronze]

Have you met induction and strong induction?

[flat scarab]

i want to show that 1 is relatively prime to all integers, using the definition of relatively prime. does the following proof seem correct? i do realize that this is kind of short and unnecessary, but i am trying to receive feedback on my logical flow of ideas, that is the goal here

[west glade]

well, -1 is another integral divisor of 1

rest is fine

[flat scarab]

does this sound better?

[west glade]

"greatest common divisor" should at least involve 2 numbers

greatest divisor would be fine

[west glade]

yeah thats fine

[flat scarab]

@west glade i think the following is a little bit better yet, although more wordy:

[west glade]

yes

[edgy jacinth]

My answer is D

a and option C looks correct

But given answer is only A

[torn escarp]

look for a counterexample for C

[edgy jacinth]

Yeah but how?

[torn escarp]

there are only finitely many possibilities to try

but the fact that a=b mod 5 is helpful

with a>b

try a=b+5, a=b+10, a=b+15, etc... as a line of possibilities for instance

plug n' chug to a+b=24 and see what works

[stoic briar]

This is pain

[torn escarp]

also not number theory

try #precalculus

[flat scarab]

does this seem like the right way to typeset this modular arithmetic problem? please critique, also feel free to look at the problem and of course how the modular arithmetic was performed as well

[lilac bronze]

Normally id use $\equiv$ rather than $=$ but honestly that’s just a stylistic preference

[sterile pumice]

Pseudonium

[lilac bronze]

Otherwise it’s completely correct

Maybe the only thing id add is an extra line saying $\equiv 15 \pmod 7$

[sterile pumice]

Pseudonium

[lilac bronze]

Between the second-to-last line and the last line

[flat scarab]

need some feedback on another modular arithmetic problem:

[wooden glen]

You should use \equiv and \pmod.

[flat scarab]

$\pmod$

[sterile pumice]

computerman4774

[flat scarab]

not a big fan of that, do i need to?

[patent acorn]

$3 \equiv 5 \pmod 2$

[sterile pumice]

bee [it/its]

[flat scarab]

is that the "standard"?

[wooden glen]

You asked for critique of the typesetting ... ¯_(ツ)_/¯

[flat scarab]

yeah im fine with you suggesting that

but is it expected/standard?

[wooden glen]

Yes, \equiv and \pmod is the standard notation.
You can also just declare in prose that you're working modulo 7, and then use =, and no explicit mention of the modulus in the equation itself.

[flat scarab]

ah yes, I forgot about that second option. now that you mention it ive seen that before.

but thanks, if its standard to use \pmod and \equiv, i will

[flat scarab]

having trouble understanding, can you write it as latex?

[flat scarab]

oh i see it!

i had to think about that

the 2 and -2 sum to 0

[tacit heart]

how do i show that the number of elements with order d is phi(d) modulo p?

[west glade]

consider the subgroup of elements with x^d=1

[tacit heart]

is there a way without group theory?

[tacit heart]

How does it go?

[brittle root]

perhaps its similar to the group theory one

[tacit heart]

alright I’m just going to learn group theory

[fading void]

Hey given two multiplicative functions I've been seeing that they're equal when they agree on prime powers, just to confirm, agreeing on primes is not enough is that right?

[still flare]

It is not enough

[wooden glen]

For example, the totient function has phi(p)=p-1 for prime p, but phi(p^n) = (p-1)p^(n-1) for a prime power.
If we want the totient to be "multiplicative" (which we really do!) we need a concept of multiplicative that is flexible enough that knowing the values on the primes doesn't tell us everything about the function.

Or for another example, the Möbius function and the Liouville function both take the value -1 on every prime, but they're not the same function.

[nocturne vortex]

Here he's reducing 2^m + 3^n = x^2 to mod 3; what exactly is happening in that first step after "Sps"? I get that 3^n is 0 mod 3 but why can he just get rid of it in the expression like that?

i.e. what are the mechanics of reducing an expression modulo n like this?

[west glade]

well if 3^n=0 mod 3, then 2^m+3^n=2^m+0 mod 3

if two things are congruent mod n, then you can just replace one with the other

[flat scarab]

hey everyone, wondering if someone could take a look at a proof i did and provide some feedback:

[still flare]

What is the definition of equivalence modulo n that you are given?

... it follows from the division algorithm that r_1 = r_2
Does it? What if r_1 is less than r_2? But in any case, isn't this already assumed?

Since n divides a-b, r_1 - r_2 = 0
This needs more explanation.

This isn't a complete proof in my opinion. I can see how to fill the gaps but I'm not convinced you have considered them. (In fact I think you haven't realised that you've actually tried to prove the same direction twice!)

[flat scarab]

this is true because if the quantity $q = q_1 - q_2$ divides $a - b$ then the quantity $r = r_1 - r_2 = 0$.

[sterile pumice]

computerman4774

[still flare]

Why?

I don't think this is immediate

I have a reason why, but can you explain it?

(N.b. You have simply restated what you claimed again without further justification)

[flat scarab]

the definition of something to divide something else, is that $a = qn + 0$

[sterile pumice]

computerman4774

[still flare]

So?

[flat scarab]

$r_1 - r_2$ has to be $0$

[sterile pumice]

computerman4774

[still flare]

You are just again claiming the same thing

OK let me put it another way

10 = 2*4 + 2

[flat scarab]

im using the definition of the division algorithm

[still flare]

But 2 | 10, so 2 = 0

This is the logic you are using

Do you see the problem?

[flat scarab]

no, this is not the logic i am using

you are wrong

[still flare]

OK

I can see you're not interested in working through this

[flat scarab]

ok, so because i don't agree with you, that means i am not interested in working through this?

[warm bison]

it would be nicer if you write the unique integers q1,r1 such that a = nq1 + r1 and 0 <= r1 < n, and the unique integers q2,r2 such that b = nq2 + r2 and 0 <= r2 < n before you proceed to prove the biconditional.

... it follows from the division algorithm that r_1 = r_2

By definition (this is from Gallian's book i'm assuming), a mod n = r1 and b mod n = r2, so when proving the forward, you're already given r1 = r2

Since n divides a-b, r_1 - r_2 = 0

What exactly are you using to reach the conclusion that r1 - r2 = 0? It seems like you are using: "Given A,N,Q,R are integers where N > 0, if A = NQ + R and N | A, then R = 0", where in the proof, you are taking A := a - b, N := n, Q := q1 - q2, and R := r1 - r2. But this statement is false; Boytjie provided a counterexample where A := 10, N := 2, Q := 4, and R := 2. In this counterexample, we see it is true that A = BQ + R and N | A, but it is not true that 2 = 0.

Of course the whole of the converse is to show r1 = r2, but the above statement doesn't allow us to reach r1 = r2 immediately. So there are gaps which need to be filled in

[flat scarab]

thank you for explaining this, need a little time to think through it

if a number is a divisor, then the remainder is 0

@warm bison here, i reworked the first part, i think it is slightly better now, what do you think?

[flat scarab]

2 divides 10 and the remainder is zero

[sterile pumice]

Vanellope von Schmugz

[flat scarab]

thank you, i have a new version of this i need to post, will write it up in a bit

[warm bison]

this is exercise 9 from section 0 in joseph gallian's abstract algebra book, right? then "a mod n = b mod n" is the correct notation (rather than "a (mod n) ≡ b (mod n)")

"a mod n" in this context refers to the following:

Suppose a,n are integers where n > 0. By the division algorithm, there are unique integers q,r which satisfy a = nq + r and 0 <= r < n. "a mod n" is defined to be this value of r

[warm bison]

Let a = q1n + r1 and b = q2n + r2 where q1, q2, r1, and r2 are unique.

this isn't what the division algorithm says; you should really say "there are unique integers q1,r1 which satisfy a = q1n + r1 and 0 <= r1 < n", and something similar for b and n.

that and my previous comment are the only two issues i see

[dry eagle]

Let $S= {2^k3^l: (k,l)\in\mathbb{N}^2}$.

Prove that $\forall s\in S, \exists {s_n} \subset S$ a sequence and some $m\in\mathbb{N}$ s.t. $s=\sum_{k=0}^m s_k$, and $\forall i \leq m, j\leq m, i \neq j \Rightarrow s_i \nmid s_j$ and $s_j \nmid s_i$.

[sterile pumice]

VirtualCode

[dry eagle]

My first thought was to write 3=2+1 and expand using the binomial theorem, but after wracking my head trying to prove the second condition I realized that doesn't even fit the first one (s_n in S)

[dry eagle]

what do you mean?

[flat scarab]

made some changes, @rugged pasture (changed to a \equiv b (\pmod n))

[edgy jacinth]

63^25 mod 1000

any short way to do this?🙄

[still flare]

Yes

If you are being asked to do this you have likely already seen a few different methods

Perhaps you have seen Euler's totient function, or perhaps you have seen people show you how to calculate something like 4^1000 mod 10 by inspecting small powers.

You are not going to be expected to compute 63^25 then work it out mod 1000. That would be a ridiculously bad approach.

[leaden stream]

you should explain why n dividing a-b implies r1 - r2 = 0. Why can't it also be a multiple of n?

[flat scarab]

the definition of c divides d is that there is no remainder

[leaden stream]

right, so you should explain why there is no remainder. For there to be no remainder, either r1 - r2 = 0 or r1 - r2 is a multiple of n. So why is it not a multiple of n?

because what you have is n divides a sum of numbers, one of which is a multiple of n. You haven't shown that the other number is not a multiple of n.

[flat scarab]

I’m sorry I don’t know how to go any deeper than what I said before

[leaden stream]

You basically have n | x + y
you know x is a multiple of n, that isn't enough to say y = 0 without further reasoning.

[flat scarab]

r1 - r2 is a quantity which is a remainder

That quantity is 0

[leaden stream]

why can't it also be n?

or some other multiple of n?

17 = 3(5) + 2
7 = 2(5) -3
5 | 17 - 7, and as i've written them 17 - 7 = 5(3-2) + (2 - (-3)) = 5(1) + 5