elementary-number-theory

[torn escarp]

I wouldn't call it wrong exactly but people consider it unsimplified I guess you could say

what you can't do is divide by multiples of 7

since those are all in the same equivalence class as 0, you're basically dividing by 0

[bleak igloo]

makes sense

cool subject but a little bit hard to understand at first glance

[torn escarp]

yeah definitely weird, kind of part of its appeal for me too at least lol

[bleak igloo]

@torn escarp Here, my book doesn't have an answer for even exercise, but since the pivot of the first line is even, we can't reduce it to one?

[torn escarp]

yeah exactly

we might still be able to get a solution though

[bleak igloo]

i did R2-R1 and got $\left[\begin{array}{cc|c} 2 & 3 $ 4 \ 2 & 0 & 4 \end{array}\right]$

[torn escarp]

well here it doesn't look like we will but just generally speaking it doesn't make it totally impossible

[bleak igloo]

$\left[\begin{array}{cc|c}
2 & 3 & 4 \
2 & 0 & 4 \
\end{array}\right]$

[torn escarp]

oh you'r eputting a $ where the & should be

[sterile pumice]

ᓇᘏᗢ Guilhotina ᓇᘏᗢ

[bleak igloo]

thanks

[torn escarp]

oh looks like there might be a solution

[bleak igloo]

i can divide R2 by 2 right ?

and them swap with R1

[torn escarp]

you can't divide

but you can subtract

dividing by 2 or 3 in Z_6 isn't doable exactly

[bleak igloo]

because 2 and 3 are the factor of 3 ?

[torn escarp]

of 6 yeah

[bleak igloo]

so if i do R2 - R1 my number of free variables, using the rank theorem would be 1 so this has infinite solutions ?

[torn escarp]

not quite

when you do R1-R2 then you get the two equations 3y=0 and 2x=4 which has multiple solutions

[bleak igloo]

forgot of -3 that is 3

[bleak igloo]

multiple solutions, because 3y = 0 is the same at any variable that multiplied by 3 is a multiple of 6?

and 2x =4 is the same as any number that multiplied by 2 has a remainder of 4 when dividing by 6 ?

[torn escarp]

well in particular what can y be in the set {0,1,2,3,4,5}

so y=0, y=2, or y=4 are the only possibilities for y

similar, x can only be finitely many possibilities

[bleak igloo]

oooo ok

thanks a lot

💙

[torn escarp]

well, work out what x should be first before you go haha

[bleak igloo]

ok

let me think

only 5 right ?

[torn escarp]

2 also

2*2=4 😛

[bleak igloo]

ooooo yes

[torn escarp]

5 was the hard one though so that's good

[bleak igloo]

my brain already melted but yeah

[torn escarp]

yeah, so those pairs are your 6 solutions

3 choices for y, 2 choices for x

it turns out you can solve it in Z2 and Z3 separately and combine the solutions with something called the chinese remainder theorem

so it's not so confusing having to check all the possibilities like this in general

[torn escarp]

@sacred junco yeah I remember you

I didn't see what else you wrote so idk lol

[sacred junco]

oop i deleted since it felt stupid

[torn escarp]

nah it's fine

[sacred junco]

well i asked if CRT and CR Algorithm are almost synonymous. Afaik CRT is used to assert unique existence and CR Algorithm provides a method to compute

[torn escarp]

yeah I guess so, I don't know if I make a distinction personally but maybe there is

I'd have to go refer back to a book or something, like maybe there's some technical case where the CRT holds but the CR algorithm doesn't work

[sacred junco]

[torn escarp]

I am pretty sure that kind of thing happens for euclidean domains where the euclidean algorithm doesn't work out or something

[sacred junco]

i see

[torn escarp]

I could be wrong I don't remember

[sacred junco]

i will check some texts

[torn escarp]

for all these kinds of cases though with Z/nZ though it'll always work

[sacred junco]

isnt it supposed to be x < sup(A) instead of x <= sup(A)? since the set of all real numbers is not a multi-set meaning no duplicates and none of the elements are equal to one another

its therefore impossible for the sup of a subset of R to be equal to the largest element of the subset

also R positive with a bar on top means the union of the positive real numbers and {0} but im not sure if that changes anything

[sacred junco]

sets with a maximum contain their own supremum, it's just the maximum

for example sup({1,2,3}) = 3 and sup((7,15e]) = 15e

In fact sup and inf are usually defined in terms of ≤ rather than <

oh i always thought that the sup has to be outside the set but ig not. thnx for clarification

yea gotcha
the supremum is just the least upper bound

if you're the biggest thing in the set than anything less than you must not be greater than you (you are in the set), so it isn't an upper bound
so then you're the least upper bound

so in other words least upper bound = maximal?

when it exists yes

sometimes it doesn't exist

the maximum I mean

damn u read fast. i see lol

@sacred junco i dont mean to sound skeptical but this post says stack exchange post says otherwise. it claims 1 is the sup of (0,1) even though 1 is not included inside the range.

https://math.stackexchange.com/questions/466134/upper-bound-vs-least-upper-bound

[sacred junco]

yes
nothing I said contradicts that tho

max((0,1)) does not exist but sup((0,1)) does and equals 1

[sacred junco]

^

and you should have skepticism thats good

OH max(0,1) does not exist because of theorem that between any two real numbers a rational is between them?

sure! or you could construct it in this case explicitly

[sacred junco]

Yes bu at the same time its very demotivating since it makes u doubt often if whatever sources u cite is infsct trustable and correct

[sage fern]

if the maximum exists, it's always equal to the supremum

the supremum is 1

[sacred junco]

something like, assume (0,1) has a greatest element called 'a'
then 0 < a < (a+1)/2 < 1 so 'a' is clearly not the greatest, since (a+1)/2 is also in (0,1)

[sacred junco]

humility is necessary in math, but along with it you can be certain when you know how to verify things
proving things clearly and taking time to write them down if it sounds sketchy can help

there are times I've thought I proved something in my head and then got home to write it down and found when I explained it clearly on paper I actually got to the opposite conclusion

I'm sure it's the same for a lot of/most folks lol, it happens and no worries whenever it does

[vernal ibex]

Hey can I get help with understanding p-adics?

[sacred junco]

which part ? What do you need help with ?

[vernal ibex]

Fundamentally understanding and using them lmao.

[sacred junco]

read a book

ask when you are stuck at some point

[vernal ibex]

Any recommendations then?

Websites or videos or books for it?

[sacred junco]

my understanding is only limited to what I read in Alan Baker's book (Comprehensive Course in Number Theory)

Not sure of more material on p-adics, sorry!

[vernal ibex]

Oh.

[sacred junco]

There is a handout if you google it by Alan Baker which I remember reading, you can try that maybe

[vernal ibex]

Thank You!

[robust pond]

Can some explain to this channel to me

[topaz ridge]

this channel is for discussing number theory

[fathom lagoon]

greetings

I want to proof that

I know that e.g.
60 * k = a-b
k being an integer
I wanted to use an full induction approach therefore I chose a to be defined as n:=n+1 and left b as original term
so
3^((n+1)^4+...+4) congruent to 3^(n^4+...+4) congruent to 21 mod 60
And here I'm stuck

[wooden glen]

It would feel more promising to try to show without induction that the polynomial in the exponent is always congruent to 4 modulo totient(60).

[fathom lagoon]

can you define totient(60)?
Is it Euler's totient function?

[wooden glen]

Yes.

[fathom lagoon]

need to read that up then

[wooden glen]

If this is from a course or class where you haven't actually been shown Euler's theorem, then that is probably not the intended approach, though.

[fathom lagoon]

It's a task from my theoretical informatics sheet

[wooden glen]

If we set P(n) = n^4 + n^2 + 2n + 4, have you tried to calculate P(n+1)-P(n)? since 3 to that power is what you multiply the previous value with to get the next one.

[fathom lagoon]

one sec

[wooden glen]

Hmm, that would still leave a cubic term which doesn't feel excessively promising either.

[fathom lagoon]

should be P(n+1)-P(n)= 4n^3+6n^2+6n+4

[wooden glen]

So if we could show that 3^(4n^3+6n^2+6n+4) is always congruent to 1 modulo 60, we could complete an induction proof of the original claim.

That's at least some progress; the polynomial in the exponent now has a smaller degree.

[dusty dragon]

n = 1 gives 3^20 which is congruent to 21 mod 60

[fathom lagoon]

I don't necessarily have to use induction. It just felt like a good way to go about it

[wooden glen]

right. Fortunately 21^n is congruent to 21 modulo 60 for all n>=1, so it would still suffice.

[dusty dragon]

which is still fine because 21^2 is still 21 mod 60

[wooden glen]

n=2 gives 3^4, which is also 21 modulo 60.

Ah! Since 21^2 == 21 (mod 60), all we really need is that n^4 + n^2 + 2n + 4 is always a multiple of 4.

