elementary-number-theory

[dusty dragon]

It helps to think about what the prime factorisation of the gcd and the lcm look like

[slim dew]

Oh wait is it because the lcm has 2^3 and since x only had 2^2 then that means y must have a factor 2^3? Otherwise the lcm could just be reduced by 2^1?

[dusty dragon]

Yes

But that’s an issue right

Because what would the power of 2 in the gcd be?

[slim dew]

Ohhhh so we've increased the gcd by a factor of 2 right?

[dusty dragon]

Well, necessarily the power of 2 in the gcd must be 2

[slim dew]

So ig by multiplying by 2^2 instead ur kinda exhausting it

Exhausting is not the word but like u get wat i mean right 💀

[dusty dragon]

The more correct way to see it is that if x contains some power of a prime - say p^a - and y contains some other power of the prime - say p^b - then gcd must contain p^{min(a, b)} and the lcm must contain p^{max(a, b)}

In our case, we require that min(a, b) = 1 and max(a, b) = 3

For the power of 2

So if you know that x is not equal to gcd and the power of 2 is different, then it must necessarily have 2^3 in its factorisation

(and that means you multiply by 2^2)

You can do the same for 5, 7, 11 and see which one gives you a smaller value for x

and it’s not hard to see that you need to multiply by 2^2 to obtain the smallest value for x

[slim dew]

Yeah this makes a lot of sense, thank you! Idk why i was so confused over this

Guess not doing maths in over a year made me braindead lol but yeah appreciate the help

[sacred junco]

I'm having trouble understanding the expansion

It doesn't make sense to me

They just threw it out of nowhere

[normal heart]

try expanding it out for r=3 or something

you should see the pattern

[sacred junco]

Gotcha

Thanks

[sacred junco]

why is $\prod_{g \in G} g= \prod_{g \in G} f(g)$?

[sterile pumice]

plazzi

[sacred junco]

Let $G=(\mathbb{Z} \setminus 5)^{\times}$ wouldn#t be $\ P= \prod_{g \in G}= 1 \cdot 2 \cdot 3 \cdot 4? \$

[sterile pumice]

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

[sacred junco]

But $\prod_{g \in G} f(g)= x \cdot(1 \cdot 2 \cdot 3 \cdot 4)$

[sterile pumice]

plazzi

[west glade]

no, $\prod_{g\in G} f(g) = (x\cdot 1) \cdot (x\cdot 2) \cdot (x\cdot 3) \cdot (x\cdot 4)$

[sterile pumice]

denascite

[west glade]

which you can check by hand for eg x=2 is again the product 1*2*3*4 just in a different order

you are multiplying over the same elements because f is bijective

@sacred junco

[sacred junco]

This helps, ty

[verbal cedar]

this looks like #prealg-and-algebra not #elementary-number-theory

[balmy dock]

Does someone know how to work with Galois field in matlab?

[molten token]

hi can i ask what background should I have to learn number theory?

[stiff rivet]

elementary number theory doesnt require any specific background, other than arithmetic and highschool algebra

[wild summit]

why are titu's books so damn expensive bro

[molten token]

thanks

[wild summit]

like why is structures and examples and problems 7k inr???

[leaden swan]

I think people just print stuff here

Because that's cheaper

[molten token]

what does | vertical line mean in number theory? for example p|a if p is prime

[still flare]

Divides

[sacred junco]

Why is $\ \sum_{d |n \cdot m^k} \varphi(d)= \sum_{d|n} \varphi(d) + \sum_{i=0}^k \varphi(d \cdot m^i)? \$
I don't get it

[sterile pumice]

plazzi

[sacred junco]

varphi(d) is the euler phi function

Shouldnt it be instand of $\sum_{i=0}^k \varphi(d \cdot m^i)$ be $\sum_{i=1}^k \varphi(d \cdot m^i)$?

[sterile pumice]

plazzi

[sacred junco]

Instead*

[still flare]

This notation doesn't make sense as d is unbound in the second sum.

perhaps this is meant to be:

$\sum_{d |n \cdot m^k} \varphi(d)= \sum_{d|n}\left( \varphi(d) + \sum_{i=0}^k \varphi(d \cdot m^i)\right)$

[sterile pumice]

Borty

[still flare]

But this too is false.

Firstly, as you point out, we would need i=1 to k

But also this is simply false unless m is prime.

This could be written must better as:

$\sum_{d \mid np^k} \varphi(d) = \sum_{i=0}^k \sum_{d \mid n} \phi(d p^i)$ where $p$ is prime.

[sterile pumice]

Borty

[sacred junco]

Thanks. How can i prove that $\ n= \sum_{d|n} \varphi(d)$?

[sterile pumice]

plazzi

[sacred junco]

Without using $\varphi(mn)= \varphi(m) \varphi(n)$

[sterile pumice]

plazzi

[still flare]

You need to refer to the definition of phi(n).

[open mist]

using ||a relevant partition of {0, ..., n-1}||

[paper trellis]

This problem looks miserable

[torn escarp]

i define phi as ||the degree of the nth cyclotomic polynomial ||

[quaint gate]

Let $p\geq 2$. Prove that if $2^{p} - 1$ is a prime then $p$ must be a prime.

Proof: Suppose $p$ is not a prime then there are integers $m,k < p$ such that $p =mk$. Now, notice that $2^{m}-1$ divides $2^{mk}-1 = (2^{m})^{k}-1^{k}$ and $(2^{m}-1) < (2^{mk}-1)=2^{p}-1$ which shows that $2^{p}-1$ is not a prime and we are done.

Am I missing something in this proof? I can't point out exactly where we used $p\geq 2$ here. Could anyone check this please?

[sterile pumice]

pikapikapikapikachu

[sacred junco]

I dont understand the last part.
Your first part is the right idea.
If you can write $2^{m \cdot k}-1$ as a prodouct of two integers, $2^{mk}-1$ cant be a prime

[sterile pumice]

plazzi

[still flare]

We need 2^m - 1 to be a number other than 1 :)

[sacred junco]

Because 1 is not a prime since 2^1-1=1

[still flare]

No, that's not why

[quaint gate]

oh right

[still flare]

It's because finding a nontrivial factor prevents something from being prime

A trivial factor of n is 1 or n

So exhibiting a factor that is not 1 or itself is necessary.

This is why we need p >= 2.

[sacred junco]

But p is a prime?

[still flare]

That is the goal of the proof, not the assumption.

[sacred junco]

Ah yes

[still flare]

In fact quite the opposite: in the contradiction, we assume that p is not prime!

[quaint gate]

I am using that $x-a$ divides $x^{n}-a^{n}$ there

[sterile pumice]

pikapikapikapikachu

[still flare]

Your proof was fine chikapu, you just missed out what I pointed out.

[quaint gate]

ah thanks

[white lion]

I think you may be missing some information, suppose p were of the fom 4k+1 but we know that 2 is a prime and not of the form 4k+1

[honest star]

does the set S have a name?

[still flare]

We would write it in ring theory as S = (a) + (b), not that it matters.

Wait, not quite

Because it's in the positive integers

Perhaps we would call it the set of positive integral linear combinations of a and b.

[random sand]

That intersect Z+

[still flare]

ye

[verbal cedar]

what about $\gen{a,b}$

[sterile pumice]

nixxy nilpotent hhhhhhh

[verbal cedar]

would that notation be equivalent

[still flare]

Yeah it would

Some people write parentheses instead of angled brackets

[sterile ruin]

hi

[loud moon]

[white lion]

I have a hint for this excercise that says an integer is congruent mod 10 to its units digit

but how is that even possible if all the digits of an integer is going to be less than 10 than that would imply that the integer could have more than one remainder or least residue modulo 10

we know that each digit is a number 0,1,. . . , 9 < 10. for example 92 then by the hint 92 = 9 (mod 10) and 92 = 2 (mod 10)

which would mean both 9 and 2 are the remainders of 92 when divided by 10 which is impossible

[torn escarp]

the units digit means the "ones place", 92 = 2 mod 10 @white lion

"unit" means "one"

[white lion]

Oh gotcha thanks

[torn escarp]

you're welcome

[white lion]

Im trying to prove that $17$ does not divide $5n^2+15$ for any integer $n$. so I attempt proof by contradiciton and show that $17|5n^2+15$ for any integer $n$. Does it suffice to show a single counter example like th case of n = 2 or no?

[sterile pumice]

jayzsparrow

[torn escarp]

no, cause it could be a different n

you might try to prove this with quadratic reciprocity

[white lion]

I haven't learnt that yet

[torn escarp]

well, I guess the easiest trick to halve the time brute forcing it would be to realize n^2 = (17-n)^2 mod 17

[white lion]

Okay

[torn escarp]

so you can stop once you reach n=(17-1)/2=8

not too many cases to check

[white lion]

how did you come up with that in a less than a minute lol

[torn escarp]

experience I guss

[verbal cedar]

quadratic reciprocity will be the fastest way. you just need to compute $\legsym{-3}{17}$

[sterile pumice]

nixxy nilpotent

[verbal cedar]

and then you can use [
\legsym{-3}{p}=1\iff p\equiv1\bmod{3}
]

[sterile pumice]

nixxy nilpotent

[white lion]

yeah merosity mentioned that but I haven't learn that yet

thanks though

I was thinking of an easier proof I don't know if it is correct though, so I want to prove that $17$ does not divide $5n^2 + 15$. Proof by contradiction: Assume $17|5n^2+15$ for any integer $n$ then $17|5(n^2+3)$ implies $17|n^2+3$ implies $n^2 = -3$ (mod 17) implies $n^2 = 14$ (mod 17). Informally this is saying that the square of an integer must have a remainder of 14 if our assumption is true, so, this may be the part where I got it wrong but I then say that $(n+1)^2 = 14$ (mod 17) since n+1 is indeed an integer therefore it's sqaure must have the remainder 14 when divided by 17. Then it's trivial to show this will lead to a contradiciton.

