elementary-number-theory

[errant otter]

It really does seem to be 0 for k odd...

Proving it

,w faulhaber formula

[sterile pumice]

Results provided by WolframAlpha

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

Requested by kiameimon

[errant otter]

Nice cancellations..... where are youuuu

[eternal shoal]

Huh

Did we not do k odd

[errant otter]

Wait where

I mean that was an observation, only the 2nd statement is true cuz of FLT

Hmm

Using the fact that it's odd

We can pair it up the way u suggested and factorize and we would be done I think

Yeah checks out

At least in my heaz

Factor Using the fact a^(2k+1) + b^(2k+1) = (a+b)(a^2k b - a^(2k-1) b^2 + .... - a^2 b^(2k-1) + ab^2k)

Then a + b in this case would give us p, so it will be modulo-ed

And also we have even number of terms (p!=2) since the last term of the summation will be modulo-ed out

So yay

Lastly for even

To summarise results so far:

• Any exponent can be reduced to < p, so we'd just have to consider that range.
• for p = 2 answer is always 1, so we deal with only odd primes now on
• odd exponents and exponent 0 will result in 0.
• exponent p-1 results in p-1.
• what remains: exponent is even, < p-1 If that helps

[errant otter]

Seems to be 0 for all other even exponents

Proof.....

Mmm

Well, the idea of "multiply with odd variant" may still work- just need to twist the argument

$\sum^p_{i = 1} i^{2k} \mod p = \sum^{p-1}_{i = 1} i \cdot i^{2k-1} \mod p$

[sterile pumice]

Kiameimon | Welt Rene

[errant otter]

Hm

[open mist]

Btw the odd case you should have found from the start of the wiki page
It said it's always a multiple of S1

[errant otter]

Wonder if I could, multiply $\sum^p_{i = 1} i^{2k} \mod p$ with $\sum^p_{i=1} i \mod p$ and get some simplifications

[sterile pumice]

Kiameimon | Welt Rene

[errant otter]

?

What wiki page

[open mist]

That's multiplying by 0

[open mist]

Faulhaber

[errant otter]

Yeah but if I can expand and show some of the terms gives me what I need then I'm good to go

[errant otter]

What is S1? Also Im not very great at sorting the important details out when it's concepts I'm not rlly familiar with

[open mist]

Sk is the sum of the kth powers
Simple notation

[errant otter]

Oh

[errant otter]

Like, make the product cancel some terms to become $\sum^{p-1}_{i = 1} i \cdot i^{2k-1} \mod p$

[sterile pumice]

Kiameimon | Welt Rene

[open mist]

I fail to be convinced

[errant otter]

So do I but....

I need to do smth 😭

Try smth

[open mist]

Writing Sk^2 ought to have a higher likelihood of being fruitful

It is

[errant otter]

Oh.

Yeah it just ends up being the odd case

Wait

Mmmmm ig so

Wait

💀

Ahem

[open mist]

Just realized there's a method to figure out what I said but by direct induction, too

Looks like it's always 0 then. If that's true, not sure how p-1 dodges that bullet

[errant otter]

Because flt

[open mist]

I mean how the proof fails for it

[errant otter]

Edgecase moment

[open mist]

Because S(k)^2 expands to S(2k) + 0, right ?

It's -S(2k)

Funny

I think

Shouldn't be doing that when I'm half awake, but screw it

[errant otter]

Huh.

Oh

[open mist]

It doesn't

[errant otter]

[open mist]

But expand nonetheless

I'd need to settle down to properly mental math that out

[errant otter]

What is -S(2k)
$- \sum^p_{i = 1} i^{2k} \mod p$?

[sterile pumice]

Kiameimon | Welt Rene

[open mist]

Yeah duh

[open mist]

But don't trust me on this

At all

[open mist]

Sometimes, my speed is frightening

I still think it holds

But still not sure how it fails at p-1

[torn escarp]

whats S

[open mist]

I hereby leave, conjecturing it is 0 except for p-1

[errant otter]

sum

from 1 to p

to the power of (stuff in bracket)

[torn escarp]

ah, is this a really easy problem or a really hard problem

mod p right

[errant otter]

prime

yeah

so it's easy

meant to be

I'm an ameutuer so it's not

I've done everything other than show it for even numbers < p-1

[torn escarp]

I'm thinking the trick is like, when $k\ne 0 \mod p$ then multiplication is an bijective mapping mod p, so $$k^n S(n) = \sum_{i=1}^{p-1}(ki)^n = \sum_{i=1}^{p-1}i^n = S(n)$$
so if n is not a multiple of $p-1$, it means
$$(k^n -1)S(n)=0$$
and since $k^n-1 \ne 0 \mod p$, it must mean $S(n)=0 \mod p$

[sterile pumice]

Merosity

[torn escarp]

sorry I should spoiler that maybe

[errant otter]

izzok

[torn escarp]

I guess I left out the case when n is a multiple of p-1, but I think I can leave that to you to work out yeah

[errant otter]

that one I alr have

damn tho

that proof was so

consise

and short and handled everything

almost

[torn escarp]

well I didn't really come up with it

I've seen this trick several times at this point haha

[errant otter]

what happens when u stay on mathcord long enough

[torn escarp]

group theory, character theory, etc

any time you have a sum of things and you're multiplying by some thing in that group, since multiplication in a group is by definition invertible, you'll end up with this trick

[errant otter]

interesting trick

[torn escarp]

similar idea for proving the field norm and trace are elements of the babier field instead of the adult field

related to this

you should look at trying to prove the Chevalley-Warning theorem

[errant otter]

nani

[open mist]

Looks correct to me at first glance
Should always be 0
Still don't know where p-1 fails here

[torn escarp]

this is basically one of the steps if I recall

,rotate

[open mist]

The idea kmm pulled me away from

I'm an idiot

[open mist]

Don't mind exo 10

[torn escarp]

nah it's good

[errant otter]

so it's my fault now huh?

[open mist]

Ofc

Can't be mine

[errant otter]

ow

[open mist]

Can it ?

[torn escarp]

idk having trouble reading it

[open mist]

Ok now I have algebra 1, bye

[errant otter]

[torn escarp]

I also should have said k != 1 mod p too just realized

main thing is k^n is not 0 or 1 cause otherwise k^n S(n) = S(n) is either not true or not giving us something interesting to work with

I guess maybe the best choice is to say k is a generator

that way we know we really can have n not a multiple of p-1

[errant otter]

fancy terms

[torn escarp]

and it not be 1

a generator I just mean an element of (Z/pZ)* that's order p-1, generates the whole set of muliplicative elements

like 2 generates (Z/5Z)* since
2^1=2
2^2=4
2^3=3
2^4=1

[errant otter]

order p-1?

[torn escarp]

smallest number you raise a number to to make it the identity

[errant otter]

ah

Interesting

NT

[torn escarp]

yup lol

weird stuff

[errant otter]

need to get on the NT grindset

[torn escarp]

the proof of the Chevalley-Warning theorem on wikipedia is pretty short too https://en.wikipedia.org/wiki/Chevalley–Warning_theorem#Proof_of_Warning's_theorem

maybe that's a bit too tricky to read on its own, if you're curious I can give some examples of using it and how to prove a simple case of it

[errant otter]

~~I'm struggling to even understand the theorem statement ~~

[torn escarp]

yeah it's a bit generalized

let's say you have a polynomial with n different variables of degree d, if n>d then the number of solutions to f(x_1, ..., x_n) = 0 is divisible by p

f(x,y,z)=x^2+y^2+z^2 let's say, what's n and what's d?

[errant otter]

n = 3, d = 2....

in which case it does work

[torn escarp]

yeah, so on it's own maybe not super exciting

but we know the number of solutions to that mod p will have to be a multiple of p

but it might have no solutions at all

[errant otter]

XD

[torn escarp]

although, if you look at it, it has one obvious solution to f(x,y,z)=0

do you see what it is

like what's an easy solution to make that 0

[errant otter]

set it all to 0

[torn escarp]

perfect

so that means there are at least p-1 other solutions out there

having one trivial solution was enough to know it actually has more solutions for free, kind of spiffy

this also leads into other things but at least that kind of gives you an idea for how it works

[errant otter]

[torn escarp]

you can have more than one equation at a time, but we can focus on trying to prove just a single polynomial case

part of the proof is that $1-x^{p-1}$ is 1 when x is 0, and it's 0 for all other x mod p

[sterile pumice]

Merosity

[errant otter]

[torn escarp]

so $N$, the number of solutions to $f(x,y,z)=0\mod p$ is congruent to this $$N=\sum_{x=0}^{p-1}\sum_{y=0}^{p-1}\sum_{z=0}^{p-1}(1-f(x,y,z)^{p-1})\mod p$$

[sterile pumice]

Merosity

[torn escarp]

makes sense?

[errant otter]

I suppose seo

[torn escarp]

if you start to work out expanding this, this is where it will tie back into the original problem when I joined in

[errant otter]

that looks so messy

[torn escarp]

because all the sums of terms will start to look like those S(n) earlier 😛

that inequality n>d is what is forcing the multiple of p-1 case from not happening, forcing it to 0, it that sorta makes sense

[errant otter]

ig so

[worn lava]

ok, so isn't it the case that due to Wilson's theorem, we may safely say that x is prime iff (x-2)! is congruent to 1 (mod x)?

[still flare]

Yes

[worn lava]

k, cool

[white lion]

Hey @torn escarp

