elementary-number-theory

[prisma folio]

Does it?

[silver oak]

if there's no max = min

[prisma folio]

why?

[silver oak]

wait what

like, not every, but it's some subset of max times some subset of min

the same subset of max that is b1

[prisma folio]

Yeah, true

[prisma folio]

Wait

Yeah, true

[prisma folio]

Are you thinking of using this fact for the n * lcm/b_1 = 20 term or the n * a_1 = 20 one?

[silver oak]

i gave up

by contruction, b1 is a susbet of b, we just picked some terms

[prisma folio]

Yeah

[silver oak]

each term is equal to a term in b

[prisma folio]

Yeah

And lcm(a, b) will be divisible by b_1 because b_1 is a divisor of b and b is of course a divisor of lcm(a, b)

So it will be some natural number

we just need to show it divides 20

Rather, we should do it the other way, I guess

n = 20 * b_1/lcm(a, b)

nvm

[prisma folio]

Wait what, I got 20 into the equation from the example for some reason

20 shouldn't be there

This basically proves it

Thank you!

[sterile pumice]

Its Me Mario

[white lion]

Well there’s quite a few paths you could take

You can make more equations by finding the prime factorization of m and n

You’ll have 2 types of conditional congruences, equations that are modulo a prime or equations that are modulo a power of a prime. We can use hensels lemma to find the solutions to polynomials modulo power of prime but I’m not aware of any trick to solve for modulo a prime, if you’re lucky the prime number is small and you can plug in all the values to see if it holds

Of course there could be other complications, what if we can’t factor m or n? What if there happens to be more than 1 solution to a congruence, then we would have multiple different systems we would have to solve for

[white lion]

So n is a polynomial not an integer?

[ripe galleon]

i think ive gotten somewhere but idk what to do from here

[foggy linden]

That conclusion in the last line doesn't exactly follow. At least from whatever you have done.
You can, at best, say that $$2^{n+1} \equiv (p-1) \equiv 0( \text{mod } d)$$.

[sterile pumice]

Enemagneto

[formal tiger]

In my number theory notes, sometimes I saw $a^n \equiv 1$, where $n$ is the order of $a$ (assume $2|n$), then $a^{\frac{n}{2}} \equiv -1$ but I found that sometimes it may not be true. In what scenario this would hold?

[sterile pumice]

hoifanrd

[torn escarp]

modulo a prime it's always true, so needs to be some composite number at a minimum. For instance, mod 8 you have 3^2=5^2=7^2=1 but of course only 7=-1 mod 8 so 3 and 5 are some examples

[formal tiger]

I can't find any proof for it online🥲
Do you mind having a proof of it?🤔

[torn escarp]

proof of what

[formal tiger]

Under modulo p prime, that property holds

[torn escarp]

It sorta depends on what angle you want to prove it from, but let's call b=a^{n/2} then we know b^2=1 and mod p we have a field so (b+1)(b-1)=0 forces b=1 or b=-1

we know b=1 can't happen since the order of a is n not n/2, so it must be b=-1

[formal tiger]

Hum we didn't talk about field in number theory 🤔

[torn escarp]

yeah I thought you might say something like that, we can prove it from that angle, because in a sense we'd basically be proving it's a field and I'm taking the lazy way out and I'm tired lol

[formal tiger]

It's ok haha

[torn escarp]

I think Silverman covers this in his Friendly Introduction to Number Theory book in one of the quadratic reciprocity chapters

or something similar enough

[formal tiger]

Ok thanks!

[torn escarp]

yeah 😎

[formal tiger]

I am asking this question actually because I am having another unsolved problem

[torn escarp]

sure sounds fun

[formal tiger]

I am having a question asking me to prove that the congruence $5^x \equiv -1 ( \text{mod } m)$, where $m = 2^\alpha, \alpha \geq 3$ is not solvable.

[sterile pumice]

hoifanrd

[formal tiger]

I have already proved that the $O_m(5) = 2^{\alpha - 2}$ in the previous sub question.

[sterile pumice]

hoifanrd

[formal tiger]

My current idea is that

If it's solvable, then $x = 2^{\alpha - 3}$, which should lead to some contradiction

[sterile pumice]

hoifanrd

[torn escarp]

oh I have a different approach entirely

I suppose your way might be possible too though, it seems harder to me though

[formal tiger]

What would be your approach? 🤔

[torn escarp]

I'm thinking if you had any solution for alpha > 3, it would still have to reduce down to a solution mod 8

[formal tiger]

Ohhhh

[torn escarp]

from there I would do a binomial expansion of (1+4)^x and notice what happens to the higher terms, it simplifies

or I guess you can brute force through it too

[formal tiger]

Wait then actually I think it's solved?

I dont think expansion is required?

[torn escarp]

well you have to actually check it one way or another but yeah

[formal tiger]

I can just say if there exist a solution, then 5^x = -1 (mod 8)

then check that there is no such x (just 1 to 8)

[torn escarp]

actually we can reduce down to mod 4 can't we, why not

1^x = -1 mod 4 is no go

[formal tiger]

Yes

wow

That's so beautiful

[torn escarp]

funny we proved something stronger than we were asked to lol

alpha >= 2 yeah, very nice

[formal tiger]

Because it's having other subquestions haha

But others are fine :P

Thanks a lot

[torn escarp]

yup you're welcome

[formal tiger]

I hope I will be fine in tomorrow's number theory makeup midterm

[torn escarp]

good luck!

[ripe galleon]

yeah i ended up figuring it out, i wasn’t sure how to make the last implication but i first had to show that d=2^(n+1 ) and then everything worked pretty smoothly

[prisma folio]

What I asked in #proofs-and-logic would probably also fit here

[nova maple]

Show that the equation $ 5x^3 + 11y^3 + 13z^3 = 0$ has no integer solutions.ive assumed that $gcd(x,y,z)=1$. Also, modulo 3 you can get that $x^3 + y^3 \equiv z^3$ but that isn't really that helpful any ideas?

[sterile pumice]

bathroom mug

[nova maple]

I just did one where you had to show that 15x^2-7y^2=9 has no integral solutions and I just kept looking modulo different integers and got a proof.
So, y = 0 (mod 3), then you get x = 0 (mod 3) then you have 15a^2-7b^2=1 which means 7b^2 = 2 (mod 3) which can't happen so there are no solutions.

This was possible because I had 2 variables, so if 2 terms are 0 mod something then the other term is forced to be 0 mod that thing. Not sure what I can do for 3 variables other than compute the possibilities for y and z modulo some integer given some x value

[torn escarp]

you can turn it into 2 variables reducing mod 5, 11, or 13

that means neither of the two variables left can be divisible by your prime, otherwise the other is which violates the gcd condition

I might have a stronger gcd condition in mind based on thinking about descent, since it looks like we can actually force x,y,z to all be pairwise relatively prime

unless I've made a mistake, this is how I solved it

[inner mist]

yo

we are doing elliptic curve cyrptography

which is basically just finding points of elliptic curves over a finite field

is there a way to know if an element is a quadratic residue?

ie for example y^2 = 7 mod 29

is there a way i for sure know this exists?

i know this is related to quadratic residue stuff ( which i did not study much ) so thats why im asking heree

[prisma folio]

What I asked in #proofs-and-logic would probably also fit here

[torn escarp]

yeah the shortcut is knowing quadratic reciprocity

in short (7|29) = (29|7) = 1 means 7 is a quadratic residue, there are a few rules you have to learn to do that cause it isn't just always "flip em"

I'm only showing how quick it is for me to see that, not explaining any steps so that you have an idea what it looks like so you might be motivated to read about it more

but after you read some stuff about legendre symbols, their properties to simplify like quadratic reciprocity and the special rules for 2 and -1 you can ask about whatever is tripping you up still

[inner mist]

yea i figured i could ask here

isntead of trying to build the whole theory on my own lfmao

but yeah any quick notes for that or resourceds?

or just google legendre symbols?

[torn escarp]

brilliant.org probably, idk just don't have time to explain everything but I can help with details

[inner mist]

@torn escarp

if y^2 = a mod p

now

can i say that

if the equivalence class of a does not contain (p-1)^2 or any b^2 , where b is in Z/pZ would that imply that this has no solutions?

what i mean is

in mod 7 for example

i know the biggest square would be 36

so a + p, a+2p ,...

if that exceeds 36 without being a square

would that imply its never one?

[torn escarp]

I don't really think of "biggest" when talking about equivalence classes since 36 is in the same equivalence class as 1, they're all the same to me

typically you just fix some set of representatives like {0,1,..., p-1} and interchange freely

to me that basically answers your question, doesn't matter how big it is as an integer

you can brute force see all the squares in Z/pZ by looking at 1^2, 2^2, ..., ((p-1)/2)^2

because x^2 = (-x)^2 = (p-x)^2 you can stop halfway

not sure I answered your question or not but maybe that helps you to reask your question @inner mist