[sterile pumice]

jayzsparrow

[loud moon]

at best this shows that if the claim holds for n then it doesn't hold for n + 1, from which it doesn't follow that the claim is false for all n

[verbal cedar]

were you given this problem by a textbook or professor? because quadratic residues are literally all about determining if n^2=a mod p has a solution

afaik your only choice is to either check every single possibility between 2 and 8, or just use quad res theorems. the first is "easier" in the sense that you can use child scissors to trim a tree. but you could also just pick up a tree trimmer and do the problem in like one step.

[marble vigil]

I am trying to prove 2xy = x + y only has integer solutions for (x,y) = (0,0) and (1,1).
I managed to do this by analyzing y = x/(2x-1), but I think this solution is a wee bit impure and ugly.
How can one do it with more elementary number theoretic tools?

One inch of progress I made is by comparing signs, but I have not been able to pursue all the cases successfully.
For instance 2xy = x + y cannot hold for integers x,y < 0, since in that case the left-hand side is strictly positive whereas the right-hand side is strictly positive. Hence the case x,y < 0 can be ruled out. But the other cases, I have failed to treat successfully. Is there a simple way to do it? Thanks!

[west glade]

cant you just compare sizes? |2xy| = |x+y| <= |x| + |y| <= |xy| + |xy| = 2|xy|

(for x,y nonzero)

[verbal cedar]

assuming y>0: i think you could take the equation mod y. you'd get 0=x mod y, so x=ny.
2ny^2=(n+1)y
y(2ny-n-1)=0
y=0 implies x=0 is a solution. otherwise
2ny=n+1 implies n must be odd (n=2k+1)
(2k+1)y=k+1 implies y=(k+1)/(2k+1)
the only way this can be an integer is if k+1=0 or 2k+1=+-1. so k=0 (y=1) or -1 (y=0 again)

[marble vigil]

ah very nice, are you using |x| <= |x| |y|, because y is an integer and |y| >= 1 if y is not zero?

[west glade]

ye

[marble vigil]

interesting, I also tried something similar and wound up with an expression like y = (k+1)/(2k+1), but I stopped there because I could not justify k+1=0 or 2k+1= +-1. I accept the conclusion but I fail to see how to justify it

[verbal cedar]

for a fraction to be an integer, either the numerator is zero, or the denominator is +-1

[marble vigil]

assuming a fully reduced fraction, right?

[verbal cedar]

yeah

[marble vigil]

fair, i'll see if I can prove that. maybe euclid's lemma should take care of it. thank you

[marble vigil]

Okay so we get 2|xy| <= 2|xy|, but is this not just a trivial inequality? what further conclusion do we draw to get what we seek

[west glade]

well we know this is actually an equality

so all inequalities along the way also have to be equalities

otherwise we would get 2|xy| < 2|xy|

[marble vigil]

oh gosh how dumb of me, right! so we get |x + y| = |x| + |y| iff y and x are proportional. I should be able to go from there

[west glade]

I think the other one is more interesting

telling you that |x|=|y|=1

[marble vigil]

do you mean 2 |x| |y| = |x| + |y|?

[west glade]

|x|+|y| <= |xy| + |xy|

you need equality there. so |x|=|xy| and |y| = |xy|

[marble vigil]

Ah I see

From |x| + |y| = |x| |y| + |x| |y|
we get
|x| ( 1 - |y| ) = |y| ( |x| - 1 )
|x| and |y| are non-negative, so the signs of 1 - |y| and |x| - 1 must be identical (or both zero, which just gives x = y = 1).
But if 1 - |y| > 0 then |y| < 1 and so the only integer satisfying that is y = 0, which forces x = 0.
And if 1 - |x| > 0 we get (0,0) again.

[west glade]

that seems a bit overkill

x can either be 1 or -1. just plug into the original equation and get that only (1,1) works

or x=0. then also y=0 by plugging in

[marble vigil]

fair! thank you

[west glade]

always the trade-off between a hard abstract argument and just bruteforcing a couple of options manually

[marble vigil]

true true

out of curiosity, how about xy = x + y? this one only has (0,0) and (2,2). Analysis of y = x/(x-1) works but is ugly imo

[west glade]

add and subtract 1. rearrange and factor

[marble vigil]

xy = x +y
xy - x = x(y-1) = y
x(y-1) - (y-1) = 1
(x-1)(y-1) = 1
x - 1 = +-1
y - 1 = +-1

very nice, thank you 🙂

[white lion]

Textbook lol Quadratic residues is literally the next chapter though it did this quite a few times

[west glade]

oh and the original problem is equivalent to 4xy=2x+2y which you can rearrange to (2x-1)(2y-1)=1

thats probably the cleanest solution for that

[marble vigil]

yeah very nice indeed, thanks!

[wild summit]

anyone here?

[loud moon]

[paper trellis]

no

[dusty hound]

https://dontasktoask.com/

[torn escarp]

im not here

[white lion]

technically he didn't just ask to ask

[torn escarp]

guess you didn't click the link

[white lion]

this is the internet I aint trusting random links

[open mist]

this one is safe

[errant otter]

I ain't trusting strangers on the internet to tell me what's safe and what's not!!!

[open mist]

expected

[wild mesa]

Prove any integer cubed is of the form 7k or 7k+1 or 7k-1

Ik How to do It with 7 cases for (7q)³,(7q+1)³... (7q+6)³ .But is there a better way to do It?

Im too lazy to write It all

And id like to know If there is a another simpler yet rigorous answer

[random sand]

Do you know modular arithmetic?

[west glade]

even if not, it might help to realise that eg 7q+5 = 7m-2. so you can reduce the cases by half with some slight adjustments

[quaint gate]

3^3 is not?? you're probably missing some hypothesis?

[wild mesa]

Sorry i forgot 7k-1

[wild mesa]

Yes

[wild mesa]

That actually helps

[wild mesa]

But im not allowed to use it yet

[random sand]

L

[quaint gate]

notice the pattern in (7m+n)^3 expansion using binomial theorem, it suffices to consider the cubes of n for your cases i think (altho i could be wrong, im only half awake), other than n^3, you should be able to factor out a 7 from the rest of them?

[wild mesa]

I thought about that, but i didnt think about generalizing that way. i think that works

Yea thats the best way

Thanks

[verbal cedar]

i think you can do it with fermat's theorem?
if 7 divides a, then a^3=0 mod 7 implies a^3=7k
if 7 does not divide a, then
a^6=1 mod 7 implies (a^3-1)(a^3+1)=0 mod 7 implies a^3=1 mod 7 or a^3=-1 mod 7 implies a^3=7k+1 or a^3=7k-1

[wild mesa]

Idk about that stuff yet

[verbal cedar]

you asked if there's a better way, and there it is

[wild mesa]

,w fermat's theorem

[sterile pumice]

Results provided by WolframAlpha

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

Requested by oxil764

[verbal cedar]

if you're not allowed to do it with modular arithmetic, then you're probably expected to do it by cases

fermat's little theorem is what i meant

[wild mesa]

I used pika's solution

[verbal cedar]

if $a$ is not divisible by $p$, then $a^{p-1}=pk+1$

[sterile pumice]

nixxy nilpotent

[verbal cedar]

that's fine

fermat's theorem is the optimal solution i think, though

[errant otter]

,w fermat's little theorem

[sterile pumice]

Results provided by WolframAlpha

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

Requested by kiameimon

[errant otter]

Yay

[static cedar]

Hi

This isn't fully a number theory question but I think you guys might be helpful...

Well I've proved for... odd... but idk about even one

This if for odd one

But... not really sure about even one

I wrote something...

About even cases which is feels very dumb

This....

Ping if you know anything...

[torn escarp]

since $\binom{n}{k}=\frac{n}{k}\binom{n-1}{k-1}$ we could simplify the earlier expression you got,
$$a_n=n\sum_{\substack{k=1 \ k \text{ odd}}}^n \binom{n-1}{k-1}\frac{\sqrt{2}^{k-1}}{k}$$
now if we consider this in $\bQ_2(\sqrt{2})$, we can see that the first term of that series is $1$ and the rest have 2-adic absolute value strictly less than $1$, so it simplifies down to;
$$|a_n|_2=|n|_2$$
which is exactly what you wanted to prove.

[sterile pumice]

Merosity

[torn escarp]

maybe we can de-jargonize it into simpler terms 😬 lol

if you have any questions lmk, I realize that's probably a bit out there

[simple thorn]

how do we recover d from p and q (efficiently)

sure if you can find the inverse of e mod p-1 and mod q-1 you multiply the latter by the former to get d

but if you could compute those inverses efficiently, surely (?) you could compute at once the inverse mod (p-1)(q-1)

[torn escarp]

well, it wouldn't quite work that way since p-1 and q-1 aren't relatively prime, so you're not going to be able to use the chinese remainder theorem so well - but it doesn't matter

[simple thorn]

oh right

[torn escarp]

by having p and q it gives you the ability to think of e mod (p-1)(q-1) in the first place since we don't know otherwise "where" the inverse of e is to be taken if that makes sense

once you know (p-1)(q-1) you can use the euclidean algorithm to get the inverse which is pretty quick

(p-1)(q-1)x + ey = 1
you do a bunch of subtractions basically until you end up with y, which is really d

[simple thorn]

oh if an attacker somehow gets (p-1)(q-1) it’s gameover cuz euclidean algorithm is easy and fast

[torn escarp]

yup

there might be some more nuanced or better way of doing this in the real world, but I think this is probably bad enough

[simple thorn]

bad?

[torn escarp]

like, for the people trying to hide their stuff

good for the person trying to decrypt

[simple thorn]

oh

[static cedar]

Thanks, but that works as well the other guy said

[torn escarp]

wdym

what other guy

[static cedar]

Well asked some ppl about it

And they said its OK

[torn escarp]

idk what "it" is lol

[static cedar]