I had friend who has this question :to if anyone sees a trick to finding/restricting solutions in $\mathbf{N}$ to $q^s - p^r(p - 1) = 1$ where $p, q$ are odd primes and $s > 1$

[sterile pumice]

jayz

[white lion]

So far the only values he found. (p,q,r,s) = (19,7,1,3)

I suggested the following: these are my thoughts, $q^s - p^r(p - 1) = 1 \implies q^s - p^{r + 1} - p^r = 1 \implies q(q^{s-1}) + p( p^{r-1} - p^r) = 1$

Since $q,p$ are primes $qx + py = 1$ always has a solution $x_0, y_0$ therefore all our solutions are of the form $x = x_0 + kp$ and $y = y_0 + kq$ then we equate with $q^{s-1} $ and $p^{r - 1} - p^r$ with $x_0 + kp$ and $y_0 + kq$ respectively and this reduces down to a problem of solving the congruences $q^{s-1} \equiv x_0$ (mod p) and $p^{r-1} - p^r \equiv y_0$ (mod q)

[sterile pumice]

jayz

[white lion]

I’m convinced that primitive roots will help out here but I’m not familiar with it, what do you think?

[slim vortex]

Greetings all. Here's a little problem I'm wondering about. As is well known, for any positive integers n and d, there exist nonnegative integers q and r < d such that n = qd + r (division algorithm).

In the special case 17 = 5(3) + 2, we happen to also have d + r = q.

This doesn't usually hold, for example 101 = 50(2) + 1, but 2 + 1 =/= 50.

Is there any nice characterization of pairs (n,d) for which d + r = q?

[open mist]

Since r < d, there's only d solutions for each d, r = 0 to d-1

And to each of those r is clearly associated the solution n = (d+r)d+r

So yes, there's a very simple characterization

[slim vortex]

I'm afraid I don't follow

if we take n = 5, there is no d that has the property d + r = q

so not all larger numbers are possible in ordered pair solutions (n,d)

maybe what you wrote accounts for that but I don't see it

[errant otter]

Need help with showing that the nth fermat number is divisible by the nth fibonacci number- I.e $2^{(2^n)} \equiv -1 \mod F_n$

[sterile pumice]

Kiameimon | Welt Rene

[errant otter]

Where F_n is the nth fibonacci number (fermat numbers are 2^(2^n) + 1)
I'm quite sure the approach to this is strong induction, but I still can't figure it out.

I tried using fibonacci recursive formula, but that doesn't seem to get far
And tried splitting 2^(2^n) into smaller components like 4(2^(2^(n-1))) where I can apply inductive hypothesis but even then.... nope

[torn escarp]

you sure this is true?

what do you get for n=2 and n=3 for instance

[errant otter]

Oh

Wait

I misread the qns

Ahem in the meantine

So (a) was pretty trivial by looking at prime factorization
(b) was basically euclid lemma

But (c)...

Err, its a bit confusing to me

So MR witness is a number a which is >= 2 and <= n-1 s.t a^d != 1 mod n and a^(d 2^i) != 1 mod n- oh

It's -1

I couldn't find my contradiction because I thought it was 1

[open mist]

Btw, b) can also be argued by saying Zn is a field so X^2-1 has at most 2 roots

[errant otter]

[formal tiger]

Oh here's a number theory channel

Let me ask here >.<

I took a horrific number theory exam today... (the exam ended already)
One of the questions asks us to proof:

Assume O_p(a) = O_p(b), where p is a prime (O_p(a) is the order of a in modulo p), then there exists positive integer s, r s.t. b = a^r (mod p) and a = b^s (mod p).

I still can't think of a solution by now :(

[wooden glen]

Do you know that the multiplicative group modulo p is cyclic?

[formal tiger]

Yup, there exists primitive root in modulo p

[wooden glen]

"elements with the same order are powers of each other" holds in cyclic groups in general.

[formal tiger]

Is there any proof of it? I tried to find it online sometime before but can't find it online 🥲
(Bad googling skills)

Ah seems I somehow found it

Oh it's called fundamental theorem of cyclic groups...

So that means the exam requires us to proof fundamental theorem of cyclic groups from scratch, what a good exam! 💀

Anyway thanks

[wooden glen]

Hmm, actually I think there's a shortcut in the case of the multiplicative group of a field in particular. Suppose |a|=|b|=n. Then, by definition, a generates an n-element subgroup of the multiplicative group, and each element of that group satisfies x^n=1. However, in a field, the polynomial x^n-1 can have at most n roots, so the powers of a are all the roots there are. In particular since b^n=1 too, b must be one of those elements.

[formal tiger]

0.0 Thats a good argument!

Thats why I love math and hate math at the same time

[west sage]

if n/0 is undefined do we still say that 0 does not divide n?

[still flare]

That's not how we define divisibility, typically.

We write a | b if there exists some n such that an = b. Note how this totally sidesteps definedness of division.

From there you should try to determine all numbers b for which 0 | b. This is your turn now.

[west sage]

there are none

[still flare]

Not true.

Try again.

[west sage]

uh okay

so to get b we must multiply some integers a and n

[still flare]

Where a = 0.

[west sage]

yeah

and if b=0 then i suppose then that 0 divides b

[still flare]

Indeed. The only number b such that 0 | b is b = 0.

[west sage]

and if b is anything else it's just simply "0 does not divide b" right?

[still flare]

By definition, yes.

[west sage]

okay, sorry if that sounded kinda dumb, i'm only learning divisibility in depth today

[white lion]

I want to find odd primes p & q such that for 1 = px + qy, we have that (p, y) = 1 and (q, x) = 1.

[torn escarp]

it's always possible

[white lion]

Really?

[torn escarp]

why would I lie on the internet?

also the euclidean algorithm

[white lion]

😞 don’t get my hopes up

[torn escarp]

the question really isn't clear to me tbh

are you saying you want to find p,q and fix them as constants

and then find x,y that make this true?

[white lion]

Nah I want to find odd primes and q such that the solutions x and y for 1 = px + qy have the property that (p, y) = 1 and (q, x) = 1

Since every two primes are relatively prime

We’re always going to have this equation but I want one where the solutions have this particulars propert

[torn escarp]

suppose they didn't

like (p,y)=p

what does that say about 1 ( = px+qy)

[white lion]

That would mean 1 is a multiple of p which is untrue

[torn escarp]

qed

[white lion]

lol

Wait..

So it always hold?

[torn escarp]

I was lying about lying on the internet

[white lion]

despicable

I mean so the reason I’m asking this is because well

[torn escarp]

actually I was thinking about a similar problem a while back, maybe you'd be interested

[white lion]

What is it?

[torn escarp]

looking for all primes solutions to 1 = pq-rs (not necessarily distinct primes)

[white lion]

Interesting why are you looking at it?

[torn escarp]

it's kind of fun, start by assuming they're all the same, solve that one, then assume there are only 2 different primes, prove those cases, etc

[white lion]

Looks like a fun puzzle

[torn escarp]

it ramps up in difficulty

idk bored

[white lion]

Hmm 🤔

Ima try it out

[torn escarp]

I was able to get quite a few cases down and then got stuck eventually

[torn escarp]

good luck, let me know how far you get, then we can try to see how to move forward

[white lion]

Sounds good

[white lion]

I was wondering if my logic was sound for this problem so I’m trying to find the solutions for this equation $q^s + p^r(p-1) = 1$ we can write it as such $q(q^{s-1}) + p(p^{r - 1} - p^r) = 1$ and since $q,p$ are primes there is always a solution to $qx + py + 1$ say $x_0,y_0$ therefore all out solutions are of the form $x = x_0 + kp$ and $y_0 + kq$ and then we equate them with $q^{s - 1} and p^{r - 1} - p^r$ respectively and this reduces down to a problem of solving the congruences $q^{s - 1} \equiv x_0$ (mod p) and $p^{r - 1} - p^r \equiv y_0$ (mod q). Now for the second congruence we can we can write as such p^{r-1} (1 - p) \equiv y_0$ (mod q). Clearly (1 - p) has an inverse in mod p so that we can further write it has $p^{r-1} \equiv (y_0)(1 - p)^{-1}$ (mod q). So far is this correct? And when would this be solvable I’m assuming this has something to do with primitive roots but I’m not too familiar with it

[sterile pumice]

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

[torn escarp]

that sounds approximately right, although I don't think there's any way forward that isn't something like hensel's lemma which just computes forever

[white lion]

I’ve never heard hensels lemma before, will have a look 👀

[torn escarp]

the equation ax+by=1 does have to do with inverses, since euclid's algorithm always gets you an answer when (a,b)=1, it means that a is invertible mod b, since ax=1 mod b

so it gives you a way of computing inverses

not sure if that's what you're sort of thinking/asking about

[errant otter]

very efficient one at that

[white lion]

I was really looking to see if the congruences p^{r-1} \equiv (y_0)(1 - p)^{-1}$ (mod q) as well as $q^{s - 1} \equiv x_0$ (mod p) be solvable by primitive roots.

My understanding is that there is always a primitive root in mod p if I remember correctly. So for example if $x_0$ is relatively prime to p. Then we can write it as a power of the primitive root as well as q and then solve. Likewise for the second congruence.

[sterile pumice]

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

[torn escarp]

you can combine congruences to get one mod pq with the chinese remainder theorem

and yeah you can use primitive root powers to do that and write a simple closed form of that

for instance say you have $z=u \mod p$ and $z=v \mod q$ then because $q^{p-1}=1 \mod p$ and $0 \mod q$ (and likewise flipping the primes) you have, $$z= uq^{p-1}+vp^{q-1} \mod pq$$

