elementary-number-theory

[fervent crest]

🤔

[torn escarp]

hensel's lemma

[fervent crest]

Lol

[light flicker]

there's an elementary solution

But yes

[fervent crest]

Ok

[torn escarp]

I can prove it by just working out the proof directly on it though by induction and so I wouldn't be "using" the lemma

[fervent crest]

Elementary

[light flicker]

lmao

[fervent crest]

Lmao

Um

[woven phoenix]

@light flicker I didn’t use your second property

[torn escarp]

the p=2 case is the annoying one

[fervent crest]

[woven phoenix]

And also use the fact that (x + y)^p = x^p + y^p (mod p)
@light flicker how did you use this fact? Btw thanks for the hint!!!

[fervent crest]

Mfw don’t have a pencil and paper

Can’t work out this interesting problem

[light flicker]

I had a different solution than you

This works as well

[torn escarp]

I'll try to do it a different way I don't wanna be lame

[fervent crest]

Lol

[light flicker]

How about this, there's a solution that doesn't use the fact that x^2 = a (mod p) has at most two solutions

Okay that's also trivial jk

[fervent crest]

Well I don’t know a lot about quadratic residue and polynomial in mod n

:/

Can’t really work this out

[light flicker]

You don't need to really

[torn escarp]

use the fact that the p-adic numbers are a field and so x^2=a has at most 2 solutions

and then just round it off to the nth digit

[fervent crest]

Mfw p-adic

[light flicker]

Yeah I found this exercise in a p-adics textbook

But there are elementary solutions

You could definitely do this question whoever

[fervent crest]

🤔

[torn escarp]

yeah, I feel like that way I just described is just the same hensel lemma way just obfuscated lol

[light flicker]

Yeah, doesn't the fact that p-adics are a field use hensel's lemma

Maybe I'm misremembering

[torn escarp]

no, hensel's lemma gives you a way to lift solutions to equations from the residue field to the p-adics

[fervent crest]

Ok I’m gonna keep reading analysis I keep getting distracted by other interesting problems

[torn escarp]

but you can make the p-adics by cauchy completions or inverse limits

[light flicker]

Yeah okay jk

[torn escarp]

hensel's lemma is actually Newton's method

but just looks slightly different when presented but does truly become the algorithm,

$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$

[sterile pumice]

Merosity:

[light flicker]

@fervent crest forget analysis go study algebra

[torn escarp]

when you find some $|f(x_0)|<|f'(x_0)|^2$

[sterile pumice]

Merosity:

[torn escarp]

^p adic absolute value

[light flicker]

Right

[fervent crest]

But I like analysis

[torn escarp]

learn p-adic analysis

[light flicker]

you'll like algebra better

[torn escarp]

the algebraic closure of the p-adics requires infinitely many field extensions

that's like, infinitely many algebra

[light flicker]

lmao

[torn escarp]

real numbers only have a single puny quadratic field extension

sad!

[woven phoenix]

Btw @light flicker what’s your most recommended (elementary) number theory textbook?

[weary basalt]

you didn't ask me but the george andrews number theory book from dover is good

[light flicker]

Depends how much algebra you know

@woven phoenix

You literally asked me about intermediate number theory the other day

Why do you think I don't know this guy's level

You said "so not exactly the same"

Which does imply that

I've never heard of that

So probably not

[swift shard]

I know left-to-right multiplication is very fast and easy to learn

Well - easier?

Possible, but I wouldn't want to

[tender cypress]

@light flicker What book would you recommend to someone with an undergrad abstract algebra level knowledge?

[light flicker]

@tender cypress Classical introduction to modern number theory by Ireland and Rosen

This book is honestly amazing

[tender cypress]

@light flicker Thanks! 🙂

[fervent crest]

Read that book and confused because i don’t have a solid understanding of abstract algebra

[light flicker]

Wow it's almost like you chose to study analysis instead

It doesn't really use too much algebra

Only what a group is and some ideas about cyclic groups

[woven phoenix]

@sacred junco @weary basalt thanks for the recommendation, will check it out!
@light flicker not yet proficient in algebra (i’m kinda reading about group theory on and off to know the scope broadly)

[fervent crest]

I mean

I scanned over the whole freilegn’s book

By scanned I meant I didn’t do ahy exercises but just read over theorems and proofs

[light flicker]

Yeah that's not really learning anything

[molten bolt]

there's a notation for "a divides b" which is "a | b"

which is similar I guess

[fathom sierra]

well a divides b exactly means b is a multiple of a

[woven phoenix]

well just like a > b is used for "a is larger than b" and we can flip it to < to say "smaller than", I propose we flip "|" (divides) to say "multiple of"

1 | 1 (1 divides 1), and if we flip
1 | 1 (1 is a multiple of 1). seems to work

[stuck lintel]

[inner crest]

it could also be a 180 rotation

[craggy solstice]

lol i think he means b=ak

[upbeat wren]

oh oh ... Pick any four integers a, b, c, d > 0 and where also gcd(ab, cd) = 1. Show that there are infinitely many ABC-triples (google please) of the form (ab^n, cd^m-ab^n, cd^m) where n, m > 1 and n and m are whole numbers. You have 3 written pages (front and back) ... to figure out the proof or if I'm joking. 🙂 hehe

[craggy solstice]

(ab)^n or a*b^n

[upbeat wren]

a*(b)^n

[woven phoenix]

that feeling when it took 4 hours to solve a textbook problem

[light flicker]

share

[woven phoenix]

(and 18 pages of scribbling)

ok start your timer

"Show that if a has order 3 (mod p), then a + 1 has order 6 (mod p)"

[light flicker]

Okay we know that p | a^3

I assume you mean multiplicative order right

[woven phoenix]

yep

a^3=1 (mod p)

[light flicker]

sorry yeah p | a^3 - 1

We note that the prime can't be 2 or 3 since no elements have order 3

[woven phoenix]

god dammit you're damn right that "p | a^3 - 1" (it's crucial for the proof and I derived it in a roundabout way)

[light flicker]

I also assume you mean order in the strict sense

[woven phoenix]

a^2 != 1, and a^1 != 1 if that's what you mean by strict

[light flicker]

yeah okay

Then we know that p | a^2 + a + 1

[jade sentinel]

||I suppose it would be enough to prove that (a+1)^3 = -1 mod p. Expanding (a+1)^3 gives us:||
|| (a+1)^3 = a^3 + 3a^2 + 3a + 1 = 2 + 3(a^2 + a) = -1 + 3(a^2 + a + 1) = -1 mod p ||
|| This shows that (a+1)^6 = 1, expanding (a+1)^2 similarly will show that it is not 1 mod p||

[light flicker]

So now a + 1 can't have order 1 since otherwise a = 0

Similarly, (a+1)^2 = a^2 + 2a + 1 = a, so a + 1 can't have order 2 since a is not 1

[woven phoenix]

nice, I also first proved that a + 1 can't have order 1 nor 2

[light flicker]

Now, (a + 1)^3 = a^3 + 3a^2 + 3a + 1 = 3a^2 + 3a + 2