Alr thanks

[torn escarp]

you're welcome lol

[errant otter]

[inner mist]

what topics of elementary NT are to be expected to be comfy with in an ANT course? (edited)

[quick furnace]

reading a number theory book rn and i stumbled upon this theorem which is apparently basic (Dirichlet's lemma) but i can't make sense of it from an intuitive standpoint, despite having read both of the proofs provided:

**Let α, τ be real numbers with τ >= 1. Then there exist a in Z and q in N such that:

|α - a/q| <= 1/(qτ), gcd(a,q)=1, and q <= τ.**

and i'm having trouble grasping intuitively what that means and why it's significant -- i can only intuit that this is about approximating real numbers with rationals but i can't comprehend exactly how this approximation is meant to work

like ok i saw both proofs of it, one of which involved farey fractions and the other involved looking at the fractional parts of integer multiples of alpha

but like something doesnt quite sit right with me with the result itself

(if anyone's interested i can show a photo of the theorem as written in the book, but it'll be the exact same only with the accompanying text written in bulgarian so)

[errant otter]

https://en.wikipedia.org/wiki/Dirichlet's_approximation_theorem this is honestly the closest find I could get... nothing in wiki, wolfram yielded smth identical to it

[quick furnace]

it's equivalent thereto

but i don't find that it helps me any with intuition...

[errant otter]

oh wait it's equivalent? I didn't see the gcd part

Well, last time I recall a discussion in #proofs-and-logic regarding it, lemme see if it may help....

#proofs-and-logic message ehhh maybe not that insightful.

merooo where r u

[quick furnace]

its ok i asked elsewhere about it and kind of get it intuition-wise i think

[glossy stump]

This kinda resembles something with lattices I think

This a slide from my crypto course

[open mist]

I can confirm it being "basic" in number theory

the intuition to me is that, for fixed q, the k/q may not get close to alpha, but if you change q, you change where the points lie, and it sorts of ends up covering the whole line (i.e. it gets close to everywhere).
So you're bound to find an appropriate q such that the splitting of the line done by the k/q gets remarkably close to alpha

or probabilisticly (though only intuitively):
For any given n, there's something like a 2/n chance that this happens.
it's bound to happen at some point (Borrel Cantelli kind of stuff)

[open mist]

In that I have seen it 3 times, which is remarkable

for how much number theory we do

including it being the 2nd (of 3) questions on the 3rd exercise I ever did in undergrad
So it holds a bit of a special place in my heart

[wild mesa]

Guys If an integer is a square and a cube i need to show it is not of the form 7k-1

Any hints?

[dusk vale]

guys

I am stack on this problem

I tried brute forcing but without any finds,
tried also to decrease q and found results that means greater q makes the problem harder
I want to solve it for q = 2^64

[open mist]

what are the possible values of squares mod 7 ? Of cubes ? is -1 a value for both ?

[wild mesa]

Ah got it

Thx

[quaint gate]

based on yesterday's problem, cubes are of the form 7k, 7k+1,7k-1. So do a similar analysis for squares (upon dividing by 7) i guess and see where you can go from there??

ah lol too late

[wild mesa]

I Just did

We get 7k,7k+1,7k+2,7k+4

We dont get 7k-1 that is congruent to 7k+6

[quaint gate]

-1 is congruent to 6 ( mod 7)

7k+6=7k+7-1=7(k+1)-1

[wild mesa]

I miswrote

[open mist]

there's also a very quick trick in this case using some elementary number theory

in Fp, if -1 = a², then -(1)^(p-1 / 2) = a^(p-1) = 1
Here p-1 / 2 = 3, and (-1)^3 = -1 != 1 mod[7] hence -1 is not a perfect square

[dusk vale]

can I have guide for this?

[open mist]

I wish I could help, but this looks kinda random

actually wait
There's the very trivial
a1 = 1, ai = 0 for i >= 2
Then s = 49, p = 49

duh

intended ?

Q2) is the same but you pick an odd prime number

[dusk vale]

49 is not prime but i got your idea

thank you

what if we want more than number lol

[open mist]

Wdym more than number ?

[dusk vale]

for example a list with 3 non zero numbers verifies the condition

[open mist]

This is a surprisingly trivial example that works for any nonempty set of xi

[dusk vale]

yeah

[dusk vale]

a_1 = 1 and the others are 0
I am looking for a list with at least three a_i are nonzero

[open mist]

Oh ok

Also it's a1 because it's x1=49

[dusk vale]

indeed

i think this problem has relation complexity, since brute forcing is hard to perform

[open mist]

I might have an idea to find large, nontrivial solutions

Finding cases where s = 1 mod q

[torn escarp]

Then it's a 6th power and Fermat's little theorem applies

[open mist]

It may not be obvious for them to show it's a 6th power but I like the idea

[torn escarp]

I guess if we want to get crazy we can say the exponent is 0 mod 2 and 0 mod 3 so using CRT we have that it's 0 mod 6

[open mist]

I kind of did that actually. I just looked at each individual p-adic valuation and said it's both a multiple of 2 and 3

[dusk vale]

I think the problem is like

a(n) is the smallest integer equal to the sum and the product of the same n positive integers: a(n) = i(1) + i(2) + ... + i(n) = i(1)*i(2)*...*i(n).

in OEIS A104173

[torn escarp]

is this supposed to be a programming problem

what is S anyways

random odd numbers in some arbitrary range lol

[potent wren]

hey can someone help me what is going on with the first equivalence? how are they going from a^2 + 2 = 0 to (2a)^2 + 8 = 0?

[inner mist]

2a-1 = 0 mod 2a-1

[potent wren]

yes but where is this 8 popping up and the factor of 2 inside the square?

[errant otter]

,w a^2 + 2 + 2a - 1 complete the square

[inner mist]

4a^2+8 = 4(a^2+2) so u would guess multiplied both sides by 4

[errant otter]

right

[potent wren]

i dont follow why would i guess to multiply by 4?

only to get the 2 in front of a?

[errant otter]

you're not meant to guess, you're just meant to use intuition (quite literally) to find a way to manupulate this to make it something easier to compute/solve

in this case yes

the idea was to make it congurent to narrow down the options

[open mist]

you want to get 2a because then it simplifies to 1 mod 2a-1

and the equivalence is guaranteed by the CRT since 2a-1 and 4 are coprime

[inner mist]

.

[verbal cedar]

say that $\a$ is a solution to $x^q\equiv1\bmod{p}$ ($p,q$ are odd primes such that $p=qk+1$). does this imply that all solutions to $x^q\equiv1\bmod{p}$ are of the form $\a^c$?

[sterile pumice]

nixxy nilpotent

[verbal cedar]

its clear that powers of alpha will be solutions, but im not sure how to prove that they comprise every solution

would it be sufficient to show that

$x^q-1\equiv \prod_{i=0}^{q-1}(x-\a^i)\bmod{p}$?

[sterile pumice]

nixxy nilpotent

[verbal cedar]

or i suppose equivalently that $\a^i\neq\a^j$ for $0\leq i<j<q$?

[sterile pumice]

nixxy nilpotent

[verbal cedar]

where alpha isn't 1 ofc

[open mist]

The set of solutions is the set of elements of order q of Fp
This set is a group since Fp is abelian.
Since q is prime, each element must have order q (or be 1).
Since they're the roots of X^q - 1, there's at most q elements.
So any alpha != 1 in that group generates a subgroup of q elements, which is the whole group itself
QED

[verbal cedar]

makes sense ty

[open mist]

yw, interesting question

Didn't do anything like that in well over a month or two

Nice refresher

Though I did spend like 15 minutes looking for a counterexample before attempting the proof lol

[verbal cedar]

haha

i shoulda known that the easiest solution would be just a basic group theory proof though lol
it keeps happening

[verbal cedar]

I think this question should be simpler but my brain is failing me

if $q$ is a prime and $p=q^2k+1$, then what can the remainder of $p\bmod{q^3}$ be such that $p$ is prime?

[sterile pumice]

nixxy nilpotent

[verbal cedar]

for q=2, the remainder can be 1,3,5,7
q=3 I think it's just 1 and 19?
and q=5 I think 1,51,101? not sure if 51 is valid...

ok so 51 is valid bc 51+125(8) is prime

is it all remainders of the form $q^2(2\ell)+1$?

[sterile pumice]

nixxy nilpotent

[verbal cedar]

for q odd i think

[ancient glacier]

Just saw a problem about showing $7 | 1+2^{2^n}+ 2^{2^{n+1}}$

[sterile pumice]

CoffeesPurple

[ancient glacier]

My approach was ||by induction and for induction step I factored as $(2^{2\cdot 2^n}+1-2^{2^n})\cdot (2^{2\cdot 2^n}+1+2^{2^n})$
Since second term is assumed true it shows that n+1 is divisible by 7. However this factoring took me lots of trial and error and|| im curious about other approaches people would take. I thought of an approach by trying to find patterns with bit multiplication. I also considered looking up modular arithmetic theorems to approach the question. Curious about other’s thoughts

[sterile pumice]

CoffeesPurple

[calm oak]

I just took the braindead approach

[sterile pumice]

suremark

[calm oak]

by inspection

[verbal cedar]

2 has order 3 mod 7 so yeah

2^n jumps from 2, 2^2, 2^4=2, 2^8=2^2, etc.

[simple trellis]

Is it just me or is elementary number theory not an early university topic

As in, it was only at the end of my second year there was even a mention of Gauss’s law of reciprocity

Even by itself the scope of elementary number theory is pretty small

Summarised by Fermat Euler theorem, Wilson’s theorem and reciprocity with Euler’s criterion and so on

[open mist]

It is just you. There's plenty of people who take it. It's true that there's not much content, but many people still see it in undergrad

It's also a great way of talking about finite groups, fields, and nonzero characteristics

[verbal cedar]