[sterile pumice]

Merosity

[torn escarp]

although p, q are not necessarily generators, you can pick a lower exponent, but it'll end up dividing those exponents

I think it's good and necessary to keep looking around to understand what does/doesn't work

[white lion]

This follows from CRT?

[torn escarp]

yeah, it's basically an explicit form of it

[white lion]

I’ve done CRT but not properly I was actually properly going through it today

[torn escarp]

you can get a bit more general and combine any number of powers of primes in this sort of fashion with the euler phi function

kind of cumbersome though to really use this, it's just nice to know we can

[white lion]

Kinda like the Euclidean algo when solving linear congruences lol

[torn escarp]

the key is that we can make somethig that's 1 mod p^a while being 0 mod q^b and 0 mod r^c etc

for instance (q^b r^c)^phi(p^a) will accomplish that

[white lion]

I see gotcha that makes a lot of sense

Thanks

[torn escarp]

basically Hensel lets you go from like mod p to mod p^k and CRT allows you to combine them after that

[white lion]

Interesting stuff going too look more into it

[torn escarp]

I think your original problem though will have to be solved another way, I don't think this will do it

might need some kind of counting argument since p^r(p-1) already looks like phi(p^{r+1})

or like, where did the problem actually come from

kind of in xy problem territory

[white lion]

So this is the “original” problem I have no idea what he was saying here but yeah

I was thinking a bit more about the field question, and I believe the following is true: If we let K_m denote Z_m* \cup {0}, then to get a consistent addition on K_m (and thus have it be a field, say F_p^k) it suffices to have Z_m* be group-isomorphic to Z/Z(p^k - 1). In fact, I believe that F_p^k is a subfield of K_m (meaning that we can define a consistent addition and multiplication on a subset of K_m in such a way that it is isomorhic to F_p^k) iff Z_m* has a subgroup which is isomorphic to Z/Z(p^k - 1).

The reason is that if we have a multiplicative group isomorphism, we can compare the addition and multiplication tables of F_p^k with the multiplication table of K_m (which is just defined via Z_m* and the 0 axiom) and use them to "trace" the addition table for K_m). Then any inconsistency in the addition table of K_m corresponds to an inconsistency in the addition table of F_p^k, of which there aren't any.

Which, using the fact you mentioned about when Z/nZ is cyclic, would imply that K_m is a field iff p^k - p^(k-1) = q^s - 1 for odd primes p, q and naturals k, s and m = p^k or m = 2p^k.

So if 19^2 - 19 = 7^3 - 1 is the only solution where s > 1, then we have that K_m is a field of composite order iff m = 361 or m = 722

Yeah kind of mumbo jumbo to me tbh

[feral pier]

can i get help on a set theory problem?

[torn escarp]

finite field of composite order?

if ab=0 but a!=0 and b!=0 then it's not a field

[feral pier]

https://discord.com/channels/268882317391429632/1164811865881325649

[white lion]

There doesn’t exist any finite field of composite order?

[torn escarp]

sorry I thought you meant composite characteristic, the only finite fields of composite order are powers of a prime

[white lion]

Oh ok

[feral pier]

The relation on N defined by a related to b if there is an integer n > 1 that evenly divides both a and b. Show wether or not the relation is transitive.

[west glade]

try some examples to get a feeling for whats going on

[white lion]

So which terms are the primes is it p and q, or p and r?

[torn escarp]

all prime

p, q, r, and s are all prime

for instance p=2, q=13, r=5, s=5

[errant otter]

write an O(n^4) sols to bruteforce this

[unique cypress]

Weak

[errant otter]

[open mist]

Duh, you can trivially make it O(n^7/2)

[errant otter]

[open mist]

Actually, optimizing this might be nontrivial

Definitely should Erathosthene this

And I don't wanna

[errant otter]

[unique cypress]

Sieves

[undone sundial]

Why is it that every number > 9 is divisible by 9 when you subtract the individual digits from the number?
Like 134… 134-1-3-4=126 which is divisible by 9.

[normal heart]

any positive integer is congruent to its sum of digits mod 9

you can try to prove that

[undone sundial]

Yeah. But I’m asking why

[normal heart]

For example, 134=1*10^2+3*10^1+4, try taking mod 9

[undone sundial]

I don’t think I follow

[undone sundial]

I think I maybe asked in the wrong place

I was hoping for the “for dummies” version. 😅

[errant otter]

idt there is a for dummies version

the only way out is a proof via modular arithmetic

[undone sundial]

I just mean a way of explaining like you’re talking to a dumb person (me) not mathematical symbols and jargon

I concede that this being the “early university” category should mean I have a certain level of understanding appropriate for the level of discussion here. Which I don’t. Hence I think I put it in the wrong channel.

[nocturne token]

Does $12345=1\cdot10^4+2\cdot10^3+3\cdot10^2+4\cdot10^1+5\cdot10^0$ make sense? Are you comfortable with the fact that if $a$ and $b$ are both divisible by some number $c$, then $a+b$ is also divisible by $c$?

[sterile pumice]

dxdydz

[undone sundial]

Yes. All of that makes sense

[nocturne token]

Those are the only things I end up using in the proof I posted.

Other than that you should look up sigma notation.

[sacred junco]

Yes , it's true

[barren garden]

Shoup's Computational Introduction to Number Theory and Algebra looks pretty nice

[unique cypress]

That sounds like applied math

[barren garden]

[white lion]

@torn escarp for pq - rs = 1, I did the case were q=p and r=s then we have q^2 - r^2 = 1 then by difference of squares we have that (q - r)(q + r) = 1 this only has solutions when q - r = 1 and q + r = 1 or q - r = -1 and q + r = -1

For the first system it’s clear there are no solutions since this would only be true for consecutive prime integers of which only exist 3,2

Same for the second system

So there are no prime solutions for this case

[normal heart]

(2,3,4)=1 but (2,4)=2

so former doesn't imply latter

[torn escarp]

nice that basically covers all the cases up to 1 or 2 distinct primes, I suggest trying p^2-qr=1 next

[white lion]

$p^2 - qr = 1$ hence $p^2 \equiv 1$ (mod q) and since it’s fact that if $a^2 \equiv 1$ (mod p) then $a \equiv +/- 1$ (mod p), hence $p \equiv +/- 1$ (mod q) hence we can write

$p = ql +/- 1$, if q is an odd prime the $p$ is even and the only even prime is 2 hence p = 2 plugging it into the equation we get 4 - qr = 1 which Implies that qr = 3 which is clearly not true when q and r are primes. In the case that q is an even prime we get that q = 2 and it follows p must be odd, hence we get the equation $p^2 - 2r = 1$ therefore $2r = p^2 - 1$ by difference of squares we get that $2r = (p + 1)(p - 1)$ hence $r|(p-1)(p+1)$ therefore $r|(p-1)$ or $r|(p+1)$ since p is odd both p-1 and p+1 are even hence the prime $r|2k$ or $r|2l$ respectively hence we have that $r|2$ or $r|l$, or we have that $r|2$ or $r|k$. If $r|2$ then r = 2 and it is clear that there is not solution likewise if r=k or r=l this will lead to a contradiction

[sterile pumice]

jayz

[white lion]

There aren’t any solutions to this equation

[torn escarp]

nice, good

I worked it out slightly differently, (p+1)(p-1)=qr so q=p+1 and r=p-1 but then this means we have 3 consecutive primes which is impossible. (I left out a few minor details that are simple to check)

the only other one involving 3 primes is then pq-r^2=1, this one I'm still working on but there's a lot of progress that we can make

I'll say what stuff I have so far after you give it a shot, maybe you have a different approach than me that will work

[white lion]

That’s actually really nice lol

[torn escarp]

thanks 😎

[white lion]

let’s do it

[torn escarp]

sounds good, I'm gonna try to comb through what I have so far and see what I can do in the mean time

[normal heart]

Quadratic residues should kill it

[torn escarp]

I don't think it can be killed, but I'm thinking maybe we can try to prove it has infinitely many solutions of some form or another

at least, I'm able to whittle it down to something roughly like that, but past a handful of conditions that doesn't really indicate one way or the other unfortunately

[normal heart]

-1 is a quadratic residue mod p and mod q, so r has one possibility mod 2

[torn escarp]

one of the primes must be 2, so the only interesting case really boils down to writing it of the form like p^2+1=2q

from here q=1 mod 4 however you like to see that, and there's a bit more annoying things we can do too

past 1=2x13-5^2 and 1=2x5-3^2 we always have q=1 mod 60 and (p|5)=-1

It'd be nice to try get something more precise

q= ((p-1)/2)^2 + ((p+1)/2)^2 probably not super useful to us

if p=1+2n then q=1+4 n(n+1)/2 more pokin around

[pure dock]

What does a sub k represent?

[nocturne token]

a_k is the kth digit of N.

[pure dock]

How is the sum of a_k divisible by 9

I understand that 10^k - 1 is divisible my 9

Is this divisible by 9

Ohh wait I understand

This is the term we subtract to make it divisible by nine.

[pure dock]

Ok so for the example 341.
341 = 3(100) + 4(10) +1(1)
341= (3(99) + 4(9) + 1(0)) + 3 + 4 + 1
Therefore by moving the the digits to the other side, we get.
341 - 3 - 4 - 1 = (3(99) + 4(9) +0)
The term on the right is divisible by 9 because all of its parts are divisible by 9.
This works for all numbers.

[undone sundial]

Omg thank you. That makes sense 🥰

[nocturne token]

That's not what is going on.

