elementary-number-theory

[sterile pumice]

Zopherus:

[light flicker]

Furthermore, show that for any two different primitive roots $\alpha, \beta$, their powers $\alpha, \alpha^2, \dots, \alpha^{p-1}$ and $\beta, \beta^2, \dots, \beta^{p-1}$ give rise to different cyclic sequences

[sterile pumice]

Zopherus:

[sacred junco]

@light flicker how would you approach the second part

suppose alpha and beta are distinct primitive roots

[light flicker]

well you should first realize that primitive roots can't be 0

so that means you can write \beta as some power of \alpha

and reason about that to show that the sequences must be unique

[sacred junco]

ok

[solemn raft]

I'm trying to show that for any nonconstant polynomial P with integer coefficients, the numbers P(n) as n ranges over the integers have infinitely many prime divisors

Clearly we can assume P is irreducible

I thought about trying to mimic euclids proof and say that for any p1,...,pk dividing P(n1),...,P(nk), there's an m such that P(n1)…P(nk) + 1 divides P(m), but I couldn't get anywhere with it

[light flicker]

That's the right idea, but you need to do it in a slightly different way

consider P(p1 * ... * pk)

[solemn raft]

So this is equivalent to the constant term mod any of the pi

Which is necessarily nonzero

By irreducibility

And so P(p1 *… * pk) isn't not divisible by any of the pi

Thanks!

[light flicker]

you need to be a bit more careful, the constant term could be 0 mod the pi

[solemn raft]

Oh lol yeah

[light flicker]

there's an easy way to remedy this though

[solemn raft]

So my thing breaks down if it's divisible by a single pi

So assume the constant term of P is divisible by p1

Then P(p1) is divisible by p1

Oh well the constant term can only have finitely many prime divisors

So this problem can only find up finitely many times

[light flicker]

the other solution is just to consider P(a0 * p1 * ... * pk)

where a0 is your constant term

[solemn raft]

Oh I mean I don't think my thing solved it

So P(aop1…*pk) is automatically divisible by a9

[light flicker]

so you can factor a0 out

and your constant term is now 1

[solemn raft]

Oh yeah

Nice

So P(a0*p1*…*pk)/a0 is 1 mod each pi and divides P(a0*p1*…*pk)

[light flicker]

yeah

[dreamy rain]

how come in their proof, they domt consider when both s and t are multiples of 5

in which case, b and c would also be a multiple of 5 and so the argument ‘eaxtly one of a,b and c is a multiple of 5’ falls apart

the question is referring to this btw

[fervent crest]

where s>t≥1 are chosen to be any odd integers with no common factors

[dreamy rain]

poop

[fervent crest]

?

[dreamy rain]

im just an idiot sometimes lol

thanks

[fervent crest]

I also like a friendly introduction to number theory

A very good intro book

[dreamy rain]

yea its really beautiful the explanations n stuff

[simple zephyr]

can some1 help me with number theoyr lol

im actually struggling really hard bc im a lil behind in my class

[light flicker]

lets hear it

[simple zephyr]

Fx should be Fx_25

so here's the problem im working with

i can prove that it's a field

but i'm not sure what it means to prove an element is a generator or how to prove its order

and part of that is im unsure of what the elements of the field are gonna look like

[light flicker]

Do you know what it means to be a generator of a group?

[simple zephyr]

uh to some extent

as far as i know,

you can form every element in that group with linear combinations of the element, right?

[light flicker]

what do you mean by linear combination?

[mighty cosmos]

that would be more for linear algebra

[simple zephyr]

er like multiplying it

[light flicker]

Yeah, the group operation on F* is multiplication

And so a generator for F* would be some element x such that

you can write every other element of F* as x^n for some n

[simple zephyr]

hm ok

my textbook gives this as the definition of the field

if i multiply something

and the resulting x+y sqrt(2) comes out to something above 5

i would just mod it by 5, right?

[light flicker]

yes

x,y are in F_p and so their addition and multiplication are operations in F_p

[mighty cosmos]

"above 5" meaning ..

[light flicker]

which is to say that you need to mod by p

[simple zephyr]

er, above and equal to 5

oop

[mighty cosmos]

I mean... 2+3sqrt(5) is "above 5" in R, but does not need to be modded

[simple zephyr]

oh i meant like x and y individually

[mighty cosmos]

yep

[simple zephyr]

ok thanks

[simple zephyr]

not sure where to start with this one, really

i know that a primitive element is basically a generator for a group

[light flicker]

So you have that 2^36 = 1

[simple zephyr]

im also pretty sure that the primitive 3rd root of 1 in F37 is 5

because 5 is a primitive root

because after using euler's totient function you get that phi of 37 is equal to 2^2 * 3^2

and then 36/2 = 18, 36/3 = 12, and neither 5^18 or 5^12 mod 37 is equal to 1

but im not sure why the number 2 being a primitive is helpful

[light flicker]

Uh, 37 is prime

Oh, yeah

[simple zephyr]

wait wouldnt it be p-1

in that case

[light flicker]

Yeah because that's the order of the multiplicative group

Sorry

Uh, it helps because you can write

(2^12)^3 = 1

So 2^12 is a third root of unity

[simple zephyr]

oh

[light flicker]

And do you see how the hint helps for the second part

[simple zephyr]

mm not really

what does being the third root of unity mean

or like

why is that relevant

and how did you get (2^12)^3 in the first place

[light flicker]

Well, 12 * 3 = 36

[simple zephyr]

oh

i see

but that isn't primitive, right?

[light flicker]

Uh

No?

[simple zephyr]

oh nvm

i confused myself for a sec

sorry

then wouldnt you say like

36-36^2 is congruent to the square root of -3 mod 37

wait no

26 - 26^2

and then that becomes 16, which is 34 mod 37 when its squared

which is congruent to -3

ok yee haw thanks

[light flicker]

Yeah

[sacred junco]