i think in some universities it appears much earlier than others. at my undergrad it was only available as a spring semester only upper division course. but imo it's relatively basic enough that a simplified (abstract algebra free version) could be taught at lower division (i'm sure they do that somewhere). i think it could replace linear algebra as a student's first proof based math course.

[verbal cedar]

but yeah this was pretty much the bullet points extent of that number theory course. plus primitive roots.

[wild mesa]

I need a hint

Prove 5|3^(3n+1) +2^(n+1), n>=1

[torn escarp]

are you allowed to use modular arithmetic?

[wild mesa]

No

[torn escarp]

that sucks lol

well, I guess you've gotta do something by induction, give that your best shot and show where you get stuck

[wild mesa]

Ok

[torn escarp]

I just solved it by induction, it's not toooo bad but might be tricky

maybe as a hint, I used the fact that 27=25 + 2 at one point

[wild mesa]

Oh i see

Thanks

[torn escarp]

Cool, you're welcome 👍

[errant otter]

How'd you use mod to solve this tho

[torn escarp]

well basically I just think of 3 as -i and 2 as i, then plug it in

$(-i)^{3n+1}+i^{n+1} = -ii^n + ii^n = 0$

[sterile pumice]

Merosity

[errant otter]

Wtfffffffffffff

[torn escarp]

basically that's what I'm thinking anytime I'm in a finite field, all the nonzero elements are roots of unity

[errant otter]

Bigbrain 😭

[torn escarp]

lol

just experience really

[verbal cedar]

3^3=2 so you have 3(2^n)+2(2^n)=0. thus, 3^(3n+1) +2^(n+1)=0 mod 5 so 5 divides it

whenever i see (n divides stuff) i usually go straight to stuff=0 mod n lol

[errant otter]

[lost yacht]

Please tell me you have a PhD cuz that’s diff

[runic token]

mero's actually just big brain asl

[torn escarp]

yeah i have a phd in elementary number theory

realistically if you spend enough time thinking about finite fields this will come natural to you I think

two relevant facts are:
Any finite subgroup of the multiplicative group of a field is always a cyclic group.
"The" algebraic closure of a field with p elements has its multiplicative group all the roots of unity with order not divisible by p

[wild mesa]

What about 24|2*7^(n)+3 * 5^(n)-5

So
$$
2 \cdot 7^{n}+3\cdot5^{n}-5=24c,c\in \mbb{Z}
$$

[sterile pumice]

oxil764

[wild mesa]

If i assume its true for n

But its not clear what to do here

Because these factors in the way

If try multoplying by 7 i get

$$
2 \cdot 7^{n+1}+21\cdot5^{n}-35=24c\cdot 7
$$

[sterile pumice]

oxil764

[wild mesa]

Then 7=2+5 and
$$
2 \cdot 7^{n+1}+3\cdot5^{n+1}+6\cdot 5^{n}-35=24c\cdot 7
$$

[sterile pumice]

oxil764

[wild mesa]

$$
2 \cdot 7^{n+1}+3\cdot5^{n+1}-5=24c\cdot 7-6\cdot 5^{n}+30
$$

[sterile pumice]

oxil764

[wild mesa]

But i cant factor 24

[wild mesa]

@mighty fable Can i ping you when i have a question?

[mighty fable]

Depends how interesting it is

If it’s silly computations or number theory problems like this please don’t

But if it’s like yesterday

Where you wanted to learn what open sets were

Then by all means please do

Though be aware I’m on vacation rn so it might be a while before I respond bc I don’t always have WiFi LOL

[errant otter]

[wild mesa]

Nvm im done here

[verbal cedar]

this is trivially true for even n (why?). if n is odd (say n=2k+1), then you can show it becomes independent of k and is also easily shown to be true.

[wild mesa]

I proved It with induction

And with the fact that d|ax+by and d|ax imply d|by

[verbal cedar]

that's fine. but you could have also noticed that 7^2 and 5^2 are one above a multiple of 24. god why are they asking you to do this without modular arithmetic it makes it a million times easier

[wild mesa]

Pset section 2.3 of elementary number theory by burton

[grand umbra]

there may be some mistake when I translated this sorry. Can someone help me solve this?

With $n\geq2$, given that $a_1, a_2,..., a_3 ∈ Z; p_1, p_2,..., p_3$ are distinctive prime numbers. Show that if $p_1|a_1 - a_2| = p_2|a_2 - a_3| = ... = p_n|a_n - a_1|$ then $a_1 = a_2 = ... = a_n$

[sterile pumice]

Atom

[grand umbra]

My take at this problem:

Let P be ${p_1}\cdot{p_2}...\cdot{p_3}$

Let f(n) be $\frac{P}{p_n}$

Let x ∈ Z be some integers