[inner mist]

aha

yeah

i should have thought about that

like basically its just this crypto class

no proofs or anything

and i just want like a way to verify if i should stop looking in the equivalence class

or just keep adding

like y^2 = 2 mod 7 is y^2 = 9 sorta thing

but then y^2 = 3 mod 7 has no solutions

[torn escarp]

not sure what you're doing here

[inner mist]

how would you solve y^2 = 2 mod 7

[torn escarp]

probably brute force check 1^2, 2^2, 3^2

although I know 1^2 wouldn't work for obvious reasons and 2^2 wouldn't work cause it's a field, so it has to be 3, but that's over thinking it

[inner mist]

yea

got it

ty

sm

what i was thinking was

abit stupid

just look at [2]

and if theres a square there then its the root of that square

and im done

as in 2+7 , 2+2*7 , 2+..

[torn escarp]

yeah I was thinking you might, seems annoying to go that route

[inner mist]

yea definitely

thank you

[torn escarp]

if the numbers get larger I might try other tricks, like probably worth knowing that QR x QR = QR, NR x QR = NR and NR x NR = QR

QR meaning quadratic residue, NR being non quadratic residue

really this is just the homomorphism f(x)=x^{(p-1)/2} that maps f: Z/pZ* => {-1,1}

this is the euler form of the legendre symbol, or whatever they call it, its' the same thing

[tough condor]

what is [2; 3, 5, 7, 11...]

[torn escarp]

2.3130367364335829

[tough condor]

Nothing special about that number?

[torn escarp]

should there be

[tough condor]

Idk, there could be

[torn escarp]

is there anything special about the power series 2+3x+5x^2+7x^3+11x^4+...

[torn escarp]

lmk when you find something

[tough condor]

I'll see you in a few years then

[torn escarp]

sounds good

[tough condor]

I was just curious if there were any known properties of it, or anything at all

A search didn't give anything

[torn escarp]

you need a hook of some kind

learn more about continued fractions and learn more about primes, right now the only relation between the two is a continued fraction holds an infinite sequence in it and the primes form an infinite sequence, past that I don't see much to do

[formal tiger]

I finished my midterm🥲

I got two questions unsolved lul
And I would like to discuss them here

[torn escarp]

that's what the channel is for lol

[formal tiger]

If $p = a^2 + b^2$, where $p$ is an odd prime, I have already proved that \
a) $(a, b) = 1$ \
b) $p \equiv 1 ( \text{mod } 4)$ \

And the remaining one is prove that at least one of the $a$ or $b$ is QR in mod p

[sterile pumice]

hoifanrd

[torn escarp]

I'm thinking we can use the fact that since p=1 mod 4 there's an element we can call i such that i^2=-1 mod p

[formal tiger]

Yes and that element is ab^-1

[torn escarp]

I only see how to get partial result so far

[formal tiger]

Wait maybe I can use Jacobi Symbol 🤔

[torn escarp]

if i is a NR then a=bi gets us one or the other is a QR, and when i is a QR then either both are QRs or neither is

[formal tiger]

Hum no it doesnt seems to work lul

[torn escarp]

what'd you try

[formal tiger]

Assume (a/p) = -1

Trying to derive that (b/p) = 1

[torn escarp]

ah, that's what I'm doing here

[formal tiger]

Yup same idea

[torn escarp]

basically we're at (i/p)=1 we need to show (a/p)=-1 can't happen

[formal tiger]

Yup

[torn escarp]

I guess that means we actually have to have x^4+y^4=p

well, I guess not

something can be a QR mod p and not be a perfect square

but we do have x^4+y^4=0 mod p

idk just trying to understand this situation better

p=1 mod 8

that much we do know

that might tie back into QR

if we can get (2/p) to pop up

[fleet bone]

well one is even wlog that be b. so p-4b^2=a^2 , as we know there exists integer x such that x^2=-1(mod p) it sufficies to show there exists integer y such that y^4=p-4b^2(mod p)<=> y^4=-4b^2(mod p)<=> (y^2/b)^2=-4(mod p). as b due to contradition is a NQR[if p=1(mod 8)].let i^2=-1(mod p) be one solution so y^2/b=2i or y^2/b=-2i. we now have to determine if 2i is QR . if p=1(mod 8) 2 is a QR so if we show i is QR. thats what i can think of

[torn escarp]

oh

the fact that one is even does give us a way for 2 to pop up, cool thanks

[fleet bone]

so we have to find (i/p) basically

so like

y^4=-1(mod p) show contradiction or something

ok ya

ord_p(y)=8 we can write it like that

as p=1(mod 8)

as fermarts lil theorom also we can use

we can guarentee i is qr this way

but y^2 is NQR contradiction

if p=5(mod 8) then what happens

2 is nqr

and (i/p)=-1(mod p) due to similar order argument i think

again contradiction

[formal tiger]

I am thinking if there any other way🤔
e.g. (a/p) = -1, then (b^2/a) = -1

So (b/a)^2 = -1 which is impossible...
I am feeling something's wrong tho

Yea because one of a or b may be even

So cannot directly apply with the law of quadratic reciprocity

[fleet bone]

maybe ur using the law of QR version of jacobi symbol

i think that most prolly works

(b^2|a)=(p|a)

[formal tiger]

b^2 does not divides a since (a, b) = 1?

[fleet bone]

ya

[formal tiger]

So we assume a is odd and (a/p) = -1, then (b^2/a) = -1 which is impossible.
How about the case that a is even and (a/p) = -1🤔

[tough condor]

Is there a name for $(-1)^{\Omega(n)}$?

[sterile pumice]

nHail

[formal tiger]

Oh wait so thats it

[torn escarp]

Liouville function

[tough condor]

Right that's it

[fleet bone]

ya that works

[formal tiger]

Since p is odd, at least one of a or b is odd, let a to be odd and a is NR, then -1 = (a/p) = (p/a) = (b^2/a) which is impossible. QED

[fleet bone]

thats a nice approach

[formal tiger]

Ok here's my last unsolved question :P

Calculate $$\sum_{k=1}^{111} \left(\frac{k}{2k+1}\right)$$

[sterile pumice]

hoifanrd

[formal tiger]

This thing is so cursed

[torn escarp]

idk is there some trick where we can approximate the sum 1/(2k+1) and have it be exact

I'm thinking $$111 = 2x + \sum_{k=1}^{111}\frac{1}{2k+1}$$ where x is your sum

[sterile pumice]

Merosity

[torn escarp]

I feel like this isn't much better

[fleet bone]

maybe we can take case x=1(mod 4),x=0(mod 4),x=3(mod 4),x=2(mod 4)

for odd cases prolly use jacobi reciprocity thing

for like x=2(mod 4) set x=2u where u is odd

[tough condor]

love that moment of rediscovering something very well known

which you already knew

but somehow not noticing it was the same thing

[formal tiger]

Thats not fraction

Thats the jacobi symbol in the question😂

[tough condor]

I will say it again, jacobi/legendre symbol should be $\left(\frac{a}{b}\right)_L$

[formal tiger]

Make sense

[sterile pumice]

nHail

[formal tiger]

Ok 🙏

[tough condor]

Someday I will make this notation widespread, mark my word

[formal tiger]

Task: Spread this notation to my instructor first

[dusty dragon]

I guess you could use [1 + \sum_{k = 1}^{111} \frac{1}{2k + 1} + \sum_{k = 1}^{111} \frac{1}{2k} = \sum_{k = 1}^{222} \frac{1}{k} = H_{222},] where $H_{222}$ is the 222nd Harmonic number

[dusty dragon]

The second sum simplifies to 1/2 * H_{111} so I suppose you could write it in terms of the Harmonic numbers

[formal tiger]

Again: the "fraction" in the question is the Jacobi symbol

[dusty dragon]

oh right

whoops

[torn escarp]

lmao

[fleet bone]

ok ya ig that works if

k=1(mod 4)
(k/(2k+1))=(-1)^((k-1)/2*k)=1

k=2(mod 4) set k=2u

The term simplifiles to

(2/(4u+1))=(-1)^(((4u+1)^2-1)/8)

k=3(mod 4)

then ig simplfiies to =-1

if k=0(mod 4) then also this can be simplified depending on v_2(k)s parity i think

actually case 4 and case 2 can be treated at same time i think

oh wait that simplfiies to some constant in case 4 pretty sure

as (8k+1)^2-1 is divisible by 16

so pretty much the only case of importance is case 2

which is dealt with by the parity of u

so again break the summation

these are kinda similar to oly probs

[nova maple]

This makes sense now that I think of it lol because in the last one 3 divided the other two terms so looking mod 3 was very nice. I think i could get something from here now

[torn escarp]

cool, lmk how you solve it curious to see

[nova maple]