For which primes $p$ does the congruence $x^2\equiv −5 (\mod p)$ have a solution?

[sterile pumice]

Slate:

[sacred junco]

I've tried to use Jacobi Symbols for solving this, but I was stuck mid-way

$x^2+5\equiv 0 \mod p$ has a discriminant $d=-20$, so it suffices to check the jacobi symbol $\text{jacobi}(-20, p)$

[sterile pumice]

Slate:

[sacred junco]

now here one can use the definition to bring this to $-20^{\frac{p-1}{2}} \mod p$

[sterile pumice]

Slate:

[sacred junco]

but im not sure how this has made things easier because looking at this expression i can't guess for which p it evalutes to 0 or 1

i've written out the list of primes that do satisfy the initial congruence and that didn't yell a pattern at me either 3,5,7,23,29,41,43,47,61,67,83,89,101,103,107,109,127,149,163,167,181,223,227,229,241,263,269,281,283,307,347,349,367,383,389,401,409,421,443,449,461,463,467,487,503

[light flicker]

Uh, I'm not sure why you're using Jacobi symbols and all of this, legredre symbols and quadratic reciprocity will solve this problem

[sacred junco]

i used jacobi interchangeably to legendre symbols, sorry

but i haven't thought of using quadratic reciprocity, so i will try that now

instead of Legendre(-20,p) i can be looking at Legendre(p,-20) right?

[light flicker]

Uh, what

You're trying to find the value of (-5/p)

[woeful marsh]

hey gota question

this statement

means that every x , y are in N

or

every x and every y are in N

∀ This symbol means for all (or sometimes, for every). For example, “∀ squares D, D is a
rectangle”.

am i right to state that

this set

stands for N ?

[upbeat wren]

means that every x , y are in N
or
every x and every y are in N

is not true. The meaning is "for every x and every y that are in N." The person playing the logic/proof game can choose ANY x or y they want. Not that the result will definitely be in N.

I may be picking at raw dictionary definitions, but unfortunately/luckily math people have to speak precisely. That doesn't mean sniping at badly written statements, but if there is a mistake to bring it up.

[woeful marsh]

so any x and any y

that are in N

pardon my english

its my third language 😦

[upbeat wren]

So "any" means sometimes the whole set or a subset. I think technically "every element of" is the most painful but correct way to say it.

[woeful marsh]

so am i right

with my answer

that this set stands for N ?

[upbeat wren]

I'm not totally sure what you mean to say so no offense, but there's likely a better way to say it? 🙂

[woeful marsh]

they are asking what this set it

and i am saying that this set

represents N

All the natural numbers

[upbeat wren]

um, if n > 1, then 1 is missing

and 1 is definitely a natural number.

[woeful marsh]

how come

he is missing

when they are saying that x=1Ux=2

y=1&******

[upbeat wren]

because n > 1 ... 1 >1 ...

[woeful marsh]

right

but it stands for all numbers that are greater than 1 ?

not all

it's wrong to say

[upbeat wren]

Some classes treat the natural numbers as 1 and up ... others treat the natural numbers as 0 and up. Just a heads up :).

[woeful marsh]

i know

here they chose to not mess with this problem

it's my first assignment and i have no clue

This set is all the integers that are greater than 1 ?

[upbeat wren]

um, I think they are going for primes 🙂

[woeful marsh]

got it now

i understand it after you said it

when they are saying that x=1Uy=1

it means either x=1 or y=1 but not simultaneously ?

[upbeat wren]

oh in math that symbol means either or both.

xor is the computer version of what you are worried about.

[woeful marsh]

either or both

so x and y can be 1 ?

[upbeat wren]

not in this case but in general yes.

[woeful marsh]

this can't be 1 because n>1

and n=xy

[upbeat wren]

Yes. "A or B" implies A or B or both (but just writing this sentence is unneeded text: A or B implies the both case). There are other restrictions here so they cannot be both true.

[woeful marsh]

ok

but

if x is divisible by 2

it is wrong

same for y

then it's not prime numbers

[upbeat wren]

um, you have to satisfy xy = n first.

[woeful marsh]

we satsify xy=n

and x=1 or y=1

but how do we prove that x is prime

[upbeat wren]

yes but further you must satisfy the entire implication

(xy = n ) --> ((x = 1) or (y = 1))

[woeful marsh]

right

and for instance y=1

we can rewrite it as x=n

right?

[upbeat wren]

hmm somewhere I got lost. Sorry!

we're looking for all n>1 such that when we take two natural factors, one of the factors must be one.

sorry! derp

[woeful marsh]

ok

yse

yes

[upbeat wren]

(at least I hope it says that)

[woeful marsh]

one of the factors is 1

but how do you prove that x is a prime number when y=1

[upbeat wren]

oops

one or both factors must be one. my mistake.

[woeful marsh]

if both factors 1

n=1

and then it's false

my question is how do you prove that it is a prime set of numbers when x can be any number in N

[upbeat wren]

you start with an n. you find all possible pairs of natural factors.

if every pair is such that either the first or second in the pair is one (or both), then it is prime.

[woeful marsh]

but

if

y=1

x*1=n

they need to state that x is prime himself

[upbeat wren]

yes, but that is for one particular y. we have to find this for all y and x such that xy = n

[woeful marsh]

oh i am starting to understand

for all x and for all y

[upbeat wren]

cool

yes!

[woeful marsh]

alright

ty for your patience and help ahhah

[upbeat wren]

🙂

[sleek cove]

I have a question about F_4

given phi^2 + phi + 1 = 0 in Z_2, you are allowed to multiply both sides by phi, since F_4 is closed under multiplication, right

[serene crag]

I assume you mean phi is an element of F_4 and you're considering Z_2 as a subset of F_4? Yes, you can multiply both sides by phi.

[sleek cove]

oh yes, sry

right, because phi can be any symbol

F_4 = {0, 1, symbol, symbol + 1} ?

[serene crag]