[nocturne token]

This sum is divisible by 9 by assumption.

Also 341 is not divisible by 9.

[pure dock]

Yea that proof supposes the sum is divisible by nine but they were asking when the sun isn’t necessarily divisible by nine

They asked why a number minus the sum of digits is divisible by nine.

[nocturne token]

Oh I see, sorry.

[pure dock]

It’s the same proof though

Which is kinda interesting

@nocturne token does this sort of proof work for other number systems?

Like base 6 being divisible by 5 or something

[nocturne token]

I have not tried it but I imagine you could try to generalize it to what you just said, find a b-1 divisibility rule for base b.

[pure dock]

I’m gunna do it. 😼

It’s actually not that interesting on further inspection.

[nocturne token]

A lot of base specific things aren't.

[pure dock]

a^k - 1 = (a-1) x 111111111 (k ones)

[nocturne token]

Yeah

[pure dock]

Where a is the base

[nocturne token]

I think it makes for a decent exercise or intro to number theory kind of thing though.

[pure dock]

@nocturne token are you graduated?

[nocturne token]

Yeah

[pure dock]

Do you have a degree

[nocturne token]

I have a masters.

[pure dock]

In what

[nocturne token]

Computational mathematics.

[pure dock]

I’m working on a program to simply return true or false as to wether the number, n, is prime. It works by looping starting at n mod 2 then n mod 3 and so on.

Is it the case that I can stop at square root n? To prove if it’s prime?
@nocturne token

[still flare]

It's generally a bad habit to ping people if you're not already in a conversation with them

Indeed you can stop at sqrt(n), since if there is a factor k of n which is greater than sqrt(n), then n/k is also a factor of n, which is less than sqrt(n).

[nocturne token]

You can do that but I recommend using a sieve instead of trial division because trial division is really slow.

[pure dock]

I don’t really know how to program that. Rn it loops through each number. I could change it so that it has a step value. If I do step value two it will increment by twos and I won’t waste my time on evens. Is this what you mean?

[pure dock]

I don’t know how to generalize that so that it skips more

[nocturne token]

Yeah that is what I mean.

https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Pseudocode

[pure dock]

I understand the sieve of Eratosthenes works but this doesn’t make sense to me.

[nocturne token]

What part are you having trouble with?

[pure dock]

for j = i2, i2+i, i2+2i, i2+3i, ..., not exceeding n do
set A[j] := false

What does this mean? (Those are powers)

[nocturne token]

For every number j=2, 3, 4, 5, .. we associate a truth value A[j]. Starting at 2 we increment by 2s and every value j we hit while incrementing (besides 2 itself) we set A[j] = false. Then, after doing that, we go the next value with a[j] = true, which is 3, and repeat the process incemenrint by 3s.

At the end only the values marked true will be prime.

[pure dock]

Ahhh

[pure dock]

I need to do a different way of sieving

[pure dock]

I can’t have an indefinite list

[nocturne token]

What do you mean?

[errant otter]

Sieve of atkin?

[loud maple]

Try the AKS primality test

[pure dock]

I don’t think I can program a sieve cause it would require an indefinite list in order to prove primality.

[noble obsidian]

why does mod 525 have a primitve root?

its 5^4 but I thought something has primitive roots iff its p^2 or 2p^2 for some p

or 2 or 4

[pure dock]

Also I need to know how to turn a list of prime factors into a list of factors

[loud maple]

Do you mean 525 or 625?

Because 5⁴=625

[loud maple]

And the condition is the number being 2,4, p^m for any m and any odd prime p, or 2×p^m for any m and any odd prime p

[brazen fox]

So the book I'm reading says it's clear that (b,a)=(a,-b) but I'm not exactly seeing how its clear. I guess I see how the gcd of a,b is a common divisor of a,-b, I just am not convinced on it being the greatest

[noble obsidian]

Ah okay thanks Knight

[brazen fox]

Okay I'm not sure if this is correct but if so I guess it is simpler than I was trying to make it.

Let $d=(a,b),$ then $d|a$ and $d|b.$ Since $d|b,$ then $b=dk \rightarrow -b=d(-k),$ so $d|-b.$ It follows that, $d|ax-by.$ Let $m=(a,-b),$ then $d|m.$ We also have $m|a$ and $m|-b,$ so $m|b.$ Thus, $m|d,$ so $m=\pm d,$ but $m>0$ and $d>0,$ therefore $m=d.$

[sterile pumice]

Kenshin

[white lion]

Am I understanding this q correctly? I need to prove that for every n positive consecutive integers $a_1,a_2,...,a_n$ we have that $p_i|a_i$ for each $i$, where $p_i$ denotes the $i$th prime.

so the first prime is 2 right?

[sterile pumice]

jayz

[white lion]

if it is this is clearly false..\

Im not sure if the question is wrong or im understanding it incorrectly

[torn escarp]

can you send the picture of the question or something, sounds like it's phrased wrong

well this might give the answer away assuming I'm guessing correctly, but I'm thinking it's asking to prove that you can solve the system of equations,
x = 0 mod p_1
x+1 = 0 mod p_2
x+2 = 0 mod p_3
...
x+n-1 = 0 mod p_n

[errant otter]

Idt it's a good idea to use primality tests to implement prime sieves

[white lion]

Yeah, it says word for word "Prove that any positivie integer $n$, there exist n consecutive positive integers $a_1,a_2,...,a_n$ such that $p_i|a_i$ for each i, where p denotes the ith prime."

[sterile pumice]

jayz

[torn escarp]

yeah that's what I was thinking, what you wrote is slightly different before

[white lion]

Gotcha, but wouldn't the first prime be 2?

[torn escarp]

yeah

[white lion]

but I can find n consecutive integers where thats not the case..

obviously

[torn escarp]

"there exists"

just cause you found one that didn't doesn't mean there isn't another that does

[white lion]

[white lion]

ah

right

its late

[loud maple]

Yeah I was just messing around, apologies

[copper wolf]

if $p$ is an odd prime such that $p\equiv1\mod{4}$, i know that the number of $k\in{1,...,p-2}$ such that $k$ is a quadratic residual modulus $p$ is $\frac{p-3}{2}$, from wikipedia. But i don't understand how to prove this, wikipedia's sources link to exercices left to the reader 😢

[sterile pumice]

Overfull hbox, badness 1000

[open mist]

f: a -> a² is a group morphism since Fp* is commutative
Since Fp is a field, X²-a² = 0 has 2 roots, a and -a. In particular, 1 has 2 roots. Hence Fp* / Ker f has p-1 / 2 elements, and is isomorphic to Im f
Therefore there are p-1 / 2 perfect squares modulo p.

Now for "-1 is a square iff p = 1 mod 4":
By Fermat, a^(p-1 / 2)² = 1, so a^(p-1 / 2) = 1 or -1
Notice that if a is a square, then a^(p-1 / 2) = 1, so we can also say
{squares mod p} subset Ker (a -> a^(p-1 / 2))
And then notice that p-1 / 2 is even iff p = 1 mod 4, so that's your NSC for -1 to be a square. Then there are p-3 / 2 other squares in Fp*

[copper wolf]

i understand now, thank you very much

[open mist]

actually
the -1 is a square part requires {squares mod p} = Ker (a -> a^(p-1 / 2)), not just subset
I think you can prove this using the cyclicity of Fp*
There's an element g of order p-1
Then if an element is in the kernel of that morphism, it's a g^k with p-1 | (p-1 / 2) k , which is only possible if k is even, i.e. g^k is a square. That way it doesn't rely on the first proof.

If you already have the first proof like we do here, you don't need to use the cyclicity of Fp*, because you can look at the cardinals using Lagrange's theorem to say the kernel must have cardinal p-1/2 (or the morphism is constant, which I'm not actually quite sure how you'd disprove) and then you get the equality as well

[open mist]

Unfortunately, I asked a friend and he doesn't know how to prove the morphism isn't trivial without saying the group is cyclic, as obvious as the property is

[copper wolf]

it's okay, i proved it using a class property. But i am very thankfull that you explained it to me so well

[rose birch]

i cannot for the life of me figure this out

have been trying for hours studying the material and proofs

and still no idea how to show this

ik i can bound this bellow by: (pk/qk is the k-th convergent)
for k+1 s.t. qk+1 > q, we have tht:
|α - pk/qk| < |α - p/q| < 1/ql
for the denominator of the l-th convergent ql

[rose birch]

made a thread about this in help where i explained the problem in detail and some of my ideas :)

[glossy coral]

hey guys i wanna ask u i want to make a survey of trending games can u guys help me?

[noble obsidian]

induct on q WLOG q > 0

let k be fixed, then induct on q

pick p accordingly

then by induction you have shown infinitely many

[sacred junco]

hello

i need some help with modular arithematic

what is periodicity in modular arithematic

for eg

[nova maple]

When you look at 0,1,2,3,.. modulo any number n, the values start repeating. Take the sequence of numbers 0,1,2,3,... modulo 3.
You have
0 (mod 3),1 (mod 3), 2 (mod 3), 3 (mod 3), 4 (mod 3),...
but since 3 is 0 (mod 3), 4 is 1 (mod 3), 5 is 2 (mod 3) and so on, your sequence becomes 0,1,2,0,1,2,0,1,2,..

This sequence is periodic , that is, it repeats. That is what periodicity refers to in modular arithmetic

[delicate vortex]

I’m trying to understand how Pythagorean triples are distributed in the complex plane, through squaring Gaussian integers. I have come across the parabolas of the form x = y^2/4n^2 – n^2 for n in N, which each have lots of triples on them, and I am trying to understand how I could arrive at this form.

