elementary-number-theory

[sacred junco]

is g equal to 9? @leaden swan

[leaden swan]

Yea

g=9

g^b=16

g^a=8

[sacred junco]

i thought g is public

[leaden swan]

It is,but Alice has to generate it

[sacred junco]

oh

[leaden swan]

Alice usually broadcasts that to public but here considering Bob alone is enough for the problem so they did that

[sacred junco]

so the secret key is 8^3 mod 23?

[leaden swan]

Yea

[sacred junco]

is 3) asking for the value of a?

[leaden swan]

Yea

[sacred junco]

i can solve g^a=8 using an index table for g=9

but it askes for an index table wrt to 5

[leaden swan]

Should work

What they intend you to do is find x such that 5^x=9 and 5^y=8

And then find x' such that 5^(xx') becomes 5

x' has to be inverse of x mod 22

[sacred junco]

are we doing RSA

[leaden swan]

Then 9^(x'y) will be your solution

No exponential manipulations

[leaden swan]

This is simpler tho

Although it might not exactly be a index table because 9 might not be a primitive root

[sacred junco]

how do we find a though

[leaden swan]

Just find values of g,g^2,g^3...

If something matches you have your a

[sacred junco]

we're solving g^a = 8 not 5^a = 8 mod 23

[leaden swan]

Yea

[sacred junco]

im not sure i get the procedure

[leaden swan]

https://cryptohack.org/challenges/diffie-hellman/
You can try the starter problems here

[leaden swan]

It's brute force

You just keep on multiplying g(=9) with itself until you get g^a(=8)

[sacred junco]

what about the index table wrt 5

[leaden swan]

That's weird and convoluted

[sacred junco]

maybe we can take log base 5 of both sides

[leaden swan]

Or I am just blind. Idk ask @torn escarp

[sacred junco]

then a log5(g) = log5(8)

[leaden swan]

Actually that works

[sacred junco]

and by log i mean discrete log

since 5 generates everything they should be valid

[leaden swan]

Remember the multiplication will be in mod (p-1)=22

[sacred junco]

isn't that for rsa

[leaden swan]

We are using a^(p-1)=1 mod p

So it applies for both RSA and DH

Actually it need not be (p-1)

[sacred junco]

i dont think DH needs fermat's little theorem for correctness

i think i get what you're trying to write

bruh

[leaden swan]

Ok,so you just divide both sides and get to 5^a=1 mod 23 form

[sacred junco]

bruh

[leaden swan]

TL;DR: I am bad at latex. You get 5^(LHS here)=5^(RHS here) actually. Now you reduce that to 5^x=1 form

[sacred junco]

not sure why you're solving that

but thanks

[leaden swan]

Well you want a, don't you

[sacred junco]

i mean once you take log wrt to 5 it's linear

[leaden swan]

so you have $a \log_{5}{g}= \log_{5}{8} \mod 22$

[sterile pumice]

Drink Drake

[leaden swan]

Yea just divide to get your a is what I meant

[sacred junco]

why mod 22

[leaden swan]

5^x=1 form remember

[sacred junco]

isn't it mod 23

[leaden swan]

The minimum x which satisfies this is 22(Because 5 is primitive modulo)

And if 5^y=1 mod 23 and y is not a multiple of 22 , 5^(y%22) will also be 1 mod 23 but y%22 is smaller than 22

[sacred junco]

i didnt know the modulus changes when you take discrete log

[leaden swan]

Well,It gets annoying

[fringe tundra]

does anyone do statistics here

[leaden swan]

If 5 wasn't a primitive modulo,you have to search for what x satisfies this

[sacred junco]

have.i been doing it wrong all this time

[leaden swan]

Which is why this procedure is important

[halcyon blaze]

#probability-statistics

[fringe tundra]

oh ok

[sacred junco]

i dont think we dealt with anything like that

we only take discrete log with base to primitive roots in this class for now

[leaden swan]

Yea, That's why

It's annoying without that assumption

[sacred junco]

also how for part 3

how do I exponentiate 570 without making a mess

cause decrypting means I calculate 570^j mod(N)

[leaden swan]

You are not allowed a calculator?

[sacred junco]

I am but

[leaden swan]

I usually do this with python

[sacred junco]

pretty insane

i guess it's doable

[sacred junco]

good idea

it's good i took a cs 1 course along side this one

[leaden swan]

It's pretty insane how you have survived a crypto class this long without python

[sacred junco]

it's a number theory class. We have applications to crypto

altho there is a crypto class in cs

[fringe tundra]

do you guys study cards or thats on statistics

and dice

[leaden swan]

#probability-statistics

[sacred junco]

@leaden swan slight issue with this problem

so if g=9 then then the second message implies 9^3 = 16 mod 23

[leaden swan]

That's g^b yes

[sacred junco]

3 log5 (9) = log5 (16)

my index table says 3*10 = 8

in mod 23, 30 is 7

[leaden swan]

Take wrt 22

[sacred junco]

it works in mod 22 funny enough

[leaden swan]

.

[sacred junco]

nice

[leaden swan]

x satisfies 5^x=1 mod 23 implies x=0 mod 22 since primitive modulo is the most important part

[sacred junco]

yeh the order's maxed out

[leaden swan]

Ok,now try solving 13^x=1 mod 23

Find a constraint on x

[sacred junco]

x log5 13 = log5 1 mod 22?

[leaden swan]

No

[sacred junco]

bruh

mod 23?

[leaden swan]

It's a problem to ponder over

[sacred junco]

why didnt log work

[leaden swan]

Log is fine,mod is not

Hint lagrange

Think what za=1 tells you about z and ord(a) where z is an integer and a is an element of a group

[sacred junco]

we dont use groups

anyways im confused about when i use mod 23 vs mod 22

[leaden swan]

You have a Lagrange theorem right?

[sacred junco]

yeh

[leaden swan]

That Lagrange is a special case of Lagrange for groups

[sacred junco]

if you mean a polynomial mod p has degree n or less roots

that's the lagrange theorem i know

so if 9^a = 8 mod 23 does that imply a log5 (9) = log5 (8) mod 22?

[leaden swan]

9 is not a primitive modulo so no

Here's how we got that 22

[sacred junco]

but 5 is

[leaden swan]

So you know 5^22 has to be 1 mod 23 by fermat's little theorem

Now you need to find the minimum x such that 5^x =1 mod 23

By Lagrange theorem,you deduce x divides 22

And since 5 is a primitive modulo you can say the min x has to be 22,otherwise you will miss elements in the group generated by 5

[leaden swan]

After this step, the minimum x such that a^x=1 mod 23 varies depending on a

Cryptography is closely related to group theory in some places

[leaden swan]

This (p-1) logic applies for all primitive moduloz

[sacred junco]

we don't call it lagrange but we proved it in class

[leaden swan]

Ok, That's a really important theorem

[sacred junco]

so I just wanna know if this is mod 23 or mod 22 or if neither is deducible

[leaden swan]

Neither is correct

You check for mod11 mod2 and mod 22

Because those are factors of 22

[sacred junco]

cause I know discrete log has logarithm like properties

why cant we use them

[leaden swan]

Oh you are converting this to a 5^x form

So this works

[sacred junco]

bruh so is it mod23 or mod22 if when it works

[leaden swan]

5^(RHS)=5^(LHS) if you don't want to skip checks

22

[sacred junco]

k

[leaden swan]

nvm,if you can just convert to 5^x=5^y mod 23 form it's always 22

[sacred junco]

so i got a is congruent to 5 mod 11

so what's the secret key

if a has multiple values

[leaden swan]

An element of {11k+5| k in Z}

Apart from that it shouldn't matter, because any a you pick from that set will give you the same equations

And the same secret

When we say Alice's secret,we really mean an integer which could satisfy all the equations

[sacred junco]

well i have to calculate 570^31 mod 1537

btw 1537=29*53

and 570=19 x 3 x 2 x 5

stonks

meant to do 570 not 5 woopsy

[leaden swan]

You know you could have done pow(570,31,1537)

[sacred junco]

what's pow

[leaden swan]

pow(a,b,n) will return a^b mod n

Inbuilt function

[sacred junco]

Also i wanna show some work

[sacred junco]

i feel like my computer's gunna go nuclear

dpeneding on how it computes

[leaden swan]

It doesn't

If your computer was made after 2010 it should work

[sacred junco]

yeah they prolly do it recursively then

[leaden swan]

Pow(a,b,n) probably uses some crazy stuff behind the scenes

[sacred junco]

that function sounds like it pounds ppl's moms

[leaden swan]

Ok, It's just square and add apparently

[sacred junco]

pretty complex

i bet i can write a pow function

[leaden swan]

People who write standard libraries are pretty smart

[leaden swan]

Do it such that a^n takes O(lg n) steps

[sacred junco]

dammit i was thinking n steps

[leaden swan]

n really starts sucking when you get to big n

[sacred junco]

btw how does this scheme work

some of the decoded numbers might be above 39

[leaden swan]

I guess you won't get any numbers above 39 because the question is designed that way

[sacred junco]

rip 833 decrypted is 170

[leaden swan]

I guess it will be seen as 17 00?

[sacred junco]

hmm

let's see if it says anything meaningful

[leaden swan]

Tell me if you are interested in this

If you do 01,70 has no counterpart

[sacred junco]

yeh

next one's 415

[leaden swan]

Why are you refusing to do this?

[sacred junco]

nice

so do i split it such that it has to make sense

[leaden swan]

I don't think that works,this is a weird problem

[sacred junco]

it's from david burton's book apparently

[vernal ibex]

Hmmm I SEe.

[shell minnow]

senku made a typo?

[vernal ibex]

No.

Even capitalisations.

[sacred junco]

Can anyone clarify this question for me? Currently it seems like nonsense.

Show that if n = product(i=1,k, n_i) where n_1,n_2,...n_k are mutually coprime integers, and R_i is a complete set of residues (mod n_i) for each i, then the integers r = r_1 + r_2*n_1 + r_3*n_1*n_2 + ... + r_k*n_1*n_2*...*n_k-1 (r_i in R_i) form a complete set of residues (mod n).

I think this will only produce k candidates for the set of residues, but that k < n for most cases.

[leaden swan]

So consider the set A made up of integers of form r

You have to show A=Z/nZ

@sacred junco

r_i will lie between 0 and n_i

[sacred junco]

But won't the size of A only be k?

[leaden swan]

No size of A will be |n_1| |n_2|...|n_k|

Each r_k can be 0,1,2... Or n_k-1

[sacred junco]

There are k, R_i, right?

[leaden swan]

As an example of what they mean,take 6=2*3

[sacred junco]

So then n_1 = 2 and n_2 = 3

And R_1 = {0,1} and R_2 = {0,1,2}

[leaden swan]

A will be {0+0(2),1+0(2),0+1(2),1+1(2),0+2(2),1+2(2)}

[sacred junco]

So r_1 always comes from R_1 and r_2 always comes from R_2

I see.

[leaden swan]

Yea

[sacred junco]

And for A we include each combination of r_1 and r_2.

Okay yes, thank you for clarifying.

[wise oyster]

do we have an explicit formula for a square root of -1 mod p when p=1 mod 4?

[sterile pumice]

Spoonman Cultist

\begin{Theorem} a^{p-1} = 1 (mod $ $p) $ for a not divisible by p and  p, a prime.$ \end{Theorem}
```Compilation error:```! Missing $ inserted.
<inserted text> 
                $
l.55 \begin{Theorem} a^
                       {p-1} = 1 (mod $ $p) $ for a not divisible by p and  ...
I've inserted a begin-math/end-math symbol since I think
you left one out. Proceed, with fingers crossed.

LaTeX Font Info:    Calculating math sizes for size <14> on input line 55.
LaTeX Font Info:    Trying to load font information for U+msa on input line 55.```

[leaden swan]

Tonelli Shanks might be the key

Like it might be reduce to a formula for that case

[wise oyster]

i knew tonelli once lol

it's such a shitshow alg i cant be bothered to look into it again but thanks

[inner anchor]

letting p = 4n+1 i think we had sqrt(-1) = (2n)! mod p

proof is just wilson

[wise oyster]

omg youre right

how could i forget wilson

[inner anchor]

yee

[wise oyster]

danke

[inner anchor]

np

[wise oyster]

this doesnt work i dont think. If it does at least proof cant just follow straight from wilson

[inner anchor]

uhh lemme check

[wise oyster]

yeah take 8!

for p=17

it doesnt work

[inner anchor]

wolfram tells me that that is 16 mod 17

[wise oyster]

idk i did (8!+1)/17 in desmos and got a decimal

[inner anchor]

(8!)^2 + 1 :D

[wise oyster]

oop idiot

yeah that works

i still dont see how the proof follows from wilson though

[inner anchor]

but for an actual proof you can just do this

[\left(\frac{p-1}{2} !\right)^2 = (1)\cdot(2)\cdot \ldots \cdot (p-1) \cdot (1)\cdot(2)\cdot \ldots \cdot \left(\frac{p-1}{2}\right)

man

[= (1)\cdot(2)\cdot \ldots \left(\frac{p-1}{2}\right) \cdot \cdot \left(p-\frac{p-1}{2}\right) \ldots (p-2) \cdot (p-1) \cdot (-1)^{\frac{p-1}{2}} = (p-1)!]

im too lazy to type this out correctly

[sterile pumice]

Pappa

[inner anchor]

can you make anything out of this

[wise oyster]

this is wilson's theorem i know the proof of that yeah

[inner anchor]

ok lemme just dig up the actual thing

[wise oyster]

but when you square things im a little confused

oh wait

nvm

i see it

[inner anchor]

here its written clearly

[wise oyster]

yeah i see what youre doing thanks

thanks a bunch

[sacred junco]

so 170415112499131422, if you think of it as blocks of 2, 17 04 15 11 24 99 13 14 22 translates to REPLY NOW

[leaden swan]

That still seems dumb and arbitrary

[sacred junco]

The message sounds like one sent by a controlling girlfriend

[ornate scarab]

Given positive integers $a, b, c$ that satisfy $c(ac+1)^2=(5c+2b)(2c+b)$. Prove that $c$ is a square of an odd integer.

[sterile pumice]

AeroBennu

[wooden glen]

What have you done so far?

[ornate scarab]

nothing, i have covid 😦

[hollow zenith]

3head question inbound

why do we say residue

rather than remainder

[hollow zenith]

For this to be true

I need that p does not divide a or b right?

[torn escarp]

nope

[hollow zenith]

I don't?

[torn escarp]

what breaks?

[hollow zenith]

I thought (ab / p) = (a / p) (b / p) only works if p doesn't divide a or b

[torn escarp]

don't look at those

look at x^2=ab mod p

if a=0 or b=0 you have x^2=0 mod p, are you saying you can't solve this?

[hollow zenith]

oh

💀

[torn escarp]

[ionic pier]

You don’t need to look at those, it is stated that a and b are quadratic non-residues, they cannot be zero, and then it’s properties of the Legendre symbol:

$\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\cdot \left(\frac{b}{p}\right) = (-1).(-1) = 1$

[sterile pumice]

DVD_Koce_DVD

[ionic pier]

Therefore the congruence in question has a solution. But if you are not allowed to use Legendre’s symbol you could just prove the property above and still use it.

While we’re still on the topic of quadratic residues and non-residues @wooden glen can you check out that problem:
Find all natural numbers n, that are coprime with all of their quadratic non-residues.

[wooden glen]

No. Please don't ping random people for help.

[ionic pier]

No, it’s not for help, I’ve just seen you solving problems here before and thought you might be interested

[fiery zenith]

Let $\lambda\not\equiv0\pmod p$.\\
By Fermat's Little Theorem,
$$\lambda^{p-1}\equiv1\pmod p$$
Then for $k\in\bN$,
\begin{align*}\lambda^{p^k}&\equiv\lambda^{p^k-1}\lambda\pmod p\\
&\equiv\lambda^{(p-1)\left(\sum^{k-1}_{i=0} p^i\right)}\lambda\pmod p\\
&\equiv1^{\left(\sum^{k-1}_{i=0} p^i\right)}\lambda\pmod p\\
&\equiv\lambda\pmod p
\end{align*}

[fiery zenith]

Does this look fine?

[wooden glen]

It would be smoother to say that p == 1 (mod p-1), and therefore p^k == 1 (mod p-1). Then you don't need the summation in the exponent.

[fiery zenith]

ah nice. ty

[wooden glen]

Alternatively you can write lambda^(p^k) as (...(lambda^p)^p...)^p and see that it collapses into Fermat's little theorem applied repeatedly.

[fiery zenith]

ah

[hollow ravine]

σ(n) is the sum of all divisors of n

σ(6) = 1 + 2 + 3 + 6 = 12

a positive integer n is "solitary" if σ(n)/n does not match σ(m)/m where m is some other positive integer

My question is...

It is supposedly "easy" to prove that if σ(n) and n are relatively prime, then n must be solitary

How do you prove this?

[hollow ravine]

http://ijmcs.future-in-tech.net/10.2/R-Jones-Ryan.pdf

lemma 1.1

[hollow ravine]

found the proof myself

[atomic fractal]

can there exist two pairs of prime numbers such as : P^a * Q^b = R^c * S^d?

Basically I have some two primes raised to any degree, can i find some other two primes raised by any degree so equality holds?

[leaden swan]

No

See fundamental theorem of arithmetic

[atomic fractal]

prime factorization is unique and only one?

[leaden swan]

Yea

Plus here's a way you can see it's false

R can't divide P^a Q^b unless it's P or Q

[atomic fractal]

thank you.

[sacred junco]

<@&286206848099549185> i'm wondering how do i start with problem 4

[cosmic bronze]

can someone help me find the missing side

[north pagoda]

this is not number theory.

[north pagoda]

dont ping helpers early

but here's a start

suppose some $a$ ($a < n$ with $a$ coprime to $n$) is not a fermat witness. show that $a \cdot a_0$ is.

[sterile pumice]

Namington

[north pagoda]

do you see why this is sufficient to prove the problem?

(be careful, the product might exceed n - why isnt this an issue/how do we fix this?)

[hollow zenith]

stuck on this

[torn escarp]

there's a nice formula you can derive, $$\prod_{d|n} d = n^{\tau(n)/2}$$ which we can use to now say $\tau(n)=4$, so all numbers with 4 divisors are multiplicatively perfect.

[sterile pumice]

Merosity

[leaden swan]

I was thinking of a counting argument,tbh

What is \tau(n) again

[torn escarp]

number of divisors of n

$$\tau(n) = \sum_{d|n} 1$$
then multiply by $\log(n)$ on both sides
$$\tau(n)\log(n) = \sum_{d|n} \log(n) = \sum_{d|n} \log(d*\frac{n}{d})$$ $$= \sum_{d|n} \log(d) + \log(n/d) = 2 \sum_{d|n} \log(d)$$

[sterile pumice]

Merosity

[torn escarp]

now we have $$\frac{\tau(n)}{2} \log n = \sum_{d|n} \log d$$ then just pull out the logs and there you go

[sterile pumice]

Merosity

[hollow zenith]

Ah I forgot about that formula

that is nice

tho funnily enough my textbook calls that $\nu$ instead of $\tau$ lol

[sterile pumice]

Spamakin🎷

[hollow zenith]

idk why

[torn escarp]

first time I saw this was just playing around with dirichlet convolutions, in particular what I found was completely additive functions give you a kind of product rule when multiplied by a dirichlet convolution, like so: $$A(n) *(f \star g)(n) = (Af \star g)(n) + (f \star Ag)(n)$$

[sterile pumice]

Merosity

[torn escarp]

in our case $A=\log$, $f=g=u$ so that $u\star u=\tau$ and $\log (n) (u \star u) (n) = \log(n)\tau(n)$ = $2 (u \star \log)(n) = \log(n) \tau(n)$

[sterile pumice]

Merosity

[torn escarp]

that's sort of terse but feel free to ask if you're interested in trying to fill in the gaps

[hollow zenith]

haven't learned about dirichlet convolutions yet but I'm supposed to midterm on monday so I'll probably come back to this later lol

[torn escarp]

yeah dirichlet convolutions are cool, definitely connect a lot of stuff together

@vernal harness witness

[torn escarp]

good luck have fun lol

[hollow zenith]

I haven't been to class in a while so I'm doing a HW I skipped and I'm rereading the text 💀

[sacred junco]

dont think so

@north pagoda if it's proving that a.a0 is a fermat witness idk how to

[sacred junco]

oh wait i read your instructions wrong

so if a is not a fermat witness a^n-1 is congruent to 1

so (a.a0)^n-1 is congruent to a^n-1.a0^n-1 is congruent to a0^n-1 is congruent to not 1 so a.a0 is a fermat witness

we have an issue though cause if a.a0 is congruent to a0 that implies a is congruent to 1

im not sure i get it though. Are you trying to continuously take products of fermat witnesses and a non fermat witnesses to generate a distinct fermat witness and eventually the whole set or smthing

[hollow zenith]

is there any intuition behind the Mobius inversion formula?

like yes I've read the proof of it but idk it just feels kind of like something pulled out of thin air

[sacred junco]

<@&286206848099549185> can i get some help

it's 2^d - 1 btw not 2^(d-1) that's a typo

[dusty dragon]

If d | n, then n = dk for some integer k. You then have 2^n - 1 = 2^{dk} - 1 = (2^d)^k - 1 = (2^d - 1)((2^d)^{k - 1} + … + 1)

[sacred junco]

yeah got it

but how do i do 2)

maybe star by writing 2^n-2 as 2^l.m where m is odd

which is 2(2^n-1 - 1) since 1 less than a power of 2 is odd

what a should i pick for the rabin miller test ? <@&286206848099549185>

[sacred junco]

<@&286206848099549185>

[sacred junco]

It has been long since I last saw Mobius Inversion so I might be not very clear here but one motivation that I am aware of is when you try proving things about phi(n), more specifically phi(n) = n * Product(1 - 1/p), you see a connection between phi(n) and the sum of mobius function(s) (iirc, the proof is by inclusion exclusion where this connection is linked) which is quite surprising. This does serve as a fair motivation to look if instead of phi(n), we can extend it to multiplicative functions. Mobius function has a tendency to show up in very unexpected places as well.

I am guessing this book is from Burton ? If so, then he doesn't build a complete background before defining any of the arithmetic functions (or anything) in general. It is kind of expected that he will pull things from thin air to exist without serving much motivation.

[hollow zenith]

nah this is from Strayer

[sacred junco]

well it doesn't build up anything relevant prior to it too

[hollow zenith]

Yea

It is useful

Proved some cool identities with it

But the intuition behind it is pretty much non-existent for me

[sacred junco]

Mobius function is basically some kind of 'inverse' element I guess is a nice intuition

I suppose it was the purpose of defining it?

[hollow zenith]

But why is that the inverse. Why does this specific function that only gives a value for square free numbers the function that allows me to "move" a summation from one side to another and use the divisors.

Maybe I'm looking for too much intuition with this inherently weird thing

[sacred junco]

I dont really know what reason you need besides thats how numbers behave lol its just its property imo

[torn escarp]

the square free aspect sorta comes out of the fact that you are looking at doing inclusion-exclusion where you have the prime and don't have that prime counted

[hollow zenith]

Yea

[torn escarp]

somewhat related but maybe not directly enough but, are you familiar with what a dirichlet series is?

[hollow zenith]

Not really

Not familiar with analysis in general lol

[torn escarp]

the dirichlet convolution corresponds to the generating functions: $D(f;s)=\zeta(s)D(g;s)$ so inverting this gets you $\frac{1}{\zeta(s)}*D(f;s)=D(g;s)$, so if you take the euler factorization of the zeta function, $$\frac{1}{\zeta(s)} = \prod_p \left(1-\frac{1}{p^s}\right) = \sum_{n \ge 1} \frac{\mu(n)}{n^s}$$

[sterile pumice]

Merosity

[hollow zenith]

Oh that's interesting

I'm familiar with the zeta function so I get that part and the rewriting

[torn escarp]

it at least pops out at you naturally here cause you're only ever multiplying one of each prime with a (-1) on it, which gets you that form which maybe makes it seem a little less mysterious

[sacred junco]

It's actually (surprisingly) not that hard to prove, even without the middle equality, if you know that mobius * identity gives a function 1(n) =1 for n=1 and 1(n) =0 for n>1 and noticing that when you multiply say (a1/1^s + a2/2^s + ...) (b1/1^s + b2/2^s + ...) you get general term in the numerator an * bn/n^s where * is dirichlet convolution.

Although for me dirichlet convolution seems kinda 'artificial' I guess, this is probably one of the best examples for intution behind mobius

[hollow zenith]

which Gauss's identity are they talking about

[torn escarp]

the one they put right there id = phi * 1

that's another way of saying $n=\sum_{d|n} \varphi(d)$

[sterile pumice]

Merosity

[hollow zenith]

ah

so it is

[torn escarp]

it's called gauss's identity because he used it to prove that (F_q)^x is a cyclic group

for q=p^k

[hollow zenith]

ahhh ok

[torn escarp]

I don't know if that's completely historically accurate tbh, but maybe he just did F_p^x I don't know to what extent he knew about fields

for what it's worth, in general the elements of a multiplicative group of finite order of any field is a cyclic group

[coral trail]

help

i know this is true

but i dont know how to show that

[leaden swan]

Why do you know it's true

[coral trail]

the exercise says that xD

[leaden swan]

What if the exercise is lying

[coral trail]

😳

[leaden swan]

It's a what if

Anyway it's just
$(m+1)^2-2(m+1)+2 = m^2+1$

[sterile pumice]

BYE BYE!

[proven rune]

Will the generating function method on solving recurrence relation find wrong solution when the generating function is divergent except for x=0?

[torn escarp]

it will work because it's just a formal series, whether it converges or not doesn't matter

all that matters is operations like multiplying series combines the terms of a series appropriately as a convolution, stuff like that

[proven rune]

I'm still quite confused by the notion of formal series. Can we really equate things that are divergent? Is it just a leap of faith in the hope that a proper solution will appear after applying this trick?

[torn escarp]

there's no leap of faith, seeing whether a series converges or not is actually extra structure put on top of a series

you can think of the ring of formal power series as simply sequences with rules for manipulating them around

although this example might not make sense, it shows that convergence is extra, the series $\sum_{n=0}^\infty n!x^n$ actually converges on a nonzero radius of convergence in the p-adic metric

[sterile pumice]

Merosity

[proven rune]

Thanks, I feel that I'm starting to grasp the idea 😆.

[coral trail]

how do i prove this?

[stiff rivet]

hint: you can consider 3 cases

[coral trail]

n = 3k
n = 3k + 1
n = 3k + 2 (?)

[stiff rivet]

try those

[coral trail]

seems to be always divisible by 3

by that logic

makes sense to me, hope it's correct

[viscid wave]

Very late but I found that n(2n^2+7) congruent to n(2n^2-2) mod 3 which becomes 2n(n-1)(n+1)

[coral trail]

how do i prove that 7 is the only prime of the form n^3 - 1

[coral trail]

n^3 - 1 = (n - 1)(n^2 + n + 1) so (n-1) must be one -> n = 2 (?)

[viscid wave]

Pretty much

Technically you may have to consider each factor being either 1 or -1 but

It’s obvious enough in this case

[vernal delta]

Hey guyes
I am stuck with this question
How to get the value of 'm' such that
(n/m) ^m is maximum? (both m and n are natural numbers)

[torn escarp]

I'd probably use regular calculus to find the max of (n/x)^x and then round to the nearest integer

it turns out that gives a surprisingly clean answer, $x=\frac{n}{e}$ but whether we should pick $m=\lfloor x \rfloor$ or $m=\lceil x \rceil$ technically still needs to be determined although probably usually $m=round(x)$ works most of the time

[sterile pumice]

Merosity

[pine badge]

That's interesting, I was thinking about the m that gives the max. cool it involves e

[coral trail]

how do I find an example of an x (if x exists)

[coral trail]

x is prime

[shell minnow]

First write out the definition of mod in this case

[coral trail]

x - 6 = 12*q

x = 12q + 6 = 2 (6q + 3) -> x is even and /= 2 so x cant be prime (?)

[shell minnow]

Yep that’s what I think

[plain oar]

ez question

redy??

e

x+6= 12 x=n

n=6

e

e

e

[shell minnow]

Please dont spam/troll

[vernal harness]

$\forall a, b \in \mathbb{Z}-{0} ( \exists n, m \in \mathbb{Z} ( a \neq b \implies na + mb = 1 ))$

[sterile pumice]

ryаn

[vernal harness]

I feel this is true

So surely there is some d, where a mod d = 1

Then, a - qd = 1

If, q = b, then we can let m = d?

Hmm, lets test this

Let a = 7, b = 13

7 mod 6 = 1

So like, 7 = q*6 + 1

Then 7 - q*6 = 1

If q = 13, then m = 6?

Ugh somethings off

What about p mod a = 1

Ok, so p = qa + 1

p - qa = 1

Let p = bm

So given some a, b, we say bm mod a = 1

Feels like I proved nothing

Ok so: (13*6) mod 7

Oh shoot theres a hole

$\forall a, b \in \mathbb{Z}-{0} ( \exists n, m \in \mathbb{Z} ( a \mod b \neq 0 \implies na + mb = 1 ))$

Ok lets try this again

[sterile pumice]

ryаn

[vernal harness]

The last statement is the same as: (mb) mod a = 1
Since (mb) mod a = 1 -> mb = na + 1 -> mb - na = 1
Now how to find this 'm'

Given a,b, where n is not a multiple of b, find n where (na) mod b = 1

fuk

Let I be the ideal that contains a,b, since any ideal of integers is principal, it must contain a generating element. Its generating element is gcd(a,b) which must be 1.

wait messed up

well fuck

$\forall a, b \in \mathbb{Z}-{0} ( \exists n, m \in \mathbb{Z} ( gcd(a,b) = 1 \implies na + mb = 1 ))$

changing the problem so my solution is right

[sterile pumice]

ryаn

[vernal harness]

na + mb = 1 <=> (na) mod b = 1

well fk whatever

[vernal harness]

Ohh this is bezout's identity

and it's iff... well no wonder why it "felt" true

time to find a nice proof

[unkempt hedge]

let p, q be primes with p>=5, q>=5. Prove that 24|(p^2 - q^2)

Is this proof correct?

By division theorem
p = 12x + r, 0<=r<12
q = 12y + s, 0<=s<12

p^2 - q^2 = (12x + r)^2 - (12y+s)^2 = 24(6x^2 + rx - 6y^2 + sy) + (r^2 - s^2)

Then r^2 - s^2 also has to be divisible by 24 for 24|(p^2 - q^2) to be true.
without loss of generality we have that let r >= s (because sign doesn't matter)

we have that 0<=r<12 and 0<=s<12 but r and s cannot be of the form 2n or 3n for any integer n, because then p or q will be composite. We also have the obvious cases when r = s which makes it so that 24|(r^2 - s^2)=0. For that reason we only have these cases
r=11 and s=7 -> (r^2 - s^2) = 24 * 3
r=11 and s=5 -> (r^2 - s^2) = 24 * 6
r=11 and s=1 -> (r^2 - s^2) = 24 * 5
r=7 and s=5 -> (r^2 - s^2) = 24 * 3
r=7 and s=1 -> (r^2 - s^2) = 24 * 2
r=5 and s=1 -> (r^2 - s^2) = 24

And we have that 24|(p^2 - q^2)

Is there a better way of doing this?

[leaden swan]

@unkempt hedge p is either 4k+1 or 4k-1 and q is 4r+1 or 4r-1 taking all cases gives you (p+q)(p-q) is divisible by 8

p is 3k+1 or 3k-1 similarly q is 3l+1 or 3l-1 ,which implies either p+q is divisible by 3 or p-q is divisible by 3

Combining everything gives you 24 | (p+q)(p-q)

[torn escarp]

we can argue more generally, all odd numbers square to 1 mod 8. Similarly all numbers not divisible by 3 also square to 1. So really this works for all p, q not divisible by 2 or 3 not just primes

[grand isle]

anyone know how to do this? i forgot all about measuring unknown lenghts after i learned photosynthesis in science

[leaden swan]

#geometry-and-trigonometry
@grand isle

[unkempt hedge]

@leaden swan Nice trick to show that 24 | (p+q)(p-q)

how do you go from 8 | (p+q)(p-q) and 3 | (p+q)(p-q) to 24 | (p+q)(p-q)
we have that
(p+q)(p-q) = 8r and (p+q)(p-q) = 3s for some integer r and s
((p+q)(p-q))^2 = 24rs
-> 24 | ((p+q)(p-q))^2

a|c and b|c -> ab|c is not true in general
counter example: a=6, b=2 and c=6

[leaden swan]

If a and b are coprime it's true

3| p^2-q^2 and 8| p^2-q^2 so
(p^2-q^2)=3(k) and is divisible by 8

Now 8 divides 3k which means it has to divide k

Giving us k=8l

If it were say (p^2-q^2)=2k then 8 need not divide k

[unkempt hedge]

I see, (p^2-q^2)=3(k)=8(t) for some k and t
since gcd(3, 8) = 1 we have that 8 | k

which is also why you didn't choose to show 4 | (p+q)(p-q) and 6 | (p+q)(p-q)

because 4 and 6 are not coprime

in general if p_i is prime, you could show that
t | n
t = p_1^(r_1) * p_2^(r_2) * p_3^(r_3) * ... * p_k^(r_k)
by FTA
p_1^(r_1) * p_2^(r_2) * p_3^(r_3) * ... * p_k^(r_k) | n
you could first show that
p_1^(r_1) | n
p_2^(r_2) | n
p_3^(r_3) | n
...
p_k^(r_k) | n

and then combine them later

Not that this always would work though

[leaden swan]

Yea only when coprime

[gritty comet]

I had to prove eulers phi(n)>2 for all n>6 and I ended up with a third of a page of looking at cases when n is even and odd etc. I was wondering if there was a simpler way to do this that I missed.

[wooden crater]

use the product formula for eulers totient function.

[gritty comet]

Wouldn't there still be a need to consider a few cases? Like if any prime factor is either greater than 3 or appears more than once we have something greater than 2. But then you still need ohhhhh then you're left with just numbers less than or equal to 6

[gritty comet]

Thank you very much lmao

[wooden crater]

lol yw

[molten lava]

can someone helkp me

[civic forge]

add them up see which ones are less than 50 and then do something

i got || 2/10 || ||1/5|| ||0.2||

[sacred junco]

"Let $p$ be a prime and let $d \in \mathbb{Z}$ with $0<d<p$. As already stated at the beginning of this section, we would like to find necessary conditions for representability of $p$ as $x^2 + dy^2$. We see immediately that $-d$ should be a square mod $p$, so assume that this is the case." Why does $-d$ have to be a square mod p?

[sterile pumice]

catfan1337

[stiff rivet]

if $x^2 + dy^2 = p$, then $x^2 \equiv -dy^2 \pmod{p}$

[sterile pumice]

Lochverstärker

[sacred junco]

ok ye

ty

[stiff rivet]

thats enough?

i was gonna say more

[sacred junco]

if left sides a square then also right

[stiff rivet]

ye and in finite fields the product of nonsquare and a square is a nonsquare

[sacred junco]

ye ye

[stiff rivet]

👍

[livid raven]

From the definition of discrete log I know is, that working in Zp, given (g,g^x) it is hard to extract x.

Now I am confused. The EDL over Fp is equivalent to normal DL over Fp^B.

but p^B is not a prime. Is the discrete log also hard for some extension fields?

Is this very theorem also the why DH-key-exchange, RSA key sizes are larger than the elliptic curve analogoues for the same security level?

[ionic pier]

Does the “E” in “EDL” stand for elliptic?

[ionic pier]

Yeah, I think it is. I haven’t researched the topic, but think about it finding that p is a prime AND a divisor of p^B should be even harder, cause p^B only has powers of p as divisors. Which kind of implies you already know p is a prime (the standard discrete log problem). Also when you’re looking at dlog_k(p^B) (mod n), that’s the same as B*dlog_k(p) (mod n) isn’t it? (Not sure, asking)

[ornate scarab]

Let $a,b,c,d \in \mathbb{R} $. Prove that:
$$\prod (a^2+1) \geq \frac{1}{2} \prod (a+1) (a+b+c+d-2)$$

[sterile pumice]

AeroBennu

[sacred junco]

what is the product over

[inner anchor]

probably a cyclic product

so the lhs would be (a^2+1)(b^2+1)(c^2+1)(d^2+1)

[harsh ginkgo]

why?

[inner anchor]

Note that there are the same number of quadratic residues as nonresidues (and every is a residue or a nonresidue) so it suffices to show that -s^2 is always a nonresidue if -1 is a nonresidue, which follows from eulers criterion

Or just the fact that the product of a residue and a nonresidue is a nonresidue

[harsh ginkgo]

how do i use the fact about the number of nonresidues to show that there is an s for every nonresidue?

[inner anchor]

Consider the map $x \to -x$ from the set of quadratic residues to the integers mod p

[sterile pumice]

Pappa

[inner anchor]

This map is clearly injective, and note then that as -x is always a nonresidue, then the map takes p-1/2 distinct values, and then is surjective onto the set of nonresidues as well, from which the statement follows

[fierce flame]

quick question, I need to prove i^2 = (m-i)^2 mod m for m > 2, is this an induction proof? I can work out the math and show that it's just outright true, but then what about for negative m values?

[wooden crater]

m > 2 doesn’t mean anything?

[fierce flame]

yea i know that, which is why this questio nis confusing me

[sacred junco]

what's confusing you

if you assume m>2 then you dont need to look at negative m

[dark anvil]

help me please

[unkempt hedge]

Is there a fast way of solving this? Feels tedious if I had to do this manually by brute force.

[unkempt hedge]

go to #geometry-and-trigonometry

[stiff rivet]

you can solve those by solving the linear diophantine equation 6x - my = 4 for m = 7, 8, 9, 10
bezout tells you when this solvable and solutions can essentially be computed with the euclidean algorithm

(in those small cases its probably faster to just bruteforce)

[hollow zenith]

is this a typo?

alpha / n! = that sum in part b right?

nvm I'm dumb

I forgot how factorials work

[hollow zenith]

Ok I'm dumb but in a different way

how do you do negative continued fractions?

so I found the continued fraction for 30/43

but then -30/43 how

[wooden glen]

A fairly simple answer would be to allow the first coefficient to be negative.

Or just slap a minus sign in front of the whole thing.

Neither of these are particularly pretty, but that's not much different from other notations (e.g. decimal fractions).

[hollow zenith]

I doubt my professor would accept that as an answer

sadly

I was hoping for an easier way since I did already find 30/43

[wooden glen]

Why not? If you have a specification for a negative continued-fraction notation, by all means use that.

[hollow zenith]

he's weird about these things

[wooden glen]

Well, then do it in the way he wants.

But don't expect us to guess which way that is.

[hollow zenith]

yea I guess

[wise badge]

why must b be invertible and the solution must be coprime?

[royal sedge]

does this maybe have a name

[vast crest]

I've never seen a name of this theorem

[sacred junco]

<@&286206848099549185> can i get some hints

does this have something to do with orders

maybe if i prove phi(q)=q-1 then q is prime

[sacred junco]

<@&286206848099549185>

[runic token]

#❓how-to-get-help

[hollow zenith]

this is something about Gauss

of course searching Gauss's theorem doesn't really narrow it down

Also Gauss's Lemma in number theory refers to something else

[torn escarp]

haha fun

[hollow zenith]

yes

very

Wikipedia says the proof is in this

https://www.loc.gov/resource/rbctos.2017gen21572/?sp=38&r=-0.142,0.553,1.524,0.93,0

page idk tho

OH YO

found it

[shell minnow]

why is this in latin

[wooden glen]

That's the language Gauss published in.

[hollow zenith]

It's from Disquisitiones Arithmeticae

[leaden swan]

The "if those conditions satisfy, then q is prime" i straightforward

You have doubts in the only if part right?

For the only if part,prove the contrapositive
"For all a<q a^(p) = 1 mod q or a^2=1 mod q implies q is not prime "

Assume q is prime

Then note for how many elements
a^(q-1)/2 is 1

And note how many residues q has in this case

[sacred junco]

instead of using contrapositive

maybe use the fact that there's a primitive root g in mod q

[leaden swan]

Could. I haven't thought of that approach but this is infinitely more straightforward

[sacred junco]

i didnt understand your approach

[leaden swan]

You understood the contrapositive statement?

[sacred junco]

contrapositives give me a headache when there are too many quantifiers

well the statement we're trying to prove is

If "q is prime" then "there exists a<q such that a^p= -1 modq and a^2!=1 mod q"

[leaden swan]

So if there is no such a<q ,q is not prime

[sacred junco]

oh maybe we can use the fact that square root of 1 is 1 or -1 mod q

[leaden swan]

Which is
"
for all a<q the condition doesn't hold"

[sacred junco]

im confused about whether negating there exists is for all or there doesn't exist

[leaden swan]

Which is
"for all a<q a^p != -1 mod p or a^2 = 1 mod p"

Exists negates to all

[sacred junco]

bruh i never did formal logic

[leaden swan]

All negates to exists

Me too

I just learnt this on the fly

[sacred junco]

my proofs class was all proofs

my friends who took the course with different instructors all started with logic

so my question is when does there exists negate to there doesn't exist

[leaden swan]

$! \exists$ is same as $\forall !$

[sterile pumice]

BYE BYE!

[abstract quail]

$\text{Prove that every natural number other than zero is of the form } n^{+} \text{for some }n\epsilon \mathbb{N}$

[runic token]

para algun?

[abstract quail]

hello guys
could someone help me

[runic token]

what does para algun mean

[sterile pumice]

Aylou-210

[runic token]

what even is this question

that's literally by definition?

[abstract quail]

No entiendo tu pregunta

[runic token]

oh

idk spanish

uhh

no hablo espanol

[abstract quail]

I don't understand your question

[runic token]

sorry

[abstract quail]

noworries

[runic token]

the answer to your question is because that's the definition of what a natural number is

a positive number $n \in \bN$ is by definition a natural number greater than 0

[sterile pumice]

valley

[abstract quail]

the definition must be demonstrated

[abstract quail]

[sacred junco]

@leaden swan for part 2 i just compute phi of phi of q right?

im using primitive roots btw

so phi(phi(q)) = phi(q-1) = phi(2p) = phi(2)(phi(p)= p-1

[sacred junco]

'

<@&286206848099549185> pls help

dont know where to start

[sacred junco]

@leaden swan bruh

[abstract quail]

Is that all?

[runic token]

well, yeah

there's nothing more to be said

[abstract quail]

I'm sorry I didn't answer you
I was talking to my brother earlier
I was watching something
that if you prove it in one
thanks Uwu

❤️

[runic token]

np lol

[abstract quail]

$\text{If m and n are natural numbers such that } m+n=0, \text{prove that }m=0,n=0$

[sterile pumice]

Aylou-210

[runic token]

natural numbers are always either positive or 0

which is all you need

[abstract quail]

so?

[sacred junco]

couldn't you just assume that $m\neq 0$ or $n\neq 0$ and show that $m+n\geq 1$ in both cases

[sterile pumice]

jswatj

[abstract quail]

For contradiction?

[abstract quail]

So what I did was wrong?

[sacred junco]

@glad nacelle u know how to solve this?

[glad nacelle]

Don't ping individuals asking for help

[sacred junco]

sorry if im bothering you but can i get some hints for part 1

[runic token]

is alpha just some number?

[sacred junco]

i think they meant to say if such an ai exists

cause they're doing lucas test and you pick an a for testing

although if a^n-1 is congruent to 1 mod n the gcd of a and n is necessarily 1

well hi divides n-1 is obviously true cause a^n-1 is congruent to 1

i think i read that wrong cause this doesnt involve pi in any way

or wait i think if hi did divide n-1/pi then ai^n-1/pi would be congruent to 1 but it's congruent to -1

@runic token i think i can prove everything myself

i had a hard time understanding what this question was asking lol

[pale fjord]

Let $a,b$ are positive integer such that
i) $a \le \frac{b^2}{4}$
ii) All prime divisors of $a$ less or equal $b$
Prove that $a \mid b!$

[sterile pumice]

erictheeonicpizhao

[stiff timber]

relevant question: https://artofproblemsolving.com/community/c7h2216904p16823221, but with wrong arguments. in the solution, $a = x$ and $b = n$.

[sterile pumice]

vin100

[stiff timber]

take $x = 35$, $q = 5$, $p = 7$, $n = 34$ so that $x = pq$ and $n \le x \le n^2/4$, but $p,q < n/2$.

[sterile pumice]

vin100

[stiff timber]

oups i needa withdraw my comment that the arg is wrong, coz it's trivial when $p,q \le n/2$:

[sterile pumice]

vin100

[stiff timber]

$n! = 1 \cdots q \cdots p \cdots \lfloor n/2 \rfloor \cdots n$

[sterile pumice]

vin100

[wooden crater]

is there a way to compute 3^{47} mod 91 without using left to right or right to left binary method?

CRT doesnt seem to apply here

[vast crest]

Chinese remainder does apply

Sorry I realized you need to use CRT

It makes things much easier

So first notice 91 = 7*13

Then calculate 3^47 modulo 7 and modulo 13 using Fermat's little theorem

Then let x=3^47, then you get that x=a mod 7 and x=b mod 13 for some a and b you obtained using Fermat's little theorem

Then use chinese remainder to find the value modulo 91=7*13

@wooden crater

[wooden crater]

3^{47} mod 7 = 5 and 3^{47} mod 13 = 9

oh wait

i think i just read the statement of CRT wrong

[vast crest]

So let x=3^47, then x=5+7n for some n, so 9 = x = 5+7n (mod 13) implies 7n = 4 (mod 13), so now you can solve for the smallest nonnegative n, and then 5+7n with this n is the smallest nonnegative answer

[atomic fractal]

What are the real time examples where partition problem is applied in real life situations?

[stiff rivet]

partition problem?

[leaden swan]

I am guessing no of ways of partitioning a nonzero natural number

[stiff rivet]

i don't think has any real life applications

[pine badge]

There are cs applications I beleive

[clever niche]

is anyone around to help with a math problem regarding intro to math reasoning?

[celest helm]

Just ask

[clever niche]

lol i have been waiting-

[shell minnow]

you should ask your question in this channel. if you want to go into a VC, state that.

[clever niche]

i just finished getting help in the help area (:

thank you for letting me know tho!

I will keep that in mind for next time (:

[unkempt void]

It falls out of multiplicativity of the Legendre symbol if you know about that

Well you can also consider powers of a primitive root mod p

If you've done that

Well say x is a primitive root mod p

Write 2 = x^k for some 0 < k < p. think about how k relates to 2 being a square mod p

That should get you started

[wise badge]

how many solutions would i have for x^2 = 5mod95? I essentially know that (A)x^2 = 5mod19 and (B)x^2 = 5mod5, and from (B) there is one solution being 0, and from (A) after doing the legendre symbol which gives 1 means that (A) has two solutions. Wouldn't chinese remainder th. imply there is a solution for each pair (x,y) where x,y are solutions which would mean 3 solutions overall?

or maybe i am just thinking about chinese remainder th in the wrong way?

[wooden glen]

How does that make "3 solutions overall"?

I only see two, corresponding to the pairs (9,0) and (10,0) -- that is, 85 and 10.

[wise badge]

oh so (9, 10) wouldn't be a solution since the solution would need to satisfy both (A) and (B)?

[wooden glen]

I'm assuming that when we write (p,q) we mean "the number that is congruent to p modulo 19 and congruent to q modulo 5".

If that case (9, 10) is the same solution as (9,0) because 0 and 10 are the same modulo 5.

But most importantly (9,10) is neither here nor there because you derived that p must be 9 or 10 and q must be 0. There's no particular reason to expect that you can move one of the possibilities for p into the q position, even though it happens to come out right here by pure accident.

Notably, (10, 9) would give x=29, which is not a solution to x² == 5 (mod 95).

[ornate scarab]

Given positive integers $a, b, c$ that satisfy $c(ac+1)^2=(5c+2b)(2c+b)$. Prove that $c$ is a square of an odd integer.

[sterile pumice]

AeroBennu

[dreamy roost]

a b c d e f g h j k l m n o p q r s t u v w x y z YAY I passed elementary

[sacred junco]

nah you missed i

[wooden glen]

25 out of 26 probably still yields a passing grade.

[pale fjord]

is it too easy

[atomic fractal]

I want to express every natural number as a sum of 2 powers 3 = 2^0 + 2^1 or 42 = 2^3 + 2^1 + 2^5. How does the proof would like to check if its possible?

[leaden swan]

Induction

You assume all natural numbers <2^i for some i can be written as sum of powers of 2

and then show that implies for all n < 2^(i+1) n can be written as sum of powers of 2

[atomic fractal]

got it. thank you!

[sick bloom]

How does one find continued fraction expressions for numbers like $\sqrt{2}$, $\pi$, and $e$? what are the methods for this kind of thing?

[sterile pumice]

Mathtard

[wooden glen]

Generally by brute force calculations:
\begin{align*}\pi = {}& 3.14159 \={}& 3 + 0.14159 \={}& 3 + \frac{1}{7.06251} \={}& 3 + \frac{1}{7 + \frac{1}{15.99649}} = \cdots\end{align*}

[sterile pumice]

Troposphere

[sick bloom]

Oh, I see, thanks

so you just brute force it until you see a pattern?

and there generally aren't methods other than that?

so you have to know the value before you find the continued fraction expression

[wooden glen]

Right. In the cases where there are patterns (such as the simple continued fraction for e), I think they were first noticed from brute-force calculations -- and then when a pattern has been conjectured, an ad-hoc proof that it works must be constructed.

There are shortcuts for certain square roots in particular -- though arguably that's just a particularly simple case of a pattern with an ad-hoc proof for the cases it works in.

[sick bloom]

I see. But I'm sure this is all logical and theoretically sound, right?

[wooden glen]

I think generally when you find a pattern asserted (in a respectable source), then the implication is that someone has proved rigorously that this particular pattern works and continues indefinitely.

[sick bloom]

I guess I'm asking how exactly?

[wooden glen]

I expect that depends intimately on how the desired number is defined in the first place. I haven't seen any of the proofs for e.g. e, but I wouldn't expect them to have much in common. In some cases I imagine it will work to find an exact general description for the sequence of intermediate results in the brute-force calculation, but there'll be a lot of ad-hoc cleverness involved in making those descriptions work.

Note that it seems to be the exception rather than the rule that any pattern is known at all.

[sick bloom]

thanks again.

[wise badge]

how do i factorize a polynomial e.g. X^2-1 over Z/8 (modulo 8) for example?

[sacred junco]

Find its roots

It has at most 2 roots because it is the degree

-1 is 7 in Z/8Z

[wise badge]

(x^2-1) = (x+1) (x-1) if i factorise normally

-1 becomes 7?

[sacred junco]

Ye

[wise badge]

so like i would just find the roots normally as i would to with polynomials, and then change the roots modulo 8? Or is there an actual algorithm/technique to work out roots modulo something?

[sacred junco]

Yeah thats the procedure that should work every time

[deft haven]

If a divides bc, does this imply that a divides b or a divides c?

[unkempt void]

Fix a. a has this property for all b and c if and only if a is prime

Euclid's lemma in this case Z (or definition of prime more generally)

[shell minnow]

is there a theorem that states if abc | d then a | d, b | d, and c | d

or if a number divides another number than all factors of the first number also divide the second number

[slim vortex]

"divides" is transitive

a, b, and c all divide abc

[shell minnow]

ah thank you

[wooden glen]

That works only over a field (or over an integral domain). Over Z/8Z, however, it turns out that x^2-1 has four roots, namely 1, 3, 5, 7.

[wooden glen]

It doesn't always work out that nicely. For example, x^2+1 does not factor over Z or even R, but it factors modulo 17 as (x+4)(x+13).

[uncut tangle]

This is my approach
$n | 2n^2 + 3n + 1 - 3n
n | 2n^2 + 1$
But idk how to prove this stuff

[sterile pumice]

Estrower

[uncut tangle]

Would you please help me figure out this stuff

[leaden swan]

Which implies n|(2n)n+1 => n | 1

[wise badge]

Could someone explain me why d being a square modulo 8 implies that implies d = 1mod8 (last part of the proof)?

[stiff rivet]

1^2 = 3^2 = 5^2 = 7^2 = 1 mod 8

[wise badge]

ohh right d is odd by assumption so although 2^2 = 4 mod 8 and 4 would be a square that wouldn't apply here, right?

[wise badge]

i am not understanding what is meant by "we may reduce mod 3 to obtain integer coefficients". Like for example why do we compute 8 inverse in mod 9, but then 16 inverse in mod 3? How does that allow me to get answers mod 81?

[wise badge]

<@&286206848099549185>

[sacred junco]

modulo powers of 3*

[wise badge]

How do i know which power do i need to consider to find the invertible element? Like for example normally -9x^2/8 mod 81, i would need to find (8)^-1 mod 81

But there they only find (8)^-1 mod 9

Why is that?

[stiff rivet]

you need to find -9*8^{-1} mod 81

turns out if you find 8^{-1} mod 9, say 8^{-1} = x mod 9, then -9*x = -9*8^{-1} mod 81

and finding 8^{-1} mod 9 is easy because 8 = -1 mod 9

similarly if you want to find 27*16^{-1} mod 81, it suffices to find 16^{-1} mod 3

and this is again easy

[wise badge]

Why is it enough to find 8^{-1} mod 9?

And then why it suffices to find 16^{-1} mod 3?

[stiff rivet]

because 9*9 = 81 = 27*3

[slender panther]

Does this integral gives 0?

I used cauchy residue theorem

[gilded jacinth]

#real-complex-analysis

[slender panther]

thanks

oh apparently im not allowed ot tlak in that channel 😦

*talk

[torn escarp]

#get-advanced-access

[slender panther]

thanks

[flat plume]

Or 1. Or 0. Or -1.

[shell minnow]

Looks a lot like fermats little theorem, but not sure how much this helps

[supple palm]

it helps greatly lol

[shell minnow]

U right

[sonic dawn]

yes something about a^p-1 is congruent to 1 modulo p and as a corollary a^p is congruent to a modulo p

1601 is pime and 17 is prime

so it's true for all k but idk how to show it without just writing out that corollary

[shell minnow]

Well if it’s a really important corollary then it should be fine just using it

[torn escarp]

yeah just go for it, and say you used fermat's little theorem like this and you're good $$k^{1601} = k^{16*100+1}=(k^{16})^{100} * k^1 = 1^{100}*k = k$$

[sterile pumice]

Merosity

[vale lynx]

well by fermat's little theorem

k^16 == 1 ( mod 17)

=> k^1600 == 1 (mod 17)

=> k^1601 == k (mod 17)

[formal minnow]

the message directly above you said that exact same thing

i have absolutely no clue how you missed that

[sacred junco]

well by fermat's little theorem
k^16 == 1 ( mod 17)
=> k^1600 == 1 (mod 17)
=> k^1601 == k (mod 17)

[unkempt hedge]

Let R be a commutative ring with identity and b E R. Let T be the subring of all
multiples of b. If u is a unit in R and u E T, prove that T = R.

Does this sound reasonable?
Because T is a subring we know that T is a ring and that T is a subset of R

The only thing we need to show that T = R is that R is a subset of T

Let a E R by any

There is an element u such that u*x = 1_R for some x E R

by identity in ring we have that
a = 1_R * a = u * x * a

because u is in T we have that u = r * b for some r E R

u * x * a = r * b * x * a

because the ring is commutative we have that
r * b * x * a = (r * x * a) * b and we have that a E T

because r, x, a E R and R is a ring with multiplicative closure so r * x * a E R

T = R

[stiff rivet]

sure i guess

but do subrings not have to contain the same unit or what

this is just the proof that the ideal generated by a unit is the whole ring

[sand iris]

Is anyone able to explain how i solve these kinds of problems? I dont really see why we start thinking about things in mod 4

[leaden swan]

Because 7^4=1 mod 10 @sand iris

So if you reduce 7^x to 7^(4k+r) that's just 7^r mod 10

[sand iris]

ok thanks

[brave glacier]

Sometimes the corollary is states as the definition of FTP and then it can be divided by a given a not congruent to 0 mod p

So literally answer is "true by ftp" as merodity showed

Unless they want a proof for the theorem

In which case the group theoretic proof is just 😍

[uncut tangle]

What's FTP

[brave glacier]

I'm using it to mean Fermat's little theorem here . idk if normal abbr

[torn escarp]

I've seen flt and FLT to distinguish between little and last theorems, what's the TP stand for? 🤔

[unkempt void]

lol

[idle steeple]

Does anyone know how quadratic residues scale with N?

E.g. on average does 2N have twice as many quadratic residues as N?

[wooden glen]

There can be at most twice as many quadratic residues modulo 2N as modulo N.

Calculating it for small powers of 2 it looks like you don't generally get all of the twice-as-many possibilities, but the fraction of them you get seems to increase towards 100%.

For 2N, it's enough to consider powers of 2, because the number of quadratic residues is a multiplicative function, thanks to the Chinese remainder theorem.

If you're interested in more general growth, then when n is prime there are (n+1)/2 quadratic residues, so you don't get a better general upper bound than that. On the other hand, if n is a product of k distinct primes, these counts multiply, giving only about n/2^k quadratic residues.

[torn escarp]

interesting, I thought this is something I would have worked out before but I don't think I had before now

I found wikipedia a link to a nice closed form to check my work, neat: https://www.maa.org/sites/default/files/Walter_D22068._Stangl.pdf

[idle steeple]

Thanks guys, good stuff, this is useful

(It came up because I'm mucking around with continued fraction factorisation and I think the time complexity may be related to this problem, or maybe not)

[sonic dawn]

My guess is that I have to use this lemma

allowing c = a^b-1 and d = (a')^b-1

but then i'd have to show a^b-1 is congruent to (a')^b-1 (mod n), which is just asking the same question

this is where i'm stuck, maybe this isn't the right lemma to use

[wooden glen]

It looks right. You need induction on b.

[sonic dawn]

Troposphere always saving my life with induction

[wooden glen]

Induction ought to be your standard reaction whenever you think "oh, that is just asking the same question". If you can find a way the new question is a smaller question of the same kind, an appropriate form of induction can probably save the day.

[knotty tiger]

The idea here is just you start with $a \equiv a' \pmod n$ and then on the left side, you repeatedly multiply by $a \pmod n$ while on the right, you repeatedly multiply by $a' \pmod n$. Since $a$ and $a'$ are congruent mod $n$, the two final quantites $a^{b}$ and $(a')^{b}$ are congruent mod $n$ as well

So yea basically induction is the way to go as troposphere said

[sterile pumice]

math man

[sacred junco]

can someone help me prove is p is a prime not congruent to 3 mod 4 then it can be written as a sum of squares

<@&286206848099549185> ples

and pls just elementary arguments. if i see one more shit abt gaussian primes i will flip

[north pagoda]

please dont ping helpers before 15 minutes

anyway, i dont think gaussian primes are that unelementary, but it's possible to avoid them

if p is not congruent to 3 mod 4, then it's either equal to 2, or congruent to 1 mod 4

2 = 1^2 + 1^2 so that case is easy

otherwise p = 4k + 1

try to prove the weaker case below:

• If p is prime and q is coprime to p, and we can find integers a, b such that a² + b² = pq, then we can write p as a sum of two squares

all this relies on is the primality of p

then you might know this lemma:

• If p = 4k + 1, then x² ≡ -1 (mod p) has a solution

[sacred junco]

i know this lemma

[north pagoda]

do you see why these facts combine to give you a solution?

[sacred junco]

but how is it useful

it's about congruence not equation

[sacred junco]

bruh im a college freshman

[north pagoda]

First I strengthen the lemma slightly.

Let's take x to be the principle (smallest positive) solution, i.e. choose x that solves x² ≡ -1 (mod p) so that 0 ≤ x ≤ p-1

I claim first that we can choose our solution to be ≤ p/2.
Suppose x > p/2. Then (p-x)² = p² - 2px + x² ≡ -1 (mod p) as well (since taking modulo p removes the terms with a p factor), so p-x solves the equation as well. In other words, if x wasn't ≤ 2, then p-x, which is ≤ 2, also solves the congruence.

Okay, so the lemma i stated above gives us a solution x to x² ≡ -1 (mod p) so that 0 ≤ x ≤ p/2, and since x² ≡ -1 (mod p), we have:

x² + 1 = np

for some integer n. But since x² + 1 ≤ (p/2)² + 1 = p²/4 + 1 < p², we must have that n < p (does this make sense to you?). And since p is prime, this means n is coprime to p, i.e. n satisfies the "q" in the initial fact about a² + b² = pq I stated (with a = x, b = 1).

and therefore p is the sum of two squares by the first lemma

that argument essentially does all the work for you, the only thing left to prove is this fact:

• If p is prime and q is coprime to p, and we can find integers a, b such that a² + b² = pq, then we can write p as a sum of two squares

do you need hints on how to prove that, or do you want to try it yourself?

[sacred junco]

somehow q is forced to be 1?

im kinda stuck there

[sacred junco]

dont u mean pq

[north pagoda]

(a² + b²)/q is prime. what do you know about the sums of two squares?

the first lemma says that, if pq is a sum of 2 squares (for q coprime to p), then p is as well

[sacred junco]

is a and b forced to be multiples of q

[north pagoda]

not necessarily, no

[sacred junco]

hmm how do u prove this

wait why is a^2 divisible by q if q is prime

[north pagoda]

oops sorry

fixed

i'm assuming a² is divisible by q for that case

in the other case i assume it's not

[sacred junco]

well ik if u take mod q then a^2 is congruent to -b^2

then if q divides one it has to divide the other

and if q doesn't divide a then it doesn't divide b

[north pagoda]

this might be easiest with an example

[sacred junco]

well if q|a^2 then q^2|a^2 and b^2 so q|p

so q is 1 since it's co prime to p

as for the case where q doesn't divide a^2

[north pagoda]

7² + 9² = 130 = 13 * 10. 13 and 10 are clearly coprime, so 13 fills the role of p, and 10 of q.

We know 13 can be written as 2² + 3². But how can we justify it from the fact that 7² + 9² = 13*10 where 10 is coprime to 13?

2 and 3 aren't obviously related to 7 and 9, right?

or how about 17² + 21² = 730 = 73 * 10. Again, 73 and 10 are coprime and 73 is prime.

73 can be written as 3² + 8². Is there an obvious connection between 3, 8 and 17, 21?

(if this is too tricky, try complex numbers - don't worry, you don't need gaussian integers, just basic complex factorization.)

[sacred junco]

isnt q less than p/2

also why are we writing p as a sum of squares when that's what we're trying to prove

[north pagoda]

i don't know how to make my argument easier to follow

that was a separate part of the proof

all that's left now is to prove this lemma

• If p is prime and q is coprime to p, and we can find integers a, b such that a² + b² = pq, then we can write p as a sum of two squares

and no, q isn't necessarily less than p/2

n is

[sacred junco]

alright

[sacred junco]

.

[sacred junco]

is this tru tho

[north pagoda]

well if q|a^2 then q^2|a^2 and b^2
this isnt necessarily true, no

7² + 9² = 130 = 13 * 10.

q is not 1 here, it's 10

[sacred junco]

but q doesn't divide a^2 in that case

[north pagoda]

again i want you to think about sums of 2 squares

[sacred junco]

im saying the case where it does

[north pagoda]

what do you know about them? what are squares modulo p?

[sacred junco]

quadratic residues?

p is congruent to 1 mod 4?

[north pagoda]

this is what im after

[sacred junco]

wait why are we talking about mod p all of a sudden

[north pagoda]

im trying to lead you to relevant facts to prove the last lemma

i'm sorry, i have to go now

[sacred junco]

i dont get the arguments

[north pagoda]

perhaps i failed to explain them clearly

that's on me

hopefully someone else can help you more

i was trying to outline the argument given here https://people.math.rochester.edu/faculty/iosevich/kirilacoronaviruslectureseries.pdf

maybe it'll be more help

[sacred junco]

thankss

[hollow zenith]

not sure where else to ask this

what is the most efficient algorithm to compute Legandre Symbols?

like using a program

I know there are some quick formulas for -1 and 2

Is there anything faster than reciprocity?

I mean trivially I can just compute squares of numbers, take their mod, and see if any of them match my desired number (say I want to find 2 | 13)

so that's linear time. Not sure how to see if quadratic reciprocity is faster than that but I'm sure it is

or by using Euler's Criterion and a square-and-multiply algorithm I could get log(n) (?) time

[stiff rivet]

first of all, you dont compute the legendre smbol, this requires prime factorization. instead compute the jacobi symbol

(this requires only factoring powers of 2)

then euler's criterion is log p running time as you said, which works

using quadratic reciprocity achieves the same but is faster in practice

you can do something similar to binary gcd which is faster on computers

you can search for "binary jacobi algorithm" or something, should give results

the reason its faster is bcs it only does subtraction and bit shifts, which is faster than multiplication

[hollow zenith]

instead compute the jacobi symbol
Ah I do not know what this is

I'll look into it

[stiff rivet]

its a generalization to non primes

[hollow zenith]

how do you get that quadratic reciprocity is logarithmic in time?

I wasn't sure how to analyze this

[stiff rivet]

you can reduce mod the other thing in every step

[hollow zenith]

yea

but idk how to show that's logarithmic

[stiff rivet]

its essentially a gcd computation

with some extra work at each step

gcd(a, b) = gcd(b, a) and gcd(a mod b, b) = gcd(a, b); same is true for the jacobi symbol

and you compute the jacobi symbol the same way except you have to keep track of some sign changes along the way

[stiff rivet]

or check Cohen's book, its in there

[sacred junco]

why does gcd(a, b) = gcd(a - b, b)?

[unkempt void]

If you divide a-b and b you divide a

If you divide a and b you divide a-b

(assuming a and b are distinct)

[sacred junco]

ohh okay

[stiff timber]

\begin{align}
a &= bq + r \
a - b &= b(q-1) + r
\end{align}

[sterile pumice]

vin100

[stiff timber]

if you're not convinced you may try to play with the def'n gcd = largest divisor

[wanton torrent]

How do I find the last 3 digits of 7^9999 ?

[unkempt void]

Finding the last 3 digits is equivalent to finding its residue modulo 1000

[wanton torrent]

indeed, got it

thanks

[unkempt void]

Np