Yes

[sleek cove]

ok

[glass obsidian]

hello would questions about modular arithmetic go here?

[stoic bear]

yeah, it is fine here probably; if it is more competition math, maybe #competition-math would be better

[alpine jasper]

i'm not too sure if my method is correct

1. even if i have those linear cong. surely the value of v is not truly free right? for example, if u=1, then (x, y) in {(1,0), (2,1), (3,2), ...} which means v can't be even
2. i have to prove those p-1 values of v are incongruent, which i'm unsure how

[torn escarp]

here's a weird way to try to do it, since there are at most p^2 solutions brute forcing all x and y, maybe

$p^2-\sum_{x=0}^{p-1}\sum_{y=0}^{p-1} (x^2-y^2-a)^{\varphi(p^2)} \mod p^2$

[sterile pumice]

Merosity:

[torn escarp]

it's 1 in the sum if it's not a solution, 0 if it is a solution

sorry that's probably not very helpful lol

[alpine jasper]

hmm

that looks painful

ok i'm going to bed

pls ping i'll reply back

[alpine jasper]

i've been stuck on the case of p does not divide a for hours

fuck me in the ass

the attempt i posted above turns shit because point 1) i made above, so i'm not even worrying about 2)

so i look back and realized that i solved this problem and i'm trying to apply to 7

the case of p does not divide a is turning into a headache

pls zoph papa i need your assistance @light flicker

[alpine jasper]

<@&286206848099549185>

[alpine jasper]

i'm goin to cry

[winter bear]

u should have pinged me smh

did you use the hint from IR @alpine jasper

||u=x-y and v=x+y||

[alpine jasper]

zoph gave me permission to ping him

so you sayig i can ping you too in the future ?

yes, i did used that hint

[winter bear]

yeah for nt sure lel

so uv= a (p) right, and p doesnt divide a

[alpine jasper]

yes

[winter bear]

ok for which valiues of u does v have a solution to this

and what is that solution

[alpine jasper]

only if (u, p) | a, so u = 1, 2, ..., p-1

[winter bear]

right, and for each of those u's, whats the sol to v

[alpine jasper]

like to find out which v it solves it?

[winter bear]

yeah

[alpine jasper]

so (p-i)v = a(p)

hmm

i have a feeling that it is in terms of a

[winter bear]

yeah

[alpine jasper]

gimme like 5 mins

[winter bear]

also just uv=a

idk why (p-i)

||what would u do if we were working in just Q for example||

[alpine jasper]

alright

i haven't look yet, gimme a moment

[winter bear]

ok, also ill brb

[alpine jasper]

oh

(Z/pZ)* = {1, 2, ..., p-1}

since u in (Z/pZ)*, inverse exists

[sacred junco]

blue boys talking

[alpine jasper]

so v = au^-1

seems to agree with your hint

i think i got it yee haw

thanks john i love you

[winter bear]

yep

[sacred junco]

No problem

[alpine jasper]

so i showed that (2/q) = 1, that means there exists x such that x^2 = 2(q)

but how does that show 2^p = 1(q)?

@winter bear

give me your power

[winter bear]

well how do u make the 2 a 2^p

[alpine jasper]

oh, so i get
x^(2p) = 2^p (q)

hmm?

[winter bear]

mhm

and whats x^(2p)

(whats 2p interms of q)

[alpine jasper]

x^(q-1)

oh and fermat

[winter bear]

yep

[alpine jasper]

sick

thank you

[winter bear]

np

[torn escarp]

https://projecteuler.net/problem=120

ok I guess obviously it's 0 or 2 mod a, guess I should hensel lift to mod a^2 😩

[fervent crest]

Well I got that if n is even then r must be 2

[torn escarp]

kek

[stoic bear]

whats going on in here

We solving a problem

[fervent crest]

by just binomial

and um

if n is odd

then it's equal to 2an

[torn escarp]

I didn't read the question

[fervent crest]

[torn escarp]

I thought it was something else haha

[stoic bear]

[torn escarp]

didn't realize we were maximizing over all n

weird hmm

[fervent crest]

yeah

[torn escarp]

oh ok that's not so bad

I'm caught up to you I just worked it out what you said 2 when n even, 2na when n odd

so it's basically like, maximizing 2n mod a I think

[fervent crest]

yeah i think so

[torn escarp]

if a is odd then pick n=(a-1)/2

[fervent crest]

lmao

yes

[torn escarp]

maximo

[fervent crest]

oh

and if a is even choose n=(a-2)/2

fantastic

should have seen this

i just wrote a loop that loops over n=1, ..., phi(a^2)

[torn escarp]

is that really it haha

lol

[fervent crest]

i feel like that is it

xD

[torn escarp]

I wrote a loop in my mind

starting from the biggest number

idk I feel like there might be some kinda issue but I haven't thought about it

[fervent crest]

lemme see if a-1/2 and a-2/2 works

[torn escarp]

I don't know if the even case works out that way well, I'll play on paper and get a snack

tell me how it goes

[fervent crest]

it printed an answer that's 499 greater than the actual one

[torn escarp]

hmm is your loop off by 1 maybe on the last check

499 is nearly half of 1000 so that's why I'd suspect it

honestly it seems like whatever this 499 is from is like from specifically the evens or odds

counting one more than it should be

[fervent crest]

3 6
12 8
15 20
30 24
35 42
56 48
63 72
90 80
99 110
132 120
143 156
182 168

[torn escarp]

idk I haven't even seen your code so

nor have I even calculated one of these out yet haha

[fervent crest]

    private static int MaxR(int a)
    {
        if (a%2==0)
            return a*(a-1);
        return a*(a-2);
    }
    private static int MaxRCorrect(int a)
    {
        int max = 2;
        //int t = Totient(a*a);
        for (int n = 1; n < a*a; n += 2)
        {
            int r = (2*a*n) % (a*a);
            if (r>max)
                max = r;
        }
        return max;
    }