So this is equivalent to -1 mod p, so a + 1 can't have order 3

Then squaring this gives that (a+1)^6 = 1 so it has smallest order 6

[woven phoenix]

fast!

[light flicker]

eh I just looked at Kan's answer, looks like he got it faster

[woven phoenix]

Could you please roll back and tell me how you claimed "then we know that: p | a^2 + a + 1"

[light flicker]

An important property of primes is that

[jade sentinel]

a^2 + a + 1 = (a^3 - 1)/(a-1)

[light flicker]

if p | ab, then either p | a or p | b

since p | a^3 - 1 = (a-1)(a^2 + a + 1)

And as we noted, we can't have that p | a - 1, since this would mean that a = 1 (mod p)

[woven phoenix]

great, so exactly the same way I found it (only took much longer!)

oh, kan's spoiler post also has the solution. You all are so fast!

[jade sentinel]

You also said that you realized p | a^3 - 1 after a lot of work, so was that a brainfart or you haven't grokked modular arithmetic?

[woven phoenix]

brainfart. it follows from the definition 🙂

[jade sentinel]

(a + 1)^3 = 🙃 mod p

[woven phoenix]

I was too fixated to use 3 | p - 1

but it wasn't fruitful

[jade sentinel]

Yeah it happens sometimes that you keep going down a road that either takes a long time to give the right proof or no proof at all

Oh well

[woven phoenix]

yeah haha

[sterile pumice]

euler/fermat:

euler/fermat:

[stuck lintel]

gcd(2n^2+2n,n-1) = gcd(n-1, 4n) = gcd(n-1, 4) = 4

[ebon stump]

Euclidean algorithm for gcd

Try multiplying the right by 2n

np

[waxen wave]

Least nonnegative residue. Does this make sense on how to find it?

[broken igloo]

???

oh

the remainder when you divide by m?

[waxen wave]

Yea let’s say if we have 282771 (mod 6) we will use EA first. 282771=6 and.....

Once we get the GCD from EA we can determine a. The GCD is a

6*47128+3

The least nonnegative residue of 282771(mod 6) is 3

Guess this is confusing to @broken igloo

[broken igloo]

it's not called EA

euclidean algorithm

I think it's just division

[waxen wave]

EA gives you GCD

a method of computing the greatest common divisor (GCD) of two integers

[broken igloo]

yeah

it seems that you just want the remainder when you divide by m

that's what you call "least nonnegative residue"

[waxen wave]

ALright. thanks so does my steps or say"guideline" make sense?

[broken igloo]

it is overcomplicated

I think just divide by m and find the remainder

that's all you need to do

[waxen wave]

Alright. Thanks @broken igloo

[twilit bronze]

@sacred junco 1 is a divisor of 1

yup

[stuck lintel]

They’re all the same number

You don’t say there are an infinite number of 1s because 1 = 1^n ._.

[quick furnace]

^

...

why... why would you

like

it's just 1

why would you count 1^2, 1^3, etc as if they were distinct from 1

when they're

not

[stuck lintel]

This is a defamation of my namesake channel

Also I don’t know whether you’re being serious or trolling Euler

[fervent crest]

bUt HoW cAn $1 = 1^n~(n\in\bbZ)$ WhEn $2^2\neq 2^n~(n\in\bbZ\setminus{2})$

[sterile pumice]

Whoever:

[jade sentinel]

what

[fervent crest]

$2^2\neq2^3$ then clearly $1^2\neq1^3$

[sterile pumice]

Whoever:

[fervent crest]

@jade sentinel idk what you’re not understanding smh

[quick furnace]

don't shitpost in these channels.

or at least fucking put a </s> marker

[fervent crest]

sorry ann

[craggy solstice]

lmao

[last parcel]

Hello, can someone help me with this: I want to prove that the sum of the squares from 1 to n with n>1 is a perfect square only if n = 24

[light flicker]

There's a formula for the sum of squares from 1 to n that might be helfpul

[last parcel]

I know

n(n+1) need to be divisible by an odd power of 2

Etc

I have some "mid results"

But I don't know where to go

There is no n >1 such as 3n+1, 4n+1 and 6n+1 are perfect squares and no n different of 24 such as n, 6n+1 et 12n + 1 are perfect squares

I've tried to look at the nearest other perfect squares

But it's actually really difficult for me

[light flicker]

The first thing you probably want to think about is why this fraction is always an integer

[last parcel]

It's the sum of the squares

I know it's an integer

I want to prove that for n>1, it's a perfect square only if n = 24

[fervent crest]

He probably meant for you to think in terms of divisors

And yes we all know the formula is the sun of squares therefore an integer

But if you’re just given the formula it’s not that obvious (but can be easily seen) that the formula always produces a natural number

[last parcel]

I got my previous results by thinking about the prime factors

I know that n(n+1)(2n+1) needs to be an odd power of 6 times other prime factors

I found that there is no n >1 such as 3n+1, 4n+1 and 6n+1 are perfect squares and no n different of 24 such as n, 6n+1 et 12n + 1 are perfect squares

[light flicker]

Why exactly are you looking at those numbers

You know that to be a square, n(n+1)(2n+1) must be 0 mod 4

[last parcel]

Yes

[light flicker]

So what does n mod 4 have to be

[last parcel]

0

[light flicker]

Okay

[last parcel]

So n mod 8 = 0

[light flicker]

Why

[last parcel]

Because n needs to have an odd power of two in its prime factors

[light flicker]

Right

[last parcel]

But I have no clue to prove it's true only when n = 24

[torn escarp]

I have some idea that might help

$n(n+1)(2n+1) = 6m^2$

[sterile pumice]

Merosity:

[torn escarp]

any prime that divides n must divide m, as the other two terms are relatively prime to n

so you can write

$n=Q^2 2^a3^b \ m = Q 2^x 3^y$

[sterile pumice]

Merosity:

[torn escarp]

and remove all the factors of n that aren't 2 and 3

$2^a3^b(n+1)(2n+1) = 2^{2x+1}3^{2y+1}$

[sterile pumice]

Merosity:

[torn escarp]

from there, I suppose you can start doing case work on whether 2 and 3 does or doesn't divide n

[light flicker]

Going my way, when is n(n+1)(2n+1) equal to mod 8 true

[last parcel]

When any of the factors equal to 0 mod 8 ? If you mean 0 mod 8

And we already know it's n

(Sorry about my wifi)

[light flicker]

We know that n has to be 0 mod 4 already

That must mean that n is 0 or 4 mod 8

[last parcel]

No because if n is even, then n+1 and 2n+1 are not
So n is the only one divisible by 4

And it needs to have an odd power

Of 2

So we already know 8 divides n

[light flicker]

I mean yeah, that's the other way of figuring that out

[last parcel]

And I'm stuck exactly at this point

For 2 days now

I really don't see how to make any progress and I'm honestly trying

[light flicker]

Where did you get this problem?

I'm not sure that my method works actually

[last parcel]

I got this problem from a friend

"a juicy problem" he said

[light flicker]

I'm not sure there's a super easy solution