(And I'm an idiot for not noticing that 3 fails to be coprime to 60; so bringing the totient of 60 into it was misguided).

[dusty dragon]

n being even is easy, so you just need to consider n being odd

[wooden glen]

And all the odd squares are 1 modulo 4.

[dusty dragon]

It ends up being 1 + 1 + 2 + 0 (mod 4) which is congruent to 0 (mod 4)

n^4 = (n^2)^2 which is congruent to 1^2 = 1 (mod 4),
n^2 is congruent to 1 (mod 4),
2(2k + 1) = 4k + 2 which is congruent to 2 (mod 4),
4 is congruent to 0 (mod 4)

[fathom lagoon]

where did the n=2 gives 3^4 come from?

[fathom lagoon]

^

[torn escarp]

I'd recommend solving the problem mod 3, mod 4, and mod 5 so that it's easier to work with

[wooden glen]

Uh, that was a bizarre typo on my part. I meant: n=0 gives 3^4 ...

[fathom lagoon]

uff

alright

thanks

soo.
If I go about merosity's idea
proof mod 3 is trivial
mod 4 is what opengangs and troposphere did
mod 5 would be
3^(n^4 + n^2 + 2n + 4) congruent 1 mod 5

[wooden glen]

Actually what we said was P(n) == 0 mod 4, not 3^P(n) == 1 mod 4.

That's actually what gets us the mod 5 case too, due to Fermat's little theorem.

[analog onyx]

is this definition sufficient?

[stiff rivet]

sufficient for what?

this is the standard definition

[analog onyx]

thats what i was asking, if it was the correct definition

thats what i was asking, if it was the correct definition

[torn escarp]

just search for it online if it's a definition

[fathom lagoon]

did you use some theorem to know that the term always returns multiple of 4?

@wooden glen

[wooden glen]

I should have used Carmichael's function, but actually I had forgotten about it, and stumbled about a bit instead. I first checked that the claim is true for n=0, which is 3^4 == 21 (mod 60). Then when Opengangs pointed out that my initial hypothesis wouldn't work, I calculated 21^2 modulo 60 and got 21 again. Then I knew that 3^x == 21 (mod 60) whenever x is a multiple of 4, and I began looking for an ad-hoc argument that n^4 + n^2 + 2n + 4 is always a multiple of 4. That turned out to be easy enough by treading odd and even n separately, rather than using any fancy general theorem.

[fathom lagoon]

ok thanks

[fathom lagoon]

I just want to make sure.
I can use Fermat's little theorem to proof mod 5 if I've proven mod 4?

[oak sluice]

Hi!

Say $t \in \mathbb{N}$, $k \in \mathbb{N}$, and $n \in \mathbb{N}$ are fixed, $t < n, k < n$. Is computing the smallest $e \in \mathbb{N}$ that satisfies this faster than the general discrete log problem?

$$
2^t (1 + 2^k)^e \equiv 2^t \pmod{2^n}
$$

[sterile pumice]

flebron

[torn escarp]

no because $e=2^{n-t-k}$

[sterile pumice]

Merosity

[oak sluice]

So far I've got it to $(1 + 2^k)^e = 1 + 2^{n-t} q$ for some q.

[sterile pumice]

flebron

[oak sluice]

Why is that the value of e?

[torn escarp]

first simplification is you can remove $2^t$ to make $(1+2^k)^e = 1 \mod 2^{n-t}$

[sterile pumice]

Merosity

[oak sluice]

yep

Did that, that's the q thing above 🙂

[torn escarp]

then expand the binomial and subtract 1 from both sides $$\sum_{i=1}^e \binom{e}{i}2^{ki} = 0 \mod 2^{n-t}$$

[sterile pumice]

Merosity

[torn escarp]

now because higher powers of 2 can't cancel out with lower powers of 2, we're sort of trapped to focusing on the first term being 0

we need to know a little more precisely how the binomial grows to really claim that, so we have to turn to legendre's formula for factorials, the power of 2 of x denoted as $v_2(x)$ can be written as $v_2(n!) = n-s_2(n)$, here $s_2(n)$ is the sum of digits of n in base 2

[sterile pumice]

Merosity

[oak sluice]

Remind me, "the power of 2 of x" is the highest power of 2 that divides x?

[torn escarp]

yeah I lost some words there whoops lol

[oak sluice]

OK, sure, I buy that (and am wikiing for the proof of that formula, on the side 🙂 )

[torn escarp]

that's pretty much it

[oak sluice]

Wait how does that formula for the highest power of 2 dividing n! give us that $e = 2^{n - t- k}$?

[sterile pumice]

flebron

[torn escarp]

that's to justify that the power of 2 dividing the first term of the sum is too small to cancel with the later terms in the sum

maybe I should show just the first 2 terms to kind of help you see what I mean by that

[oak sluice]

OK presumably I should apply this v_2 to the terms in the binomial coefficient

[torn escarp]

yeah, it's completely additive, that means v_p(xy)=v_p(x)+v_p(y)

[oak sluice]

Yeah

[torn escarp]

when you apply it to the product of 3 factorials it'll work out

[oak sluice]

So v2(\binom{e}{i}) = v2(e) - v2(i) - v2(e-i)

[torn escarp]

$$e2^k + \frac{e(e-1)}{2}2^{2k} + \cdots = 0 \mod 2^{n-t}$$

[sterile pumice]

Merosity

[torn escarp]

not quite

you just left out the !

[oak sluice]

lol, right

OK, so I should count the highest power of 2 dividing each term.

And this will show that the first few terms must be zero.

(mod 2^(n-t))

[torn escarp]

so if you look here, since usually $2k-1<n-t$ if we reduce further, we end up with $e2^k = 0 \mod 2^{2k-1}$

[sterile pumice]

Merosity

[torn escarp]

this is what I mean about the lower power terms not cancelling with higher power terms

in terms of the 2-adic absolute value this is called the strong property of the ultrametric inequality, if you're wondering if there's some kind of underlying method to this madness

[oak sluice]

mmm

[torn escarp]

I'll admit I've been sort of careless here so keep asking questions if you have any doubts, there may be a flaw

[oak sluice]

I don't get this part "so if you look here, since usually $2k-1<n-t$ if we reduce further, we end up with $e2^k = 0 \mod 2^{2k-1}$"

[sterile pumice]

flebron

[oak sluice]

What do you mean by "usually"?

Some sort of statistical argument??

[torn escarp]

well if it's larger then it's trivial

that means the second term is already 0 mod 2^{n-t}

and so are all the further ones

so you really are just looking at e2^k = 0 mod 2^{n-t} in that case which reduces to e=2^{n-t-k}

[oak sluice]

I might be a bit lost here. We expanded the binomial coefficients into their product. So I'm with you until $e 2^k + e(e-1)/2 * 2^{2k} + .... \equiv 0 \pmod{2^{n-t}}$.

[sterile pumice]

flebron

[oak sluice]

I'm not sure how v2 enters here.

[torn escarp]

it doesn't at this point

[oak sluice]

(Have never done p-adics, maybe this is obvious)

[torn escarp]

think of it this way, the second term is 0 mod 2^{2k}, do we agree on that much?

[oak sluice]

Yes

And the first one is zero mod 2^k, for the same reason.

[torn escarp]

because binomial coefficients are integers, the later terms will be some integer times 2^{ik}

[oak sluice]

Yes, agreed.

I see, you're saying after some point these are zero.

Mopd 2^{n-t}.

[torn escarp]

yeah

[oak sluice]

Specifically the Rth term, where Rk >= n-t

[torn escarp]

if we look mod 2^{2k} right away, we automatically kill all the later terms leaving just the first term

[oak sluice]

Sure, this would be true, but we're not looking mod 2^{2k}

[torn escarp]

so if n-t <= 2k we have just the first term

[oak sluice]

Yes

[torn escarp]

that's what that part was about

you can always think if something is true mod p^m then it must also be true mod p^n for n<m

so there's no harm in checking that the simpler condition is satisfied

since it's necessary

if you don't satisfy something mod p^n, then there's no chance of it being satisfied mod p^m for m>n

to phrase that slightly differently

[oak sluice]

Right, yes

So what happens if 2k < n-t?

[torn escarp]

then the term sticks around, and that's where the next part of that argument comes in

hopefully that's clear so far, this is just us establishing why I originally made that statement about the inequality, right

[oak sluice]

Yep yep, thanks for clarifying!

[torn escarp]

cool, one sec gonna grab a snack and go to the bathroom

[oak sluice]

(Back yet? lol)

[torn escarp]

oh yeah, just forgot to say anything

[oak sluice]

lol

[torn escarp]

ping me if I ever get lost again

[oak sluice]

So the issue was what happens when 2k < n-t then

And you were saying you'd use v_2

To argue that something cannot disappear

[torn escarp]

we might not need to use v_2

[oak sluice]

There's some index after which the terms vanishes

In particular ceil((n-t)/k)th one

[torn escarp]

yeah, in particular we know the second term and the first term need to cancel out, we need the power of 2 dividing e2^k to be equal to the power of 2 dividing e(e-1)/2 * 2^(2k)

you can see that in part by seeing that e2^k = 0 mod 2^(2k) is necessary

[oak sluice]

The reason they "need" to cancel out is related to this thing about higher powers being unable to cancel lower ones?

[torn escarp]

yeah exactly

I can't really say this stuff very cleanly even with p-adic notation, but without it, it's a bit worse so trying to think of how best to flesh this out

there are sort of 3 main avenues to think through, 2 are simple and 1 might cause a little trouble

when k=1 and when k is very large are the easy cases

[oak sluice]

By the way, the origin of this is in computer programming, the function f(x) = x ^ (x << k), where ^ is xor, and << is left-shift (i.e. multiplying by 2^k) can be seen to have power-of-two periods, modulo 2^32 or whatever the bitwidth is.

[torn escarp]

neat, that sounds fun, yeah a handful of 2-adic stuff is sort of related, like 2's complement representation

in the 2-adics you represent -1 as ...111111 just infinitely many 1s to the left

[oak sluice]

Yep 🙂

I just haven't delved there, not sure when I would've.

[torn escarp]

similarly f(x)+x+1=0 for f(x) being the complement of the digits of x is true

[oak sluice]

I took some math electives in university for CS, but none of them talked about p-adics.

[torn escarp]

so you can represent -x = 1+f(x) like you'd expect

[oak sluice]

That seems... like algebra, but before abstract algebra I suppose.

[torn escarp]

yeah pretty much nobody in CS is going to mention this

nor is anyone going to mention it in an abstract algebra class haha

[oak sluice]

Where does one see it in a math curriculum?

[torn escarp]

sorta too far removed from the basics to be taught in a single semester course

[oak sluice]

I got to Galois theory as far as algebra went, and no analysis at all, so maybe in analysis???

[torn escarp]

honestly they don't really pop up, they are mentioned a few times in passing, they're a part of number theory

[oak sluice]

That

's fair

I didn't do number theory either.

[torn escarp]

no analysis, although there is analysis involved

[oak sluice]

Got scared right around class numbers

[torn escarp]

galois theory applies to p-adic numbers because they're a field

they're an alternative completion of the rational numbers

[oak sluice]

Is the issue about 2k < n-t a pedagogical one, or it's actually unclear what the result will be?

[torn escarp]

so you can have p-adic field extensions and talk about galois groups and so on

[oak sluice]

Oh nice I didn't know the p-adics were a field extension of Q

[torn escarp]

there might be some devil in the details that I haven't thought through completely

[oak sluice]

Your result matches my experimental ones so far, btw

[torn escarp]

one simple way would just be to brute force check for a handful of cases to see if it matches to feel sure

oh well then

nice

I think there's an exception for k=1 case

but other than that I don't think there are any other exceptions

because k=1 means we're looking at 3^e = 1 mod 2^(n-t)

[oak sluice]

def go(x, k, m):
    return x * (1 + 2^k) % m

start = 10 # t = 2
x = start
k = 3
m = 2**16
ctr = 0
while True:
    x = go(x, k, m)
    if x == start: break
    ctr += 1
ctr

[torn escarp]

since 3 is a generator we have e = phi(2^(n-t))

[oak sluice]

aren't all odd numbers generators?

[torn escarp]

maybe k=2 has a problem

no definitely not

1 doesn't generate I guess as a silly example

[oak sluice]

Oh multiplicatively

So coprime to phi(2^32)

[torn escarp]

yeah

cause if you think of (1+2^k)^e = 1 mod 2^(n-t) we're sort of saying 1+2^k is generating a multiplicative subgroup

[oak sluice]

yes

And that's an iff

[torn escarp]

well really there's a kind of intuitive view on this

when we go to the p-adics, they can be collapsed back down to the field of addition and multiplication mod p

and so while the discrete logarithm problem is kind of hard

[oak sluice]

What does collapsing mean here? What are we preserving?

[torn escarp]

taking p-adic integers and reducing mod p

p-adic integers are numbers represented as $\sum_{n =0}^\infty a_np^n$, with $a_n \in {0,1,...,p-1}$

[sterile pumice]

Merosity

[torn escarp]

basically numbers written in base p that extend infinitely far, we need to say more to make this more rigorous but reduction mod p just means taking the first digit, a_0

multiplicatively speaking, the image gives us the numbers mod p where the discrete logarithm problem is, while on the other hand the kernel of this homormophsim is basically where mod p^n for n>1 happens which has the p-adic logarithm

that's easier to compute

I feel like that's probably a bit too rough an explanation to really get much out of it, the main thing to really get from it is the p-adic logarithm is very easy to compute

you can basically think of p-adic numbers as working with numbers mod p^n for any n>1

[oak sluice]

OK

[torn escarp]

well, the 2-adics are sort of special and since that's our main concern, uhh I can just write down one way to compute the 2-adic logarithm for a number of the form 1+2^k haha, although we can go back to the problem if you like instead

yeah now that I think of it, it'll get kinda messy so let's avoid that for now

just extra details we'd have to discuss to explain things, lol

[oak sluice]

Experimentally, 2^{n -t - k} is correct whenever n - t - k >= 0. After that it seems to be 1.

1 is a bit odd, it's saying x == x * (1 + 2^k) % 2^n.

Oh that's not odd.

2^k became zero.

And 1 remains. So of course.

[torn escarp]

yup 👍

[oak sluice]

So experimentally the result is valid when n - t >= k. But we've only proved it for n - t >= 2k.

[torn escarp]

ok let's start going through the details a bit more in depth

[oak sluice]

(And by we I mean you, lmao)

[torn escarp]

hah

ok quick recap where are we, we have $e2^k = 0 \mod 2^{2k}$ we established and now I sort of asserted that we want the slightly stronger condition $v_2(e2^k) = v_2(\frac{e(e-1)}{2}*2^{2k})$

[sterile pumice]

Merosity

[torn escarp]

that first condition already establishes $v_2(e2^k) \le v_2(\frac{e(e-1)}{2}*2^{2k})$, make sure that makes sense

[sterile pumice]

Merosity

[oak sluice]

And we said e*2^k = 0 mod 2^2k because otherwise the 2^k term cannot cancel out later.

Everything's "shifted too far" by then/

[torn escarp]

yeah exactly

[oak sluice]

(Bringing this back to bits.)

[torn escarp]

we say this is "2-adically small"

[oak sluice]

The distance is based on v_p?

[torn escarp]

well I don't want to overload you with notation but we can define an absolute value on rational numbers

$$|x|_2 = 2^{-v_2(x)}$$

[sterile pumice]

Merosity

[oak sluice]

Nice, that makes sense.

[torn escarp]

we can try to reason this way and if it gets confusing go back to just the valuation

[oak sluice]

So you're closer if you approach from infinity

Which is the opposite of how 0.xyz... works for reals.

[torn escarp]

for instance, $|x|_2 \le 1$ if x is an integer or has no power of 2 in the denominator

[sterile pumice]

Merosity

[torn escarp]

yeah, we have the weird circumstance that $$\lim_{n \to \infty} 2^n = 0$$

[sterile pumice]

Merosity

[oak sluice]

Makes sense, again as bits

[torn escarp]

perfect, I feel like you naturally have some intuition and experience with algebra and math to make this actually useful to use then haha

[oak sluice]

Been a few years out of university, but I remember some stuff 🙂

[torn escarp]

so another way to phrase it (dropping the subscript 2 since it's 2-adic absolute values from here on out), $$|e2^k| \le |\frac{e(e-1)}{2}2^{2k}|$$

[sterile pumice]

Merosity

[torn escarp]

I might have said that backwards earlier cause I was thinking this earlier, this should have been $v_2(e2^k) \ge v_2(\frac{e(e-1)}{2}*2^{2k})$

[sterile pumice]

Merosity

[oak sluice]

RIght, I buy that

[torn escarp]

because we know the power of 2 dividing e2^k is just as large, if not larger

[oak sluice]

Because you're dividing by 2 so you lose 1 power, but you're increasing the exponent in 2^2k to more than make up for it.

Plus you get the e-1 freebie.

[torn escarp]

yeah, so now we can try to see when the reverse holds, cause I said it's actually an equality we want

because inequality the reverse direction never occurs, $$|e2^k| > |\frac{e(e-1)}{2}2^{2k}|$$

[sterile pumice]

Merosity

[oak sluice]

Hrm wait to see if I understand

[torn escarp]

we can now just simplify as you might normally

sure

[oak sluice]

Oh that reads badly, I didnt mean for that to sound like an order or anything lol

More like "Hrm, wait, to see if I understand: "

[torn escarp]

oh I didn't haha

[oak sluice]

This bit says there's higher powers of 2 dividing the left side than the right side. But I'd think the other way around. When we go from left to right, we're adding an extra * 2^k (so v_2 increases by k), and losing just 1 (because we divide by 2). And we're getting another multiple of * (e-1). which may or may not add further multiples of 2.

So I would assume v_2 increases as the terms go on in this summation.

[torn escarp]

actually second guessing my sign choice there, I kept flipping back and forth and confused myself It hink lol

yeah you're right, v_2 increases as the terms go in the summation

[oak sluice]

So we should have $|e 2^k| \ge |\frac{e(e-1)}{2} 2^{2k}|$

[sterile pumice]

flebron

[torn escarp]

ah but the sign is reversed, $|x|=2^{-v(x)}$

[sterile pumice]

Merosity

[torn escarp]

|x|>|y| means v(x)<v(y)

[oak sluice]

Yep

I think there's higher powers of 2 in the 2^{2k} term

So it has a smaller 2-adic norm

[torn escarp]

yeah, there can be

[oak sluice]

Always, right?

The /2 removes one, the * 2^k adds k.

And the (e - 1) can only add.

So it increases by at least k - 1.

[torn escarp]

well that's sorta what I was trying to prove yeah

I guess to make it a bit clearer what I'm thinking,

[oak sluice]

(k == 1 might be spooky, I agree)

[torn escarp]

$x = 0 \mod 2^n$ means $|x|\le 2^{-n}$

[sterile pumice]

Merosity

[oak sluice]

Agreed

[torn escarp]

ok cool, I guess next we want to force $$|e2^k| = |\frac{e(e-1)}{2}2^{2k}|$$

[sterile pumice]

Merosity

[torn escarp]

if they're not equal, one is larger than the other and so there's no cancelling happening

in the 2-adics the exact property is written as $|x| \ne |y|$ implies $|x+y| = \max(|x|,|y|)$

[sterile pumice]

Merosity

[torn escarp]

that's really just a more refined perspective on reducing the sum mod 2^(2k) earlier

the first term had to be 0 mod 2^2k or else they could not be 0 mod 2^(n-t)

we don't have to do this all in one sitting, we're juggling a lot right now so no pressure is all I mean

[oak sluice]

hrm

A bit of a dumb question but.

We had this sum:

$e 2^k + \frac{e(e-1)}{2} 2^{2k} + \cdots \equiv 0 \pmod{2^{n-t}}$

[sterile pumice]

flebron

[oak sluice]

And we said if $n-t \ge 2k$, then everything vanishes.

[sterile pumice]

flebron

[oak sluice]

And we're left with $e = 2^{n-t-k}$.

[sterile pumice]

flebron

[oak sluice]

Can we say something if $n-t \in [k, 2k]$?

[sterile pumice]

flebron

[torn escarp]

wait that's backwards, $n-t \le 2k$ makes all the later terms vanish

[sterile pumice]

Merosity

[oak sluice]

Err right.

But the expression $2^{n-t-k}$ only makes sense when $n-t-k \ge 0$

[sterile pumice]

flebron

[oak sluice]

Meaning $n-t \ge k$.

[sterile pumice]

flebron

[oak sluice]

So some part of the argument must require that $n - t \ge k$, surely?

[sterile pumice]

flebron

[torn escarp]

yeah this is what we're having to refine right now

[oak sluice]

Oh hrm, I had sort of bought the argument already.

So I must've missed when I assumed that, because I certainly assume it in the conclusion.

[torn escarp]

well we were going through it but I think it was just getting mixed up with notation

might help if we have this written in like mathb.in rather than backtracking to keep it straight

maybe I should push forward anyways from here $$|e2^k| = |\frac{e(e-1)}{2}2^{2k}|$$

[sterile pumice]

Merosity

[oak sluice]

Sounds good 🙂 I probably should get to sleep now being 3am, but I'll come back tomorrow haha

Well... today technically.

[torn escarp]

let's finish this little bit

[oak sluice]

Sounds good

[torn escarp]

and then I'll let ou run free

ok so you can simplify that like the real absolute value

[oak sluice]

We haven't yet shown the equality above, I understand?

[torn escarp]

no but I think we can revisit that tomorrow

[oak sluice]

OK

[torn escarp]

good to see where it's going now

[oak sluice]

Sure

[torn escarp]

so you simplify that like in 7th grade algebra class

$$1 = |e-1| |2^{k-1}|$$

[sterile pumice]

Merosity

[torn escarp]

because e-1 is an integer, we have only two choices for k here, 0 or 1

if it's larger we can't get a 1/2 from the e-1 term to cancel out to make 1 again

well, k=0 I don't think is in N (or is it?) and k=1 is the case 3^e=1 mod 2^(n-t) which is what I mentioned earlier

3 generates so it's phi(2^(n-t))

[oak sluice]

So if that equality is true, then k must be 0 or 1.

And sure, we can solve those two cases separately.

So we may assume that that equality is not true, is that the point?

[torn escarp]

we know it's an inequality in one direction

we just need to show the reverse inequality to make it an equality, that's really the step missing

[oak sluice]

Yes

But if that equality holds, that would force k = 1 or k = 0

So that can't be true for all k

[torn escarp]

the reverse inequality we need to show is like looking when the first term is divisible by a larger power of 2 than the 2nd term

which feels obviously wrong

[oak sluice]

Yep

[torn escarp]

so that's good

[oak sluice]

Yeah, so the normal inequality is strict, except perhaps in k <= 1.

What does that buy us?

[torn escarp]

it means when k is not 0 or 1, then there is no competition happening

the only way for it to be 0 is if the first term is 0 mod 2^n-t

[oak sluice]

I see!

[torn escarp]

that forces us back to e2^k = 0 mod 2^(n-t) and yup

[oak sluice]

Yes

OK, I buy the argument 🙂

So we don't need to assume that the 2nd term is zero and get that 2k bound

[torn escarp]

yeah, I think it needs to be fleshed out all in one page to feel convincing to me haha

[oak sluice]

We just need to say that the 2-adic norm will not disappear

But it must since we're equivving it to 0

So all of those terms must be zero, and in particular the first one must be zero.

And we get the desired result.

[torn escarp]

yeah that sounds about right

btw where did you /how did you come up with that function f(x) earlier?

I plan on playing with that in the mean time

[oak sluice]

The long story is there's some common techniques in hashing in computer science

And this function introduces things that look like noise, statistically having good bitwise independence

But it is reversible

[torn escarp]

ah I see

[oak sluice]

Specifically this argument shows that it has a period, and can in fact be computed faster than just doing it this many times

https://marc-b-reynolds.github.io/math/2017/10/13/IntegerBijections.html

[torn escarp]

nice time to try to break aes with p-adics next

[oak sluice]

Now that you mention it!

There's a fun puzzle in the code to construct the AES S-boxes.

https://en.wikipedia.org/wiki/Rijndael_S-box

The C-code at the bottom has a quirk.

[torn escarp]

oh?

[oak sluice]

/* loop invariant: p * q == 1 in the Galois field */
    do {
        /* multiply p by 3 */
        p = p ^ (p << 1) ^ (p & 0x80 ? 0x1B : 0);

        /* divide q by 3 (equals multiplication by 0xf6) */
        q ^= q << 1;
        q ^= q << 2;
        q ^= q << 4;
        q ^= q & 0x80 ? 0x09 : 0;

[torn escarp]

interesting I'll have to check this out when I'm more awake this sounds cool

[oak sluice]

p being multiplied by 3 is clear, and the 0x80 thing is checking for "will it overflow, and if so i need to reduce by the irreducible polynomial, which is 0x11B, and so I xor with 0x1b"

But the second one, where they're dividing by 3, is a bit more interesting.

They first do their division (really multiplying by 0xf6), and then check to see if the computation overflowed.

The key is that every time they did "q ^= q << 1" for example, because this is a single byte, they're chomping the coefficients higher than degree 7.

Which is invalid in the finite field.

It turns out you can "just do it", multiply by 0xf6 like that, and detect (and correct for!) whether you overflowed after the computation.

This post explains it: https://math.stackexchange.com/questions/1229797/rijndael-s-box-algorithm-can-someone-please-explain-how-this-code-calculates-th

[torn escarp]

ooh

[oak sluice]

Anyway a small token of thanks for your explanation 🙂

[torn escarp]

thanks this sounds cool, I'll check it out, I appreciate it

[rugged moth]

rijndael

[torn escarp]

for anyone interested in that original problem we were talking out together just now, I typed up the solution but found a slightly different more streamlined path http://mathb.in/69455

[sacred junco]

Could I ask you to rehash it sometime next time we chat cause I'm pretty sure I understand all the methods and concepts but can't seem to piece it together myself lol

[livid birch]

are there any essential tools i should now in tackling problems regarding the divisibility of numbers

stuff like fermat's little theorem

i picked up sierpinski's book of problems but am having a hard time approaching the problems, having never done number theory lol

linking myself to this convo rq

[lean vapor]

What is the point of :

$\overline{\mathbb{R}}$ ?

[sterile pumice]

Eglvoland

[wooden glen]

Depends on context. It's probably not topological closure of R in itself, because that would be stupid. It might be the algebraic closure of R, but then only to say that it's the same thing as C. Most probably it's neither and you'll need more context to make a reliable guess.

[torn escarp]

yeah of course, also two things I should mention, flebron pointed out the euler phi at the end should really be the carmichael function, and also that final lemma with the inequality of the form |x^i/i| which sort of comes out of nowhere came from a known trick when looking at the p-adic logarithm power series; all of its terms are of course of that form.

just wanting to demystify slightly where it came from

[wooden crater]

sometimes its used to denote the extended reals

[analog onyx]

Did i do this correctly? This is my first time doing induction with a fixed variable, though its not much different.

[oak sluice]

@analog onyx When you expanded the sum, after "computing the sum yields,", some of your terms still have "k" in them. Presumably when you expanded a "sum over k", there should be no "k" in the expansion.

I don't quite follow the part after "By part b, we know that ____ for k = 1, 2, ..., n". OK, that's true. But which binomial coefficients are you either splitting or joining, and how does that lead to the result in the "Hence"?

[rugged moth]

wrong order

also wrong channel

[analog onyx]

i see what you’re talking about when i compute the sum, i have some k’s instead of u’s. For the binomial coefficients, isn’t it for the whole sum or is that not correct

[sacred junco]

find all positive integers n such that 3n+1 and 6n-2 are perfect squares and 6n^2-1 is prime

[oak sluice]

I mean that you cite a property about binomial coefficients of a particular types. Then you say it applies to a sum, where we have bionmial coefficients of all different types. And from that you conclude that the entire sum collapses into half as many terms, so presumably you're taking {some binomial coefficients} and {some other binomial coefficients] and fusin them. But it's not clear what those are.

For example, are you using that binomial coefficient identity to fuse the first 2 coefficients in your sum, $\binom{u}{0}$ and $\binom{u}{1}$? It matches your binomial coefficient identity, but no idea what would happento the x's and y's that you have multiplying those binomial coefficients. If you are indeed using this binomial identity on the first two terms to fuse them, how do you transform $\binom{u}{0} x^{u+1} + \binom{u}{1} x^u y$, using that identity, and what do you get? It's not clear from that sort of magical "Hence".

[sterile pumice]

flebron

[oak sluice]

In other words, there are two things missing: 1) How does that binomial identity help you, when everything in your sum has attached x and y coefficients, and your identity has no coefficients, and 2) What exactly are the pairs of binomial coefficients that you are fusing using that identity, to achieve the desired "Hence" result?

[vernal ibex]

Is it so that if a number x when divided by n has remainder r, then will x^y divided by n always give remainder r, given that y is a natural number?

Like how do we know in the 3rd case and in the 2nd case it will be like what it is in the remainders?

@iron edge.

Basically how do we know for other cases and what to do and stuff?

Here it is 3 so simply understandable.

But what if it was a much bigger number?

[iron edge]

If a is congruent to 1 in any modulo, then a to any power is congruent to 1 as well

Is that what you asked?

[vernal ibex]

Can you write that in equation form please?

In LaTeX or something?

[iron edge]

n ≡ 1 (mod a) => n^k ≡ 1 (mod a) for any natural number k

[vernal ibex]

Ohhh.

What.

[sacred junco]

It's easier to see if you try to show that for any two integers and some modulus, product of remainders is the remainder of the products

[vernal ibex]

Can you explain this?

[sacred junco]

Then just note that exponentiation is specific case of doing that repeatedly

[iron edge]

All I did was raise both sides to k-th power, that's allowed in modular arithmetic

[vernal ibex]

You took 1 there because it was the remainder?

And what for other remainders?

How do we know the precise value?

Aaaa I am so confused.

[iron edge]

What's exactly confusing you?

[vernal ibex]

Everything here.

[sacred junco]

if n = n' + sa, m = m' + ta, then nm = (n')(m') + (Junk)a

[vernal ibex]

'?

[sacred junco]

So the product of remainders mod a is the remainder of the products mod a

[vernal ibex]

What is ' ?

[sacred junco]

Now take m=n

[vernal ibex]

Something not n or not m?

[sacred junco]

Just a different number given by Euclidean division, so it's guaranteed to be between 0 and a-1, aka remainder of n mod a

Do you know Euclid's division algorithm/theorem?

[vernal ibex]

No.

[sacred junco]

That's super important, basically the foundation of mod arithmetic that makes it much nicer to work with at the beginning

[vernal ibex]

Oohh.

Let me read it quickly.

This is it?

[sacred junco]

That's the Euclidean algorithm, which is very close in name lol

[vernal ibex]

Oh.

F.

[livid birch]

arent they the same

[sacred junco]

Euclidean division is the guarantee that for any integers n and natural number a, there exists some other integer say n' so 0<=n'<a and n = n' + sa for some other integer s

[vernal ibex]

Oh.

[sacred junco]

Euclidean algorithm uses Euclidean division repeatedly with arguments keeping track of divisors and a minimality argument so they're slightly different

[vernal ibex]

Junk?....

[sacred junco]

Yeah just some other integer

You could work it out yourself if you wanted

But it's not hard to see that upon multiplying n and m that every term besides the n'm' term has a factor of a

So basically you get nm =n' m' (mod a)

[vernal ibex]

Okay.

[sacred junco]

Sorry if something wasn't clear I can explain in further depth and give examples

[vernal ibex]

Can I DM or ping here later?

Need to sleep now lol.

Also Thank You for that!

Good night.

[sacred junco]

Do they even exist? Lol I'm super scuffed rn but I just tried getting Pellian equations out of these and the topograph is telling me they don't exist

Basically if a=3n+1, b=6n-2, then (a, b) have to be solutions of the binary quadratic form x^2 - 2y^2 representing -4

But the topograph only has small values -1, 1, -7, 7 and monotonically increases/decreases on the positive/negative side

[analog onyx]

i am revising it, i will send it when i am done, thank you

[sacred junco]

So -4 can never show up

So if I'm not making a mistake (which I very might well be making LOL) such a and b cannot exist, so then of course n cannot exist either, even without the condition of 6n^2-1 being prime

Oh wait this is only for coprime a and b lmao bruh

Well I guess I just proved they have a common factor

Well then that common factor has to be plus or minus 2 since it's square needs to divide -4

So then examining 3n+1 is even tells ya n is odd but maybe you figured that out already

Sorry I wasn't much help

[analog onyx]

@oak sluice

[oak sluice]

@analog onyx I don't quite follow the expansion (there's still some k left when you expanded btw, in both expanded lines). I believe you're first listing all the x * (something), and then all the y * (something)? But presumably to use your identity, you are mixing terms from each of these (i.e. one term from x * something, plus another term from y * something)? Otherwise x * (that sum) would yield again a binomial expansion, if you are only fusing terms from the first, x * (something) part.