So the two column of data

The left one is the correct r_max for a=3,...

[torn escarp]

wait

[fervent crest]

the right column is the MaxR

that's wrong

[torn escarp]

a%2==0 return a*(a-1)

that's backwards

[fervent crest]

shit

[torn escarp]

lol

[fervent crest]

fantastic

the code works

[torn escarp]

nice 😎

[fervent crest]

i can probably optimize it even more to get constant time

[torn escarp]

dibs on your $1,200 check

[fervent crest]

😔

[torn escarp]

lol

[fervent crest]

I can't believe I made a mistake as stupid as this one

[torn escarp]

nah that mistake doesn't matter

you know come to think of it, I think this could potentially be solved with some lifting the exponent lemma thing

meh whatever it's done for now just

I like to try to bash other stuff if possible to see anyways

[fervent crest]

fantastic

the code is now constant time

    private static long getResult120()
    {
        int n=1000;
        
        return n*(n+1)*(2*n+1)/6-1-2*2 - (3+n)*(n-2)/2 - (2+n/2)*(n/2-1);
    }

xD

[torn escarp]

lol

cool

lmao

nice pen and paper level

[fervent crest]

?

btw

[torn escarp]

like we could have solved this with pen and paper and not program

[fervent crest]

do you know how to factor integers in the form of 111...1

yeah

[torn escarp]

yeah in the obvious way of geometric series

but idk if there's more you can do than that

I think I was interested in that in the past so I might remember if I get to thinking about it

wait are you asking cause you were gonna show me something or you didn't know

[fervent crest]

https://projecteuler.net/problem=129

This problem

i don't know how to do it

[torn escarp]

well I guess we can place a naive upper bound of R(n)>= A(n)

lol that might actually be a bit too naive lol

$R(k) = \frac{10^k-1}{10-1}$

[sterile pumice]

Merosity:

[torn escarp]

might be easier if we're looking at this mod n

[fervent crest]

k+1 I believe

[torn escarp]

so long as 3 doesn't divide n

plug in k=1 and we should get R(1)=1

[fervent crest]

right

[torn escarp]

if k has divisors it will factor but I don't know if that helps us since we are probably wanting k to be unfactorable anyways

I was more interested to see when 10^k=1 mod n

so k is a multiple of a divisor of phi(n) lol

what was that gcd condition they gave us again

gcd(n,10)=1 ok well necessary that's good

idk I feel like I'd try to brute force and write a program at this point, what are you thinking

[fervent crest]

?

[alpine jasper]

so, i then write pt = (s-i)(s+i)

since t is integer, p | s-i or p | s+i given that p is prime

i want to show a contradiction but i'm getting no where

i know that i can transform that into divisibility in norms, so like
N(a+bi) = a^2 + b^2
so N(p) | N(s-i)
hence p^2 | s^2 + 1

and i got nothing

@light flicker

[light flicker]

Remember that Z[i] has unique factorization.

You should think about the divisibility in the other direction

[alpine jasper]

hmm

so since p is not \pm 1 or \pm i, p is not a unit, so p can be written as p=ab for some irreducible element a and b in Z[i]

then N(p) = N(a) N(b) where N(a) and N(b) are prime..?

uh meh that doesn't show shit i think

i'm gonna need a bigger hint on this one

[light flicker]

either (s-i) | p or (s + i) | p

@alpine jasper

[alpine jasper]

hmm

ok let me try

couldn't i just write that

i still don't see where to go with (s-i) | p or (s + i) | p

[light flicker]

remember that prime implies irreducible here

[alpine jasper]

i don't know man i'm stuck hard on this one

[light flicker]

I mean, can this happen?

p is an integer, s is an integer

[alpine jasper]

i was just about to conclude that

and same for s + i surely

?

[light flicker]

I mean yeah

[alpine jasper]

noice

thank you

you saved me again

actually, there's still one thing that confuses me,
how does either (s-i) | p or (s + i) | p?
i write pt = (s-i)(s+i) and i try to reach a contradiction but i can't

i know (s-i) | pt and (s+i) | pt

what if that t "eats away" both of the s+-i?

[light flicker]

yeah, why can't that happen?

[alpine jasper]

let me think about it

oh, so if i write t = (s-i)(s+i)k for some k
then pt = p(s-i)(s+i)k = (s-i)(s+i)
=> pk = 1 which is bad

[light flicker]

Yes

[alpine jasper]

nice

thank you

[ivory ferry]

If a prime number divides a product, it divides one of the factors. How can I prove it without using prime number factorization?
I cant remember.
I cant use that Z_p is a field
Because, well, we prove that Z_p is a field using this.

@woeful marsh n=6

that is, N = 1+235711*13 = 30031 is not a prime number

[woeful marsh]

alright

but is there any other way

oh i think i got another way

2 3 5 7 ....

this multiplication consists of 2* all prime numbers

it means the result would be even because of 2*

and when added +1

shit

it makes no sense now

[grave bough]

How do I write good number theory questions?

[light flicker]

This is very vague, what are you writing them for?

[grave bough]

a math contest I am writing

so it would be more competition math I guess, but most number theory questions I end up rwriting become trivial and useless

either too easy, or not elegant

[stoic bear]

@grave bough you are here what

[grave bough]

are you the guy on usnco

[stoic bear]

Ye, but I mostly talk here

[grave bough]

nice

[stoic bear]

Anyways, my advice is to just keep writing problems

This is definitely a skill that develops with practice

Since you are starting out, maybe try to draw inspiration from past problems

Also, I don't really see the "not elegant" thing as a huge downside

[light flicker]

uh, your solutions are plus or minus a^50?

Ah this isn't right

How'd you solve it

[sacred junco]

using euler's thm

[light flicker]

Uh, how so

[stuck lintel]

is it possible for two numbers to have the same euler totient function value?

[winter bear]

yeah it is, take for example 6(which has toitent 2) and 4