[last parcel]

I don't think there is a super easy solution

Like, I know I suck at math but this, is really hard for me

[torn escarp]

fun problem, I'll try to think about it more seriously

[last parcel]

ok, actually it's a "known" problem, and I didn't have the knowledge to do it

(cannonball problem)

so I'll have to learn how to solve it without internet, thanks for your help !

[last parcel]

(side note: the proof can be found on different websites, and it's not that easy)

[light flicker]

Yeah that's why I asked

[last parcel]

I didn't know until I searched for it on google

[fervent crest]

How to solve a problem, just follow a 3 step procedure:

1. Formulate the problem using the simplest terms
2. Stick it in google
3. Copy the first stackoverflow answer

[stoic bear]

Even if it is an irl problem, search stackoverflow

[torn escarp]

don't forget the best step,
4. Never gain self reliance

[knotty jungle]

@last parcel MÉLOOOOOOOOOOOOOO

[last parcel]

don't me ping me here for nothing, you can dm me Inès : )

[upbeat wren]

Hmm ... I need a girlfriend.

1). I need to look good. I need to smell good.

2. Sticking in Google

4 Ways to Look Good - wikiHow
Yadda Yadda

Here are our 18 tips for smelling good all day.

Drink Plenty of Water. ... 

Yadda Yadda

Hmm. No StackOverFlow answer. Property not found for top 10 Googled results. Process Abort.

Math is simple. Dating is not 🙂

[light flicker]

What the actual fuck

[torn escarp]

I like how he put 1). instead of 1.) but after that no further )

well, almost as much as 3.

[light flicker]

I'm just going to say it

Getting a girlfriend is not all about looking good

[torn escarp]

I never thought about looking or smelling good when I got my girlfriends in the past, I think caring about what a girl thinks about you is probably the first wrong step towards not getting a girlfriend

[light flicker]

I mean, it's a valid reason to worry

It's just more that girls like guys who are super motivated and super interested in things

As in, guys who are motivated to become better people

[craggy solstice]

lol smelling good

????

[stuck lintel]

Where’s le number theory

[light flicker]

Sorry pluwum

I reask interesting question

[sacred junco]

If a positive integer, n, has a prime number of factors, how can I prove that all of its factors are in the form of p^(k-1) for some prime number p?

[half fable]

@sacred junco factorize n into primes

the statement immediately follows

[sacred junco]

That is what I am trying to prove—that its prime factorization would be in the form of p^(k-1).

[half fable]

from prime factorizatio

yes

so factorize it

[light flicker]

Wait, what's k?

[half fable]

doesnt matter

some number

he wants to prove that n is a power of a prime

[light flicker]

I know

[half fable]

k would be a prime number

[sacred junco]

Yes.

[half fable]

which is the number of factors of n

do you need more help?

or will you manage

[sacred junco]

I don't know which definition I should cite.

[half fable]

what definition

why would you need to

[sacred junco]

I don't follow your train of thought. Can you expand on how the statement immediately follows after factorizing n?

[half fable]

yes

once you decompose it into primes, you can write an expression for how many divisors n has

by inspecting the expression, you immediately see that the number of distinct primes dividing n is 1

[sacred junco]

Is there a way to express the latter statement more formally?

[half fable]

of course

you don't think I'm talking gibberish do you?

I'm giving you the outline of an actual proof

or do you want me to write it out explicitly for you

and solve it for you

[sacred junco]

I'm sorry, I'll be fine.

[half fable]

👍

[light flicker]

If a is relatively prime to some prime p, then show that x^2 = a (mod p^n) has at most two solutions for all positive integers n.

[half fable]

@light flicker that's not true

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

but for p>2 that IS true

do you want me to show you why?

brb

x^2 = 1 mod p^n has only two solutions

because p only divides one of the factors (x-1) or (x+1)

so p^n only divides one of them

this is because p>2

now a is invertible mod p^n by bezout

hence x is a unit

if x^2 = y^2 = a, then (xy^-1)^2 = 1, hence from what we found before

xy^-1 = +- 1

and we're done

[light flicker]

2 isn't a prime

No I posted it as an interesting exercise from a p adic book

[half fable]

2 isn't a prime

also why was this in a p adic book?

or is there a nice solution using p-adic numbers?

[light flicker]

This is like foundations for how p adics work kinda

It's basically Hensel's lemma

[torn escarp]

nonsense

2 is prime all day long

[light flicker]

2 isn't a prime

[torn escarp]

2 is just small so it has some issues

[light flicker]

If 2 was a prime why would half the theorems exclude 2

Imagine even numbers being prime lmao

[torn escarp]

but the same issues emerge when you start rammifying the other p-adic fields

[broken igloo]

there are two types of primes

even primes and odd primes

[torn escarp]

and primes at infinity

[broken igloo]

for quite a few number theory problems, they both cause about the same amount of issues

[sacred junco]

By definition, a prime number is an integer greater than 1 that cannot be formed by multiplying two distinct integers other than 1 and itself. From that definition, 2 must be prime.

[wary dune]

hi

[broken igloo]

let's use prime|| ideal||s

[wary dune]

can someone help

prove that x^2+y^2+z^2 = 2xyz has only 1 solution
x y and z are integers

i found out that x y and z must be even

but idk what to do next

[torn escarp]

-1 is a prime according to your definition @sacred junco

[broken igloo]

they all have to be even?

@torn escarp is -1 greater than 1?

[wary dune]

2xyz is a even (multiple of 2)

[torn escarp]

in my world

[wary dune]

so x^2+y^2+z^2 is even

[broken igloo]

so mod 4

so all even

why not write x=2a, y=2b, z=2c?

try it out

[wary dune]

4a^2+4b^2+4c^2 = 16abc

which simplifies to a^2+b^2+c^2=4abc

[broken igloo]

okay, what now?

(literally the same thing you did, just keep doing)

[wary dune]

a b and c are all integers
so a b and c have to be even

[broken igloo]

so now, what do we do?

[wary dune]

write a=2m b=2n c=2k

[half fable]

⏬

[wary dune]

4m^2+4n^2+4k^2=32mnk

[broken igloo]

hmm

[sacred junco]

@torn escarp "greater than 1"?

[broken igloo]

well, it just keeps going

[wary dune]

so x y and z have to be infinitely divisible by 2

[broken igloo]

so the idea is?

[wary dune]

only possibilty is

0?

[broken igloo]

okay, let's use a technique to do that properly

[half fable]

2^∞

[broken igloo]

Consider the number of times 2 divides into x

Let's call it k

Then?

[wary dune]

k+k+k+k...

[broken igloo]

no, not like that

say x=2^k a, where a is odd

[wary dune]

ok

[broken igloo]

then?

plug it in and figure out y and z

[wary dune]

x/2 = [2^(k-1)]/a

then what

[broken igloo]

no

plug in to the diophantine

then find out properties of y and z

the number of times 2 divides them

[wary dune]

ok

[sacred junco]