Hence:
$p_1|a_1 - a_2| = p_2|a_2 - a_3| = ... = p_n|a_n - a_1| = P\cdot{x}$,
$(a_1 - a_2) = ±xf(1)$
$(a_2 - a_3) = ±xf(2)$
...
$(a_{i} - a_{i+1} = ±xf(i)$
...
$(a_n - a_1) = ±xf(n)$

This implies: $(a_1 - a_2) + (a_2 - a_3) + ... + (a_n - a_1) = (a_1 - a_n) = ±xf(1) ±xf(2) ±...±xf(n-1) = P\cdot{x}(±\frac{1}{p_1} + ±\frac{1}{p_2} + ... + ±\frac{1}{p_{n-1}})$
$-(a_1 - a_n) = (a_n - a_1) = P\cdot{x}(±\frac{1}{p_1} ±\frac{1}{p_2} ± ... ±\frac{1}{p_{n-1}})$ (Since it's plus/minus)
But then: $(a_n - a_1) = ±xf(n) = ±x(\frac{P}{p_n}) = Px(±\frac{P}{p_n})$
$\implies ±\frac{P}{p_n} = ±\frac{1}{p_1} ±\frac{1}{p_2} ± ... ±\frac{1}{p_{n-1}}$

[sterile pumice]

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

[grand umbra]

My take at this problem:

Let P be ${p_1}\cdot{p_2}...\cdot{p_3}$

Let f(n) be $\frac{P}{p_n}$

Let x ∈ Z be some integers

Hence:
$p_1|a_1 - a_2| = p_2|a_2 - a_3| = ... = p_n|a_n - a_1| = P\cdot{x}$,
$(a_1 - a_2) = ±xf(1)$
$(a_2 - a_3) = ±xf(2)$
...
$(a_{i} - a_{i+1} = ±xf(i)$
...
$(a_n - a_1) = ±xf(n)$

This implies: $(a_1 - a_2) + (a_2 - a_3) + ... + (a_n - a_1) = (a_1 - a_n) = ±xf(1) ±xf(2) ±...±xf(n-1) = P\cdot{x}(±\frac{1}{p_1} + ±\frac{1}{p_2} + ... + ±\frac{1}{p_{n-1}})$
$-(a_1 - a_n) = (a_n - a_1) = P\cdot{x}(±\frac{1}{p_1} ±\frac{1}{p_2} ± ... ±\frac{1}{p_{n-1}})$ (Since it's plus/minus)
But then: $(a_n - a_1) = ±xf(n) = ±x(\frac{P}{p_n}) = Px(±\frac{P}{p_n})$
$\implies ±\frac{1}{p_n} = ±\frac{1}{p_1} ±\frac{1}{p_2} ± ... ±\frac{1}{p_{n-1}}$

[sterile pumice]

Atom

[torn escarp]

hmm interesting problem

Here's what I came up with:
Without loss of generality assume $p_n$ is the smallest prime that occurs, then $$|a_n-a_1| \le |a_1-a_2| + \cdots + |a_{n-1}-a_n|$$
Substitute in the fact that $|a_i-a_{i+1}|=\frac{p_n}{p_i}|a_n-a_1|$.
$$|a_n-a_1| \le \frac{p_n}{p_i}|a_n-a_1| + \cdots + \frac{p_n}{p_i}|a_n-a_1|$$
Multiply through by all the primes and divide through by $|a_n-a_1|$ explicitly assuming that it's nonzero:
$$p_1\cdots p_{n-1} \le (n-1)p_n$$
But since $p_n < p_i$ for all $i<n$, the sum of $n-1$ copies is less then the product of $n-1$ things bigger than it, which is a contradiction. So it must be that $|a_n-a_1|=0$ which implies all the differences are $0$.

[sterile pumice]

Merosity

[verbal cedar]

prove that if $p,q$ are odd primes and $p\eq1\bmod{q}$ then
$$x^{q-1}+x^{q-2}+\ldots+x+1$$
splits over $\bF_p$

[sterile pumice]

nixxy nilpotent

[verbal cedar]

I'm stuck and not sure where to start. i don't think I can quite do induction can i? any help appreciated

i also need to prove that
$$x^{q-1}+bx^{q-2}+\ldots+b^{q-2}x+b^{q-1}$$
splits over $\bF_p$ as well.

[sterile pumice]

nixxy nilpotent

[verbal cedar]

not sure if it's easier to start with b=1 and use that to prove the general case

[torn escarp]

second result follows from a substitution, if you call the first f(x) then the second if b^{q-1} f(x/b)

this happens to have a name btw, homogenization

[torn escarp]

I think you can probably squeak the first result out by simplifying the geometric series and using fermat's little theorem, maybe there's some extra details to iron out

[verbal cedar]

by geometric series do you mean like writing
1+...+x^(q-1)=(1-x^q)(1-x)^(-1)?

[torn escarp]

yeah

I think I have a full proof, have just sketched it out a bit, might have used a slight trick too, it's debatable

[verbal cedar]

I'd be curious to see it
the original problem came from trying to show x^q-1 splits over Fp so I'm not sure how to proceed

[torn escarp]

sure, you know x^{p-1}-1 has all elements except 0 as factors in Fp right

actually let me give a hint instead of outright answering it

$$\frac{x^{ab}-1}{x-1} = \frac{x^{ab}-1}{x^a-1}\frac{x^a-1}{x-1}$$

[sterile pumice]

Merosity

[torn escarp]

notably it shows that the polynomials with integer coefficients on the right divide the polynomial on the left

in case it's not clear, suppose you know the polynomial on the left splits entirely - use x^(p-1) - 1

[verbal cedar]

so using that
1+x+...+x^(p-2) splits? into (x-2)...(x-(p-1)) im guessing.
then that equals
(1+x^q+...+x^(qk-1))*(1+x+...+x^(q-1))
which is something times the desired sum. the desired sum divides something that splits, so the desired sum splits?
is that the basic idea or did i fuck up somewhere

[torn escarp]

yeah that's it

[verbal cedar]

cool yeah that works thanks

[torn escarp]

yup you're welcome

[quaint gate]

so the answer to this is 6, but i can't figure out the more clever (formal?) way of doing this, any hints?

[open mist]

just do it honestly

3, 7, 31, 211, 2311, 30031=59*509

[static cedar]

Ive concluded upto here

Now I just have to prove, it's a integer for some a,b any idea?

[torn escarp]

yeah I don't think the point of this is to find a clever answer, I'd say the point is to weed out a misconception people sometimes have over euclid's proof of the infinitude of primes

[torn escarp]

see how much progress you can make if a=1 and b=1

[static cedar]

[sterile pumice]

_basudev

[static cedar]

This ig?

[torn escarp]

guess again

[static cedar]

I mean this should be right..

Is it not?

[torn escarp]

you have a p^-1 what is that

how'd you come up with this formula

[sterile pumice]

_basudev

[static cedar]

So let me explain

[static cedar]

.

Here

[torn escarp]

your original formula isn't wrong

but what you're doing by plugging in is horrendously wrong

[static cedar]

You said try seeing it for a=b=1

[torn escarp]

start from a=1, b=1 then what's n

[static cedar]

N=2

[torn escarp]

you're not thinking about what you're writing, you're mindlessly plugging and chugging without thinking what you're putting down

[static cedar]

Alr cool

Let me explain how I come up to that

So I used this fact

Since the number of divisor will be (a+1)(b+1)

The A.M =

[sterile pumice]

_basudev

[static cedar]

Applying the Expansion I get

Now let's test for a=b=1

[sterile pumice]

_basudev

_basudev

[static cedar]

This is true... for all distinct prime except 2...ig

How do I continue from here now?

[torn escarp]

idk what have you tried

[static cedar]

[torn escarp]

you tried nothing and are all out of ideas? i hope not

[static cedar]

I tried what you said dude

Yes, I'm out of ideas dude that's the reason why I'm here for help

[west glade]

it would be ideal if this was already an integer. what would you have to show for that

[static cedar]

For that I've to show it should be divisible by 4

[static cedar]

If you're talking about this

[west glade]

I am

[static cedar]

.

The only even prime is 2

2+1= 3(odd)
Odd+1 = even

So

2 | odd+1, 2 | odd+1

4 | (odd+1)(odd+1)

[west glade]

great so if both p and q are odd then you are done. so now you reduced the problem to either p=2 or q=2

[static cedar]

Alr let's take q=2

we get 

{3×(q+1)}/4

So, 4 doesn't always divides "q+1" for some prime "q"

let's take q=2

we get 

{3×(p+1)}/4

So, 4 doesn't always divides "p+1" for some prime "p"

[west glade]

yes for p=2 or q=2 you cant just choose a=b=1. but maybe some other choice

[static cedar]

Yes, so what do I conclude from here...

.

Can I say?

For if p,q are odd then a=b=1 gives us an integer...
For p = 2 or q = 2 some other value of a,b gives us integer

[static cedar]

Or perhaps

For if p,q are odd there exits a,b such that it gives us an integer...
For p = 2 or q = 2 some other value of a,b gives us integer

[grand umbra]

wow, thanks!

[fickle trout]

Are there infinitely many nontrivial (i.e. not just scalar multiples, permutations etc) positive integers $a, b, c, x, y, z$ so that $$a+ b + c = x + y + z$$ and $$\frac{1}{a} + \frac{1}{b} + \frac{1}{c} = \frac{1}{x}+ \frac{1}{y}+ \frac{1}{z}$$

[sterile pumice]

الله أكبر

[fickle trout]

I've been stuck on this for a while now at first I tried to take the reciprical of the second equation which gives you terms that resembles coefficients of a cubic(via VIeta formula) but that didnt go anywhere

then I tried to use an argument with arithmetic and harmonic mean which also didn't go anywhere

I was told that this problem can be reduced to a subtle number theory problem

any hint will be appreciated

[torn escarp]

Yeah, you're welcome

[open mist]

Look at each factor mod 3. One must be zero
I'd do it by contradiction

[neon pumice]

thanks

[verbal cedar]

pigeonhole principle. nice

[wild mesa]

If a is any integer and n is a positive integer, prove gcd(a,a+n)|n

Ik there exists integers x,y such that gcd(a,a+n)=ax+(a+n)y=ax+ay+ny

[still flare]

Hint: divisors of x and y are also divisors of integer linear combinations of x and y

[wild mesa]

Ik

[still flare]

Great, then this should be a breeze for you

[wild mesa]

Ah

Its trivial

[errant otter]

is that, um, bezout identity or smth

[still flare]

No

[errant otter]

crap

[still flare]

It holds in any ring.

Prove it and you will see how simple it is

[foggy linden]

But it's still also known as Bezout identity.

[still flare]

No it’s not

There’s no identity here

Bézout is saying something much stronger

[wild mesa]

,w bezout identity

[sterile pumice]

Results provided by WolframAlpha

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

Requested by oxil764

[wild mesa]

I didnt know that had a name

[open mist]

Frenchman spotted ?

[foggy linden]

Ironically, I learned that today itself.

That it has a name.

[still flare]

No I just like writing peoples’ names correctly

[open mist]

damn

[still flare]

But I see that space before the question mark

Frenchie spotted

[open mist]

imagine writing Weierstrass the german way

[errant otter]

indeed

[errant otter]

imagine NOT

[open mist]

it's just cleaner

[still flare]

Sure thing nerd

[open mist]

I guess I gotta accept the nerd title now, being a CS major

[errant otter]

so like, divisors of x and y are divisors of nx and cy?

[still flare]

No

I mean

If n | x and n | y then n | ax + by

[errant otter]

ah

mmmmmm

[wild mesa]

Then gcd(a,a+n)=a(x+y) + ny and because It divides a, it must divide n

[still flare]

Even simpler

gcd(a, a+n) divides a and a+n by definition

Therefore it divides a+n-a = n

You do not need Bézout.

[errant otter]

damn

[wild mesa]

Clever

[tawny bobcat]

Any good recommendations for number theory books?

[still flare]

I think Jones & Jones' book Elementary Number Theory is a good start

[wild mesa]

Burton number theory

[tawny bobcat]

Danke

[reef plinth]

Hwo

Do

I start

[torn escarp]

idk, I'm just trying stuff like reducing mod 2 and reducing mod x

when we reduce mod x we get y!=1 mod x. If we assume x<=y then it would make x | y!, so y!=0 mod x, contradiction. So must be that x>y

dunno just keep trying random ideas and see where they lead

[reef plinth]

🤔

[reef plinth]

Ok

[torn escarp]

this is a bit whacked out maybe, $$x^y=-1 \mod \prod_{p\le y}p^{\lfloor \log_p(y)\rfloor}$$

[sterile pumice]

Merosity

[torn escarp]

dunno if that's useful to us, just taking the idea that for each $n\le y$ we have that $x^y=-1 \mod n$ and then I'm just clustering up all that info together with the CRT

[sterile pumice]

Merosity

[torn escarp]

oh, I should also say that product of p<=y means I'm taking a product only over primes <= y

[grim token]

How can I show that if $a,b\in\mathbb{Z};;2|a,a|b$ and $b|2 \implies a=b=2$?

[sterile pumice]

schoolunchbug

[still flare]

What you say is not true!

For example it could be that a = b = -2.

[open mist]

For positive numbers, it's sufficient to note that x|y means x <= y, that simplifies things

[torn escarp]

you could write 2|a as a=2x for some integer x. similarly b=ay, and 2=bz then plug them all into each other to get 2=2xyz. Then dividing out 2 you get 1=xyz. From there it looks like there are 4 ways to solve that depending on how you distribute +1 and -1 in there.

[grim token]

thank you!

[grim token]

Then must be a mistake from the author

[verbal cedar]

my guess is that they specified positive integers or used N instead of Z. but we cant know without seeing the problem

[torn escarp]

kind of fun offshoot of this problem, if you have $a_0 \ne 0$ and $a_i|a_{i+1}$ with it periodic like: $a_n=a_0$, then how many solutions are there?

[sterile pumice]

Merosity

[open mist]

Doesn't it have to be fixed between 2 values a0 and -a0 ?
Still infinitely many solutions though

Since |an| is increasing and periodic

[still flare]

for a specific n

[open mist]

What ?

Ah ok

Periodic of period n

[still flare]

and, ig, for a specific a_0

[open mist]

The need to avoid smaller periods makes it at least pretty difficult I think

[still flare]

It's not hard.

[open mist]

Requires more thought than I'd probably be able to give it given how many drinks I took

[torn escarp]

maybe work it out in the n=2, 3, 4 case and see if you can find the pattern

[open mist]

n=2: + +
n=3: + - +
n=4: + - + + or + + - + or + - - +
Well

It's always an insert ?

[torn escarp]

I think you missed a couple cases

[open mist]

Called it

[open mist]

Though I'm not sure what I missed

[torn escarp]

I don't think you have to avoid any smaller periods

like n=2 you have ++ and -- (if I understand your notation correctly)

[open mist]

I said wlog a0 = 1 = +

[open mist]

Then any pattern works and it's kinda lame

[torn escarp]

wdym any pattern works

[open mist]

then you can have any sequence of n-1 terms and call it periodic of period n

[torn escarp]

any? like 2,3,4 would work?

[open mist]

any sequence a0,.., an-1 can be extended to be n-periodic

[open mist]

I mean ofc it's still just + and -, so you have 2^(n-1) possibilities

[still flare]

Unless a_0 = 1 🤓

Wait

I meant 0

lmao

[torn escarp]

good thing I specified that 😌

ok now generalize to the arbitrary ring of integers of a number field now... lmao

I'll take care of the case when the unit group has rank 0, you take care of the rest

[open mist]

Well don't you only need the number of invertible elements ?
Since divisibility is still almost an order ?

[torn escarp]

yeah, rank 0 I'll just say there are d distnct units, so there's d^{n-1} solutions

idk I haven't really thought this through

[open mist]

I don't know what "rank of the unit group" is so ...

[torn escarp]

the units are the invertible elements of the ring

and the rank is basically the number of elements that are invertible but generate a subgroup iso to Z

that's phrased poorly

so you have your standard roots of unity, those are finite order elements

[open mist]

So of infinite order ?

[torn escarp]

yeah, the rank is the number of generators you need for this infinite subgroup of units

[open mist]

How does that match ?
Wait isn't it 0 or infinite

[open mist]

By this definition

[torn escarp]

see this comment

[open mist]

Yeah

[open mist]

So that's the definition?

Cause I only took basic group theory

[torn escarp]

maybe it's better to just give an example

let's say u and v are units, then you have ..., u^-2, u^-1, 1, u, u^2, u^3, ... and 1, v, v^2, v^3, ... and neither of these sets of integer powers of u and v have any nontrivial intersection, then the rank is at least 2

the unit group is going to be isomorphic to some finite group with a direct product of finitely many copies of Z

the number of copies of Z is the rank

[open mist]

Assuming it's of finite type

i.e. the generating set is finite

[torn escarp]

what's of finite type

[open mist]

French vocab

[torn escarp]

oh I'm not assuming but I see why you say that

Dirichlet unit theorem proves this is finitely generated

if I recall it follows from doing some fundamental cell shenaningans with the Minkowski bound

[open mist]

This is getting out of hand

It's interesting

[torn escarp]

point is, it was proven to be finitely generated yeah good point though

also if we want to get even crazier with the original assumption we might start devolving away from number fields which have number rings that are dedekind domains and start looking at more general cases and recast the divisibility criteria in terms of ideals and try crying about class numbers or whatever

not something I'm that familiar with

[open mist]

This is getting pretty out of hand

I don't know yeah much at all about ideals

[torn escarp]

but maybe a simple enough vehicle that's "natural" enough to suck us (me?) in

[open mist]

Besides the potential for a ring to be principal, to have a gcd and all that

[torn escarp]

the name 'ideal' I believe originally came from them being thought of as "ideal numbers"

[open mist]

Gonna have to read a group theory group at some point

[open mist]

Was stuff from Gauss

To solve stuff with radicals

I think

[torn escarp]

came from a lot of people, I'm just talking about the etymology

I think it might have been kronecker? idk who it was

[open mist]

You mean he did more than a symbol? /s

[teal zealot]

yeah kronecker iirc

[torn escarp]

like if you start thinking of them as ideal numbers you can get away with a handful of operations on ideals as if they are numbers

[teal zealot]

came about in non PIDs i think?

[open mist]

I have yet to find a nontrivial example (besides stuff like Z^2 x Z/nZ)

That's where my mind left

[torn escarp]

yeah I can give an explicit example

[teal zealot]

if you want a nice example of non principle ideal i like to use (2, x) in Z[x]

[torn escarp]

I think Z[sqrt(2)] has 1+sqrt(2) and all its powers are units

so Z/2Z part is {1, -1} and the Z^1 part is <1+sqrt(2)>

1+sqrt(2) has norm -1, so should be good I think

you can tell it's a unit cause it has norm (1+sqrt2)(1-sqrt(2))=-1, so not too hard to see the inverse of 1+sqrt(2) is -1+sqrt(2) there

you can keep raising it to powers and prove it'll have larger coefficients too

[open mist]

Yes

Starting to remind me this is potentially stuff I saw and forgot

[torn escarp]

yeah, it's not something I think about much so its good for me to say some stuff lol

[open mist]

I feel like I'll regret becoming a CS major if I don't keep studying math

[torn escarp]

idk, in some sense you're more free to study whatever you want at your own pace in math now

[open mist]

Yes

But will I find the strength

Cause then the ressources kind of need to be self-motivated

But I def wanna learn more group theory, Galois theory, complex analysis

Some set theory

[torn escarp]

my approach is just, I do it if I want to do it, and I don't if I don't actually want to do it, but I can see how that doesn't work for everybody

I get a bit of an itch if I just sit around doing nothing for too long you know

[open mist]

Yes

[wild mesa]

If there exists integers x,y such that ax+by=gcd(a,b), show gcd(x,y)=1

What i thought so far

Let d=gcd(x,y)

then d|ax+by

I wanna show somehow that d=1 and there are integers q,p such that 1=xq+yp

[still flare]

Hint: a, b have a common factor, namely...

[wooden glen]

Write a=Ad, b=Bd, then your assumption is Adx+Bdy=d. Divide through by d.

[wild mesa]

Ah i get it

gcd(a,b) divides a and b

So a/gcd(a,b) and b/gcd(a,b) are integers

Hence 1= (a/gcd(a,b))x+(b/gcd(a,b)y

Thus d=1

Right?

[wooden glen]

Well yes, if you redefine d on the fly to mean gcd(x,y) instead of gcd(a,b) ...

[wild mesa]

Thats what i defined d to be initially

[wooden glen]

Sorry, it's me who cannot read.

[wild mesa]

Thats why i thought this was weird ig

[wooden glen]

Yeah, I see that was confusing because I thought d was gcd(a,b)...

[hardy ember]

not sure where to put it, but are there any nice/cool properties of a prime * prime + 1

[torn escarp]

are the primes the same or distinct?

[hardy ember]

distinct

[torn escarp]

it's a perfect square iff they're twin primes ig

I assume you're more interested in things relevant to cryptography since it's nearly a semiprime

[wild mesa]

I need to show If a is odd then gcd(3a,3a+2)=1
If a is odd, the a=2k+1 for some integer k. I know gcd(a,b)=1 iff 1=ax+by for some integers x and y.
Let d=gcd(3a,3a+2)
So d=3(2k+1)x+(3(2k+1)+2)y
d=6kx+3x+6ky+5y
d=6k(x+y)+3x+5y
If i want to show d=1, i have to make x+y=0 and 3x+5y=1
But the solution to that system is (-1/2,1/2), which is not integer. This is where im stuck

[torn escarp]

I'm thinking I'd try to use the euclidean algorithm directly, like gcd(3a,3a+2) = gcd(3a,2) since you can subtract 3a from 3a+2

[wild mesa]

euclidean algorithm?

[wooden glen]

The 3 seems like a red herring: What you're really showing is that if n is odd then gcd(n, n+2)=1.
n=3a for a odd is just a particular case of odd number.

[verbal cedar]

eh more like just gcd(n,m)=gcd(n,m-nk)=gcd(n-mk,m)
you can use that to simplify gcd problems (and that principle underlies the euclidean algorithm)

[wild mesa]

but i should be able to solve this without the euclidean algorithm

[verbal cedar]

that's what i'm saying

just use those gcd properties to reduce the problem to gcd(3a,2)

[wild mesa]

ill look into that later

time to game

[verbal cedar]

i'm just explaining that those properties are what the euclidean algorithm is based on

[wild mesa]

but thanks y'all

[wild mesa]

I didnt see that in the book so far so i proved it

But im still stuck

14.c.First we have to prove that If $d=\gcd(a,b)$, Then $d=\gcd(a,b+na)$ for any integer $n.$Because $d=\gcd(a,b)$, It follows that there are integers $x,y$ such that $d=ax+by$. By adding and subtracting $nay$, we get
$$
d=ax+by+nay-nay
$$
$$
d=a(x-ny)+(b+na)y
$$
Because we know $d|a$ , and and $d$ divides a linear combination of $a$ and $b+na$, it follows that $d|b+na$. But notice If $c$ is a divisor of $a$ and $b+na$, then $c|d$. Therefore by definition,$d=\gcd(a,b+na)$.
Now let $d=\gcd(3a,3a+2)$, where $a$ is odd. So $a=2k+1$ for some integer $k$.
By our previous result,
$$
\gcd(3a,3a+2)=\gcd(3a,2)
$$
So there are integers p,q such that
$$
d=3ap+2q
$$
$$
d=3(2k+1)p+2q
$$
$$
d=6kp+3p+2q
$$

[sterile pumice]

oxil764

[wild mesa]

Is this right?

I still cant find integers such that d=1

Wouldnt p have to be 0 and force q to be 1/2, a non integer

[wooden glen]

If a=2k+1, then try (1+k)a - k(a+2)

[shy wave]

Well, 3a = 3(2k+1) = 3+3k*2
So, gcd(3a, 2) = gcd(3+3k*2, 2) and you could apply your newfound property again

[wild mesa]

Now let $d=\gcd(3a,3a+2)$, where $a$ is odd. So $3a$ is odd,hence $3a=2k+1$ for some integer $k$.
By our previous result,
$$
\gcd(3a,3a+2)=\gcd(3a,2)
$$
So there are integers p,q such that
$$
d=3ap+2q
$$
$$
d=(2k+1)p+2q
$$
$$
d=2kp+p+2q
$$
Now Let $q=-k$ and $p=1$
So
$$
d=2k+1-2k=1
$$
Therefore $\gcd(3a,3a+2)=1$

[sterile pumice]

oxil764

[wild mesa]

I think that completes it

Right?

[verbal cedar]

i don't think you can just set values for p and q. you know they exist, but you don't know what they are necessarily.

[verbal cedar]

i think an easier way is just to say that 3a=2k+1. then gcd(3a,2)=gcd(2k+1,2)=gcd(2k+1-2k,2)=gcd(1,2)

or you can say that a=2k+1, then do gcd(3(2k+1),2)=gcd(3(2k+1)-2(3k+1),2). same thing

idk if you need bezout for this at all

funny enough, by subtracting off multiples from each element, this is basically just doing the euclidean algorithm lol

[wild mesa]

Honestly i was using It because It is pretty much the only tool i have so far

Next section is on the euclidean algorithm

[wild mesa]

But in this case, If i can find values of p and q that give me 1 then It means the gcd is one

[verbal cedar]

yes, that is absolutely true. if you can find an integer linear combination that gives one, then the numbers must be coprime.

so you could do the argument like this
[3(2k+1)]1+2(-(3k+1))=1 therefore gcd(3(2k+1),2)=1.

or go back to the beginning i guess
3(2k+1)(2+3k)-3(2k+1)+2=1

[wild mesa]

So is my proof valid?

[verbal cedar]

this is how you can get that using the euclidean algorithm

[verbal cedar]

so is your proof what?

[wild mesa]

Srry

[wild mesa]

I meant valid

[verbal cedar]

a^2=7+2b^2
clearly a=±3,b=±1 are solutions, but how can I find out if there are any others?

[torn escarp]

sorta boils down to finding the units in Z[sqrt(2)]

I believe 1+sqrt(2) generates all of them but since (1+sqrt2)(1-sqrt2) = -1 you'd want to square that and then multiply or divide your found solution of 3+sqrt(2) by it

I think probably i am not saying the essential fundamentals of this too, like how we use the norm function and Dirichlet's unit theorem

I think there's also a way to get the solutions via continued fractions/pell's equations discussion too so maybe that's more elementary/easier

maybe someone can say this more coherently than I just did but in short, x = (3+sqrt(2))(3+2sqrt(2))^n multiplied by its conjugate should get you all solutions

[exotic bone]

1+sqrt(2) can't generate all of them because it's positive

It is the fundamental unit though.

[wild mesa]

Can i get some feedback

Prove that if $a$ and $b$ are odd integers, then $8| (a^2 -b^2)$.
Let $a=2k+1$ and $b=2n+1$,where $k,n\in\mathbb{Z}$.
Then $(a^2-b^2)=(a+b)(a-b)=(2k+2n+2)(2k-2n)$
And we have
$$4(k+n+1)(k-n)$$
If $k$ and $n$ are both even or both odd, then $k-n$ is even and by factoring we conclude $8|(a^2-b^2)$.
Without loss of generality, assume $k$ is even and $n$ is odd. So $n+1$ is even and $k+n+1$ is even too, hence by the same as above,$8|(a^2-b^2)$. Therefore it is always the case that $8|(a^2-b^2)$.

I just wanna know if I am writing correctly

[sterile pumice]

oxil764

[loud maple]

Yes, what you have done is correct

[wild mesa]

Thanks for the feedback!

[white lion]

So we know that for p prime and $(p,10) = 1$ there exists integers k and y such that $yp = 10k +1$ this is trivial to show, Im trying to prove the following, Let $n = 10a + b$. if p is a prime with $(p, 10) = 1$ then $p|a$ if and only if $p|a - kb$. I did the following, suppose $p|a$, since yp = 10k + 1 (since this is of the form 10a + b and $p|a$) then $p|k$ then it follows $p|kb$ and finally $p| a - kb$. I am confused about it because since yp is of the form 10a + b and we know then that would neccesarily imply that 1 is a multiple of p which is impossible.

[sterile pumice]

jayz

[patent acorn]

how did you get that p|k?

[white lion]

if we assume p|a for any integer of the form 10a + b. then yp = 10k + 1 and p|k

[patent acorn]

...oh so you're assuming that for all integers of the form 10a+b, p|a?

in that case what you have is a proof by contradiction that no prime number can have that property

[torn escarp]

I think what I described there addresses that

[sacred junco]

I don't really get the example why is p ≠1 mod q^2 important?
Could someone give me an example?

1.4.3 example

[patent acorn]

well if p = 1 mod q^2, then p-1 = 0 mod q^2, so (p-1)/q is divisible by q, and then q^-1 mod (p-1)/q doesn't exist

[sacred junco]

Aaah

Make Sense, thanks

[errant otter]

Three non-negative integers A, B, and C are given such that A <= B <= C. You can either subtract 1 from two of the integers of your choice, or subtract 1 from all of the integers. If if A + B +C = 2x + 3y for some nonnegative integers x and y, and C <= A+B, does it guarantee that by applying these 2 operations (as many times as we want/need to), we can get all 3 integers to 0?

[patent acorn]

yes, ||subtract one from all of them A+B-C times; then A is C-B which is nonnegative, B is C-A which is nonnegative, C is 2C-A-B >= 2C-2B = 2(C-B) which is nonnegative. now subtract C-B from A and C, and subtract C-A from B and C, now they're all zero||

[errant otter]

damn

that's ingenious 😭 how

[patent acorn]

well if C is A + B, then subtracting A from A and C, and subtracting B from B and C, solves it

so we want to reduce anything else to that easy case

if C is less than A + B, then the amount that it's less will go down by 1 every time we subtract 1 from each integer (because A+B contains two integers and C contains 1)

[errant otter]

mmhm...

[patent acorn]

then once you've had that idea it's just working out what the formulas actually are and how to verify that you're not taking an action a negative number of times

[errant otter]

.... the rlly rlly funny thing is that

the min amt of moves u need to take to get all of these 3 numbers to 0, assuming that they can be reduced tot aht

is literally jsut the largest number

[blazing mist]

Does $\sum_{n=1}^{k-1}(\zeta_{k}^{n}) = -1$ , where $\zeta_{k}$ is a primitive nth root of unity?
I know that $\sum_{n=0}^{k-1}(\zeta_{k}^{n}) = 0$. So simply subtracting 1 on both sides yields $\sum_{n=1}^{k-1}(\zeta_{k}^{n}) = -1$.

[sterile pumice]

Sapphire

[verbal cedar]

yeah, by the exact logic you described

[verbal cedar]

what's the source of this?

[sacred junco]

@verbal cedar Abstract Algebra Paul Garrett

[blazing mist]

Is there any way to figure this out without using the equality fact?

[white lion]

@blazing mist Ask in #advanced-number-theory

I don't usually allow people who violate servers rule to stay for long but since your new here ill let it slide

[blazing mist]

uh, sorry..

[verbal cedar]

well if you prove the equality, then it's a trivial result. you just subtract 1 from both sides.

[torn escarp]

yeah, there are two ways you could go about proving it, you could:
evaluate it as a geometric series directly
or
call the original sum S, multiply by zeta_k, and see that zeta_k * S = S and since zeta_k != 1 it means S=0

[pale fjord]

https://www.youtube.com/watch?v=6lTUKDq5v7Q

i dunderstand the sequence substitution

from 5:40

[sacred junco]

Why is this true (Grey circle)

[eternal shoal]

Every positive integer 1 ≤ m ≤ n has a greatest common divisor with n. So when you take the union of the S_d, each m will be in (exactly) one of the S_d

[analog onyx]

is there a special name for the even number between two twin primes? or like what should i call this number if i wanted to reference it for arbitrary twin primes

[sacred junco]

Thank you

[buoyant mason]

#help-13 message lol someone else asked about this too (and it is resolved there)

[torn escarp]

Idk, their average? I think since you have 6n+-1 as the primes you can refer to it directly as 6n so not super necessary to name it

[analog onyx]

fair enough

[wild mesa]

If $\gcd(a, b) = 1$, then $\gcd(ac, b) = gcd(c, b)$.
By hypothesis, there exists integers $x,y$ such that $1=ax+by$. Let $d=\gcd(ac,b$). So there are integers $p,q$ such that $d=acp+bq$.
Now Let $n|b$ and $n|c$. So $n$ divides any linear combination of the two, hence $n|d$. Thus $d=\gcd(c,b)$, by definition.

[sterile pumice]

oxil764

[wild mesa]

Is this wrong?

Because i didnt really have to use the hypothesis

[still flare]

Yes, it is wrong.

[wild mesa]

What did i do wrong?

[still flare]

Your final conclusion that d = gcd(c,b) is unjustified. You need to actually prove not only that it is greater than all common divisors of b and c, but also that it is actually a common divisor of c and b!

[wild mesa]

Ah

That makes sense

But if I prove that it is a common divisor indeed, would the proof be right?

[still flare]

If!

[wild mesa]

Ok I'll so that

Thanks

[still flare]

Hint: show that every common divisor of ac and b is also a common divisor of c and b, and vice versa.

[wild mesa]

Why do i need to show the converse?

This is what i came up with

If $\gcd(a, b) = 1$, then $\gcd(ac, b) = gcd(c, b)$.
By hypothesis, there exists integers $x,y$ such that $1=ax+by$. Let $d=\gcd(ac,b$). So there are integers $p,q$ such that $d=acp+bq$.
We know $d|b$ by definition of $d$.
Notice that If $d|b$ and $d|cx+by$ for arbitrary integers $x,y$, then $d|c$, so $d$ is a common divisor of $c$ and $b$.
Now Let $n|b$ and $n|c$. So $n$ divides any linear combination of the two, hence $n|d$. Thus $d=\gcd(c,b)$, by definition.

[sterile pumice]

oxil764

[wild mesa]

Doesnt this show its a common divisor of b and c as well?

[still flare]

This proof is still insufficient

[wild mesa]

Why?

[still flare]

You have said:

Notice that If $d|b$ and $d|cx+by$ for arbitrary integers $x,y$, then $d|c$,
so $d$ is a common divisor of $c$ and $b$.
But you (1) do not explain why the first line is true, and (2) do not prove that the assumption of the first line is true.

So your conclusion, the second line, is completely unjustified.

I think you know what a correct proof looks like so I don't want to keep pointing out these errors.

I think you should read my hint again and think about it a bit.

[wild mesa]

Well d|b by definition of d and

Oh i dont think i showed the Second assumption

[wild mesa]

Ok

[wild mesa]

So this means they share the same set of divisors, so the gcd of on is the gcd of the other, right?

$$
1=ax+by
$$
$$
c=axc+bcy
$$
Then $d|c$ because c is a linear combination of ac and b

[sterile pumice]

oxil764

[wild mesa]

So that does it ig

[still flare]

Yup

[wild mesa]

Thanks!

[thick panther]

hi
im not quite sure how to go about (d), could i get a starting point please?

[spiral flame]

The order of such an $x$ is $8$. Hence $8 \mid p-1$ which is a contradiction since $p$ is NOT of the form $8n+1$.

[sterile pumice]

RickC137

[thick panther]

OH that was fast

thank you very much sir

[fervent grove]

Let $p$ be a prime. For given nonzero $a,b,c\in\mathbb Z/p\mathbb Z$, define
[n(a,b,c)=#\left{(k,\ell)\in(\mathbb Z/p\mathbb Z)^2:ak^2+b\ell^2\equiv c\pmod p\right}.]
I think it's the case that $n(a,b,c)$ is independent of $c$ (as long as everything is nonzero). How do I see this?

[sterile pumice]

dfoiler

[fervent grove]

change of variables shows that n(a,b,c) at most depends on whether or not c is a square, but I do not see how to complete the argument quickly

[fervent grove]

I think I see an argumeny by explicitly computing n(a,b,c) (roughly speaking, it suffices to determine how many x have x^2-a equal to a square where a is constant)

so I guess I'm hoping for a proof which does not explicitly compute n(a,b,c)

[torn escarp]

yeah I think I have it for the most part, I'll go ahead and divide through by a and write -b/a=d and suppose that d is not a square in $\mathbb{F}p$. Then the norm function from $\mathbb{F}{p^2} \to \mathbb{F}_p$ is $N(x)=x*x^p$. If we exclude 0, then we can think of it just as a homomorphism of the multiplicative groups and since an element of order $p^2-1$ will be raised to the $p+1$ power, it is still order $p-1$, which means this map is surjective. So then Lagrange's theorem partitions it out into equal sized cosets, which is what we wanted to prove.

[sterile pumice]

Merosity

[torn escarp]

I didn't end up using z=x+sqrt(d)y at all I realize I was doing some scratch work figuring it out and just typed up some useless stuff there lol whoops

it's funny how $x-\sqrt{d}y = (x+\sqrt{d}y)^p$ by frobenius so I let myself go down a silly path prior. Actually I guess the thing I did would only be for when d is not a square, if it does factor we're not in a field extension, idk I just assumed that would be easier I'll worry about that later lol

[sterile pumice]

Merosity

[torn escarp]

I guess nothing happened since then here, but I just came back to thinking about the case when -b/a is a quadratic resudue, then it's of the form x^2-r^2y^2=c and we might as well absorb r into y for convenience and have (x+y)(x-y)=c and we now have uv=c with u=x+y and v=u-v. Simply fix v in F_p and then this determines u=c/v. Invert the system of linear equations for x, y again for an explicit solution, although for the sake of counting solutions we have exactly p-1 possibilities now, so that wraps it up.

[fervent grove]

oh yeah this is essentially the combinatorics I had in mind when I sent this message

[fervent grove]

I mean this message here

the case where d is non-square seemed harder, but rearrangement allows combinatorics still

the lagrange's theorem approach is better though

thank you

[torn escarp]

cool yeah, you're welcome. Also for fun, I think these proofs also generalize to arbitrary finite fields, but haven't thought it through to check. I'm also slightly interested in how far this sort of proof can be pushed to other things too since the fact that I used the norm as a group homomorphism suggests we might be able to get more milage from it if that interests you

actually I have to dig but since it was brought up in #advanced-number-theory I am pretty sure I know a way to count the points with gauss sums and a fourier transform with that, but I'm busy at the moment so I'll come back if you're interested in that and I can remember how that goes.

[fervent grove]

uh

my original question was one of Gauss sums, which I then translated into point-counting and asked here

kind of at least

:/

but like I genuinely wanted a combinatorial solution to the combinatorial problem

[fervent grove]

also yes this works for finite fields

nothing in the proof changes

I am of the opinion that it would be rather difficult to write down an algebraic statement which works for finite fields of prime order but not of general prime-power order :/

[torn escarp]

yeah I think you're right, I just didn't want to think it through, easier to just give the disclaimer lol

[astral grove]

is this correct?

[loud maple]

Yes

[astral grove]

Okay thanks !

[little kelp]

am a bit confused if im understanding the problem correctly

is this just asking me to use induction to prove that this is true? just formulated weirdly?

like would this be valid in that case? or am i misunderstanding something

[open mist]

that's not really using induction
Rather, letting Sn be such that a^n - 1 = (a-1) Sn, you use Sn rather the the ...
Then a^n - 1 = a^n - a^(n-1) + a^(n-1) - 1 = a^n - a^(n-1) + (a-1)S(n-1) and work from there

[little kelp]

sorry i am confused on what youre going for there, wym work from there?

[open mist]

Nvm I misread the ...
That's actually good
My bad

[little kelp]

If im checking inequality statements with induction

do i need to like go step by step in finding bigger and bigger functions or something like that

or can i just check if the desired form holds the correct inequality? like i did under the "need to check if true"

like is it necessary to rewrite the expression into the deisred form step by step

[leaden stream]

how does the last inequality follow from the previous ones?

typically it's bad form to jump to the final answer, the whole point of a proof is to show the reader why this holds. Skipping huge chunks of reasoning doesn't do that.

[dusky trench]

Is there a name for composite numbers whose prime numbers in their prime factorization all have exponent equal to 1?

[potent torrent]

Squarefree

[little kelp]

do you mean jump in this step?

[leaden stream]

no, that's what you should be trying to prove. How does the rest of the inequalities imply the last one?

[native fog]

I don't know if this is the right channel for this, but does anyone here know sth abt the Continuum Hypothesis and how it was proven? I'm doing a school project on it and I'm kind of stuck at the part how it got proven that it wasnt provable. How Gödel and Cohen did that.

[errant otter]

#proofs-and-logic and iirc it's true iff zfc is consistent?

[eternal shoal]

no

It's independent of ZFC

[errant otter]

Ah

😭

But yes, #proofs-and-logic

[patent acorn]

well it's independent of zfc, iff zfc is consistent

if zfc isn't consistent then you can prove CH and you can also prove ¬CH

[eternal shoal]

true

but ZFC is consistent in my eyes 🙃

[errant otter]

"Proof?"

"It was revealed to me in a dream"

[random sand]

Cohen’s forcing is a related topic, I believe

[native fog]

yeah it is indeed

[native fog]

do you know more of what forcing is/could you explain?

[sacred junco]

I have this book

For some reason it’s like 1000$ on Amazon now

[errant otter]

what book is it?

[sacred junco]

Oh nvm

[little kelp]

what ?? hahahah, it wasnt even hard to find the pdf lmao

[sacred junco]

https://www.amazon.com/Elementary-Number-Professor-Emeritus-Mathematics/dp/0073383147/ref=mp_s_a_1_1?crid=2DTXYO50CUTUK&keywords=number+theory+burton+indian&qid=1692262897&sprefix=number+theory+burton+indian+%2Caps%2C141&sr=8-1

It’s still expensive

I got it for like 10$ somehow brand new

But it says Indian edition lol

[errant otter]

very.

[little kelp]

80 usd at my uni shop

[errant otter]

the list of proofs that amazon is a scam grows

[little kelp]

the entire university coursebook industry is a scam tbh

[sacred junco]

Math books are just expensive for some reason

[errant otter]

well, because not many buy them.

[sacred junco]

Like every publisher want to charge 50$ minimum

Yeah

That is a reason

But also probably because they have monopoly

Cause Dover books are cheap

And can be good sometimes

Ofc they’re less recent

[little kelp]

you can always "borrow" a book, and just scan every page

[sacred junco]

Lol

You can also use lulu.com to get a print

😉

[little kelp]

top 1 best side hustle

[sacred junco]

Of course only do this for the books out of copyright

Or for your own writings

Stealing is very bad

[verbal cedar]

<@&268886789983436800>

[solid garden]

handled

[verbal cedar]

thank you

[solid garden]

actually dami handled but I'm taking credit :^)

[verbal cedar]

i can only hope i can unburn that image from my eyes lol thank you all

[little kelp]

what happened

[grand umbra]

I need help quick
$$a and b are integers, prove that |a+b| + |a-b| {/geq} |a| + |b|$$

[sterile pumice]

Atom

[grand umbra]

bruh whatever

a and b are integers, prove that

|a+b| + |a-b| >= |a| + |b|

[patent acorn]

$a$ and $b$ are integers, prove that $|a+b| + |a-b| \geq |a| + |b|$

[sterile pumice]

bee [it/its]

[grand umbra]

ok no but how to solve it?

I mean prove

[torn escarp]

I'm guessing something like: play around with signs to say why you can take a, b to be positive without loss of generality with a>b then use that to throw away all the absolute value bars

I think that works, weirdly enough at no point do I use that they're integers, they could be real numbers I think, so I imagine there's a simpler proof that leverages the fact that they're integers rather than noticing the 2-3 cases which are equivalent by symmetries

I don't think this is useful, but tangentially related: 2*max(a,b) = a+b + |a-b|

[errant otter]

is it even true

oh. Seems like it

[torn escarp]

I proved it and explained the outline of what I did to prove it in my first message

[errant otter]

wait how can we be sure that the WLOG here works-

Ah right... if b > a then |a-b| would just "flip"