phi(6)=phi(4)

(however, i believe phi(x)=n for a fixed n always has a finite number of solution, curtiosy of some bounding action on phi)

[fervent crest]

$\lim_{n\to\infty}\varphi(n)=\infty$ so yes it is true

[sterile pumice]

Whoever:

[fervent crest]

But I feel like this limit is proved based on the fact that the fibers of singletons are all finite, so this is probably not a good justification for the fact

[sleek cove]

is there a name for the theorem that states f has at most d zeros in Z_p

its annoying to have to write it all out

[sleek cove]

Also, is it possible to prove that s =/= -s?

i know thats true for p>2, but not if p = 2

wait nvm im dumb

[fervent crest]

[sleek cove]

shhhh

but does anyone know if theres a name to refer to when using that thm?

[light flicker]

It's not obvious

[fervent crest]

🤔

Is Z_p the integers modulo p? Or p adic integers

[light flicker]

The first one

[fervent crest]

Then how is it not obvious?

(-s)^2=s^2

[light flicker]

I'm talking about the fact that a degree d polynomial has at most d roots

[fervent crest]

ah

[sleek cove]

what

i wasnt confused ab solving a or proving the thm

[light flicker]

Yes we know

[sleek cove]

wait so do you know if theres a name for that theorem

[light flicker]

There's not

[sleek cove]

ok

ty

[light flicker]

It holds in all polynomial rings over integral domains

[sleek cove]

yes, i too know what that means

[sick zinc]

help me

[light flicker]

What have you tried

[sick zinc]

10^9 +1 = 11*(10^8-10^7+10^6-...+1)

but it only shows that 11 is divisior

[light flicker]

think about fermat's little theorem

[sick zinc]

I thought about it too

but there is no prime in exponent (forget about it)

[light flicker]

Uh, that's not what you need for Fermat's little theorem

[sick zinc]

p is 19

a is 10

now there is 10^18

[light flicker]

so you have that 19 | 10^18 - 1

that looks pretty close to what you want

[sick zinc]

yes but how to prove that 19 isn't divisor of 10^9 - 1

[winter bear]

you familiar with quadratic reciprocity?

[sick zinc]

unfortunately I'am not

[winter bear]

oh, ok then ur best off just manually finding 10^9 mod 19

[sleek cove]

can you sub 18 for -1, and then you have odd = even?

[winter bear]

so like find 10^3 first, and then cube that

odd and even dont make sense in Z/pZ

like 1=20 mod(19)

[sleek cove]

yea im dumb

[sick zinc]

It is possible to do it not manually

[winter bear]

it is, but it requires more advanced stuff

and doing it manually in this case

is actually p fast

[sick zinc]

but lecturer give that exercise on first lesson of congruency

[sleek cove]

u need to find 10 to a smaller power mod 19

[sick zinc]

I don't know how to make it fast

without Euclides

[sleek cove]

what is 100 mod 19

[winter bear]

i mean as i suggested do 10^3 first, and then cube that

[sick zinc]

you mean something similar?

this is my last exercise

[winter bear]

yeah something like this

[sick zinc]

it is not that simply in this case

(-2)^4 = 16 = 17 -1

it's harder for me to find number k, that k^3+1 is multiple of 19

[sleek cove]

...

[winter bear]

just find 10^3...

i feel like

[sleek cove]

if u want to do it this way, let k= 10^3

[sick zinc]

my idea was to find small k

[winter bear]

we are missing some basic understanding of modular arithmetic

whats 10^3 mod 19

[sick zinc]

12

[winter bear]

mhm

and whats 12^3 mod 19 (prolly wanna say -7 here)

(so (-7)^3)

[sick zinc]

unfortunately I still don't get it

[winter bear]

$10^9\equiv (10^3)^3\equiv (-7)^3 \pmod{19}$

[sterile pumice]

JohnDoeSmith:

[winter bear]

do you get this

[sick zinc]

Yes but

I forgot one thing

I cannot use calculator

[sleek cove]

then do -7 x -7 x -7

49 is what mod 19

[sick zinc]

11?

[sleek cove]

ye

[sick zinc]

ehh I still don't know how to do this

[winter bear]

$10^9\equiv (10^3)^3\equiv (-7)^3 \pmod{19}$

[sterile pumice]

JohnDoeSmith:

[sick zinc]

i need fast, neat solution without using calculator

[winter bear]

the steps after this are very natural

[plain fable]

because 1000 = -7 (mod 19)

oh without calculator

I mean you can do it

by hand

1000/19 is not too hard

[winter bear]

p easily too

950 for example

is divisible by 19

[plain fable]

ya, add 19s to it

until you're over 1000

you need 3 more

950+3*19 = 1007

1000-1007=-7

[winter bear]

and u should be able to do 7^3

[plain fable]

it's 353

343*

[sleek cove]

we got to 11*(-7)

ifk how u need a calc for that

[winter bear]

oh just realized there is an instant way to do this lel

$10^9 \equiv (-9)^9 \equiv - 3^{18}\equiv -1$

[sterile pumice]

JohnDoeSmith:

[sleek cove]

big brain

[torn escarp]

nice I was just thinking 9 = (19-1)/2 but didn't think how to reason out 10 is a primitive element

[winter bear]

yeah my first approached used QR, by doing (5/19) (2/19) lel

but then i realized, 9 perfect square lel

[sick zinc]

is it okey? all those calculations are necessary?

[winter bear]

u can make stuff for efficient ofc

[sick zinc]

what stuff for example?

[winter bear]

-343= 380-343 for example

which is 37 which is -1

[sleek cove]

this seems like a lot

[sick zinc]

okey, but i see that

$10^9 \equiv (-9)^9 \equiv - 3^{18}\equiv -1$

[sterile pumice]

Vlad:

[sick zinc]

this is better

3rd equality is fermat?

[winter bear]

yeah, but u should also be able to do it the manual way (often it is quicker to do it manually then to spend time looking for a good sol)