After you expand, you should still keep the form x * term_1 + x * term_2 + ... x * term_n + y * term_1 + y * term_2 + ... + y * term_n. Then, in a separate line, permute these in whatever order you want, like = x * term_1 + y * term_2 + x * term_2 + y * term_3 + ... whatever order. And from here, once the terms that you want to combine are actually contiguous, you can use the binomial fusing.

So 1) expand the sum syntactically, no permutation, 2) permute the terms from the last line so that contiguous terms have the same x and y coefficients, and their binomial coefficients look like the ones in your binomial fusion expression, and 3) actually fuse the terms, perhaps even with a line identical to the one before, just with parentheses to show the reader "here, this is what i'm about to fuse", and 4) fuse the terms. That should give you another binomial expression. That should not be " = (x + y)^{u+1} = thesumhere", but "= thesumhere = (x + y)^{u+1}".

To put it perhaps another way: When you have a " ... ", there should be one way the terms are changing in that " ... ". But here you have two different " ... " sums. One of them is being multiplied by x, the other is being multiplied by y. Yet in the expression you wrote, after you expanded the [] brackets, you have only one " ... ". That makes it unclear what the terms are.

[sacred junco]

Just realized this also means 3n+1 is 0 mod 4 so n is 1 mod 4

[sacred junco]