$5x^3 +11y^3 \equiv 0 (mod 13)$. Let $F(x,y) = 5x^3 + 11y^3$ Now make a table of all possible values of F(x,y) (mod 13) and amazingly it turns out that both x and y should be 0 (mod 13)

[sterile pumice]

bathroom mug

[nova maple]

Yes I made a table with 169 entries yes I have quite the time to waste

[torn escarp]

yikes

at least learn to program lol

[nova maple]

Here's the table and there's only one 0 which is when both x and y are 0 mod 13

[nova maple]

I genuinely think it took lesser time to write this out than it would've taken to program it

I did check with a calculator

Any reason as to why this is happening?

[torn escarp]

what I did was solve for (y/x)^3 = -5/11 = 9 mod 13 and check that 9 is not a cube mod 13

$ python3
Python 3.10.12 (main, Jun 11 2023, 05:26:28) [GCC 11.4.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> for x in range(13):
...     for y in range(13):
...             if (5*x**3 + 11*y**3) % 13 == 0:
...                     print(x,y)
... 
0 0

[nova maple]

Oh wow, descent works here since now you'll have that if (x,y,z) is a solution, x ,y and z are all divisible by 13 which contradicts our original assumption

[torn escarp]

yeah, I should have been more explicit when I mentioned it earlier

[nova maple]

This is cool, but why mod 13?

I calculated tables mod 5 and 11 but didn't get anything of this sort

[torn escarp]

probably cause 13=1 mod 3

that at least chops (13-1)/3 = 4 down into only four possibilities which is less likely

the cubes are 1, 4, 8, 12

1 and 12 are obvious, 8 is obvious once you get 4

[nova maple]

Yes

[torn escarp]

or rather, 4 is obvious once you get 8=2^3 lol

so that's how I enumerated them to see "ah 9 don't work"

mod 5 and mod 11 don't have a third root of unity, 3 doesn't divide p-1, so cubing is just a permutation so it's basically like solving a linear equation in those circumstances

[nova maple]

Yeah that makes sense

[torn escarp]

good question, I didn't really think it through "why" myself I just sorta looked at 5 and 7, but in hindsight probablys hould be thinking if p=1 mod 3 when dealing with cubics

I had tried 7 since 3=(p-1)/2 so it also cut down our choices to -1, 0, 1 for what x,y,z could be

just a similar idea maybe, but failed attempt

[nova maple]

You get this stuff when dealing with square roots

[torn escarp]

yeah, I was thinking about quadratic reciprocity

[nova maple]

I'm not too good at python but 0,0 is the only pair giving 0 mod 13 right?

[torn escarp]

yeah

[nova maple]

Thats what I'm reading the code as

[torn escarp]

it loops through x=0 to 12 and similarly for y

[nova maple]

Yeah

[torn escarp]

and then checks if (5*x**3 + 11*y**3) % 13 == 0 the ** is exponentiation and % is mod

then prints, exactly just to confirm what you're thinking

[nova maple]

Nice

This also definitely takes way lesser time than hand computing

[torn escarp]

yeah, definitely useful to know a little coding and try to use it

[nova maple]

I could've skipped some columns in my table though since values repeat

[torn escarp]

any time you would spend writing out tables of junk you can spend, maybe even a little more time learning how to code it

but at least once you get it, everything after becomes faster

[nova maple]

Not some, 8 of the columns were redundant lmao

[torn escarp]

you can just steal my code and reuse it for other stuff by changing a few numbers

[nova maple]

Yeah, the last time I coded was a long time ago

Stuff like nested for loops are obvious once you see someone use them

[torn escarp]

yeah, also could just make the table itself with code too if it's not so obvious

at least you can focus on generating a lot of different examples

[torn escarp]

just wrote a program now to give some more examples for you, this one lets you check any number, if you save it as thingy.py and run it, it'll run through and print out all the possibilities for 5, 11, 13

def f(x,y,z):    
    return 5*x**3 + 11*y**3 + 13*z**3    
    
def check(n):    
    print(f"Checking {n}")    
    for x in range(n):    
        for y in range(n):    
            for z in range(n):    
                if f(x,y,z) % n == 0:    
                    print(x,y,z)    
    
check(5)    
check(11)    
check(13) 

or you could even make another loop and put check(n) in there to check n from 2 to 20 or whatever

[nova maple]

Thanks!! I don't have access to a PC or laptop at the moment but il run this when I can

I should only expect (0,0,13) when check(13) gets called, right?

5 and 11 should give more solutions

[torn escarp]

output is:

$ python3 examples.py 
Checking 13
0 0 0
0 0 1
0 0 2
0 0 3
0 0 4
0 0 5
0 0 6
0 0 7
0 0 8
0 0 9
0 0 10
0 0 11
0 0 12

yeah for 5, and 11 it's significantly longer

[nova maple]

Oh my bad

Any z value gives 0 mod 13

[torn escarp]

it's literally brute force checking and only printing the solutions yep

sagemath is also something good to look into since it's python + a bunch of math libraries and a little more interactive

[nova maple]

I've heard of sage, seemed overkill for my use case so I never bothered to look more into it

[torn escarp]

anyways point is, getting more comfy with python is a good investment no matter what imo

[nova maple]

Agreed

[torn escarp]

yeah can be overkill for sure

my main reason for learning was just my hands hurt from writing too much math lol

[nova maple]

Ouch

I've never done that much math

Proof based higher level math needs more writing ig

[torn escarp]

just over time

[serene niche]

can someone help me to solve

$2024^{2024} mod 102$

[torn escarp]

use { }

[serene niche]

what is {}

[torn escarp]

instead of () to keep the exponent

[serene niche]

OK thanks

[sterile pumice]

Rainstop

[fleet bone]

use CRT

102=2* 17 *3

mod 2 its 0

mod 3 its 1

mod 17 2024=1(mod 17)

so x=0(mod 2),x=1(mod 3),x=1(mod 17)

x=1(mod 51),x=0(mod 2)

x=52(mod 102)

[prisma folio]

hat I asked in #help-16 would probably also fit here

[nova maple]

Are there any theorems similar to warning's or chevalley's theorem but the degree of your polynomial is greater than or equal to the number of variables?

[open mist]

I'd recommend also asking that in whichever advanced channel you deem most appropriate (probably #groups-rings-fields ?)

[nova maple]

Alright

Wasn't sure if it was advanced enough to be sent there

[fleet bone]

It takes a ton of guts I think to post ur first doubt in advanced channels , without ever putting it in first in the non advanced channels 💀

coz we can imagine someone popping up and say "this prolly belongs to #elementary-number-theory "

[nova maple]

Lmaoo

I usually don't send anything there because I just assume il have to get to college atleast to learn something "advanced" enough to be sent there

[fleet bone]

ya same

[open mist]

Yeah but sometimes you just stumble upon some obscure stuff

[open mist]

Multivariable polynomials aren't much of a topic of study in undergrad

You see them, but not much about them
Until you take a proper algebra class, and then the contents of the class belong in #groups-rings-fields

When I see a question about a part of math I know almost nothing about, I don't feel inappropriate redirecting them to an advanced channel

Especially #groups-rings-fields , there's some early undergrad stuff in there sometimes

[fierce totem]

yo is this where you post stuff about different bases?

[torn escarp]

probably not, I'd say that's more #discrete-math or just general help channels like #❓how-to-get-help stuff

[nova maple]

Yeah, this topic seems pretty obscure-ish

Compared to other number theory topics that is

[torn escarp]

it's more mainstream/fundamental past undergrad though if you're looking at algebraic geometry

[formal tiger]

Me: When x = 1...

[torn escarp]

0 isn't an integer it's nothing! lol

maybe they mean it's never a natural number when x, y are natural numbers?

defining natural number to be integer > 0

[normal heart]

agreed

[torn escarp]

this is just false lmao

once you realize x^2-1 can be made divisible by any number arbitrarily, you just pick the divisors of the denominator

for instance, y=1 gets you 5 in the denominator, so you solve x^2-1=0 mod 5 and one solution is x=6

or hell, substitute x-1 = 2y^2+3 or x+1 = 2y^2+3 lmao

[formal tiger]

Yup I think there's some problem with this question

Gonna ask the instructor for it lul

[wheat tinsel]

Does anyone have an idea on how to do this?

I tried to simplify the statement but idk

I think what is after the "or" might hold always for m>n

but then you can forget about the N_i, but the n_i are not "free", so should still be 1=n_1<n_2<...<n_k<=n, and so you cannot remove much of i

[wheat tinsel]

I'm thinking that's fake now (it's true, I eventually proved it)

[formal tiger]

I got a question would like to ask:
Let $q > 2$ be an integer, not necessary be a prime, assume $a^m \equiv -1 (\text{mod } q)$, does that mean that the order of $a$ must be $2m$?

[sterile pumice]

hoifanrd

[wheat tinsel]

No

(-1)^3=-1 for example

[formal tiger]

Seems good

Thanks!

[torn escarp]

what if we added the restriction that m was the smallest integer such that a^m = -1 mod q, would it hold then?

[formal tiger]

Hum I am thinking about this too

I think if it's smallest then it would hold

[next belfry]

yo guys

how to get the square root of a perfect square

[fleet bone]

smallest positive integer? Under the assumption that such a m exists yes I think .

because first m<order of a

a^(2m)=1(mod q)

so if I let order = k

k|(2m)

(2m)<2k

And k|(2m)

implies k=2m

I think such a m exists iff order is even

If we wonder about when that happens I think that's like write q=(p1)^(a1)p2^(a2).... *pn^(an) as it's prime factorization

And if a happens to not be a quadratic residue modulo some (p_i)^(a_i) and is also coprime

[rare isle]

Let a_1 < a_2 < a_3 < ... < a_n be odd positive integers.
Prove that 1/a_1 + 1/lcm(a_1,a_2) + ... + 1/lcm(a_1, a_2, ..., a_n) < 3/2.

[zenith dragon]

is there a simple way to convert every number of base 10 of : a congruent to b (mod m) into another base? say hexadecimal?

[kind bronze]

What is the number of square free numbers (squares greater than 1) that are less than or equal to 200

Please answer if you are only 100% confident, I just had exam

[kind bronze]

I got 200-78

[kind bronze]

Fuck I just realised the answer is 77 numbers divisible by squares instead of 78 fuck me ded

[surreal tangle]

Have you looked into the am≥gm≥hm inequalities? That seems like it could help

Also $$\prod_{i=1}^{k} a_{i} \geq lcm(a_{1},a_{2},..,a_{k}) $$

[sterile pumice]

smidgin

[fleet bone]

hint :- || induction ||

like

given a1

try to find how to set a2,a3,... to maximize the sum

that is to minimize the lcms

for example

a1|lcm(a1,a2)

if lcm(a1,a2)=a1

then a2|a1 however a_2>a_1

lcm(a1,a2)=2a1 is not possible, as a1,a2 are odd

so lcm(a1,a2)=3a1 is the lower bound here

i am pretty sure u will in the get the GP

$\frac{1}{a_1}(1+\frac{1}{3}+\frac{1}{9}+.....)$

[sterile pumice]

lucid

[fleet bone]

which is less than or equal to 3/2 cleary

[fleet bone]

bashy nt ☠️

this sometimes makes me hate some nt of objective stages of math oly o

[shell spire]

Paul must make an estimation for the installation of solar panels on the roof of a house. He has the dimensions written on the diagram opposite and he knows that the west facade has an area of 22.86m2. What are the dimensions of the roof ?

Hello u have to use the Pythagorean theorem

Can someone help me plz🥺😭😭😭🥺🥺

?

[tacit sinew]

Have you tried opening up a help thread?

[nova maple]

Les Français n'acceptent pas d'aide

[scenic edge]

Where can I read about general approaches to solve n degree polynomials congruent to 0(mod m) where m is some composite number? I am reading Niven's book but I am looking for something that goes into a bit more detail.

[unkempt void]

Well by Chinese remainder theorem we may assume m is a prime power but that can still be tricky

[urban dust]

So, Niven kinda summarizes the general steps in this para from the end of the section on CRT:

Also, if you are doing Niven, you may find Borcherd's playlist useful (esp on quadratic residues and forms), Niven is the reference he mentions: https://www.youtube.com/watch?v=E-6llnLZ7J8&list=PL8yHsr3EFj53L8sMbzIhhXSAOpuZ1Fov8&index=21

[tough condor]

When you learned hensel's lemma, did you learn it in "cases" for a root?

Like, if a is a solution to f mod p^k

a is in case 1 if it can be uniquely lifted to p^k+1

case 2 if it can be lifted non-uniquely

and case 3 if it can't be lifted

[torn escarp]

I learned it first as you can lift if you find an x such that f(x)=0 mod p and f'(x) !=0 mod p.

Then after that I learned the more general, if you can find an x such that |f(x)| < |f'(x)|^2 then you can lift it to a unique point in the open ball of radius |f'(x)| centered at x.

I don't think I see a reason to really emphasize those cases, basically you can or you can't is kinda how I feel about it

once you start just thinking with Q_p, you have a field, so you're not mucking around with any kind of annoyances of the rings Z/p^kZ with multiple solutions that kinda get blended together but go away as you lift higher.

[scenic edge]

Thanks a lot, like, a lot. Seriously.

[tough condor]

yeah that's case 1

Here it is straight from our notes

[torn escarp]

I don't really have anything to add

[white lion]

phi(N) given that N = pq for p and q are distinct primes is (p-1)(q-1) = pq-p-q+1 not pq-p-q-1 right?

[still flare]

Yes

[proper oyster]

if we have p, q primes st 3 <= p < q, how do you prove that if R >= (p-1)(q-1) then there exists m, n in N such that R = mp + nq ?

been struggling with that but it doesn't seem hard at all

[urban dust]

Not sure why you need that condition, since p,q are coprime, can find ap+bq=1 so Rap+Rbq=R for any R?

[open mist]

he wants them positive

[urban dust]

Ah ok

[open mist]

see Chicken McNugget theorem for extra info

[proper oyster]

seems weird to have to use this in the exam i'm working on but as it's the 1st question and the theorem completely answers the question i will take it, thanks

[open mist]

let m', n' be a solution given by the Bezout/Euclid algorithm
Then R = (m'+ qk)p + (n' - pk)q is also solution for every integer k

if m' + qk and n' - pk are never both positive
let k be the smallest for which m' + qk >= 0 and n' - pk < 0
then m' + qk - q < 0 and n' -pk + p >= 0

that means m'+qk < q
So R = (m'+qk)p + (n'-pk)q <= (q-1)p + (-1)q = pq - p - q
Yet (p-1)(q-1) = pq - p - q + 1, so R > pq - p - q
Contradiction

so you can prove this very intuitively from just looking at what happens

and prove that it's impossible, in one jump from a solution to the next closest, to change both signs (to not have 2 positive coefficients) and still have a big enough sum to equal R

[proper oyster]

alright i see the outline of the proof thanks a lot

[shell spire]

No how ? Plz help meee 🥺🥺🥺😭😭😭😭😭😭

@tacit sinew

[shell spire]

Haha aide moii stppp @nova maple 😭😭😭

😭😭😭

@urban dust hey plz help meee

[rotund gust]

To ask for mathematics help on this server, please open your own help channel or help thread. See #❓how-to-get-help for instructions.

[white lion]

chicken nugget theorem but no bbq sauce lemma?

[open mist]

Is that actually a thing ?

[white lion]

wait wut

the chicken mcnugget theroem is real..

it is real

[iron tulip]

I was messing around on desmos during my discrete math class and I found that the numbers of divisors of 0 mod m in each column of a*b mod m will always be factors of m. Why is this?

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

[white lion]

if an integer is say n = 0 mod m that means n|m by definiton of modulo hence m = nl for some integer l

[fleet bone]

what's m?

[restive saffron]

where is the fraction by multiplacation center?

[iron tulip]

the modulus

some integer

[nova maple]

Thats because a and b have to multiply out to a multiple of m. So either a or b has to be atleast a factor of m, if not a multiple of m

Since your a's and b's are coming out of the set {1,2,..,m-1}, both a and b have to be factors of m such that ab=some multiple of m

[magic needle]

i don't get why does this imply the statement. why can't there be 2 factors that become not a factor modm?

[silver oak]

i don't understand what the table is

it's multiplication table mod 10?

it clearly doesn't work for any number

mod 4 you get 10 3 5 3 10 3 5 3 10 3

[patent acorn]

the divisors of 0 include 0 and are closed under addition and negation (if a*b = a*c = 0, then a*(b+c) = 0 and a*-b = 0) which makes them a subgroup of the additive group of integers mod m, then apply lagrange's theorem

in other words: each value that occurs at all in a column occurs the same number of times, so the number of unique values multiplied by how many there is of each must be the total size of the column which is m, which means both of those numbers divide m

[silver oak]

oh i see

mod 4 you make a smaller table and it works

[magic needle]

oh right lagrange theorem

yeah size of a subgroup devides the size of the group itself

[magic needle]

If there is a coset that within the group hides, the coset compared to the group size devides.

[west glade]

yes

[tight eagle]

so I can use a generalization of fermats to get 7^12(17-1) is congrutent to 1 mod 17

[wooden glen]

You can use the bog standard version of Fermat's little theorem.

[tight eagle]

im not sure I know that one

[wooden glen]

So you only know special versions of it? 😕

[tight eagle]

wait no you mean the regular theorem I just dont know what you meant by bog

[wooden glen]

Sorry, that might have been too colloquial language.

[normal heart]

[wooden glen]

https://www.merriam-webster.com/dictionary/bog-standard, for what it's worth.

[tight eagle]

The versions I know are
a^p-1 congruent to 1 mod p
a^p confruent to a mod p
a^n(p-1) congruent to 1 mod p

[wooden glen]

The first one is what you want here.

[tight eagle]

oh I see yea I've never encountered that lol

[wooden glen]

The hint points out that 7^193 = 7^16 · 7^16 · 7^16 · ·· · 7^16 · 7^1.

[tight eagle]

ohh okay

[tight eagle]

im not really good at modular arithmetic so im still kinda lost about how to proceed to be honest

[wooden glen]

What does the little theorem say about each of the 7^16 factors?

[tight eagle]

that they are congruent to 1

mod 17

[wooden glen]

Yes.

So what is 1 · 1 · 1 · · · · 1 · 7^1?

[tight eagle]

7

so 7^193 = 7 mod 17?

[wooden glen]

Yes.

[tight eagle]

Okay that makes sense thank you, I guess I just am still confused about the whole equivalence part of congruence in the same modulo

so with a^(n(p-1)) = 1 mod p
id just have 7^(12(16)) = 1 mod p I could just multiply both side by 7 to get the same result

by the reverse of the cancellation law

[stuck wedge]

How do i prove that if d divides n then one of d or n/d is less than or equal to sqrt n

[dusty dragon]

Towards a contradiction, suppose that d and n/d are both > sqrt(n). Then n = d * n/d > sqrt(n) * sqrt(n) = n which is a contradiction

[brave citrus]

if a,b,m,n,p,q are positive integers and gcd(ma+nb,pa+qb)=gcd(a,b) then |mn-pq|=1, its true?

[open mist]

mka + nkb + pha + qhb = (mk+ph)a + (nk+qh)b
Let i, j in N, we want a solution to mk+ph = i, nk+qh = j

That will exist (probably iff) gcd(m,p)=gcd(n,q)=1
Doesn't quite look like your expression.

Let a = 2, b = 3
m,n,p,q = 4,5,6,7
ma+nb = 23, pa+qb = 33
gcd(ma+nb, pa+qb) = 1 = gcd(a,b), yet |mn-pq| = 22 != 1

[white lion]

pro tip, we can always reduce the exponenet modulo phi(m) for a given congrunce modulo m

[stuck wedge]

Thank you

[brave citrus]

Oh thanks😳

[river spruce]

Hello people, I have an elementary question about group, what are left coset and right coset really ?

[white lion]

#groups-rings-fields

[formal tiger]

I found a bug in the question 4.2!

Can I just say that the even number 0 has infinite representation as difference of 2 primes?

[white lion]

atleast

[tough condor]

Is there any closed form for the sum of two continued fractions?

If $[a_0;a_1,a_2,...]+[b_0;b_1,b_2,...]=[c_0;c_1,c_2,...]$, can you write the $c_k$s in terms of the $a_k$ and $b_k$s?

[sterile pumice]

nHail

[wheat tinsel]

I doubt it

it is an interesting operation tho

Say you have two continued fractions [1; X] and [1; Y], and add them together. The first term will depend on whether [0;X]+[0;Y]<1 or not.

if it's <1 then it's two, if not, then idk what it is (although it will be strictly in between 2 and 3)

But it could be anything between those two values, and then it is not very clear what you are supposed to do afterwards

if you add two periodic continued fractions, then the result will still be periodic, tho

anyway

look at this

,w continued fraction of 1+sqrt 2

[sterile pumice]

Results provided by WolframAlpha

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

Requested by Croqueta#3385

[wheat tinsel]

,w continued fraction of (1+sqrt 5)/2

[sterile pumice]

Results provided by WolframAlpha

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

Requested by Croqueta#3385

[wheat tinsel]

,w continued fraction of 1+sqrt 2+(1+sqrt 5)/2

[sterile pumice]

Results provided by WolframAlpha

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

Requested by Croqueta#3385

[wheat tinsel]

oops nvm that is wrong

very wrong

because when you add two quadratic irrationalities they need no longer be quadratic irrationalities lol

the above example is one

@tough condor

[tough condor]

yeah

[wheat tinsel]

wait I goofied a little bit here, if [0; X]+[0;Y]>=1 then the first term will be 3

[tough condor]

Yep

[wheat tinsel]

I don't even see how it would be just slightly helpful to know the continued fractions of x and y to calculate that of x+y

I think it may be more fun to look at it the other way around: Is the operation [a0;a1,a2,....]+[b0; b1,b2,....]=[a0+b0;a1+b1,a2+b2,...] any meaningful?

or can you characterize it in terms of the numbers involved? probably not but idk

[wheat tinsel]

How to evaluate $\sum_{a+b=1} \left(\frac{ab}{p}\right)$ where a,b run through Z/pZ

[sterile pumice]

Croqueta

[wheat tinsel]

I know one way which is to rewrite it as $-p+\sum_{a+b=1}\left(1+\left(\f ap\right)\right)\left(1+\left(\f bp\right)\right)$, and then $\sum_{a+b=1}\left(1+\left(\f ap\right)\right)\left(1+\left(\f bp\right)\right)$ counts the number of solutions to $x^2+y^2=1$ but the point of writing this is to count the number of solutions to that equation mod p, so it would be redundant

[sterile pumice]

Croqueta

[wheat tinsel]

nvm I think I got it

$\sum_{a+b=1} (a/p)(b/p)=\sum_{a+b=1}(ac/p)(bc/p)=\sum_{a+b=c} (a/p)/b/p)$ whenever $c\neq 0$. Thus $p\sum_{a+b=1} (a/p)(b/p)=-\sum_{a+b=0}(ab/p)+p\sum_{a,b}(a/p)(b/p)=-\sum_{a+b=0}(ab/p)=-p(-1/p)$

[sterile pumice]

Croqueta

[wheat tinsel]

[proper oyster]

Hi, been stuck on this one :
if we write $<p, q>$ for the set of all positive integers of the form $mp + nq$, with $m,n$ positive, and we call $S(z) = \sum_{s \in <p,q>} z^s$ then how would i go about proving that $(1 - z^p - z^q + z^{p+q})S(z) = 1 - z^{pq}$

[sterile pumice]

Extends

[proper oyster]

I've tried writing the left hand side as (1-z^p)(1-z^q)S(z) and finding some factorization of (1-z^p)S(z) to get something along the lines of (1-z^q)*some factorization that equals the sum from 0 to p-1 of (z^q)^k but that's about it

(forgot to said it but 3 <= p < q with p, q primes)

[wooden glen]

I'm almost sure you need to allow m,n >= 0 instead of requiring them to be positive. If <p,q> doesn't contain 0, then if we plug in z=0, your goal ends up claiming 0 = 1.
Idea: since p and q are coprime, you can replace the sum over <p,q> by a sum over 0 <= m < q and 0 <= n, which generates each element of <p,q> exactly once as mp+nq.
Then you can multiply (1 - z^p - z^q + z^(p+q)) into each term of the sum and possibly hope to find an argument that all terms of it except the stated ones telescope.

[proper oyster]

yeah sorry might be language barrier, when I mean positive I mean >= 0

[wheat tinsel]

I think you can calculate z^pS(z) in terms of S(z) + something else

[wooden glen]

Another way to state this would be to factor S(z) as (1 + z^p + z^2p + ... + z^((q-1)p))·(1 + z^q + z^2q + z^3q + ...) and use the formulas for finite and infinite geometric series to get both of these to closed forms.

[proper oyster]

ah yep this looks promising, thanks

[still flare]

Hint: gcd(a, b) = gcd(a + b, b) = gcd(a + 2b, b) etc.

It's a hint, so I want you to think about it

[fleet bone]

For the first one I think use Z[i] is UFD?

or if you know this https://mathworld.wolfram.com/SumofSquaresFunction.html for r_2 , though it's a result of that only

[brisk shard]

How do I prove that the sum of two positive integers is larger than each of those integers with the normal ring axioms and things like that (not Peano arithmetic)?

Or is it generally just taken as an axiom?

[fathom sierra]

with the normal ring axioms, you could also have Z/nZ you know, or even weirder stuff

• it's not like you necessarily have a notion of order with the ring axioms

[brisk shard]

Well, I mean there are a few axioms about the inequalities.

[fathom sierra]

what axioms are you talking about then?

[brisk shard]

I'm going through Spivak's Calculus book and a number theory book and I was wondering. Here are Spivak's axioms and definitions of the inequality signs:

P is the positive integers.

[fathom sierra]

yeah well that's not part of the definition of being a general ring

that's specific to integers

[brisk shard]

Are those axioms enough to prove it?

[fathom sierra]

wait there's multiplicative inverses also in your axioms

[brisk shard]

Oh, that's for the reals.

[fathom sierra]

you're talking about real numbers aren't you ?

[brisk shard]

Hmm.

[fathom sierra]

would make sense for spivak

[brisk shard]

OK, how would you prove that the sum of two positive reals is larger that each of them?

Hmm, I think I see a way.

a > b if a - b is in P.

a and b are in P.

So, (a + b) - b = a is in P, so a + b > b, and then you can just do the same thing for a + b > a.

[fathom sierra]

yeah

[brisk shard]

OK, thanks.

[dreamy silo]

Hey, I have a task that basicly boilds down to solving a system of equations that looks like this:

x = 3 mod 17
x = 4 mod 11
x = 5 mod 6

or written differently

x = 3+17a = 4+11b = 5+6c with a,b,c in N

How would I solve these?

I have this task in Algebra, but I was told in that channel that it belongs here.

[open mist]

Chinese remainder theorem

It leads to an algorithm that lets you solve these

[dreamy silo]

I'll have a look

I just sort of brute forced it with python. The answer is 785

lowest answer*

[open mist]

yeah should be unique mod 6*11*17

(because they're coprime)

[dreamy silo]

Thank you : )

[white lion]

What people refer to the The Chinese Remainder is actually really tedious to try and use to solve a system of congruences (but it does tell us if there exists solutions). A better method would be find the set of solutions for the first congruence and then dropping all the solutions for the first congruence that are also not solutions for the second congruence e.t.c

You can do this really fast by first saying that (for example in your case) that the for the first congruence all the solutions are x = 17k + 3 for all k. Then we plug this into the second congruence 17k + 3 = 4 (mod 11) and solve for k, you’d get k = 2 (mod 11) and so 17(2) + 3 is a solution for the first and second congruence and you can continue like this

[wooden glen]

is actually really tedious to try and use to solve a system of congruences
What one does in practice for n, m coprime is:
Once and for all, use the extended Euclidean algorithm to find p and q such that pn + qm = 1.
Then we have qm == 1 (mod n), qm == 0 (mod m) and also pn == 0 (mod n), pn == 1 (mod m).
Now if we want x such that x == a (mod n) and x == b (mod m), just set x = aqm + bpn. Reduce modulo nm if desired.

[tough condor]

maybe this is just personal preference

but extended euclidean algorithm by hand is a pain in the ass

[west glade]

well sure but if you did the other method you would also have to do it to solve the equations like 17k+3=4 mod 11. well if the numbers were bigger of course

[primal pewter]

CRT and Euclidean division can be avoided in this case. It's a matter of choosing the right equations to work with and being a bit lucky.

@dreamy silo
write x=11a+4,
plug it in the third equation: -a+4=5 (mod 6), so a=5 (mod 6), thus a=6k+5, so x=66k+59
now plug this in the first equation, thus getting -2k=-56 (mos 17), and since -2 is invertible mod 17, we get k=28=11 (mod 17).
Finally, x=66(17t+11)+59=1122t+785.

[white lion]

if you're good at solving linear congruences its not that bad

[rotund zinc]

if (x, y, z) is a primitive pythagorean triple how do you show: (all positive)

$\cancel{\exists} w \in \bZ^+ : x^2-y^2=w^2$

[sterile pumice]

CoolShot

[rotund zinc]

i think this is equivalent to showing $2x^2 - z^2$ can not be a perfect square

[sterile pumice]

CoolShot

[rotund zinc]

but im not sure how to proceed with that

[rotund zinc]

hii

can anyone help me with this

i tried some other stuff but it did not help

i tried using the general solution of x^2 + y^2 = z^2

but it didnt help

[prime gust]

since (x,y,z) is a primitive then we can conclude that x is even and y is odd or x is the odd and y is the even. separate those cases and try solving it that way

[dreamy silo]

Thanks, that's basicly how I attenpted to solve but for me it didn't seem to lead anywhere 😅

[fossil fog]

When we have something like $\mathbb{Z}/3\mathbb{Z}$, would it be right to say that this breaks up $\mathbb{Z}$ into equivalence classes? As in, would we say $\mathbb{Z}/3 \mathbb{Z} = $ a set of equivalence classes?

[sterile pumice]

JJCUBER

[still flare]

Yes

[fossil fog]

Is there a notation as to how one would represent said set? (As in, some expanded form involving the descriptors 0, 1, 2?)

[still flare]

{3Z, 1 + 3Z, 2 + 3Z}

This is ‘coset’ notation.

[fossil fog]

I see, thank you! I probably should have surmised that on my own now that I think about it. (This was brought up in my linear class when we were going over stuff like direct sums and quotient spaces — $V/W$.)

[sterile pumice]

JJCUBER

[still flare]

You're probably aware that V/W is constructed exactly the same way, then

[fossil fog]

Yep!

Although we wrote it as

Where we had (left) cosets of the form

[red raven]

As a complete outsider with no real knowledge of number theory outside of the basics, has the teaching of the subject shifted toward algebra? Pretty much every book or resource I look into uses algebraic ideas like rings, fields, etc. in order to qualify number theory.

In the same way that there's algebraic number theory, etc., is there something like "numerical number theory" which attempts to strip all of the algebra away? I love algebra, but I'm curious if number theory is even teachable without algebra.

[still flare]

I don't know what you think ‘numerical number theory’ would be. We have plenty of analytic number theory though, wherein we use methods from analysis to understand number theory.

If you're asking for something like a non-algebraic interpretation of modular arithmetic, this is a bit silly as this is in some ways the prototypical example of an algebraic structure.

[white lion]

Im going to assume you're talking about elementary number theory, but yeah you defintely don't need to know what a field, group or ring is

[tight eagle]

can someone confirm if this is correct

[torn escarp]

yeah, but I would finish it off by reducing 289 mod 21 to a number in the range 0 to 20

also the line where you squared it looks a bit off, but you worked it correctly in the next step, specifically it looks like: $$17^{12^2} = 1^2 \mod 21$$ but it should be $$(17^{12})^2 = 1^2 \mod 21$$

[sterile pumice]

Merosity

[tight eagle]

oh gotcha

thanks

[torn escarp]

yup you're welcome

[wheat tinsel]

There's analytic number theory. There is computational number theory too, but it still uses a lot of algebra whenever useful

Look up Apostol's book for analytic NT, for example

[tight eagle]

so 11 is a symmetric algorithm key?

also

does this work if p=q or do the primes have to be distinct

[primal pewter]

it doesn't work for p=q
check: p=q=3, r=1, a=4

btw, it works for any coprime integers p and q, not necessarily primes

[tight eagle]

gotcha

also can someone give me a hand solving

I'm having difficulty with the mod power of prime

I was thinking I should apply euler's theorem but I dont know how I can easily calculate totient(49) since I cant use (p-1)(q-1)

[primal pewter]

phi(p^k) = p^k - p^(k-1)

[tight eagle]

hmm okay I'm not sure thats a property I can use though

I haven't learnt it

[primal pewter]

then refer to the definition: phi(n) is the number of elements in the set {1,2,...,n} coprime to n

for n=49 these are all the numbers in that set, except for 7,14,21,28,35,42,49 (multiples of 7)

[tight eagle]

ohhhh

okay that makes sense

I thought u meant to brute force it but I guess by applying FTA we can clearly see all the non coprimes are those that are factors of 7

[tight eagle]

though this method wouldn't work well for higher powers but I guess then you can prove this property

[primal pewter]

yeah, it's the same idea: not being coprime to some power of p is equivalent to being a multiple of p

[tight eagle]

gotcha thank you

[cursive furnace]

Does the Chinese Remainder Theorem have any applications outside of algorithms?

[fleet bone]

yes very much

by algorithms u mean solving congruences?

u can use it for example to derive a closed form of the number of quad residues of a natural no n using its prime factorization

it is used for example in , forming explicit constructions to provide examples sometimes ,converting composite numbers to power of primes

counting things like the previous example

u maybe want go through some of these https://web.evanchen.cc/handouts/CRT/CRT.pdf

[cursive furnace]

I think I meant, non number related things. Like something I can relate it to for a nonSTEM major.

[fleet bone]

oh then I don't really know

[charred roost]

I just discovered the identity $2^{jk} = (1 + 2^k + \dots + 2^{(j-1)k})(2^k -1)$. Is there a name for this, or a derivation that's easier/more enlightening than just multiplying out?

[sterile pumice]

sheddow

[urban dust]

Shouldn't LHS have a -1? and isn't it just the geometric series sum?

[unkempt void]

As was said above, this is the basis of geometric series, but nice

I think just seeing that stuff cancels when you multiply out is the most enlightening way to prove this

[charred roost]

Yeah, I guess there should be a -1 on the LHS. Thanks 👍

[timber tartan]

How can I approach this question: Find all number n such that all it’s positive divisors can be arranged in a rectangular grid such that the sum of all rows and the sum of all columns are equal

[white lion]

Well have you tried making any trivial examples?

[surreal crescent]

very interesting problem

how tf could n be prime

[oblique wigeon]

hello

I'm reading Euler's theorem proof but there is something that is not clear to me but seems obvious

[timber tartan]

Surely n being prime doesn’t work because u need at least 4 divisors?

[oblique wigeon]

this part

or in other words:

[surreal crescent]

yes

[timber tartan]

Like I got that 6 works

[surreal crescent]

how does 6 work

[timber tartan]

Like

1 2
3 6

The sum is 12

[surreal crescent]

but the sum of all the columns are not equal

[timber tartan]

I think I misunderstood

Okay yeah

I’m struggling to come up with an example tbh

[white lion]

how big is the grid, and wdym by the "sum of all the rows must be equal to the sum of the all the columns" as in if you sum up the rows or the sum of each row should be equal to the sum of each coloumn?

and is it an nxn grid?

[surreal crescent]

grid can be of any size

[white lion]

is it n by n?

[surreal crescent]

no im pretty sure u can only use each divisor once

[white lion]

Im aware but the question says rectangular so i want to know if there are any restirctions on the dimension of the grid

[surreal crescent]

Find all numbers, if any, such that all of its positive divisors can be arranged in a rectangular grid, with each divisor only used once, where each row has a constant sum and each column has a constant (not necessary distinct from the sum of the rows) sum.

like this is how its meant to be stated

i think

[urban dust]

If $(a,n)=1$ $aa_i$ will also be relatively prime to n. And, the $aa_i$ are all distinct coz if $aa_i=aa_j$ then $a_i=a_j$. So, the $aa_i$ are the same numbers $a_i$ in some different order (as you have noted they are permutations of each other). So, their product mod n will be the same.

[sterile pumice]

JS

[jade nexus]

https://projecteuler.net/problem=864

C(n) is the number of 1 ≤ k ≤ n s.t. k²+1 is square free. Problem wants you to compute C on a stupidly big number, so basically find a simpler expression for C. So far, I've noticed C(n+1) is either C(n) or C(n)+1. If the first thing happens, say that C staggers on n. Looking at the distance between when staggers happen, it seems to be at most 14 and 14 and 11 occur a lot at least in the first 1000 n. Fun problem, though idk number theory so maybe there's something obvious I'm missing

[torn escarp]

I'd probably start thinking about the gaussian integers and see if that leads to any insight

[fleet bone]

also that if p^2|k^2+1 for some prime p <=> 4 is the order of k mod p^2

[timber tartan]

No matter which row or column you’re summing over it has to be the same

Sorry for the confusion

And one row works

[oblique wigeon]

So, the $aa_i$ are the same numbers $a_i$ in some different order (as you have noted they are permutations of each other)

[sterile pumice]

.1

[oblique wigeon]

I can't get why 😦

I know both sets are reduced residue systems, but why each element of one set has to be congruent to another element of the other set
When both sets are a complete system of residue It make sense, but this is not that case
the claim in yellow is what I don't get

[primal pewter]

@oblique wigeon the point is there are exactly phi(m) residues mod m coprime to m

[leaden stream]

because a is relatively prime to m, if r_i and r_j are different residues mod m then ar_i and ar_j must also be different residues.
since you have listed all the residues already, each ar_i must correspond to some r_j you already listed

[urban dust]

it's the same as for a complete system of residues. Note that the reduced residues are mod m. So any full set of reduced residues mod m will be the same set (in possibly different order).

[sterile pumice]

JS

[thick panther]

what is N supposed to be here? i could not find it in my notes anywhere and its clearly not the norm map on Z[sqrt2] either

rest of sol:

[west glade]

it is the norm map

[thick panther]

it is? but surely N(3 + sqrt 2) would thus be 11 not 7

and also, N([3+2sqrt 2]^n) would not be 1^n either

[torn escarp]

show your work computing it

[thick panther]

i thought N: Z[sqrt d] -> Z is defined as N(a+bsqrtd) = a^2 + db^2 if we take N to be the norm map? which would mean N(3 + sqrt2) here would be 9 + 2 if it was to be the norm map

if it were, not was even

[torn escarp]

nope this is not the definition N(a+bsqrtd) = a^2 + db^2

the definition is multiply it by its conjugate

[thick panther]

oh ... i got signs mixed up then

thank you

[torn escarp]

yeah you're welcome

[thick panther]

oh i understand why i thought it was so hahaha
because im also taking an algebra class and we only really looked at Z[sqrt(-d)] for d>0 for that class

[torn escarp]

yup mixed up the real with imaginary quadratic 😛

[keen pagoda]

even with the hint idk what to do

[primal pewter]

@keen pagoda using the hint, you have x^(4n+2) = 1 (mod p)
now use the equation to conclude that x^(4n+2) = -1 (mod p)

[keen pagoda]

I have absolutely no idea how to do that

Oh actually

I think I do

I don't.

[primal pewter]

p=4n+3

so the first part comes from substituting p=4n+3

[keen pagoda]

I know

I have no Idea how to do the second

[primal pewter]

the second part comes from x^(4n+2)=(x^2)^(2n+1)=...

[keen pagoda]

Ah I'm dumb

Very

Extremely

I completely forgot how exponents work

I would never get to the answer lmao

Yikes

[prisma folio]

Prove Fermat's Little Theorem: $n^p \equiv n \pmod p$ for all prime $p$ and $n \in \mathbb Z$. \begin{enumerate} \item We could perhaps try to do this by induction. After $p$ it doesn't make sense, but after $n$ perhaps? Though [(n + 1)^p \equiv n + 1 \pmod p] doesn't seem to get resolved from [n^p \equiv n \pmod p.] \item We could try to binomial expand it? [n^p = \Big(\frac n 2 + \frac n 2\Big)^p = \sum_{k=0}^p \binom p k \Big(\frac n 2\Big)^k \Big(\frac n 2\Big)^{p - k}.] Though that doesn't seem very useful. \item Perhaps we could try something like rewriting this as \ $p \mid n^p - n$ and try to use Bezout's lemma?\end{enumerate}

[normal heart]

induction could work, consider binomial expansion on (n+1)^p

[prisma folio]

That's [\sum_{k=0}^p \binom p k n^k]

[normal heart]

yeah

[prisma folio]

Hm.

[normal heart]

you could continue from here

[prisma folio]

That can be divided by n

Atleast for k >= 1

[normal heart]

you're modding p so you'd consider divisbility by p instead of n

[prisma folio]

Ah

Right

Well it can get divided by p

p!/(p - k)!k!

The p term in p!

[normal heart]

when is this divisible by p?

for which values of k

[prisma folio]

not equal to 0

Or else it cancels

Also k not equal to p

[normal heart]

yeah

so that's your proof

[prisma folio]

Though, how can we be sure that (p - 1)!/(p - k)!k! is an integer?

We could prove that p!/(p - k)!k! is, but what about this

[normal heart]

pCk is an integer, and clearly the denominator doesn't divide p, so we can take p out and it is still an integer

(since p is a prime)

this is not true if p is not a prime, for example 4C2 is 6 but 6/4=1.5 is not an integer

[prisma folio]

Oh

[prisma folio]

Right, thanks!
But then, the induction is useless. We could go with my approach 2.

We have a p choose k term there too?

[normal heart]

no, you use induction

(n+1)^p = n^p+1 mod p by binomial

and use induction hypothesis on n^p

[prisma folio]

Yep

[prisma folio]

Oh, true

Yeah, it'll be n + 1 on the RHS

Thanks!

[prisma folio]

Do you think one could make my approach 2. work somehow too or not really?

[normal heart]

i doubt

[prisma folio]

Right away binomial expanding n^p

And somehow seeing that it can be divided by p

[normal heart]

since n need not be even

[urban dust]

you can use Euler's theorem if you are allowed to use it?

[prisma folio]

Ah

[prisma folio]

What is it?

[prisma folio]

True, we'd have to show that that becomes an integer after all too, right?

[urban dust]

$a^{\phi(p)} \equiv 1 (mod p)$

[normal heart]

you can't really consider divisibility when not everything are integers

[sterile pumice]

JS

[prisma folio]

Yeah, we'd first need to show it's an integer

And then consider divisibility

Right?

[prisma folio]

What does phi denote?

[urban dust]

Totient function. I guess if you are not there yet, then you want a proof without it 😄 so I guess you can't use it yet.

[normal heart]

you could morally make the 2nd approach work, but it's in the same spirit as induction. It's worse than the first approach since you'd have to split into cases, when n is odd and when n is even

[prisma folio]

Yep, true. Thanks

[prisma folio]

I've heard of it but my lecture notes didn't cover it, so I assume I shouldn't use it right now

Thanks

[open mist]

People are generally not allowed to use theorems that are simply stronger versions of whatever they're proving

[urban dust]

yep makes sense 👍

if i remember right Niven/Zuckerman prove Euler first and then use it to prove Fermat's little so wasn't quite sure which comes first.

[open mist]

History doesn't matter much in the face of the mathematical state of things

[fleet bone]

yes in niven

[sacred junco]

heyo, i got a lesson in diophantine equation earlier and i still can't understand it, can anybody help me understand its concept or how it works?

[torn escarp]

no one can help if you don't post it

[sacred junco]

wdym exactly?

[dusty dragon]

https://dontasktoask.com/

[thick panther]

hey, could i get some help with a few problems please? ill post them in succession and where exactly im struggling with them:
here is the first one; i've seen similar problems before but i'm kind of stuck with going about them,
my first attempt was considering x^2 + (p+1)x + 1 to make the coeff. of x even and thus i'd be able to complete the square, but it doesnt seem like this helps with anything
next thing i tried considering working back and thinking where (-3/p) = 1 could lead instead but to no avail; it doesn't seem to help at all once more

so to sum up; im not sure how to remotely get close to anything that would lead to the condition that -3 is a QR mod p
could i ask for a hint or starting point please?

[urban dust]

See if you complete the square perhaps? with integer coefficients

[primal pewter]

@thick panther multiply the equation by 4

[thick panther]

ill see where it goes, thanks

oh i understand what youre getting at

nice

[primal pewter]

also notice that 4 is invertible modulo p
this is important because it guarantees that the equation you get is equivalent to the initial one

[thick panther]

yeah i see

thank you

[white lion]

means you need to be more specific, what exactly are you confused with, in regards to Diophantine equations

[next cave]

Why is it a meaningful question to ask what percent of integers are even,

But it’s not meaningful to say what percent of prime numbers are comprised of only 1 digit? (Like 2 , 3, 5, 7, 11, 1,111,111,111,111,111,111 )

[iron edge]

It hasn't been yet proven/disproven whether there are infinitely many such primes as far as I'm concerned

[next cave]

I think it’s proven there is infinite

But what I’m saying is with even numbers we can say 50% of integers are even

[iron edge]

Then they have the same cardinality as the integers, but where have you seen the proof?

[next cave]

But with prime numbers even though it’s infinite we can’t put it in percentage terms

[iron edge]

Saying it's 50% of integers is kind of worthless, that could be said about any countable set

Since 2|Z| = |Z| so to speak

And you should be careful when doing arithmetic on cardinal numbers

[torn escarp]

look into the 'natural density'

[iron edge]

Yeah I just thought about instead taking the limit of density Interesting

[torn escarp]

if the original question was asked based on seeing something that was based on natural density, then I'm guessing that means the liminf and limsup are provably different

like plausibly assuming the assertion that it wasn't meaningful originally came from somewhere and they're coming here asking about it

[urban dust]

Anyone can ask whatever question. You may wanna look into repunit primes.

[next cave]

I came up with the question myself, I guess I meant not meaningful because I was wondering why you couldn’t attribute a percentage to it

[next cave]

Yeah i agree, but do you disagree with the statement that 50% of all integers are even?

[iron edge]

Not really

[urban dust]

There is the prime number theorem....

[next cave]

Brand new to number theory

I’ll look into that

[next cave]

the set of all odd numbers is a countable set right?

[iron edge]

Right

[next cave]

Those have 0% even numbers

So it is slightly meaningful to say that about a set

[fleet bone]

hol on to start with we need to define percentage here i think as its only defined for fininte sets?

Or even sometimes

when we count things such as percentage of primes

like pi(x)/x

we use limits to be more formal

but set of integers ? That does not have a lower or upper bound so how r u defining the progression of the limit firstly

[coarse otter]

how do i do this?

n is any positive integer

some*

[sand iris]

This is definitely more appropriate in a help channel

And when you post there, show your working don’t just ask someone to do it

[coarse otter]

oh

so should i delete it?

[urban dust]

It can be checked that $2a_i + \lfloor 2 a_i/10 \rfloor$ mod 10 is the same as the permutation $\sigma$. And, it is similar to saying "multiply the digit by 2 and add the digits of the result" which might be how they came up with it. You may see the first answer here for some more info or look up Luhn's algo. https://math.stackexchange.com/questions/3251960/how-does-luhn-algorithim-actually-work

[sterile pumice]

JS

[gilded breach]

Theorem 1: If $\binom{n}{r}$ denotes the number of r-combinations taken from a set S of n elements, then

$\binom{n}{r} = \frac{n(n-1)...(n-r+1)}{r!}$

[sterile pumice]

Autumn

[gilded breach]

Prove theorem (1) using the principle of mathematical induction in conjunction with exercise (3)

Exercise (3): Prove combinatorially that

$\binom{n}{r} = \binom{n-1}{r} + \binom{n-1}{r-1}$

[sterile pumice]

Autumn

[gilded breach]

Proof of Theorem 1 using induction:

$\binom{n}{r} = \frac{n(n-1)...(n-r+1)}{r!}$

[sterile pumice]

Autumn

[gilded breach]

When n=1, $\binom{1}{r} = \binom{1}{r!}$

[sterile pumice]

Autumn

[gilded breach]

I don't know how to do (1 r)

If we assume theorem 1 is true for n, then we try to show $\binom{n+1}{r}$ is true, by using

$\binom{n+1}{r} = \binom{n}{r} + \binom{n}{r-1}$

[sterile pumice]

Autumn

[gilded breach]

How do we prove for $\binom {n}{r-1}$?

[sterile pumice]

Autumn

[gilded breach]

Since we assumed (n r) is true, but it's not mentioned about (n r-1)?

I feel confused if induction is supposed to be on n or on r.

[brisk quarry]

Find the number of pair of primes $(p,q)$ for which $p^2+2pq+1$ is also prime

[sterile pumice]

Heckin' Beluga

Find the number of pair of primes $(p,q)$ for which $p^2+2pq+1$ is also prime

[lone pumice]

Do you have any ideas?

[nova maple]

p must be 2, if I'm not wrong

Because if p^2+2pq+1 is a prime, it must be an odd prime.So, p^2+2pq must be even <=> p^2 is even <=> p is even

Since p is even and a prime, it should be 2

[fleet bone]

ya that's clear

but it's hard to go from 5+4q prime

for q prime

[nova maple]

There is a theorem of dirichlet that says there will be infinitely many primes of this form, but you cant say anything about q from it

[fleet bone]

yes

actually

There is also a open problem

are there infinitely many primes p, q such that p=1+2q

I belive

these two look similar

[nova maple]

Well then we can give up just about now

xD

[fleet bone]

I think this can be converted to some quadratic residue condition

I forgot the details

maybe applying it here helps

(5|q)=(5|(4q+5))

I think

[nova maple]

2
3
17
23
47
59
83
101
107

Here are a few values of q

No real patten

I did a check for q under 10000 and it goes on till 9941

I suspect there are infinitely many

[nova maple]

The difference of the 2kth solution and the 2k-1th solution seem to be a multiple of 6

[patent acorn]

that's because all of the solutions are one less than a multiple of 6

excluding 2 and 3

[nova maple]

Why?

[patent acorn]

all primes (excluding 2 and 3) are either one less or one more than a multiple of 6, otherwise it would be a multiple of either 2 or 3

[nova maple]

Oh right

[patent acorn]

if it's one more than a multiple of 6, then 4(6n+1)+5 = 24n+9 is divisible by 3

[nova maple]

Yeah makes sense

When you subtract the solutions either the 9 goes away or it becomes an 18 both give multiples of 6

[patent acorn]

this feels like the kind of thing where the answer is in fact that there are infinitely many but it's ridiculously difficult to prove

same as how fermat's last theorem was a conjecture for hundreds of years and then proved using modular curves or something, except we're conjecturing it now and it gets proven in 2300 using complete semistable riemannian monoidal algebras or whatever

[nova maple]

Yeah

[fleet bone]

2300 💀

[white lion]

@merosity weren't we playing with this same exact equation a while ago? or atleast on similar to it?

[prisma folio]

For prime p

[lone pumice]

this isn't even true

e.g.

a = 2 and p = 3 has counterexamples for both directions

x = 1, y = 3 is a counterexample to =>
x = 1, y = 4 is one to <=

[still flare]

2^2 = 2^4 modulo 3.

[white lion]

no but x = y (mod phi(p)) follows

[primal pewter]

not even this is true
counterexample: p=7, a=6, x=2, y=4

all you can conclude is that x=y (mod ord_p(a) )

[white lion]

where is the a coming from?

[tight eagle]

I'm probably missing something very obvious here but

for n= 3

aren't all the possible functions simply

so |s| = 6 not 2^3 = 8

but the question is telling me its true and to prove it so something must be flying over my head here

[urban dust]

A function is defined on the entire set not only on single elements.

[tight eagle]

@urban dust can you give me an example with n=2

[urban dust]

f(1)=0, f(2)=0 is one function. f(1)=0, f(2)=1 is another and so on...

[tight eagle]

wait so I'm still confused

so then 2^2 = 4

[tight eagle]

so how does this apply

wait

ok nvm I think I know what you're saying

ok oops thanks