mhm

[sick zinc]

how to fast prove first equality?

[sleek cove]

..... what is 10 - 19 =

[sick zinc]

yes I see

I mean

nevermind

it is clear now

[fervent crest]

Omg that is big brain

[limber charm]

Prove that if a is congruent to b (mod c) and c is an odd number, then (a/c) = (b/c)

[light flicker]

What are you confused about?

[limber charm]

I don't know how to even start the problem

[light flicker]

Try something

think of related results

play around with it

[limber charm]

Well all I can think of is that (a-b)/c is equal to some integer but I don't think that helps.

There was another problem I had earlier that said "If c is an odd number, prove (ab/c)=(a/c)(b/c)

[light flicker]

Well, first, what's the definition of (a/c)

[limber charm]

The book actually showed how to solve this one in particular and it started by saying let c=(p1)(p2)...(pr)

[light flicker]

Uh

That's not what it means

[limber charm]

sorry that was me being dumb for a second there

[light flicker]

So what's the definition of (a/c)

[limber charm]

a is congruent to b mod c where b is the remainder when c divides a

[light flicker]

What

That's not what I asked at all

[alpine jasper]

either A and B are true => P = 1(12) or A and C are true => can't happen. so P = 1(12)

does my solution makes any sense?

[alpine jasper]

@light flicker

give me power zoph papa

[winter bear]

yeah, but u dont need to consider (-1/p) = -1 cause u already said (-1/p)= 1. but yeah the solution is right

[alpine jasper]

oh wops bad logic

thanks

[sleek cove]

losing 4 points because you didnt say that r^-1 exists, even though the problem defines r to be in Z_p \ {0}

[sick zinc]

help pls

[snow plaza]

u know groups?

[sick zinc]

nope

I need to use Euler's theorem

From Euler's theorem I know that a^48 = 1 mod 65 and a^12 = 1 mod 13

but I don't know how to prove that a^12 = 1 mod 65

[fervent crest]

so by fermat's or euler theorem, we have that a^4 = 1 mod 5, and a^12 = 1 mod 13

which means 1 = 1^3 = (a^4)^3 = a^12 mod 5

so 5 | a^12-1 and 13 | a^12-1

since gcd(5,13)=1

we can say that 5*13 = 65 | a^12-1

or a^12 = 1 mod 65

@sick zinc

[sick zinc]

wait

i'm trying to understand it

ok

thank you

it's clear

[sleek cove]

not sure where to put this, but given an arithmetic function f : S -> S, why is it only necessary to show injectivity or surjectivity to prove its a bijection

its because its self mapping right

[winter bear]

umm arithmetic function? what S?

[fervent crest]

You can only do that when S is finite

[sleek cove]

sorry, S is a finite subset of N

[winter bear]

yeah thats true then

[sleek cove]

can you eli5?

Like, how does injectivity lead to surjectivity

[winter bear]

think about what the image will be if each element of S maps to something different

[sleek cove]

then each element has a unique element mapping to it

[winter bear]

think size

[sleek cove]

there has to be #S elements getting mapped

[winter bear]

mhm

[sleek cove]

ah

[sleek cove]

wait what is phi of 0

[gilded tinsel]

euler's totient isnt defined for 0 usually i dont think

but id say 0 is a reasonable value

[winter bear]

arithmetic functions are typically not defined at 0 ye

(a lot of the defination that involve factors and stuff just dont work with 0)

[gilded tinsel]

yeah i say 0 as everything divides 0

[sleek cove]

hmm ok

[sick zinc]

help pls

[alpine jasper]

something something eulers theorem

[sick zinc]

yes

gcd(2,100) =/=1 so i don't know how to use it

[alpine jasper]

hmm true

[simple zephyr]

not that one

i think you apply euler's totient theorem

[winter bear]

this is chinese remainder

[simple zephyr]

yeh

[fervent crest]

[sick zinc]

i know totient

[fervent crest]

Euler totient theorem

[winter bear]

anyhow

do mod 25 and then mod 4

and then combine

mod 25

[sick zinc]

I've already tried this way

2^20 = 1 mod 25

from totient

[winter bear]

mhm

[sick zinc]

so 2^1000 = 1 mod 25 too

and 2^1000 = 0 mod 4

[winter bear]

yup now combine

[sick zinc]

but how to link it

[fervent crest]

Chinese remainder theorem

[winter bear]

oh so let me show you how its generally combined

[sick zinc]

I think I have to create equation system with mod

[winter bear]

so you let $y=2^{1000}$ in this case right, we said $y=0 (4)$ so that $y=4n$ for some n. we also said that $y=1 (25)$ so that $4n=1 (25)$. now invert $4$ and you will get $n=$ something $(25)$, so $n=25 m+$ something. combine these two equations to get your $y=100m+$ something

[sterile pumice]

JohnDoeSmith:

[simple zephyr]

isnt it like

nvm

[winter bear]

4's inverse is ||-6|| mod 25 btw

[simple zephyr]

is anyone really good at writing proofs

im getting slapped around like a little baby

not really sure how to approach this one, most of my ideas are from my textbook which only deals with primes and not a vaguely non-prime n

[winter bear]

well what did you try

i can give you a hint to start you off ig

you want the hint?

[simple zephyr]

sure

that's why im here

at first i thought that because n is the sum of squares it would be congruent to 1 mod 4

[winter bear]

if a prime divides $a^2+b^2$, then $a^2+b^2= 0 (p)$

[sterile pumice]

JohnDoeSmith:

[simple zephyr]

is that 0 mod p

[winter bear]

yeah

anyhow try using this to figure out something about p

[fervent crest]

John why are you doing (p) instead of (mod p)

[winter bear]

its shorthand notation smh

[fervent crest]

Your short hands are sacrilegious

Use \pmod{p}

[winter bear]

imo mod looks ugly if used too much, (p) is much more concise notation and has 0 ambiguities so why not use it