If there is a positive integer m with exactly four positive factors, such that the sum of all 4 factors is equal to n, how many such n exist in the set {2010, 2011, 2012, ..., 2019}. I thought about splitting it into cases, where I look for integers in the form of 2010 <= ab + a + b + 1 <= 2019 where a, b are prime numbers, but I didn't get far. Advice appreciated.

The cases would be: a nor b NOT = 2, and a or b = 2.

[stuck lintel]

You can factorize it into (a+1)(b+1) and looking at each of their prime factorizations, see whether they can be put in that form or not

[sacred junco]

@stuck lintel Yes. I am now at (3+1)(503+1) = 2016, but I am not making much progress.

[craggy solstice]

ayee

how to prove every prime AP that is formed for primes >=3

the common difference is 6

[light flicker]

What's prime AP?

[quick furnace]

AP = arithmetic progression?

@craggy solstice are you sure you aren't asked to prove the common difference is a MULTIPLE of 6

i can give you an example of an arithmetic progression of three primes with a common difference that is not equal to 6

[craggy solstice]

ya a multiple of 6

and yes arithmetic prog

sorry for my mistakes

[quick furnace]

then consider your progression modulo 6

[broken igloo]

@stuck lintel There's also the a^3 factorisation

[craggy solstice]

is this true

[half fable]

yes

in general, phi(p^k)= p^(k-1) phi(p)

@craggy solstice

[craggy solstice]

K

i thought i discovered some new property or shit

[half fable]

no, this is extremely elementary...

[craggy solstice]

ok OK

[half fable]

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

[craggy solstice]

lol

[half fable]

try proving that phi(ab)=phi(a)phi(b) for a, b relatively prime

[craggy solstice]

hmm

is it easy to prove

[half fable]

depends

probably not too easy

[craggy solstice]

ok ill tru

try

[half fable]

but it's elementary

[craggy solstice]

and tell you

no spoilers nor hints

[half fable]

you don't need high power math to prove it

ok

[torn escarp]

also fun one:

$n = \sum_{d|n} \varphi(d)$

[sterile pumice]

Merosity:

[light flicker]

||mobius inversion formula ||

[sacred junco]

Hello. Is there an intuitive explanation for the formula of the product of the divisors of some integer?

[light flicker]

Yes, think about the prime factorization

[sacred junco]

Care to expand on that?

[light flicker]

Think about it

What do the divisors of a prime factorized number look like

[sacred junco]

They are all prime numbers raised to some power.

[light flicker]

but what prime numbers

and what power

[sacred junco]

It depends on the integer. I need to correct that not all divisors are prime, as our integer is not necessarily prime.

[light flicker]

Think about what the prime factorization of a number

It's primes raised to some powers

What do the prime factorization of the divisors of this number look like

If you have that $n = p_1^{m_1} p_2^{m_2} \cdots p_k^{m_k}$, what do the divisors of this number look like

[sterile pumice]

Zopherus:

[craggy solstice]

ok is he asking about the number of div isors of the number?

[sacred junco]

I apologize, I am back now. @light flicker each divisor is in the form of p_1^n*p_2^k*p_3^j... and so on, where n, k, j can each be any nonnegative integer up to the exponent of the prime in the prime factorization of the integer.

[light flicker]

Yep

So what do the products of all those numbers give you

[sacred junco]

That's the fuzzy part.

[light flicker]

Think about the case when $n = p^k$

[sterile pumice]

Zopherus:

[sacred junco]

Assuming p is a prime number, then n should have k+1 divisors, to account for k = 0.

So the product of each of the divisors would be p^0*p^1*p^2*...*p^k.

[light flicker]

Yep, and what's that?

[broken igloo]

??

[sacred junco]

Perhaps p^(2k) I meant to say.

[broken igloo]

let's see if you are right

let's try some cases

p^4 let's go

p^0*p^1*p^2*p^3*p^4=?

[sacred junco]

p^10 I suppose, so that's clearly false.

Ah, it might be p^(2k+2).

[light flicker]

Check p^3

[sacred junco]

So it seems both of the answers only work in certain cases, and neither were the general case formula.

[broken igloo]

hmm

do you know how to calculate

$\sum_{i=0}^ni$?

[sterile pumice]

Element118:

[sacred junco]

It would be 0 + 0 + 0 + 0 + ... + 0 n times?

[broken igloo]

no

it's 0+1+2+3...+n

[sacred junco]

Okay.

[craggy solstice]

whats the sum of the AP

[broken igloo]

actually I don't think this is a great method, try this instead

Suppose I have a number n and I tell you that a is a factor of n. What other factors of n do you know?

@sacred junco

[sacred junco]

I only know a^0,a^1,a^2,...,a^k, where k is the highest possible power of a, where a is a prime number.

[broken igloo]

So, say I have the number
n = 696,498,447,002,239,121,371,797,248,947,864,146,020,879,995,870,198,065,801,366,806,408,633,811,483,757,917,176,532,107,342,550,394,104,778,117,564,019,271,634,707,451,191,410,894,679,642,753,940,888,217,163,255,877,346,160,368,489,287,646,500,144,333,426,167,611,569,479,616,878,356,276,398,762,087,787,207
and I say
a = 25,966,579,129,585,375,179,420,807,630,527,191,860,794,510,244,741,759,058,306,632,613,552,047,090,404,018,620,438,112,185,763,930,657,747,650,794,363,289
Can you find another nontrivial factor of n? (as in, not 1, not n)

[sacred junco]

I could divide n by a.

[broken igloo]

yeah

so, think of multiplying pairs of factors

[sacred junco]

Unfortunately, I don't think I get it.

[broken igloo]

okay, let me be a bit more blatant

if we have a factor a of n, we can find the factor n/a, and it turns out that a*(n/a)=?

so, the square of the product of all factors can be written as?

[sacred junco]

I'm sorry, what? Why are you multiplying a*(n/a)? That will just be n.

[broken igloo]

That's why

a and n/a are two factors of n

that's why we are multiplying them together

because no matter what factor a you pick, the result is n

[sacred junco]

Okay.

[broken igloo]

think about it as pairing up factors

[sacred junco]

Ah, I think I got it now

To calculate the product of all the divisors of some positive integer n, we have n^(divisors(n)/2)

[broken igloo]

can you show that?

[sacred junco]

I thought about forming two sequences on numbers, one where each of the divisors are increasing, and one where they are decreasing from greatest to smallest.

[broken igloo]

yeah that works

[sacred junco]

When I multiply both sequences together, I paired them off in pairs, but overcounted by exactly 2, so that's where the division comes in.

Thank you for your help.

[daring ice]

Is there any method to determine if a polynomial has no solutions modulo some prime p?

[swift shard]

If there are any integer factors, they will still be a factor mod p

@daring ice

Have an example we could do?

[daring ice]

x^3+x^2-4=0 mod 10007.

I should say this is an example I made up. This polynomial has no roots mod 7. Which I determined by hand.

[light flicker]

Rational root test works

Mod p

[stuck lintel]

"rational" "mod" nani?

[light flicker]

@gilded quest hello

[gilded quest]

ur amazing

ok

[light flicker]

i need to leave soon but

[gilded quest]

so