The focus of a parabola x = ay^2 + by + c is the point (c + 1/4a, -b/2a). If we set the focus to be (0,0), we get that b=0 and c= -1/4a. And setting n^2 to be -c = 1/4a, we arrive at the above parabolas.

I don’t understand how these views are in any way equivalent. How do we know that the integer points on these curves are an integer distance from the origin? Why would we think to construct something like this, and/or set the focus to be at the origin?

[torn escarp]

I'm confused, I thought you thought this up, why don't you say how you came to it?

[delicate vortex]

found in a comment by user MegaMoh under this video and don't fully understand the justification https://youtu.be/QJYmyhnaaek?si=lTkRniWZkMHvAmgZ

[torn escarp]

I'm not gonna look for a youtube comment sorry

[delicate vortex]

"For anyone who wants to graph the intersecting parabola, the general equation for each parabola is x=[+/-](y^2 / 4(n)^2 - n^2) where "[+/-]" is plus or minus and "n" represents the nth parabola away from the origin. In latex, it's written as:

x=\pm\left(\frac{y^2}{4n^2}-n^2\right)

for those who want it written neatly. The straight line equations are as simple as taking each coordinate that from the intersection (a,b) and making the equation y=b/a * x or y= \frac{b}{a}x in latex

NOTICE: A parabola written in the form of ax^2+bx+c has a=1/(4f) where f is the focus. I noticed that the focus for those parabolas using the equation is n^2 so that the focus of all of these parabolas is it's number squared. then noticed that the focus changes when the "c" term changes in the equation, then the focus get translated by "c" and what turned out is that the "c" term in the above equation is also n^2! so n^2(the focus) - n^2(translation by "c" term) gives 0. so that all of those parabolas have their focus at the origin and each one is away from the origin by n^2 distance! Let's work together to figure out why this equation works with these givens"

[torn escarp]

thanks

bit too long for me to think about, maybe someone else will play, I might try looking at it tomorrow

goodnight

[nova maple]

Wow I didnt know such parabolas existed

My guess would be that it has something to do with the (m^2-n^2,2mn,m^2+n^2) parametrisation

Oh obviously it does

x=m^2-n^2, y=2mn
Eliminating m from these,

m=y/2n (from the second equation) substitute this in the first equation and you have x=y^2/4n^2-n^2
And you have exactly what you wanted. I hope this answers your "how do I arrive at these" or "where do these come from" questions

[errant walrus]

Let a>=2 and b>=2 with gcd(a,b)=1. How can I show that the only integer solutions to ka+lb=0 are those of the form k=-bn and l=an for integer n?

[west glade]

ka=-lb. a divides the left side, so it also has to divide the right side

[errant walrus]

ty

[rose birch]

isnt this equal to τ(n)

i lied

[torn escarp]

step 1: recognize why it's a multiplicative function
step 2: work out what F(p^k) is
step 3: piece it together

[rose birch]

i solved it i solved it

we know sum multipolicative if what it sums is

and F(p^k) = F(p)

as μ(p^l) l > 1 = 0

[torn escarp]

nice

[white lion]

@torn escarp hey we just wanted to know if there exists a solution for the equation we were trying to solve right?

[cloud widget]

hey all, I'm doing some modularity stuff for an algorithms class and haven't been able to really sort this one out.

My idea so far has been that since the number has 2k digits, we can split this up into k pairs where the first digit has weight 1, and the second has weight 2. We can also utilize some logic with making sure each pair will be divisible by 11. Beyond that though I'm not really sure how to approach this without doing an annoying case-by-case with each digit 0-9. Any advice?

[open mist]

Just argue that either operation must change the value mod 11.

[cloud widget]

how do we know it wouldnt end up still being 0 mod 11?

[open mist]

Prove it

[open mist]

Well unless you swap 0 and 0 I guess

But it's fair to only consider meaningful perturbations

[cloud widget]

I suppose the first one could be argued with two cases, one being with a number with weight 1 being changed and another with weight 2 being changed, and using some kind of difference to show that that isn't the same mod 11. so, thank you for help on that 🫡

otherwise for swapping two consecutive digits, aside from 00 there are no other valid same consecutive digits, but otherwise can you use the same kind of difference idea as in part i...?

[open mist]

Express the change in the "valuation" for the operation
Show that it can't be 0 mod 11

[cloud widget]

how would I even address a swap for 00? I feel like that's a hiccup on the question's part

[open mist]

That is both rigorous and short

[open mist]

Yeah, that's why I said it's fair to assume we're meant to only consider meaningful perturbations

[cloud widget]

makes sense. I'll just say something like "considering only meaningful perturbations, not counting a swap on 00..."

I guess a swap of any two consecutive digits wouldnt change anything anyways even if there was somehow two consecutive 2s for example

duh

thanks again lol

[somber hornet]

Hi guys, I'm confused by the first part of this proof, why would (a^ds)-1 necesarly divide a^d - 1?

[loud maple]

Because the polynomial (x-1) is a factor of (xⁿ - 1) for all n

Also you switched around the two. a^d - 1 divides the other

[somber hornet]

ah yes thanks so much

[somber hornet]

by the factor theorem right?

[torn escarp]

I was looking for the best description of all solutions, I'd guess there's probably infinitely many solutions but I've been busy, but that might be easier to shoot for.

[white lion]

yeah

[sand rain]

for any given t\in N, there exists n\in N,n>=t , such that 2^n-1 is prime

is this true

oh nvm, seems like an open problem

would've made a cfl quesstion easy

[torn escarp]

There is some stuff we can say though about when it can be prime

[white lion]

im trying to check if x^5 - x + y^2 + 3 has any solutions this what a collegue did: (reduce mod 5) x^5 = x mod 5 by Fermat's little theorem
so x^5 - x = 0 mod 5
and then y^2 = 3 mod 5

how did he get y^2 = 3 (mod 5)??

[torn escarp]

looks like a mistake

y^2+3=0 mod 5 if you're looking for solutions

assuming that means roots of the expression

[white lion]

hmm wdym?

[torn escarp]

what does "solutions" mean

[white lion]

oh right, the original equation was like this I frogot to put it up x^5 - x + y^2 +3 = 0

[torn escarp]

cool

[white lion]

so y^2 + 3 = 0 (mod 5)

ive never reduced equations before by a mod m so im not to familiar with the rules of the game

[torn escarp]

fortunately -3=2 mod 5

and both 2 and 3 are not quadratic residues

[white lion]

yeah gotcha

Im guessing if i wanted to reduce it mod 5 I would initially write it like this x^5 - x + y^2 + 3 = 0 (mod 5) right

?

[torn escarp]

yeah

[white lion]

and a solution in this Z_5 is a solution in Z

right?

[torn escarp]

not quite

you can have a solution in Z_5 and no solution in Z

(not in this case ofc)

[white lion]

wait huh

I was lied to

[torn escarp]

idea is if there is a solution in Z, then there's a solution in Z/nZ

if you can't find a solution in Z/nZ, then there can't be a solution in Z

otherwise it would reduce down to it

let's take a simple case

clearly x^2+1=0 has no solution in Z, much less R

[white lion]

yeah

[torn escarp]

but x^2+1=0 mod 5 has two solutions

[white lion]

right

2 and 3*

[torn escarp]

believe again

-1=4=2^2 is basically the reason why the original mistake didn't mess up the answer between picking 3 and 2, -1 is a quadratic residue mod 5

[white lion]

oh interesting

coincidence

[torn escarp]

for which primes is x and -x are both quadratic residues?

or both nonresidues

[white lion]

mod 5?

[torn escarp]

no, which primes as in mod p

p=5 is one case

[white lion]

let me try

[torn escarp]

p=3 doesn't work, 1 and -1 are not both QRs

[white lion]

all primes of the form 4l + 1?

[torn escarp]

yup

[white lion]

nice

I want to know weather or not $(x + 1)^3 = x^3 + y^2 + 2$ has any solutions to me I think reducing it mod 3 is a good choice and we will be left with $x + 1 = x + y^2 +2$ (mod 3) hence $y^2 = -1$ (mod 3) from here its straightforward

[sterile pumice]

jayz

[white lion]

is my argument on the right track?

[torn escarp]

on the right track? it looks like it's arrived at the station already

[white lion]

https://tenor.com/view/jason-bateman-forced-laughing-forced-fake-laugh-gif-5412334

@torn escarp Im trying to recall this fact im not sure if Im correct or not but basically suppose we have a congruence of the like x^k = n (mod m) and gcd(phi(m),k) = 1. Then if we know the inverse of k in modulo phi(m) call it f, then (x^k)^f = n^f (mod m) should reduce down to someting nice right?

[torn escarp]

yeah you can use euclid's lemma to get fk+phi(m)t=1, since you can think of the exponents as mod phi(m)

and you end up with x=n^f mod m

[white lion]

right right

is there a name for this method or no?

[white lion]

euclids lemma or bezouts identity?

[torn escarp]

whoops I meant euclid's algorithm, yeah to get solutions to bezout's identity

[white lion]

[noble obsidian]

if p \cong k mod m

then is p always \cong k mod m_1 where m_1 is a factor of m?

oh yeah wait this is true by definition lol

so the chinese remainder theorem is only useful for going backwards

[torn escarp]

the CRT is not sufficient to go backwards always, if m_1 | m and gcd(m_1, m/m_1) > 1

Hensel's lemma helps with that

[noble obsidian]

I see

thanks

[torpid dagger]