[alpine jasper]

yeah i'm on the (p) gang because ireland rosen uses that notation

[simple zephyr]

hm im still a little confused

[upbeat wren]

lol if you want to adopt a not-so-popular dialect of math / English ... I guess you have the freedom, but you're got a lot of explaining to do ...

[sick zinc]

@winter bear

[upbeat wren]

Desimos rocks 😛

[winter bear]

yep

[sick zinc]

is it okey?

[winter bear]

yeah it is

[sick zinc]

okey so thank you

[sacred junco]

You're welcome

[winter bear]

hmm ok @simple zephyr so using the a^2+b^2=0 (p) what can you say about -1 mod p

[simple zephyr]

a^2 is congruent to -1 mod p, i think?

but im not sure where to go from there

[winter bear]

well (a/b)^2 =-1 (p) not a^2 but yes

are you familiar with Quadratic reciprocity?

[simple zephyr]

is it just applying sum of squares to say that -1 is a square mod p iff p is congruent to 1 mod 4

[winter bear]

yep

[simple zephyr]

hmm

but how does n being even or odd become relevant to that though

or like

why do those cases matter

[winter bear]

well we only considered odd primes p right

the other case is purely for the power of 2

[simple zephyr]

hm

i guess i just need someone to explain quadratic reciprocity as a whole to me

that was the last chapter but tbh im not very familiar with it so i think that's why im getting slapped around

what does it mean for something to be a quadratic residue?

[winter bear]

i mean you found the critical fact

that x^2=-1 (p) iff p=1(4)

$x$ is said to be a quad residue mod $p$ if there is some $y$ such that $y^2=x (p)$

[sterile pumice]

JohnDoeSmith:

[simple zephyr]

oh ok

so it's like the remainder of the square of y when divided by p?

that makes sense

[winter bear]

yeah

[simple zephyr]

i will give these problems another shot ill come back if i get stuck

thanks for the help doe

[winter bear]

try rereading the QR section, its cool stuff+important

no problem

[zealous hawk]

hi @willow knot @delicate fiber

[willow knot]

hello

why r u in elementary number theory

lol

[zealous hawk]

this is a new environment

uh

[willow knot]

r u learning modular arithmetic

[zealous hawk]

i was interested

in numbers

[simple zephyr]

ok from this

i substituted s and t with (2m+1) and (2n+1), and then found the result of that substitution for a,b, and c

but i'm not sure if just saying that there aren't any terms that can be factored out from that is sufficient to say that there are no common factors

[grave bough]

How do I prove that 2^n is congruent to 1 mod 3, when n is an even integer?

[fervent crest]

fermat's little theorem

[grave bough]

oh thanks

right

[last grove]

hey, does anyone know of a good video series that covers elementary number theory?

[light flicker]

Read a book

[last grove]

All the libraries are closed right now ;;-;;
I read the first part of "Topics From the Theory of Numbers" by Emil Grosswald and I got the part where he began analytic number theory but that was ~3 months ago... I'm just looking for a resource to refresh my memory

[light flicker]

there are plenty of books online

[last grove]

ok, I will look for one

[light flicker]

depends on what exactly you're looking for

you could look at Silverman's A Friendly Introduction to Number Theory

or Hardy and Wright's Theory of Numbers

[last grove]

ok, I will check them out

thanks

[simple zephyr]

zopherus, are you there?

i need some help with the proof for silverman's chapter 25 sum of two squares proof on the second half of the theorem

im getting slapped around like a little baby because i'm not sure how to approach the proof lol

[light flicker]

is it what you posted above

[simple zephyr]

https://cdn.discordapp.com/attachments/418981682117345288/696467051774214314/unknown.png yeah this one

at first i thought it would be enough to just show that n is a square and apply the sum of squares to say that it is 1 mod 4

but that doesn't really account for all of its prime divisors

would i need to use method of descent

[simple zephyr]

wait i dont think that would work to prove what im trying to prove though

i only understand how to prove sum of squares itself but i don't get how to extend it to each prime divisor of n

[simple zephyr]

OKAY I GOT IT I THINK

[upbeat wren]

So inspired by others, I came up with a nice digit problem. Given a digit sequence where all digits are 1 through 6:

1123455

Any adjacent doubles can be changed into any other pair of doubles.

1123455 --> 2223455 --> 2333455 -->2333411

Is it possible using this method to get from 1123 to 3112?

[supple furnace]

If a_1, a_2, a_3, a_4 are the digits, a_1-a_2+a_3-a_4 is invariant, so one cannot get from -1 to 1.

[upbeat wren]

nice

[fervent crest]

damn nice solution

[woeful marsh]

i need help

with understanding a basic mathematical sign

if any one is willing to explain it to me via vc id be more than happy

[last grove]

hey, I'm interested in reading number theory papers to expand my knowledge. However, I currently do not know much outside elementary number theory. Can anyone recommend any papers/journals? I will share them with my friends as well

[light flicker]

You should just learn more number theory from textbooks

There are interesting papers that you could read but it wouldn't really teach you much number theory outside of some neat facts

You should learn more elementary number theory and then algebraic number theory

[last grove]

okk =:) ty

what if I do analytic number theory first?

[light flicker]

Either way

You should finish learning elementary number theory things first

[last grove]

ok

thanks very much

[light flicker]

But to learn analytic number theory, you should know complex analysis

And to learn algebraic number theory, you need to know galois theory so

[long wasp]

Would this cover each solution or am I missing solutions?

Also meant to say "Let k be any integer greater than or equal to 3."

[light flicker]

You're missing solutions

[fervent crest]

phi(15)=8=4*2

👀

[light flicker]

@long wasp

[craggy solstice]

even the primes

all primes of the form 4k+1

are solution s

[broken igloo]

Maybe it's easier to try the reverse "phi(n) is not a multiple of 4"

[supple furnace]

Yes, consider complement and casework on the power of 2 that divides the number