Yeah, an exemple for n=1, 3n+1 is 4, 6n-2 is 4 and 6n^2-1 is 5

[oak sluice]

@analog onyx let me know if anything there was unclear 🙂 Basically when you wrote the " ... " after the []-expansion, the stuff before the ... was all the "x multiplied by the sum terms". But then when you come out of that ..., it seems these are the "y multiplied by the sum terms" terms, so it's now unclear what happened in the ... . Did the "x multiplied by the sum terms" end somewhere there, and the sum terms start again from the "y multiplied by the sum terms" stuff?

[analog onyx]

well the x is counting down and eventually vanished, and the y is counting up which is why it starts without it

[oak sluice]

@analog onyx but these things don't happen at the same time.

There are some terms that are being multiplied by x, and some terms that are being multiplied by y.

Before the ..., all of the terms are "the ones being multiplied by x".

After that ... I've no idea what those are. Presumably they are still the ones being multiplied by x (since "x * (foo bar ... baz)" expands to x * foo + x * bar ... + x * baz), but then where did the ones being multiplied by y go?

That is, there should be 2n terms in that expansion.

[analog onyx]

we are looking at the line after, “Multiplying our induction hypothesis by” correct?

[oak sluice]

But if you are counting down and up at the same time, that means there's only n terms.