[light flicker]

Things like

[gilded quest]

i know some basic group theory

and i really like just wanna know

how can u use these htings

in other fields

the most field that anybody knows about is NT ig

so like whats up with algebriac NT

[light flicker]

Algebraic NT

[gilded quest]

just interestest

interested*

ye

[light flicker]

is not where you use algebra in number tehory

It's more specific than that

[gilded quest]

ohh fuck XD

what then

[light flicker]

Things like

Showing that the group (Z/pZ) has is cyclic

makes solving linear equations mod p straightforward

Because you can write things in terms of the generator and from there it's easy to solve

[gilded quest]

sounds cool lmfao

are there linear equations mod p

that are hard to solve?

[light flicker]

No

[gilded quest]

why need this stuff then

[light flicker]

Because we can use the fact we have a generator

[gilded quest]

is there something you cant do without algebra

oh

[light flicker]

I have to go, you should just pick up Ireland and Rosen's book called a classical introduction to number theory and read it

[gilded quest]

i was thinking david bourton

wdu thinnk?

i am interested inNT tbh

but i heared there are many fields

'analytical NT' , algebraic

whats the david bourton

NT?

basic NT? XD

[light flicker]

I've never heard of that book

[half fable]

XD

[sacred junco]

Are there infinitely many primes such that they're made from only 1s (Like 11)? (Other variants: only 3s,7s or 9s.)

,w is (10^(23)-1)/9 prime

[sterile pumice]

Display results online and refine query

Requested by Godel#3113

Display results online and refine query

Requested by Godel#3113

[torn escarp]

unknown problem

at the very least, if the exponent is not prime, then the number can't be prime

if we could solve problems like this then we'd know that there are infinitely many Mersenne primes

[sacred junco]

Ahh ok, so nothing changed

[lean hound]

there shouldn't be any primes greater than 10 made up of only 3's,5's ,7's and 9's... since they will always be a multiple of a number made up of only 1's.

[sacred junco]

True, also the ones ending with 5 will be divided by 5 😛

[balmy night]

why does the quotient remainder theorem (a = bq + r) require that b is positive? dont q and r still exist if it is negative

[swift shard]

It asserts that q and r exist and be unique

You're right that there's likely another solution if you allow b to be negative, or larger. But that's exactly what we don't want

[chilly zodiac]

yo i need a tiny bit of help

i've been looking at the sequence of numbers in the form of n^2 + 1

and was wondering how to check if in that sequence there would be a multiple of m

so i've kinda done that though it gets quite long winded to prove it for larger m

but looking at the possible multiples you end up with a weird sequence

2,5,10,13,17,25,26,29,34,37,41,50,53,58,61,65,73,74,82,85,89,97, ...

and it looked as if say if you had a multiple of a and b then there would also be a multiple of ab

for example 2 works and 5 works, 2*5=10 and 10 works too

but it doesn't quite work for all cases

say 2 and 10

but it works for lots of others

anyway just wondering if someone could shed some insight into this

[light flicker]

If n^2 + 1 is a multiple of m

Then n^2 +1 is 0 mod m

Which means that n^2 is -1 mod m

So now the only question is if there's a square that's -1 mod m

[tawdry scaffold]

Question: can the set of all roots of all cyclotomic polynomials be mapped subjectively to the set of all points on the unit circle?

[light flicker]

What does subjectively mean

[tawdry scaffold]

Surjectively

But autocorrected lol

[light flicker]

No

It can't

[tawdry scaffold]

Are we missing some transcendental points in that mapping, then?

[light flicker]

Basically yes

[tawdry scaffold]

And those holes are not filled in when you get to a "polynomial" of "infinite degree"?

[light flicker]

That makes no sense

Polynomials have finite degree by definition

We can arbitrarily approximate any number on the unit circle using roots of unity

If you consider power series

[tawdry scaffold]

Yeah, but if you're summing the roots of $x^n-1$ for all n?

[sterile pumice]

Jythro:

[tawdry scaffold]

All integer n, from 0 to infinity

Would we say, in a sense, that we are converging on the unit circle?

[light flicker]

Eh

Yes in some senses no in others

There are only countably many roots of unity

There are uncountably many points on the unit circle

[tawdry scaffold]

Ah, there's the kicker...

Would you happen to know if there are cyclotomic polynomial equivalents for other shapes? Is that even an area of study?

Like, say for a square of side length 1, or perhaps some polar curves like a limacon?

[gilded tinsel]

Is there any theory on solving modular equations like n^n=a (mod p) for a prime p?

[light flicker]

I don't know of anyone

It seems a lot harder and I'm not sure there would be a nice pattern for things like that

[whole sigil]