Does anyone know linear programming

[sacred junco]

Please I have this problem with almost all the exercises : I give you an exemple,
The question is : "Solve the following equations."
a) x^2+x+3 is congruent with 0 modulo 5. Thanks to a congruence table, I can say that it is true for x is congruent with 1 and 3 modulo 5. The problem is that there is an infinity of solutions : we can do bounds of 5 in every sense and with every number, and find a solution for the equation. Ex : 3+5=8
8^2+8+3=75 whom is also a multiple of 5. Sorry for my bad english I am French. Thanks

Obviously, it works also with 1+5 and for 1+10, 1+15, 3+20,3+15, etc.... In fact, it works for 3+5k and 1+5k

[west glade]

well in modulo you dont care about all these other solutions. in modulo they are all the same thing

but why are you doing mod 5 and not mod 3

[sacred junco]

Ho sorry, what i writed is inexact, in fact the a) is modulo 5

[sacred junco]

So i just have to write : "the solutions are x=1 and x=3 ?"

[west glade]

beforr you do that you should check your work again

[sacred junco]

Oh

Okay

But in my calculator it works

[fathom sierra]

you wrote x^3 + x + 3 in your post

[sacred junco]

Sorry, it is -2, for x is congruent with 2 modulo 5, x^2+x+3 is congruent with -2 modulo 5

[sacred junco]

Oh sorry, so can I write that these are the solutions ?

[fathom sierra]

how do you get 0 for x=3 ?

@sacred junco

[sacred junco]

-1^2-1+3=3 =5-2

Yes it is strange

And it is also strange that it works with 3...

[fathom sierra]

also 3 = -2 mod 5, not -1

[sacred junco]

Yeah true

Ho no 3^2 =10-1

[fathom sierra]

yeah -1 that's what you should get

[sacred junco]

And for the equation, we see that the solution is 3, it is strange because x^2+x+3 is congruent with 3 modulo 5 but in practice it is congruent with 0

[fathom sierra]

what

[sacred junco]

But 3^2+3+3=15

[west glade]

it is

[fathom sierra]

ah wait

I should what myself now

[sacred junco]

?

What does it mean

[fathom sierra]

I said something stupid

[sacred junco]

Ha okay, but thanks for your help

[fathom sierra]

I thought the equation was x^2+x-3 for a second there

[sacred junco]

Okay no problem

If we do 2 graphics, one with x^2 + x + 3 and the other with 5x we can also see that they find themselves for x=1 and x=3

[sacred junco]

Can you explain this ?

[west glade]

that 3^2+3+3 = 0 mod 5?

[fathom sierra]

he was replying to me, cause I screwed up

your results are correct indeed

[sacred junco]

Yeah

[sacred junco]

Yes but the congruence table doesn't show this

[fathom sierra]

how

you get 0 for x=1 and x=3

[sacred junco]

Here, my answer at the bottom isn't correct

NOOOO I UNDERSTAND

X^2 is congruent with -1 for x is congruent with 2 so -1^2+2 +3 i am dumb af

So to conclude i just have to say that the solutions are 1 and 3 ?

[fathom sierra]

yes

[sacred junco]

Okay thanks

Thank you, platypus and denascite you are cool

[wheat tinsel]

what is an example of a function f that is not multiplicative but f*f is completely multiplicative, where the asterisk denotes the Dirichlet product

nvm I think I have an example

but its recursive in nature

set f(p)=1 for all primes, f(1)=1. Then you can just find everything recursively

[open mist]

better than SE
Asker documents answer rather than saying "nvm I solved it"

now we just need a search system /s

[white lion]

true

i got banned on SE

lol

[open mist]