Let's use colors to refer to these.

In the red line, you have something like (x + y) (foo bar ... baz).

That expands to (x * foo + x * bar + ... + x * baz) + (y * foo + y * bar + ... + y * baz).

Note the two "..." that it must expand into.

There's 2n terms in what I wrote.

However in the blue line, there's only one "...", and so only n terms.

So it's not clear how we went from a sum of 2n terms, which is what the red line expands to, to the blue line, with only n terms.

Presumably you're permuting at the same time, but it's not clear if it's done at the same time.

[analog onyx]

well we multiplied the x in which adds one to the exponents and the same with y

[oak sluice]

(The fact that there's still "k" there doesn't help, note the "k" in both the blue and the green lines, that shouldn't be there)

[analog onyx]

yes i agree that’s a mistake

is what you’re describing a mistake or just something that wouldn’t be clear to a reader?

[oak sluice]

Well, since it's not clear to me what's going on, it might be a mistake or not, I can't tell 🙂

[analog onyx]

hahaha okay got you

[oak sluice]

So b), I suppose, wouldn't be clear to a reader, namely this reader, me 🙂

Also another small improvement is that in the green line, you're coupling terms 2-by-2.

But in the blue line, the last \binom{u}{1} term doesnt have the corresponding \binom{u}{2} term after it. It just appears in the next line.