[light flicker]

??

Just take all the odd numbers?

And count the number of subsets of the odd numbers?

[sleek cove]

if i have a convergent inf product with a constant in front, i can multiply the constant into all of the inside terms right

[fervent crest]

Um no?

You can’t

[sleek cove]

oh, is there anything u can do with it

[fervent crest]

You can distribute power inside

I think

Also this probably belong to #advanced-analysis

[sleek cove]

hmm it might be better to leave it in my case

[fervent crest]

Usually you can ln it

[sleek cove]

true, but this is for a euler func problem

[fervent crest]

Ok

Well

The only thing I remember about infinite product is this

[sleek cove]

is there a notation for p!, or do you have to write out the product, and specify that p is prime

[celest plinth]

@sleek cove is that supposed to be factorial

there's another notion of primorial, which is denoted n# in some places, which is the product of the prime numbers less than or equal to n

[sleek cove]

sorry yea, p is just replacing n for n!

[celest plinth]

then no need for new notation

p! works just fine

[sleek cove]

ok thanks

[sleek cove]

it is valid to take log base p in line 2->3, correct?

[torn escarp]

no

just try to reverse that step from 3->2 and you have completely abused exponent rules

[sleek cove]

ah ok

wait u can just get rid of the left hand side in step 2 im dumb

[fervent crest]

Funny thing is that altho he abused exponent rules, all inequalities were correct

[sleek cove]

why is taking log_p not allowed? I just figured it would be the same as taking ln like when you are dealing with e to a power

is it because there are addition/ subtraction so i would need to divide/multiply the exponents?

[torn escarp]

log(x+y) is not log(x)+log(y)

just try out some specific numbers for yourself

[sleek cove]

yikes, my memory is bad

i was thinking log of each element, but thats just as wrong

[sleek cove]

yikes 9 pages for 5 problems

[supple furnace]

Memory? Try proving the rules on your own

[fallow owl]

is it possible to prove this?
$$
(((x \mod W)(y \mod W) \mod W) - W / 2) \mod W
$$
is the same as
$$
(xy - W / 2) \mod W
$$

[sterile pumice]

Frank:

[fallow owl]

or disprove; I'm not 100% if its correct

[light flicker]

okay well first, W - W/2 is just W/2

and no, you can see its not true by just letting x = y = 0

the first one will be 0, but the second one will be -W/2

[fervent crest]

You can use \pmod

[fallow owl]

@light flicker wouldn't the first also be -W/2?

oh shoot

parentheses

It should be this:
$$
(((x \mod W)(y \mod W) \mod W) - W / 2) \mod W
$$
is the same as
$$
(xy - W / 2) \mod W
$$

I wrote a python script to test random #s and it seems pretty true ://

[sterile pumice]

Frank:

[hasty jacinth]

As long as w doesnt have 0 divisors it should work?

[fallow owl]

0 divisors?

i mean i guess I shouldve stated everything's an integer

dont know if thats required

[hasty jacinth]

2*2=0 mod 4 then 2 is a 0 divisor for Z/4Z

[fallow owl]

o_O

[light flicker]

No this always works

[fallow owl]

whys that?

[hasty jacinth]

Oh yeah it always works im dumb

It's in a ring

You can verify this by writing x as x+nW and y as y+mW and expand

[light flicker]

you should see that $(x \pmod W)(y \pmod W) = xy \pmod W$ always

[sterile pumice]

Zopherus:

[fallow owl]

isnt like, x = 9, y = 9, W = 10, a counterexample to that

or did you miss a mod on the left?

[light flicker]

depends how you want to think about mod I guess

like I'd write that $81 = 1 \pmod{10}$

[sterile pumice]

Zopherus:

[fallow owl]

oh right, sorry i rarely use mod but i remember reading that earlier today

You can verify this by writing x as x+nW and y as y+mW and expand
I think this method works, thanks!

$(x \pmod W)(y \pmod W) = xy \pmod W$ is easy to show with that method and everything falls into place

[sterile pumice]

Frank:

[sleek cove]

wait how do u end a contrapositive proof, after showing the contrapositive holds, do you have to like restate the original statement and say therefore it holds?

[stoic bear]

I mean, you could to make it more clear

[sleek cove]

we start riemann zeta and rsa now

[upbeat wren]

yay rsa!

[woeful marsh]

am right ?

[light flicker]

no, do you understand what "necessary" means

[woeful marsh]

i cannot conceive the difference between nece and sufficient

yep

i mean a num to be divisble by 6 is even and divisibale by 3

divisible

]\

now i am right?

[light flicker]

nope

You really should go figure out what "necessary" means instead of just guessing

[woeful marsh]

ce

necessary means required to be done

and i don't understand why my first selection is wrong

he is required to be divided by 3 and 2 \

It is only the last 2

and first

[light flicker]

Because you're trying to use some sort of english intuition on a mathematical term

[woeful marsh]

english is my 3 langauge

and i am trying to move into english in maths

language *

[alpine jasper]

you should move english in english before english in maths

i finished 4, but i'm having trouble seeing how i can use 4 to do 5

[light flicker]

alpha has a minimal polynomial thats in Z[x], it must divide f

[alpine jasper]

hmm

let me think about that

go that minimal poly. is a monic poly. in Z[x], call it g, such that f=gh where h is in Z[x] again?

that doesn't make much sense since i'm not allowed to assume coefficients of f are all integers?

[light flicker]

g divides f in Q[x] so h is in Q[x]

[alpine jasper]

i see, i should review some old stuff about poly.

thanks

[light flicker]

but you should think about scaling h so that its in Z[x]

[alpine jasper]

i see

[alpine jasper]

so i thought about writing kf=gh' where h' is h multiplied by some k such that it's in Z[x]

but then i thought a bit more and i realized that i don't understand why g divides f

is it because Q[x] is a field extension of Z[x]? idk if this is even true

i'm really bad at this