shush, that might be against the terms that shall not be named
(they can, but it's not fun)

[open mist]

and what evil did you commit to earn such harsh punishment ?

[white lion]

I know but Im a changed man

[normal heart]

[white lion]

they dont tell you, you are banned by a computer but I think its because I asked a question and didn't engange with it until after a month

tbh that was annoying of me

[wheat tinsel]

actually, the sequence you get f(p), f(p^2), f(p^3) is almost the same as the sequence of coefficients in 1/sqrt(1-x). Maybe you can actually obtain the generating function as a function involving square roots, given that the recursion for f(p^k) is not too complicated, but I won't bother

by almost the same I mean the numerators are the same and the denominators are the same but divided by some power of 2

[wheat tinsel]

I think this doesn't work

because f is multiplicative, although not completely multiplicative

but I think you can set f(1)=-1, f(p)=1 for p prime, and do the same

[prisma folio]

Can we make this follow from Euclid's lemma or Bezout's lemma?

Or is just a direct proof faster

[cold tendon]

Like how?

If you have idea share

[prisma folio]

Bezout's lemma says that gcd(a, b) = sa + tb

We are now looking for the prime factorization of sa + tb

Thus of s * p_1^a_1 * p_2^a_2 * ... * p_n^a_n + t * p_1^b_1 * p_2^b_2 * ... * p_n^b_n

[prisma folio]

Something like this

Now after the exponent laws

We can factor out p_1^min(a_1, b_1) etc.

[cold tendon]

Ok you show that gcd is divisible by p_1^min(a_1,b_1) etc. how to prove that is equal

[prisma folio]

equal to what?

[cold tendon]

Gcd equal to p_1^min(a_1,b_1) etc.

[prisma folio]

Yeah, the problem would be showing that there is no "remainder"

After we factor everything out, there will still be something in brackets

[cold tendon]

Yea that is equal 1

[prisma folio]

Yeah, we need to show that

\begin{align*} \gcd(a, b) = sa + tb &= s p_1^{a_1} \cdots p_n^{a_n} + t p_1^{b_1} \cdots p_n^{b_n} \ &= p_1^{\min(a_1, b_1)} \cdots p_n^{\min(a_n, b_n)} \bigl(s p_1^{a_1 - \min(a_1, b_1)} \cdots p_n^{a_n - \min(a_n, b_n)} + t p_1^{b_1 - \min(a_1, b_1)} \cdots p_n^{b_n - \min(a_n, b_n)} \bigr) \end{align*}

We need to show that [s p_1^{a_1 - \min(a_1, b_1)} \cdots p_n^{a_n - \min(a_n, b_n)} + t p_1^{b_1 - \min(a_1, b_1)} \cdots p_n^{b_n - \min(a_n, b_n)} = 1.]

[cold tendon]

But its realy hard you had no information about s and t

Although you can get s and t by euclid algoritsm its will be complicated

I think

[cold tendon]

How do you think?

[prisma folio]

Hm, a lot of the terms will be 1, some will be p_k^{a_k - b_k} or p_k^{b_k - a_k} but we still have s and t in there too, yeah

[cold tendon]

I think that is dead end

[prisma folio]

We probably could continue and find a way to show it is equal to 1, but it's probably faster to take the other way

[cold tendon]

Maybe you could continue but is maybe

[prisma folio]

Well, I'm sure there is a way to show it is equal to 1, there can't just be a "dead end" in maths.
It might just take much longer than the other way, in which case it's better to go with that one

So let's go with the other one, yeah

[cold tendon]

You cant be sure but it is another area of math mathematical logic or something like it

[cold tendon]

You have other ideas?

[prisma folio]

Ah, you mean Gödel's incompleteness theorems

[cold tendon]

Maybe i am not sure ok lets do the problem

[prisma folio]

Well, we need gcd(a, b) | a = p_1^a_1 * ... * p_n^a_n and gcd(a, b) | b = p_1^b_1 * ... * p_n^b_n so it's kind of intuitive that we need to take the min of the exponents

[cold tendon]

Yea

Ok let do it together

What is gcd?

Ok you know it

Greatest common diviser

[prisma folio]

gcd(a, b) := max{a in N | a divides m and a divides n}

[prisma folio]

Yes

[cold tendon]

Then first of all prove something a diviser

[prisma folio]

a | b if b = k * a for k in Z

[cold tendon]

Another thing how their prime factorization relates to each other. a and b

[prisma folio]

Wait

Bezout's lemma states the following: Let $m,n \in \mathbb Z$ with $m = 0$ or $n = 0$ be given. Then there exists $a, b \in \mathbb Z$ with gcd$(m, n) = am + bn$. It also follows that if $d$ is a common divisor of $m$ and $n$, then $d |$ gcd$(m, n)$.

See the last sentence

Couldn't that basically prove the entire thing?

[cold tendon]

How?

[prisma folio]

We know that p_1^min(a_1, b_1) is a common diisor of m and n

So it needs to divide gcd

Do that with all of them

[cold tendon]

Ok

[prisma folio]

So p_1^min(a_1, b_1) * p_2^min(a_2, b_2) * ... is a divisor of gcd(a, b)

[cold tendon]

We already say it

[prisma folio]

Well we need to justify that it's not larger

[cold tendon]

That is a problem

[cold tendon]

Ok let me say how to prove

[cold tendon]

You can prove C | A if and only if
[A]p>=[C]p for all p prime numbers

[prisma folio]

what does [A] denote

[cold tendon]

Like highest degree of p that divides A

Like p^a... in factorization it is a

Ok?

[prisma folio]

Alright

[cold tendon]

Then if C is common diviser of B and A then [A]p>=[C]p and [B]p>=[C]p for all p ok?

[prisma folio]

Yeah

[cold tendon]

If C is the greatist then its [C]p should be the greatest possible number

Then it should be min of [A]p and [B]p for all p

Ok?

[prisma folio]

Yep

Thus, you are done

[cold tendon]

Yeah

[cold tendon]

Yes my its more general approach

[prisma folio]

Yeah, you started with just A, B and C, not with a prime factorization

But the idea should be the same, then

[prisma folio]

Thank you. I will keep the question up to see if we can follow this out of some known lemma, since that would be even quicker.

[cold tendon]

Its the same

[prisma folio]

Can this follow out of some known lemma or theorem right away?

[cold tendon]

I dont think because we use simply and basics propositions

[prisma folio]

@tropic flame can I grab you for a sec

[tropic flame]

no

but also like, you can prove this pretty directly

prove this for a=p^A and b=p^B first and then notice how gcd behaves for coprime factors

[prisma folio]

What do you mean with how it behaves for coprime factors?
gcd(a, b) will be p^min(A, B)

gcd(q, p) where q and p are coprime will be 1

[tropic flame]

right, and more generally for a and b coprime, gcd(ab,c)=gcd(a,c)gcd(b,c)

one way to think about this is in terms of multisets, if M_a is the multiset of prime factors of an integer a (for example M_12={2,2,3}) then multiplication corresponds to union of multisets, and gcd corresponds to intersection of multisets, 1 corresponds to the empty multiset

so if a and b are coprime, M_a intersect M_b is empty

[prisma folio]

Yeah, it makes perfect sense intuitively, it's just that writing the proof as "first we look at the first factor in common, p_1. To get the most out of it, we take p_1^min(a_1, b_1). We do this with all other factors and we get the desired formula" sounds a little weird

[tropic flame]

under this assumption you can show that (M_a union M_b) intersect M_c is the same as (M_a intersect M_c) union (M_a intersect M_b)

which is just like, standard set theory stuff

if you're interpreting gcd in terms of multisets like this you can write the proof pretty directly: take M_a={p_1,...,p_1 (a_1 times), ... , p_n,...,p_n (a_n times)} and similarly for M_b, and then compute their multiset intersection

the min(a_i,b_i)'s will come out of that multiset intersection

[prisma folio]

Oh, that's nice. If we stay with the more algebraic version as stated, then can we still justify it better than that "get the most out of it"?

[tropic flame]

I would just say that the greatest common divisor of p^{a_i}_i and p^{b_i}_i is p^{min(a_i,b_i)}_i (essentially by definition)

[prisma folio]

So your argument would involve that gcd(a_1a_2..., b_1b_2...) = gcd(a_1, b_1) * gcd(a_2, b_2) * ...

[tropic flame]

if you want to justify this further, the only divisors of p^n are p^m for m\leq n, and so the greatest p^m dividing both p^a and p^b is p^{min(a,b)}

right yeah

[prisma folio]

Though, then how would you justify gcd(a_1a_2..., b_1b_2...) = gcd(a_1, b_1) * gcd(a_2, b_2) * ...

[tropic flame]

if you're thinking about this in terms of multisets, this is the distribution of intersections over unions

If you partition the multiset M_a into disjoint multisets M_a,i corresponding to the distinct prime divisors, and similarly for M_b you would have like

$\bigcup_{i,j}(M_{a,i}\cap M_{b,j})=\Big(\bigcup_i M_{a,i}\Big)\cap\Big(\bigcup_j M_{b,j}\Big)$

[sterile pumice]

nGroupoid

[tropic flame]

the right hand side is the gcd you want, the left hand side is the product you want

but you have $M_{a,i}\cap M_{b,j}=\emptyset$ for $i\neq j$ corresponding to distinct prime factors $p_i\neq p_j$

[sterile pumice]

nGroupoid

[tropic flame]

so a bunch of the terms in this product will just be 1

so you just end up with like

$\bigcup_i(M_{a,i}\cap M_{b,i})$

[sterile pumice]

nGroupoid

[tropic flame]

which is the product of p^min's you want

[prisma folio]

Hm, can we also justify it algebraically?

[tropic flame]

yeah definitely, it's just a little cleaner to phrase this in terms of multisets I think

otherwise you just have to say a lot more words

but you can unwrap everything into something that doesn't involve multisets if you want

[prisma folio]

Wouldn't it cause problems because multiplication is associative and with
gcd(a_1a_2..., b_1b_2...) = gcd(a_1, b_1) * gcd(a_2, b_2) * ... we are creating an order?

[tropic flame]

it shouldn't cause an issue, remember the right hand side is secretly the product \prod_{i,j} gcd(a_i,b_j) and a bunch of these gcd(a_i,b_j)'s are 1

the result you get won't depend on the order

(you need some coprimality assumptions but that's the idea)

[prisma folio]

Hm, how would we translate this into algebra

[tropic flame]

p^{a_i}_i and p^{b_j}_j are coprime if p_i and p_j are distinct primes

anyways I'm gonna head out, good luck

[prisma folio]

Thank you

[noble obsidian]

if our number is divisible by a cube which is greater than 1 what can we say about our number?

mod 4

is this common knowledge?

[normal heart]

could be anything, 8 mod 4 is 0, 27 mod 4 is 3, 54 mod 4 is 2, 81 mod 4 is 1

[noble obsidian]

if m | n does m | p^v_p(n) for at least one prime p?

given that m > 1

oh no

[still flare]

No

[noble obsidian]

WTF

take m = n

I see

[minor crown]

what sort of optimisations are typically used for pollard rho / miller rabin when implementing them

like in code for example
i know one where using a 3rd pointer for pollard rho makes it about 15% faster compared to just 2 pointers, but what are some other things to consider?

[worn lava]

is there an operator that describes the residue class of a number as close to zero as possible, instead of as a strictly positive number? i.e. 17 mod 6 =5, but I want specifically the -1 representation

[wooden glen]

You'll probably need to define a notation for that yourself.

[prisma folio]

What I asked in #help-19 would probably also fit here

[worn lava]

Cool, henceforth I shall define "a mid b" to be the residue closest to identity of a number, biased positive (2 mid 4 = 2)

[normal heart]

that's mid

[wooden glen]

That sounds like it would be in danger of confusion with the "divides" relation, written \mid in TeX...

[worn lava]

Meh.

[prisma folio]

What I asked in #help-3 probably also fits here

[sonic wharf]

This is a proof that sqrtn is irrational if n=/=+-1 and n is a square free integer. I don't understand the last sentence, what do they mean by "looking at the prime factorization of p on both sides"?

[torn escarp]

nt^2=s^2
p divides the left side an odd amount of times and p divides tieh right side an even amount of times

[pastel magnet]

Can I please get some help with this item (b)? We assume we're working unital rings.I'm struggling to prove this because f isn't 1-1, and then I'm stuck

[white lion]

lets work through this

recall the definition of surjectivity

[pastel magnet]

Sorry I’m on train now, don’t have pen and paper but I remember I just wrote something like f(a)f(b)=1=f(1) but because it’s not 1-1 I cannot conclude ab = 1, and that was the problem for me.

[west glade]

if you cant make a proof work, maybe you can construct a counterexample. if that one doesnt work either then find out why it doesnt and use that to attempt a proof again. and so on

[torn escarp]

maybe try using Z or some other ring you're familiar with to help see happens

[jade nexus]

Ye, that's the usual definition. Might be more appropriate in #proofs-and-logic

[umbral ginkgo]

Alr, sorry 🙂

[sacred junco]

prove that for every integer n there exist a integer m such that 2^m - m is divisible by n

can anyone solve this please

[loud maple]

Consider the homomorphism f from ℤ to ℤ/(n), that sends x to x mod n. The homomorphism is clearly surjective. ℤ has only two units, while ℤ/(n) has ϕ(n) units. If ϕ(n)>2, then it is clear that not every unit in ℤ/(n) is of the form f(u) for some unit in ℤ.

[pastel magnet]

Oh yes that makes sense, thank you! I’m still getting familiar with the basic concepts and just assumed it looks correct….

[iron surge]

based on ur notation u mean $2^m-m$, right?

[sterile pumice]

logician

[iron surge]

actually yea it can't be 2^(m-m) cuz that's just 1

but before anyone helps you, you got to show us at least what you have so far. Show us that you've actually attempted the problem at the very least...

I'm not convinced this is even true for n=0. Because then we would require that 2^m=m. Clearly, no negative integer m satisfies this. m=0 doesn't satisfy this either since 1 doesn't equal 0. So m would have to be positive, but then I'm pretty sure 2^m>m for all integers m>0.

[torn escarp]

think we can safely assume n is a positive integer

[fleet bone]

prolly meant n in N not Z

[sacred junco]

no (2^m) -m

[iron surge]

So what I said^

[keen pagoda]

I was testing out prime number modulos

multiplying stuff

like, numbers modp

and didn't test a lot but seen a pattern
the numbers squared modp seem to have a symmetry

mod 3:
1² = 1 mod3
2² = 1 mod3

mod 5:
1² = 1 mod5
2² = 4 mod5
3² = 4 mod5
4² = 1 mod5

mod 7:
yk how it works:
1
4
2
2
4
1

is this reflexive symmetry just a coincidence or is it general?

if it is general don't tell me the proof btw

[still flare]

4 = -1 mod 5 ;)

[keen pagoda]

👍

[loud moon]

at least we can easily see that it's true for (odd) prime n, by setting m = (n - 1)^2 for example. not sure yet how to generalize

[sacred junco]

so i solved it using euclid division lemma but my answer is not so much satisifactory i assume m is of form 4k +1 and 4k +3 so 2 ^ m on division by 6 gives 2 as remainder and 4k+1 and 4k+3 can be written as 6k+1, 6k+3 and 6k+5 and for m = 6k+3/5 we proved it for all prime > 3 and using 6k+1 we proved is for all odd multiples of 3 and now for m of form 4k and 4k+2 on division of 2^m by 6 gives remainder 4 so 4k and 4k +2 can be written as 6 k ,6k+2 , 6k+4 by 6k+4 it is proved for all even divisor of 3 and 6k+2 and 6k on adding two gives 6k+2 and 6k+2 is always a multiple of prime so its proved for them and we proved our answer for even divisors of 3, odd divisors of 3 and the multiples of prime so all the numbers are also either even divisors , odd divisors or multiple of prime hence proved but i think there is some catch here\

[sacred junco]

you can do that by fermats little theorem

[torn escarp]

it isn't a coincidence you're right, keep at it I won't spoil it for ya

oh I missed jan's comment there

[torn escarp]

are you familiar with the chinese remainder theorem?

then you can think about solving the problem 2^m - m = 0 mod p^k for any prime p

[torn escarp]

oh I think I found a cute way to do it by (strong) induction. Suppose we can solve it for all $n' < n$ then substitute $m=2^k$ and we get: $$2^{2^k}-2^k=2^k(2^{2^k-k}-1) \mod n$$ We can always pick $k \ge v_2(n)$ because it's periodic and we have that $2^k-k=0 \mod \varphi(n)$ because $\varphi(n) < n$.

[sterile pumice]

Merosity

[sacred junco]

ya i know that

[keen pagoda]

THANK YOU I did it I proved it me happy

[wooden glen]

That's neat indeed!

[sacred junco]

for any integer k, prove there exists some pair of primes p, q such that p - q = 2k

i'm pretty sure this is true

but not sure how to go about a proof

works for k = 1 to 60

bwoc consider the minimal k for which this wouldn't be true?

[sacred junco]

feels like this can be strengthened somehow

would this still be true if we forced p, q to be consecutive primes?

oh nevermind the term is prime gaps

https://math.stackexchange.com/questions/1634110/are-there-prime-gaps-of-every-size

it's an open question looks like :/

[wooden glen]

Or at least was within the last dozen years ...

[unique cypress]

That sounds like a Polignac conjecture-type question

#advanced-number-theory

[sacred junco]

yeah nvm this question is likely very very hard

[wooden glen]

There doesn't seem to be an obvious reason for it to be easier than Goldbach ...

[sacred junco]

need to prove that if (n choose k) is prime, then either k = 1 or k = n-1

[torn escarp]

Thanks!

[fallen temple]

Hi, so im doing some work on pythagorean triples and ive written some mathematica code to generate all the primitive triples below a certain hypotenuse. I also was having a look and discovered that squaring Gaussian Integers admits the same parameterisation for generating triples, so I decided to plot my triples below a certain hypotenuse and where all the lattice points go to overlay them nicely, however, some of my triples that I generated below a certain hypotenuse do not lie on the lattice points, can anyone explain why? Its confusing me. Here is a picture attached, where the green dots are the primitive triples I generated below a hypotenuse of 1000 (not all will be in the plot because its too small).

bound = 1000;
primitiveTriples = {};

For[m = 2, m^2 < bound, m++,
For[n = 1, n < m, n++,
If[CoprimeQ[m, n] && OddQ[m - n], a = m^2 - n^2;
b = 2 m n;
c = m^2 + n^2;
If[c < bound,
primitiveTriples = Append[primitiveTriples, {a, b, c}];];];];]

primitiveTriples = DeleteDuplicates[Sort /@ primitiveTriples];

primitiveTriples This is my mathematica code for generating the primitive triples.

[prisma folio]

Let $a, b \in \mathbb N$. Show that there exists $a_1, b_1 \in \mathbb N$ s.t. $a_1 \mid a$, $\quad b_1 \mid b$, $\quad \gcd(a_1, b_1) = 1$ and $\text{lcm}(a, b) = a_1b_1$. \[15pt] I first thought about $a_1 = \frac{a}{\gcd(a, b)}$ and $b_1 = b$, but that doesn't necessarily fulfill the $\gcd(a, b) = 1$ requirement. \ So what else would you pick, or how would you show this?

[silver oak]

i must misunderstand something but i can;t tell which part

well you can;t show that gcd(a,b) is 1, so you meant gcd(a1, b1) = 1?

[prisma folio]

Yes, I did

Let $a, b \in \mathbb N$. Show that there exists $a_1, b_1 \in \mathbb N$ s.t. $a_1 \mid a$, $\quad b_1 \mid b$, $\quad \gcd(a_1, b_1) = 1$ and $\text{lcm}(a, b) = a_1b_1$. \[15pt] I first thought about $a_1 = \frac{a}{\gcd(a, b)}$ and $b_1 = b$, but that doesn't necessarily fulfill the $\gcd(a_1, b_1) = 1$ requirement. \ So what else would you pick, or how would you show this?

[prisma folio]

I can give you a counterexample to the gcd(a_1, b_1) = 1 if we keep it like this in a sec

[silver oak]

just take 20 and 50

if you find how to separate the lcm, it will generalize

[prisma folio]

Yeah, in this case, we'd have a_1 = 20/10 = 2 and b_1 = 50

gcd(a_1, b_1) = 1 doesn't hold

I thought I proved it, but there must've been a mistake

[silver oak]

i mean it's obvious how to do it

[prisma folio]

I argued by contradiction, that if a_1 and b_1 had a gcd > 1, then that factor would also be in gcd(a, b)

But that's just wrong

[prisma folio]

Would you always do these by examples first and then generalize them?

[silver oak]

i don't know much number theory

[prisma folio]

I mean proofs in general

[silver oak]

yeah i guess

[prisma folio]

Thanks

[prisma folio]

Alright, take a = 20 and b = 50

Then, we need to find a_1 | 20 and b_1 | 50 with gcd(a_1, b_1) = 1 and lcm(20, 50) = a_1b_1

[silver oak]

yeah

[prisma folio]

Let's start with gcd(a_1, b_1) = 1, I guess

a = 2 and b = 5

lcm(20, 50) = 100

Doesn't fit

100 = 4 * 25

That should be fine

Take a_1 = 4 and b_1 = 25

[prisma folio]

Yep, it's that

So now let's try to generalize

Well, I started with lcm(20, 50) = a_1b_1 and found a_1b_1 with gcd(a_1, b_1) = 1

gcd(a_1, b_1) = 1 means n * a_1 + m * b_1 = 1 (Bezout's identity)

Hm

[silver oak]

idk what that is

[prisma folio]

There is a result that says gcd(a, b) = k (a, b, k in Z) means that there exists n and m in Z so that
n * a + m * b = k.

[prisma folio]

Or do you have another idea on how to generalize?

We need to somehow show that we can rewrite lcm(a, b) = a_1b_1 into d_1 * d_2 with gcd(d_1, d_2) = 1

[silver oak]

lcm of 2 numbers is p_1^a × p_2^b × p_3^c ...
where each term only divides one of the numbers

[prisma folio]

prime factorization?

[silver oak]

yes

[prisma folio]

p_i^max(a_i, b_i)

[silver oak]

or i guess at least one

you put the ones that divide b into b1

[prisma folio]

Wait

Both, no?

[silver oak]

the rest divide a

[prisma folio]

Ah, yes, one, nvm

Atleast one, yeah

[silver oak]

i just didn;t know how to hint it so i lamely suggested you try 20 and 50

[prisma folio]

[a = p_1^{a_1} \cdots p_n^{a_n}] [b = p_1^{b_1} \cdots p_n^{b_n}] Now [\text{lcm}(a, b) = p_1^{\max(a_1, b_1)} \cdots p_n^{\max(a_n, b_n)}.]

Now, take all terms with exponents max(a_i, b_i) = a_i and put them into a_1, right?

[silver oak]

yes

maybe nothing is left, then b1 = 1

[prisma folio]

Similarly for b

Then we'll have [a_1 = p_{k_1}^{a_{k_1}} \cdots p_{l_1}^{a_{k_n}}] [b_1 = p_{k_2}^{b_{k_1}} \cdots p_{l_2}^{b_{k_n}}] where $a_{k_n}$ are the exponents with where $a_{k_i}$ was larger and $b_{k_n}$ where $b_{k_i}$ was larger. \ Thus, by definition of $a_1$ and $a_2$, they have no $p_i$ in common and thus $\gcd(a_1, b_1) = 1$.

[silver oak]

and if b_k was the same you must choose one or the other

[prisma folio]

Yeah, max = min in that case

Hopefully the way we defined max/min already deals with that

[prisma folio]

Hm, the justification for the last line

Oh

They have no prime factors in common

The p_1 in both was bad notation

Perhaps still bad notation with the common k_1

[silver oak]

this still sounds like you're losing primes that were equal

[prisma folio]

You mean where the exponent is max = min?

[silver oak]

yes, the lcm part will not hold

[prisma folio]

Well, say we just put all of the cases where max = min into a_1

[silver oak]

that will work

[prisma folio]

Then we shouldn't have to worry about that anymore, right?

Yeah

Ok, then we need to justify a_1 | 20. hm

I feel like we need an argument using lcm(a, b) = a_1b_1

a_1 | 20 means that there exists n in N with n * a_1 = 20

Thus $n \cdot \frac{\text{lcm}(a, b)}{b_1} = 20$.

Perhaps we could easier show that there exists an n with that?

lcm(a, b) * gcd(a, b) = a * b, we could turn that into a gcd but that wouldn't be very useful, no?

[silver oak]

b equals (every max) × (every min)

that was the idea