It was obviously there anyway in the " ... ", it's just it's a character that appears out of nowhere in the story, so to speak.

Like, "the group then went for ice cream. Vinnie chose strawberry" -- wait who's Vinnie? Oh he's a member of the group.

Hopefully that makes sense ^_^''

[analog onyx]

so to improve that, i would need to add the corresponding binomial coefficient in the blue line

[oak sluice]

Yeah, the terms you are "grouping" together in the next line should be the same ones you explicitly mentioned in the term above

[analog onyx]

okay makes sense

[oak sluice]

While the green ... comes from the blue ... above.

[analog onyx]

this makes sense okay

[oak sluice]

@analog onyx I see, I think how you expanded was:

(x + y) * (a + b + ... + c) becomes

x * a + y * a + x * b + y * b + ... + x * c + y * c?

As opposed to x * a + x * b + ... + x * c + y * a + y * b + ... + y * c?

That's not an expansion style I've seen, so it might be good to have this second style first (first all by-x multiplications, then al by-y multiplications), and then another equality, where you permute the terms to look like the first one (alternating x and y).

[analog onyx]

yes that is exactly it, you can kinda see that from my binomial coefficients being the same for the first 2 terms, 2nd two terms ect

i did that so it made the step from blue to green easier for me to see

and then i think i applied part b correctly to end the proof

[oak sluice]

Yeah that step is clear, I'd just add an intermediate between red and blue, for the permutation on top of the expansion 🙂

Green to yellow is also clear, of course removing the extra "k" stuff.

[analog onyx]

yes i was just getting confused with my letters since i normally do my inductions with n = k + 1

but k was fixed here

[sacred junco]

Hmm so I'm working on that same problem and I can't get anywhere, it comes down to finding primes of the form 96k^2+48k+5 where k also works to help a particular matrix over Z[sqrt(2)] be of a certain form but it feels like a red herring and the problem was easier, would love to see more crack it in maybe a easier way

[sacred junco]

Here is the original btw

Whoops I pinged instead of linking, sorry
Still works I guess lol

[sacred junco]

Well I got home and it's kind of annoying cause the polynomial I got generates a lot of primes but some results are composite, and I'm not sure how to just solve for primes of that form, much less also make sure they satisfy the other conditions

[sacred junco]

The other conditions being that 3k+1 and 6k+1 are square

nvm tried something but it didn't make any sense rip

Well actually even though I cannot find the obvious solution that is probably out there this observation does give us bounding conditions: solving the quadratic in k gives us the extra condition that (p, k) is a point on (you can verify it's the positive root using properties of the prime in the formula involving n) the curve 1/24 (sqrt(6+6x) - 6)

which grows quite slowly compared to the (x^2-1)/3 and (x^2-1)/6

meaning k will have to be huge for small steps in those squares and the prime

[sacred junco]

So actually this formula will sometimes hit non-integer rationals but it is faster in terms of getting a bound of p based on the smaller of the squares, 3k+1
That being 1/3 (32x^4-16x^2-1)

[torn escarp]

if I didn't make a mistake, there is only one solution p=727

[sacred junco]

p=5 works too unless I'm buggin

[torn escarp]

the p=6n^2-1 is a red herring and I never used it except at the end

maybe I made a mistake and left out some cases

[sacred junco]

I've been kinda obsessed with this problem cause it looks like the kinda thing I should be able to crack easily but I can't

[torn escarp]

what I did was write $a^2=3n+1$ and $b^2=2(3n-1)$ and then rewrite it as $a^2-\frac{b^2}{2}=2$ then I did the annoying task of just working down if they're even or odd one base 2 digit at a time

[sterile pumice]

Merosity

[torn escarp]

$2a^2=b^2+4$ we know b is even, so put $b=2b'$, then you end up with $a^2=2b'^2+2$ we know $a$ is even so $a=2a'$, etc...

[sterile pumice]

Merosity

[torn escarp]

eventually I had gotten it down to $$a''(a''+1)=\frac{b''(b''+1)}{2}$$ and since they're relatively prime factors on each side, that means I can associate them in 4 different ways, $a''=b''$ or $a''=b''+1$ or $a''=\frac{b''}{2}$ or $a''=\frac{b''+1}{2}$ then it became simple to solve, but 3 of the 4 cases gave me a negative so what was left is how I ended up with 727

[sterile pumice]

Merosity

[torn escarp]

which seems to work so I dunno if along the way I'm losing solutions somehow without thinking about it cause like you said, 5 is a solution haha

[sacred junco]

727 being the prime or n?

[torn escarp]

the prime

n=11

[sacred junco]

right 726 isn't a multiple of 4

kk cool

[torn escarp]

p=727 is the prime for n=11

idk what 726 = 0 mod 4 does haha

[sacred junco]

wait oof doesn't work for me for some reason

[torn escarp]

although that's not right, 726=2 mod 4 I'm pretty sure

to check mod 4 you check divisibility of the last 2 digits, 26=24+2 = 2 mod 4

oh you said it isn't or you edited it or

whatever

lol

[sacred junco]

yeah first time was a typo

basically since a is a multiple of 2 you get 3n+1 = a^2 is a multiple of 4 and you can get n is 1 mod 4 from there

[torn escarp]

oh I got a case where a''=b''=0

I assumed that was invalid cause the numbers are positive but these are just higher digits

so I think this saves it

[sacred junco]

and then I substituted n=1+4k which maybe was a painful idea cause my shit gets weird and unhelpful

the bounding thing I found was cool but probably doesn't help at all with solving things

and nice

[torn escarp]

oh yeah it does cause I have a=2+4a'' and b=2+4b'' so a''=b''=0 gives a=b=2

basically I'm trying to avoid doing mod 2, mod 4, mod 8, mod 16, etc by instead plugging in and reducing each step to keep working mod 2 to prevent it getting too crazy for me

actually

for fun we can see what the negative solutions get us

oh just -a and -b

[sacred junco]

I could just code it to go further but I checked primes up to the millions or so using my bounding trick as well as making sure the initial a and b are integers

so that n=1 p=5 is the only one so far

[torn escarp]

can you show me what you were doing, still curious to see what stuff you were doing, I could even walk through the painful steps of my solution again if you want

oh you didn't get the other one

like in voice chat or call I mean

[sacred junco]

I expanded p = 6n^2 - 1 after substituting n = 1+4k

I aint home yet unfortunately 😭 still no mic

[torn escarp]

I meant this stuff back here with the topograph actually haha

ah, ok some other time when it's easier to draw and such

[sacred junco]

oh yeah it ended up being unnecessary and just obvious by looking at gcd stuff as you did

but you can get a nice form for a and b unrestrained from the annoying primality thing on n at least

via matrices in PSL_2(Z)

I figured that probably wouldn't help with this problem though

[torn escarp]

I'm kind of interested in generalizing this situation, the fact that $2a^2-b^2=2$ has only 2 positive solutions seems kind of interesting to me

[sterile pumice]

Merosity

[torn escarp]

this is probably some kind of well known ring theory thing like $x^2-2y^2=-2$ written as $N(x+\sqrt{-2}y)=-2$ having only 2 solutions or something might be easier to get by playing with $\bZ[\sqrt{-2}]$

[sterile pumice]

Merosity

[torn escarp]

which sounds like where you were headed

[sacred junco]

wait there's infinitely many it's given by [3 & 4\ 2 & 3]^j times column vector [0\1] I am too lazy to latex 😢

with j an integer

[torn escarp]

that doesn't work

[sacred junco]

err something is wrong

eyah

yeah

[torn escarp]

earlier you were using Z[sqrt(2)] but I'm using Z[sqrt(-2)]

maybe that's the confusion

[dusty dragon]

Could probably use something to do with fundamental units

My algebraic number theory class had to solve some sort of Diophantine equation using Dirichlet’s unit theorem

[torn escarp]

only units in Z[sqrt(-2)] are 1, -1

[sacred junco]

ahh wait figured out the right matrix I just forgot how to do the continued fraction stuff to make it right

[torn escarp]

oh I'm backwards I should be in Z[sqrt(2)]

that's kind of weird cause this gets us infinitely many solutions

[sacred junco]

wait my earlier thing did work I just forgot to square is all

it was the same as I got from working it out more fully

doesn't really matter for this problem but I always like doing a little topograph stuff

we do a little topograph

[torn escarp]

N((2+2\sqrt{2})^{2n}) = 2 is what I'm getting basically for the solutions

but they seem to break

and not satisfy the equation for n simultaneously

I should use a different

[sacred junco]

wait uhh it's representing 0 instead of -2 sometimes wtf

my bad

or maybe it's just wolfram? it should be right tho

[torn escarp]

$N((2+2\sqrt{2})^{2j}) = 2$ is what I'm getting basically for the solutions

[sterile pumice]

Merosity

[torn escarp]

if it's not even it'll be -2

cause 1+sqrt(2) alternates between +-1

[sacred junco]

wait x^2-2y^2 can literally not represent 0 lol wolfram buggin

(31988856, 22619537) was the 10th solution I got for fun of x^2-2y^2=-2

ayy desmos got my back

me @ wolfram rn https://youtu.be/OGQx37dwnhM

[torn escarp]

x=sqrt(2)

[sacred junco]

fancy code moment

[torn escarp]

cut out the middle man and just do even

[sacred junco]

this is for representing 1 right?

[torn escarp]

yeah

[sacred junco]

I actually wrote a really shitty codebase for all of this kind of stuff using the Conway style theory last winter 💀 my prof still smiled and nodded though, he wanted me to do it as an exercise and thought it would help with research stuff

which it kinda did maybe?

Now that I know pari/gp exists I might just have to crash course it cause it seems so useful

[torn escarp]

yeah I use it all the time

[sacred junco]

giga pog

also any ideas on the original problem cause I am crashing and still be stumpied af

[torn escarp]

https://pari.math.u-bordeaux.fr/tutorials.html

some pretty simple tutorials on there to play with

I'll probably go through the algebraic number theory one on there right now, I know there are more streamlined ways to do quadratic extension stuff on there

[sacred junco]

bookmarked lets goooo

[torn escarp]

oh just found something already

poldisc(x^2-2) returns 8 ofc

and quadunit(d) returns a fundamental unit of the quadratic field of discriminant d

so I never have to look it up again just type in quadunit(poldisc(f)) done

has an optional parameter for what to call the variable

[sacred junco]

kekw

winning

[torn escarp]

that's cleaner than doing Mod(..., x^2-2) like I was doing cause the ugly mod popped up

[sacred junco]

nice!!! that's very convenient

[torn escarp]

apparently there's a polisirreducible function, that's convenient

[vernal ibex]

"How do we know what will be the remainder when x^y is divided by n and the remainder is r, if we know the remainder for x^1 when divided by n?".
For example, in the given problem in the image with the solution, how do we know that if in case 2, n has remainder 1, then n^3 will have remainder 1; and in case 3, if n has remainder 2, then n^2 has remainder 1 and n^3 has remainder 2.
Here it is still relatively simple because we are dealing with 3, but what if we were dealing with arbitrarily large numbers or Diophantine equations?

[shrewd lake]

I can't download the image, there is an error, but from what I am reading you are badically talking about modular arithmetic

[shrewd lake]

Well if x has a remainder r1 for example. Then x^y will have the same remainder as r^y

[vernal ibex]

Huh.

[shrewd lake]

Wait

[vernal ibex]

Okay so um I think this is wrong.

Since 7/3 has a remainder 1.

7^2 = 14.
1^2=1.

14/3=2.

So not 1.

@sacred junco yo.

[sacred junco]

7 is definitely 1 mod 3, meaning we can write 7 as 1+3(2)

[vernal ibex]

Yessir.

[sacred junco]

So 7^2 = (1+3(2))^2 = 1 + 2(3)(2) + (3(2))^2 = 1 + 3(4+12) = 1+3(16)

And so 7^2 is 1 mod 3

[vernal ibex]

Huh can you show how?

[sacred junco]

Distribute and multiply :)