@chilly zodiac there's an n such that m | n^2 + 1 iff m - 1 is congruent to n^2 mod m iff m - 1 is a quadratic residue of m. To check whether m - 1 is a quadratic residue of m (aka if there's any solution for n) you only need to check each congruence class mod m once (aka you only need to check 1 n of each remainder by division by m). One way you could do that, for example, is only checking the numbers below m.
Furthermore, the list of squares modulo m is symmetrical around n/2 because (x + m/2)^2 = x^2 + xm + m^2 = x^2 + (x + m)m congruent to x^2. This means you only need to check half. (when n is odd, this might complicate things a little bit, but i think there's still an analegous way to shorten the path)

[chilly zodiac]

Yh you only need to check up to floor(m/2) right

[whole sigil]

yeah im writing a computer program to do that rn

im really trying to get better results on this

this problem really interests me for some reason

[chilly zodiac]

I wrote a little bit of code to spit out the possible multiples under a given number

But im about to sleep lol

[whole sigil]

good night

[chilly zodiac]

I was thinking of a way to prove a weaker case where if you have some multiple you know works, and multiply it by 5 then that should work

Or at least on all the ones i checked it worked

But i have no idea how to begin proving it

Food for thought

Good night

[whole sigil]

I'll think about it, if it's true I don't think it'll be too hard to prove.

[chilly zodiac]

Yh im just not in any way familiar with working with congruences

So i could have easily missed something

[light flicker]

@whole sigil @chilly zodiac wait there's an easier way to check if -1 is a quadratic residue mod m

[chilly zodiac]

How?

[light flicker]

oh lmao whoops

[chilly zodiac]

Yh sorry im tired too lol

[light flicker]

Anyways

You start with the case of figuring out if -1 is a quadratic residue mod p for some prime p

[chilly zodiac]

How do you do that?

[light flicker]

If you know the legendre symbol

Youre trying to find (-1 /p)

It's a well known fact that $a^{(p-1)/2} \equiv \left( \frac{a}{p} \right)\pmod p$

[sterile pumice]

Zopherus:

[light flicker]

so if you let $a = -1$, you get that $\left( \frac{-1}{p} \right) = (-1)^{(p-1)/2}$. And since every prime is $1,3 \bmod 4$, we get that $\left( \frac{-1}{p} \right) = 1$ if and only if $p \equiv 1 \pmod 4$

[sterile pumice]

Zopherus:

[whole sigil]

this is helpful, i've heard about the legendre symbol once before, maybe if i'll study a bit more results about it, i'll be able to figure this out

[light flicker]

Yeah maybe I won't give the rest away then

There are nice properties of this so that you can extend this to all integers m

In a very nice way, just by using the results for primes

[whole sigil]

oh, i see, according to wikipedia it's completely multiplicative on the top half, which would allow us to generalize this for non-primes

and 2 is a special case that we can handle trivially

but is computing the prime decomposition of a number, and then computing the legendre symbol for each of the primes that have an odd power in the decomposition, and then multiplying that really more efficient than just checking half of the numbers until m?

though now that i think of it, i don't really care about efficiency here

i'm not trying to compute as much of this sequence as possible

i'm trying to understand the sequence

and this does give us more understanding

in fact, im pretty sure this solves the problem with just a bit of checking some things

[light flicker]

Computing the legendre symbol for primes is super straightforward, just check if its 1 mod 4 or not

[whole sigil]

yeah

[light flicker]

And multiplying is easy, you're multiplying 1's and -1's

Just count how many -1's you have if you want efficiency I guess

[whole sigil]

if you're doing it by hand, it's way easier of course

but prime decomposition is way harder for a computer than just iterating over a few numbers

[light flicker]

I'm not convinced that's true

For the majority of numbers, prime factorization is pretty fast

If you take m = 10^10, you're squaring numbers up to five hundred billion

[plain fable]

prime decomposition is not that hard for a computer

[light flicker]

And calculating their remainder mod m

[whole sigil]

No known algorithm can factor all integers in polynomial time.

[plain fable]

and

[light flicker]

That really doesn't mean a problem is hard in the real world

[whole sigil]

And iterating over n/2 numbers is better than polynomial time.

literally exponential

[light flicker]

At least, doesn't always mean

There are subexponential algorithms

[whole sigil]

it means a problem is hard in the real world given sufficiently large numbers

[light flicker]

I mean sure, but sufficiently large may mean 10^10^10^10

which is not a real world number

[whole sigil]

well, the difficulty of defactorization is used in RSA, so i bet it's real-world enough

[light flicker]

RSA uses very, very special numbers

Most numbers are not semiprimes

[whole sigil]

if anything, semiprimes are friendlier to the defactorizer than most integers, provided that your purpose is to find a prime decomposition rather than just any factorization

[light flicker]

That is not true

Finding a single prime means you can decrease the size of your number, making testing for divisors easier

[whole sigil]

actually, you might have a point there

anyway, i don't care about efficiency that much anyway, but i do want more understanding of the sequence

which your idea sure provides

[whole sigil]

if we generalized the legendre's symbol to allow p=2, would it still be completely multiplicative?

[light flicker]

@winter bear @ivory patrol This might be intersting for you guys

[winter bear]

seems fun

will check it out when its not 5 am for me lol

[fair lynx]

hi;
can someone rate my proof :

A number n is nonperfectsquare if the only perfect square that divides into n is 1.
Prove that for every positive integer, it can be represented as a product of a nonperfectsquare, and a perfect square.

[stuck lintel]

whomstve did you pung zoph

[fair lynx]

proof :
let n be a nonperfectsquare.
we know that every positive integer could be represented as a product of primes.
so let n = p1p2p3*p4...pn.
We know that for each pi, the exponent = 1, since if exponent > 1,
we can divide pi^2 | n, and n will not be nonperfectsquare.

Let x be any positive intger.
There can be 2 cases :
(1)
x = p1p2p3...pn, where one (or more) pi's will have exponent > 1.
If this is the case, we can factor out these pi's so that they are perfect squares.
The remaining pi's that have exponent = 1 is clearly a nonperfectsquare.
So this is a product of a nonperfectsquare and a perfect square.

(2)
x = p1p2p3...pn where all pi's have exponent = 1.
This is simply the case where p1p2p3...pn is a nonperfectsquare.
Let 1^2 be the perfect square.
Then, x = 1^2 * p1p2p3..pn.
Or, it is the product of a nonperfectsquare and a perfect square.

[fair lynx]

<@&286206848099549185>

[light flicker]

It's fine

[near meadow]

ax ≡b mod m so if we already have a,b,m....then how can we find x quickly ?

[light flicker]

Multiply by the inverse of a

Mod m

[near meadow]

oh i got it now

using this https://www.expii.com/t/solving-linear-congruence-ax-b-mod-n-3389

thanks anyway 😄

[light flicker]

I saw this one a couple years ago

And I remember I could never solve it so

Have at it @stuck lintel @winter bear @fervent crest

[stuck lintel]

[fervent crest]

“Elementary” number theory

Ok first of all

It’s not even obvious to me that LHS is an integer

😔

[supple furnace]

It isn’t

[fervent crest]

Oh right

So multiplicative inverse

Hmm

$\sum_{i=1}^{p-2}\frac{i^i(i+1)^{p-i-1}}{(i+1)^p}$

[sterile pumice]

Whoever:

[fervent crest]

And (i+1)^p is always 1 I believe

Hmm

So

[supple furnace]

(i+1)^p is always i+1

[fervent crest]

[light flicker]

the size of the multiplicative group of Z/pZ is p - 1

[fervent crest]

Oh right

🙃

$\sum_{i=1}^{p-2}i^i(i+1)^{p-i-2}$

[sterile pumice]

Whoever:

[fervent crest]

Hm

And idk what to do other than multiplying by 1

[supple furnace]

Maybe try binomial thm

[fervent crest]

Hm

Seems like it will get dirty

$\sum_{i=1}^{p-2}\sum_{n=0}^{p-i-2}\binom{p-i-2}{n}i^{n+i}$

[sterile pumice]

Whoever:

[fervent crest]

Ok ew wtf is this

[light flicker]

I mean I'm not even sure there's a nice solution

I found it on a facebook group and no one posted a solution

I confirmed that it is true for a couple small cases though

[fervent crest]

Hm

I bet there is an algebra solution

[stoic bear]

I will try this a bit later

[winter bear]

Hmm will try later

I have a thing for the next few hrd

[light flicker]

the nt god comes to our rescue

[winter bear]

Lmao

[light flicker]

I haven't thought about it since a couple years ago either

Maybe I'll think about it some

[fervent crest]

@winter bear how does it feel to be a god?

[winter bear]

Lol it feels like a mockery

[stoic bear]

Did you solve all those problems for usamts @winter bear ? I couldn't so I won't submit but I am interested in solutions

[fervent crest]

I did

Well actually im interested in his solution too

[stoic bear]

Do you think I should submit my 1 complete sol with 2 partials or not even worth it? @fervent crest

[fervent crest]

I really don’t know

:/

[light flicker]

Just submit

There's no harm in submitting

[fervent crest]

I mean it doesnt hurt

Yeah

[stoic bear]

Idt I will submit; it seems in the rules they only want complete solutions

Oh well, it was good practice

[light flicker]

It's usually fine

back in my day people submitted incomplete solutions

[stoic bear]

I just feel that as an 11th grader, my math skills are lacking

[light flicker]

I mean compared to the average 11th grader, you're obviously a billion times better

[stoic bear]

Like especially when I see these younger kids destroying me

[light flicker]

There's always going to be someone better than you

It's best to get over that fact and help it motivate you rather than discourage

[stoic bear]

Yeah, I just gonna keep trying even if I might never be that good

[light flicker]

Hard to say

You've just got to try harder than other people and eventually you'll be "good"

Winning is really not everything

This is coincidentally, the reason I really dislike math competitions

It fosters too much of a hyper competitive attitude in young children

Who only think about winning and are too emotionally attached to how well they do

[stoic bear]

Yeah, I noticed that in younger kids (asians/indians specficially due to parental pressure)

I think math competitions are great for generating interest, but learning should be the goal

[light flicker]

There's a lot of great things about competitions, which is partially why I did them, but all that pressure isn't healthy for young children I think

[stoic bear]

Another thing is that how do you put mathematically related things on your college app for a math major without competitions? I guess research but that is pretty complex for high school

[light flicker]

True and it's one of the hard things

Not necessarily research, but reading ahead like lots of people in here do

Even if you write that down, it's hard for people to believe your word

[stoic bear]

But how do you demonstrate "reading ahead" on a college app?

[light flicker]

So you'd need to do it with a teacher or something which usually can't happen

[stoic bear]

oh you answered nvm

[light flicker]

Yeah which is the unfortunate part

[stoic bear]

I think I am gonna try to take online courses soon - BYU or John Hopkins

[light flicker]

Unfortunately, I'm not sure there's a great solution to this problem

[stoic bear]

Alright nice talk, cya zoph

[light flicker]

The only partial solution is giving more resources to high schoolers to do that sort of thing

Which do happen, things like Canada/USA math camp

https://cdn.discordapp.com/attachments/418981682117345288/633767263652151306/55692939_1008584612862327_2806951334857670656_o.jpg

This got buried so let me repost

[torn escarp]

shot in the dark but, first step to try

$\frac{1}{2^2} + \sum_{k*k^{-1}=1} \frac{k^k}{(k+1)^{k+1}} + \frac{k^{-k^{-1}}}{(k^{-1}+1)^{k^{-1}+1}} $

remove the i=1 term then the rest are pairs that are multiplicative inverses

and so I sum over those pairs like this, looks pretty awful though so I probably will not go down this path immediately

[sterile pumice]

Merosity:

[torn escarp]

alright forget that nonsense, alternative take

$a_i = i^i \ \sum_{i=1}^{p-2} \frac{a_i}{a_{i+1}} = -2 \mod p$

[sterile pumice]

Merosity:

[torn escarp]

might be easier to learn something about the behavior of i^i then look at all the ratios together

[light flicker]

I tried this

i^i has the worst behavior you can imagine lmao

[torn escarp]

I might have a rough path to the solution using it

I started looking at i^i and (p-2-i)^(p-2-i) being similar but inverses

juggling terms around I get:

$\frac{a_{\frac{p-1}{2}}}{a_{\frac{p+1}{2}}} + \sum_{i=1}^{\frac{p-2-1}{2}} \frac{a_i}{a_{i+1}} + \frac{a_{p-1-i}}{a_{p-i}}$

[sterile pumice]

Merosity:

[torn escarp]

need to actually confirm now, but I believe the right sum is all 0, the middle term which I've pulled out on the left however is really:

$\frac{\left(\frac{p-1}{2}\right)^{\frac{p-1}{2}}}{ \left(\frac{p+1}{2}\right)^{\frac{p+1}{2}}} = -2$

[sterile pumice]

Merosity:

[light flicker]

As in each individual term is 0?

[torn escarp]

yeah, although I won't hold my breath I'm not sure that those terms in the sum are 0

I just pulled out the middle term and it seemed to pop out as -2 so maybe they should be reorganized in a different way to cancel out

don't mistake my handwavy brainstorming as some kind of rigorous statement of fact haha

[light flicker]

I think I remember trying this too

Pretty sure those terms aren't 0

[torn escarp]

at the very least, the middle term being -2 seems to be a good sign, idk I think I'll come back to this after I finish doing some important stuff before I can relax and poke around at this more

[light flicker]

Right and it gives a symmetric split of the elements

[solemn raft]

What's an easy way to show -1 isn't a quadratic residue mod 20?

Someone asked on reddit how to show 20x^2 - 19y^2 = 2019 (the post got deleted)

If you look mod 20, you get y^2 = -1 mod 20, and wolfram alpha says that impossible

[quick furnace]

-1 mod 20 is -1 mod 4 and -1 isn't a qr modulo 4

[solemn raft]

Oof yeah lol

[ruby egret]

How does this corollary follow from the above theorem?

[light flicker]

You kind of induct

[ruby egret]

How?

Don't you have to use (a,b,c) = ((a,b), c) ?

[supple furnace]

Well it should be obvious that (a_1,...,a_n)|(a_1,a_2)

[daring ice]

How to prove this: $e_j(r_1,...,r_n)\equiv 0$ mod (p) for elementary polynomials $1\leq j< n$ and $r_1,...,r_n$ are a reduced residue class mod p

[sterile pumice]

Token:

[daring ice]

Basically when you take elementary symmetric polynomials modulo a prime the additive inverses all cancel out.

[hollow bay]

how can I solve for x if x^107 is congruent to 11 modulo 900?

[light flicker]

you use a computer

[hollow bay]

im not supposed to

[light flicker]

Was this a homework problem you were given

[hollow bay]

kinda, its an example in the notes before the homework

[light flicker]

The idea is that you have to use Chinese remainder theorem to break up the mod 900 into smaller problems

where the modulus is the power of a prime

[hollow bay]

I tried dividing in the prime factors and then using fermat little theorem I got x^3 is congruent to 11 mod 5

is that helpful in any way?

[light flicker]

I'm not sure exactly what you mean by dividing in the prime factors

[hollow bay]

ill try to eplain. So the prime factorization of 900 is 2^2 x 3^2 x 5^2

so I just separated the 1st congruence in 3 where the modulos are the primes, like this :
x^107 congruent with 11 mod 2
x^107 congruent with 11 mod 3
x^107 congruent with 11 mod 5

im just not sure if I can do this

are the mods supposed to prime 2^2 ,3^2 and 5^2?

[light flicker]

Yes it needs to be 2^2 etc

That's what the Chinese remainder theorem allows you to do

[hollow bay]

yeah the problem Im having is :
Lets say we have X congruent with 3 mod 11 and then the other mods, I usually say x=11k +3 and keep substituting in the other congruences, but with the exponents I dont know how to do that

[light flicker]

Why can't you do the same?

[hollow bay]

because i would get x=4k+11 and then I would need to solve (4k+11)^107 congruent to 11 mod 9.

[light flicker]

And what's the problem with that

Compared to having it be 2k + 11

[hollow bay]

the problem is not the inside, its the fact it has an exponent, I dont know what to do. In the example I gave it was a linear(If I can call it that) case

[sterile pumice]

Archsys:

[sharp pagoda]

or you can write 3 mod 4

@hollow bay use hensel lifting or Taylor expansion f(x+h)

terms with h²,h³,... will be 0 in modulo

f(x) is x^(107)-11

like for mod 4

you need f(1+2k)=0 mod 4

which is f(1)+2kf'(1)=0 mod 4

cos terms (2k)²,(2k)³, ... are 0 mod 4

-10+2k(107)=0 mod 4

,w solve -10+2k(107)=0 mod 4

-2+2k(3)=0 mod 4

2k=2 mod 4

k=1 mod 4

x=1+2k=1+2(1)=3 mod 4

so x=3 mod 4 is solution for
x^(107)=11 mod 4

,w 3^(107)=11 mod 4

[sterile pumice]

Display results online and refine query

Requested by Nick ( 11111010011 )#3263

[sharp pagoda]

and similarly you can do for x^(107)=11 mod9 ,mod 25

and use CRT

I got x=3 mod 4
x= 5 mod 9
x= 6 mod 25

,w x=3 (mod 4); x= 5 ( mod 9); x=6 (mod 25)

,w solve x=3 (mod 4); x= 5 ( mod 9); x=6 (mod 25)

😼

,w 131=3 (mod 4); 131= 5 ( mod 9); 131=6 (mod 25)

,w 131=3 mod 4

[sterile pumice]

Display results online and refine query

Requested by Nick ( 11111010011 )#3263

[sharp pagoda]

,w 131=5 mod 9

[sterile pumice]

Display results online and refine query

Requested by Nick ( 11111010011 )#3263

[sharp pagoda]

,w 131=6 mod 25

[sterile pumice]

Display results online and refine query

Requested by Nick ( 11111010011 )#3263

[sharp pagoda]

so 131 is a solution for original question

,w (131)^(107)=11 mod 900

[sterile pumice]

Display results online and refine query

Requested by Nick ( 11111010011 )#3263

[twilit rivet]

Hey. Are there any applications of the Prime Number Theorem? Like for example, another proof that was solved with the Prime Number Theorem. Im doing a project on it and dont know what else to write about other than the proof and Chebyshev's weaker PNT.

[broken igloo]

you can write about a stronger version involving the Riemann hypothesis

or different forms about it

maybe prime gaps?

@twilit rivet

maybe about finding primes for RSA?

[twilit rivet]

ok i will look into them thanks!

[hollow bramble]

nah pnt is useless for finding primes for rsa

primes are found by basically brute force

pnt is useful ig for like asymptotic behaviour of primes and having a quick approximation for π(x)

rh just gives a tighter bound

[vestal blaze]

Assuming some bounds on the PNT or equivalently the RH, you can prove certain things about primality tests, for example their deterministic behavior or estimating their complexity.

I think one example for such a test is the Miller-Rabin test.

[hollow bramble]

(tho its usually assumed rh is true when finding primes)

[cunning stump]

any tips on studying this field? I failed this course twice and starting again now

it's the only course I failed so hard

[light flicker]

Depends at what level you're studying

But I don't think the advice is any different for any courses

Work hard, study a lot, ask questions etc

[hollow bramble]

also maybe try to look back at why did you fail, didnt have prereq or just lack of understanding

[sacred junco]

How to multiply base numbers like 76_8 * 57_8?

[stoic bear]

You have 2 main ways

You can multiply but unlike in normal multiplication you carry if greater than 10, you use 8

Or convert to base 10, multiply, and reconvert to base 8

[sacred junco]

How can I carry using 8?

[stoic bear]

So take 23 x 6 as an example

If we use long multiplication, we do 6 x 3 first

Equals 18, so we carry the 1

If it were 23 base 5 times 6 base 5

3x6 equals 18

But this time we carry 2 as there are 2 8's in 18

Key thing to remember is that any number in base n, each digit can only be 0 to n-1

[sacred junco]

What about 76_8 * 57_8?

[stoic bear]

Just do one of the ways I showed you?

[sacred junco]

I keep doing it wrong.

That's why I asked it here.

[stoic bear]

What do you get

[sacred junco]

I think I mess up this step

When you have 76_8 * 57_8, you first do 7 * 6 to get 42, so that's 52_8. So I put down 2, and carry the 5. But when I have to do 7 * 7 = 49. So I have 9 * 8 + 4?

[stoic bear]

49 turns into 61_8 + 5_8 from the carry

[sacred junco]

Why 61_8?

[stoic bear]

7 x 7 equals 49_10 , which is 61_8

[sacred junco]

Ok, but how do I do that without converting to base 10 first?

[stoic bear]

You really are not

[sacred junco]

My book does it. But they don't go over it in detail..

[stoic bear]

When you multiply in base 10, you automatically carry any groups of 10

Same in any other base

http://mathcentral.uregina.ca/QQ/database/QQ.09.13/h/alise1.html

[sacred junco]

I know that?

But how do I carry when I do 7 * 7 like in that example?

[stoic bear]

7 x 7 = 49

How many groups of 8 go into 49

No

8 x 9 equals 72

[sacred junco]

Oh man

I have forgotten multiplication in the natural numbers under 10.

This is embarrassing.

[stoic bear]

May I ask what grade/course this is?

[sacred junco]

No

Why are you asking?

[stoic bear]

You should know your multiplication up to 10 at least. Just curious cause they are important

[sacred junco]

I was joking... I was just making a mistake for some reason. Not sure why.

[stoic bear]

Sorry sarcasm doesn't translate well in text and I am dense

So is you mistake resolved?

Or more q?

[sacred junco]

I have a different question if you don't mind

[stoic bear]

Sure fire away

[sacred junco]

Find the one hundredth positive integer that can be written using no digits other than digits 0 and 1 in base 3.

I think you need to find the 100th base-2 digit instead, but why?

[stoic bear]

Yeah I am fairly certain you are right

Notice that base 3 vs base 2 is just adding the 2 digit as an option

So restricting the digits to 0 and 1 just make it easier to find 100th integer via base 2

[sacred junco]

But wouldn't this just be 100 in base-2?

[stoic bear]

Oh I misinterpreted the q

So the hundredth integer in base 10 that cannot be expressed using the 3 digits in base 3

[sacred junco]

Ok

How?

[stoic bear]

@sacred junco

If you find the 100th smallest integer in base 10, convert that to binary or base 2

Then take those digits in base 3 to convert to base 10

That is how to get the answer

[sacred junco]

@stoic bear What do you mean?

Why would I need to take base 2 and then convert to base 3 and then back to base 10?

[stoic bear]

You are not converting from 2 to 3

You just take the digits that base 2 and transfer the to base 3

In this case the 100th smallest integer is 100

In base 2 that is 1100100

Now you have 1100100 in base 3

Convert that to base 10 and you have your answer

[sacred junco]

But why is what I am asking?

This is what I said earlier

[stoic bear]

So if you only can use 0, 1, 2, then this is similar to a base 2 number

So find the 100th smallest int in base 2

This is 1100100

Because you need a base 3 number without digit 3, this number in base 3 will satisfy the condition s

[sacred junco]

Ok

I think I get it, thanks