It's just (a+b)^2 = a^2 +2ab +b^2

[vernal ibex]

Ah fuck.

Let me see.

Oh yes it is that!

Man how do you pros use and determine such clever tricks and know how to use them?

Just experience?

Then uhhh this?

[shrewd lake]

The general case is (a+b)^n

There you use the binomial theorem

[vernal ibex]

@sacred junco?

What formula here?

Finally the lord is back .

Hello zd....

[vernal ibex]

Now what?

What if the remainder is not 1? Great than 1 that is.

https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/the-quotient-remainder-theorem
This seems like it is getting to the point.

[shrewd lake]

Dude you have to learn modular arithmetic

It's super useful

And not that hard

[vernal ibex]

Can you show ToC for that?

Table of Contents?

This stuff?

[shrewd lake]

Ahhhh yesss Khan Academy

But just type modular arithmetic explanation in Google

And you will learn in 20 times faster than here

At least that's my opinion

[vernal ibex]

Can someone explain this?

[oak sluice]

@vernal ibex It's saying if $X \equiv y \pmod{B}$, then $X + B \equiv y \pmod{B}$. The first equation means B divides X - y. That is, $X - y = q * B$ for some $q \in \mathbb{Z}$. If that's the case, consider adding B to both sides of this equation. On the left, you get $X - y + B$. On the right, you get $q * B + B = (q + 1) * B$. Thus, we see that $X - y + B$ is a multiple of $B$, specifically it is $q + 1$ times $B$. And so, we know $B$ divides $X - y + B$, which means $X - y + B \equiv 0 \pmod{mod B}$. Moving the $y$ to the other side of the equivalence (which you should prove you can do in modular equations), we get $X + B \equiv y \pmod{B}$, which was to be shown.

[sterile pumice]

flebron

[vernal ibex]

Oohh.

Thank You!

[oak sluice]

No problem 🙂

[vernal ibex]

https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/fast-modular-exponentiation

Any more optimization techniques like this?

[sacred junco]

Euler's theorem pairs well with this but I strongly recommend getting a good grasp of mod arithmetic first, it will help give you a good understanding of how to abuse groups of units lol

[glad junco]

So that's exponentiation by squaring (plus modulus), right? If so, that's about the best you can do for exponentiation.

[wooden glen]

If the exponent is large and the modulus is known well in advance, you can get faster in practice by using https://en.wikipedia.org/wiki/Montgomery_modular_multiplication together with exponentiation by squaring.

(This is not worth the complication for small examples with pencil and paper, though).

[wheat tinsel]

Is it true that ax^2+bx+c=0 has a solution if and only if b^2-4ac is a quadratic residue?

[oak sluice]

You might enjoy https://fedelebron.com/fast-modular-fibonacci

[wooden glen]

It doesn't work modulo 2: 1x²+1x+1=0 doesn't have any solution, but 1²-4·1·1=1 is a quadratic residue.

[wheat tinsel]

But for odd primes?

[wooden glen]

I think so. To be sure, find a derivation of the quadratic formula and check that each step works modulo an odd prime.

[wheat tinsel]

One direction is trivial

The other direction is also easy

I just realized that you can just plug the quadratic formula expression into the congruence, which is in the group of integers modulo p, as you assume b^2-4ac is a quadratic residue

some high school algebra probably does the rest

Given that it's a formula for the equation in the integers, I don't think you have to do more, since symplyfying these type of expressions is the same in both rings

[wooden glen]

Yes. (You do need to be sure that you can divide by 2a at all, which is what mucks things up for p=2).

[wheat tinsel]

right

but for odd primes, assuming a is non zero, it works fine

2 is so fucked up man

[wooden glen]

The oddest prime.

[wheat tinsel]

true

I wonder if similar simple criteria appear for polynomial congruences in higher degrees

this is easy because quadratic formula

[stuck shore]

if i had a nickle for every time i had to read "Let p be an odd prime"

[wheat tinsel]

in general I suppose solutions in higher degrees to these type of equations appear more rarely

[wooden glen]

Yeah, because for each class of polynomials-modulo-constant-terms three are only so many potential roots they all have to compete for, and in higher degrees the winners can gobble up more of them, leaving more of the polynomials as losers.

[torn escarp]

this problem becomes much easier when you learn $n^p=n \mod p$ so that showing your problem becomes $n^3+2n = n+2n = 3n = 0 mod 3$

[sterile pumice]

Merosity

[vernal ibex]

Oooo will read, thank you!

[vernal ibex]

Yes I more or less completed this last night https://www.khanacademy.org/computing/computer-science/cryptography#modarithmetic (modular arithmetic basics).

[vernal ibex]

Hmmm Oohh.

[glad junco]

Actually its even.

[wooden glen]

... ooh, that's what I've been doing wrong! Thankyouthankyouthankyou

[glad junco]

Any time

[wheat tinsel]

Most primes are odd though

[torn escarp]

[stiff rivet]

the even evil prime

[livid birch]

grothendieck prime

[wheat tinsel]

Would you write the (mod p) and the congruence symbol at the end? Or it should be understood by the context?

It just looks cleaner without it

[torn escarp]

I personally never write it and also just use regular =

[wheat tinsel]

ye

Like I don't even mention p is an odd prime

cuz, come on

[torn escarp]

I'll mention that if it's relevant

but yeah typically I ignore p=2 too

[wheat tinsel]

this is something I'm writing for myself, maybe I should mention it, but it should be clear for what I do next

[torn escarp]

I guess it depends, dealing with quadratics probably obvious I guess

[pine bolt]

if A = {1, 2, 3}, and B = {∅}, then what would be A x B ?
would it be {(1, ∅), (2, ∅), (3, ∅)} ?

[formal minnow]

yes

[pine bolt]

nice

[analog onyx]

could i get some help proving this lemma?

[wooden glen]

Uniqueness is not always true -- for example 1x == 5 (mod 10) has two solutions with |x| <= 10/2, namely x=5 and x=-5.

[analog onyx]

the word unique implies only one solution?

[wooden glen]

Yes,

[torn escarp]

unique means only one exists in english, it's not a math term

[analog onyx]

would this lemma be provable without the word unique?

[wooden glen]

You'll also need to clear up whether your variables are a,b,c or a,m,n.

[analog onyx]

that confused me too bc it put a restriction on b but we have no b

[wooden glen]

What would work is something like: Let $a$, $m$, $n$ be integers with $m\ge 0$, $n\ge 1$ with $a$ and $n$ relatively prime. Then $ax\equiv m \pmod n$ has a solution $x$ with $|x|\le n/2$. (The solution is unique unless $n$ is even and $x=n/2$ is a solution).

[sterile pumice]

Troposphere

[analog onyx]

okay i will work with that one i think

[wooden glen]

Note that the conditions on m and n are also different from the version you posted. It would be a bit strange to speak of congruence modulo 0...

[analog onyx]

my professor gave me this lemma in context with diophantine equations, but it doesnt seem to be a very good one

[wooden glen]

There's a kernel of truth, but the presentation sure seems to be rather hasty ...

[wind glacier]

https://media.discordapp.net/attachments/885521812065239110/932664230040182854/789503407588900964.png

Pls help

[oak sluice]

First idea would be to reparametrize into (1/a + 1/b + 1/c) * ((a-1)/a + (b-1)/b + (c-1)/c), or to multiply everything by (a^2+1)(b^2+1)(c^2+1). Expanding those to see if there's some way to use the given identity between ab, bc, and ca.

[vernal ibex]

https://www.youtube.com/watch?v=Ez6GBxo-2pc&list=PLi01XoE8jYojnxiwwAPRqEH19rx_mtcV_&index=1

So this is the work going on in like some of number Theory?

[vernal ibex]

How?!!?

What is going on here lol.

[torn escarp]

which part

to me it's too clear what's happening, describe exactly what you're thinking at the step you are unsure of

it's also useful to explain when you're confused since it helps clear up your own confusion to yourself @vernal ibex

[vernal ibex]

Actually everything in case 2 lol.

[torn escarp]

ok tell me what happens in the first step

[vernal ibex]

x + 1 == 0(mod p), so x == -1(mod p)

== means that mod symbol.

[torn escarp]

ok good

[vernal ibex]

But how is x == p - 1(mod p)?

[torn escarp]

p=0 mod p

so we're not really changing anything

[vernal ibex]

Huh.

[torn escarp]

we're just shifting it to be a number between 0 and p-1

[vernal ibex]

Where is that shown?

[torn escarp]

it's just a simple fact they used to move from one line to the next

does p=0 mod p make sense?

[vernal ibex]

= means that congruent symbol?

[torn escarp]

yeah

[vernal ibex]

Okay.

Yes it definitely makes sense.

[torn escarp]

ok good

[vernal ibex]

OHHHHHH I see whaaaaat happpened.

AhaAAAAAAA.

[torn escarp]

nice

[vernal ibex]

Man you Mathematicians are so clever you understand everything so fast and do not even need to see what clever manipulation or so is done .

[torn escarp]

haha, I didn't know this at one point either

it helps to think of them as equivalence classes, and you can exchange any choice of representative you want

[vernal ibex]

I am talking about like every time .

[vernal ibex]

Oohh.

[torn escarp]

like easiest example to think of is when you're doing something mod 2, you have 0 and 1 only, but these are representatives for the set of all even numbers and all odd numbers respectively

[vernal ibex]

I will resume studying Number Theory after like 2 hours . Probably will have lots of doubts, will ask here.

[torn escarp]

and you can just as well interchange them around when it's convenient

[vernal ibex]

Ooh yes.

[dusty dragon]

number theory is hard, takes a lot of just thinking and no writing

[torn escarp]

sounds good

[vernal ibex]

Yes !

Why is there hate for it by many people though .

[dusty dragon]

I will offload that question to all my friends who don’t like number theory

I love it!

[vernal ibex]

Me too!

[dusty dragon]

It was my favourite topic when I took discrete math

[leaden swan]

I mean look at any sufficiently complex nt problem

I think it goes from 0 to 360 really really quick

[vernal ibex]

Oh.

Hey can you give examples where there are inverses here? Like where are numbers with negative power here haha?

[torn escarp]

inverse just means it's a number you multiply by it to make 1, so for instance

$2^{-1} = 3 \mod 5$

[sterile pumice]

Merosity

[torn escarp]

why? because $2*3=1 \mod 5$

[sterile pumice]

Merosity

[vernal ibex]

Yes.

[torn escarp]

so for instance in this simple example, $4! = 1234 = 122^{-1}(-1) = -1 \mod 5$, try to write out the case for p=7 and if you have trouble I'll help

[sterile pumice]

Merosity

[vernal ibex]

Huh?

You can take mods with fractions? What?!!?

[vernal ibex]

Yes.

[torn escarp]

there are no fractions here, although there's no problem with writing fractions so long as you don't have any divisors of your modulus in the denominator

[vernal ibex]

2^-1 = 1/2.

[torn escarp]

here I just mean the multiplicative inverse $2^{-1} = 3 \mod 5$

[sterile pumice]

Merosity

[vernal ibex]

Huh what?

[torn escarp]

it's not a fraction, the $-1$ exponent doesn't mean fraction, $x^{-1}$ means "this is the number you multiply by $x$ to make $1 \mod p$." so $x*x^{-1} = 1 \mod p$

[sterile pumice]

Merosity

[torn escarp]

like the example I showed you 2*3=1 mod 5, neither is a fraction, but 3 is the multiplicative inverse of 2

[vernal ibex]

Huh so mods work like that?

Are you supposed to already understand that fact by common sense or it is taught?

Where did you learn Modular Mathematics Merosity? Maybe I should give some days learning it from there. I seem to miss some stuff sometimes.

[torn escarp]

well I suppose it's taught, I don't know what material you're learning from but sounds like you're missing some of the basics

[vernal ibex]

I did the Modular Arithmetic Course from KA, and it was small.

So yes I also think so.

[torn escarp]

I learned it from friends casually at first, they were doing competition math problems and I would join them, I never really learned the basics from a book in any kind of linear way

[vernal ibex]

https://www.khanacademy.org/computing/computer-science/cryptography#modarithmetic

[vernal ibex]

Oohh.

Many competition math books do not really teach them fully I think.

They show what mods are and then proceed.

I have a few.

Let me check them again.

[torn escarp]

I just get a bunch of resources and use whatever works and bounce around, usually I have an idea of something I want to understand better and am pretty self guided that way

[vernal ibex]

Yes.

I also try to do it that way lol.

Hmmm okay.

I will keep focusing on Number Theory.

[mild sierra]

can someone help me?

[torn escarp]

dunno, no one can say without seeing the question

[mild sierra]

i have been stuck with this question

[torn escarp]

ah wrong channel try #❓how-to-get-help

[mild sierra]

everyone is dead there\

[vernal ibex]

Go to #prealg-and-algebra.

Such a cute theorem.

[torn escarp]

yup pretty nice stuff

you can think of this as saying that every element (not equal to 0) is a root of unity, kind of like how complex numbers have roots of unity other than 1 and -1

idk maybe that's confusing to hear haha

[vernal ibex]

Woah.

What.

p-adics vibes.

Hey are there other number systems? Like I loved to learn about the Complex Numbers(Imaginaries), and p-adics on which I actually need to learn well.

[torn escarp]

the complex numbers and p-adic numbers are all examples of fields

and arithmetic mod p is also a field

there are tons of other number systems out there but these are some of the more common nicer ones

although p-adics I'd say aren't that common

[dusty dragon]

I don’t think I’ve touched p adics since my last semester of 2019

[vernal ibex]

WOAH you can do SUC cool stuff with Fermat's Little Theorem!!!!

[vernal ibex]

Oohh.

[vernal ibex]

I see I see.

[vernal ibex]

Oh do you know about those other ones?

[vernal ibex]

Yeah lol.

[dusty dragon]

You also have the quaternion number system which extends the complex number system (they aren’t a field though)

[vernal ibex]

Do you think they will get more popular(p-adics) as time goes? I have heard that they might be the next revolution in Mathematics, or so.

[vernal ibex]

Ohhhhh yeeeessssss I will watch the 3B1B video on that.

Thank you for reminding lmao.

[torn escarp]

where did you hear that?

I don't really think so, they are not really geared towards some kind of huge revolution where they become commonly known among regular people or anything

[vernal ibex]

Oh.

In a few comments on a blog about p-adics lmao.

No like just that they can tell us a lot more about the nature of numbers and stuff.

[torn escarp]

yeah, they are definitely involved in number theory stuff but even within number theory it's possible to ignore them if you didn't want to think about them

stuff gets pretty broad, lots of different tools out there for number theory

[vernal ibex]

Chinese Remainder Theorem and all those stuff are based on Modular Arithmetic too, like this Fermat's Little Theorem?

[vernal ibex]

Oohh.

So what are these fields you say?