elementary-number-theory

[leaden swan]

Ye, That's pretty trivial

[ebon dagger]

explain

pls

[leaden swan]

The coefficient of (p r) contain a factor of p

[ebon dagger]

what is (p r)

[leaden swan]

Since r! and (p-r)! don't contain a factor of p while p! does.(for 0<r<p)

pCr

[ebon dagger]

what is r? there is no r

u mean remainder?

[leaden swan]

The coefficient of n^r in expansion of (1+n)^p is pCr

[ebon dagger]

what is C in pCr

[leaden swan]

Yea,That works too

[ebon dagger]

i never heard of a C

ohhh :P

thx

i need to learn elementary number theory :P

always been my weak point

[sleek cove]

what anime is this from asking for a friend btw

not like im a weeb or smth

[ebon dagger]

@sleek cove Puella Magi Madoka Magica

it's a very very very very deep anime

makes you think

it's the type of anime that makes u think about it for a week after watching

but u gotta watch till the end

[sleek cove]

[light flicker]

i hate weebs wtf

[sleek cove]

ur so cring pls stop

[fervent crest]

[abstract flax]

Lmao, I once saw someone's list of top 10 films and they were all serious good films and then.

10: I know it's not a film, but Puella blah blah.

Then I googled and saw it's just little girls and I laughcried

[ebon dagger]

bro it's so good. its deep and intellectual

someone recommend number theory book

i wanna learn this next year

[deft verge]

I didn't read it but my professor was very enthusiastic about An Illustrated Theory of Numbers by Martin H. Weissman

[fervent crest]

"A Classical Introduction to Modern Number Theory" by Ireland, Rosen

[wind parcel]

what is it asking me to prove with $0_R=1$ and $1_R=2$ ?

[sterile pumice]

cRaZyNiChOlAs12

[wind parcel]

does it want me to prove that its additive identity is 1?

[light flicker]

yes

and the multiplicative identity is 2

[wind parcel]

alright, is the additive and the multiplicative identity always denoted as $0_R$ and $1_R$

[sterile pumice]

cRaZyNiChOlAs12

[light flicker]

yes but depending on context people just write 0 and 1

[wind parcel]

and is the first problem really just 2+3-1? or am i missing something

[light flicker]

yeah thats it

[wind parcel]

is there a reason profs will give easy problems like that? Cause i always feel like the super easy problems are overthought

[light flicker]

I mean, just to get you comfortable with the operations I guess

[wind parcel]

what is the difference between like [a] and a

[light flicker]

in what context?

Usually [a] denotes the equivalence class of a under some equivalence relation

[wind parcel]

like in my problem why is it just a and not [a]

cause isnt it saying a is in ring R

[light flicker]

Uh, there's no equivalence relation? You're just working with the integers

I'm not really sure what you mean

[wind parcel]

i think i get it, if it was a ring like Z6 then it would be [x] whatever x is in Z6

[light flicker]

Right

because we usually think of Z6 as Z/6Z

so you have an equivalence relation on Z where x ~ y if x = y (mod 6)

[wind parcel]

ah alright thanks lol

[regal aspen]

how is this divisible by p?

well, the original problem is

his translation isn't

rip

[fervent crest]

$(n+1)^p=n^p+\binom{p}{1}n^{p-1}+\binom{p}{2}n^{p-2}+\cdots+\binom{p}{p-2}n^2+\binom{p}{p-1}n+1$

[sterile pumice]

Whoever

[fervent crest]

Then, you also know $p\mid\binom{p}{k}$ when $0<k<p$

[sterile pumice]

Whoever

[grave carbon]

is there a formula for finding d(p^r) and sigma(p^r)?

[fervent crest]

Think about it

What are the divisors of p^r

[grave carbon]

1, p^1,....,p^r

[fervent crest]

Exactly yes

Now can you use this information to find d(p^r) and sigma(p^r)

[wind parcel]

whenever i open this chat and see a much more advanced problem than mine it scares me

can a subring have multiple solutions to a identity? like in this it is asking me to prove that $Q sqrt{2}$ is a subring of $Q$ and $Q sqrt{2}=a+b sqrt{2}$

[leaden swan]

There is exactly one identity in Q[sqrt[2]]

Which is 1

[wind parcel]

so like a=0 and b=0 would work but wouldnt a=-bsqrt(2) also work?

wait wut

why 1

[leaden swan]

1(a+b√2)=(a+b√2)

Wait,You mean additive identity

[wind parcel]

yea sorry

my b

[leaden swan]

Yes, There's exactly one identity 0

Because a and b have to be rational

[wind parcel]

oh yea they have to be rational duh

and since sqrt2 isnt irational wouldnt a nonzero rational x irrational gives u a irrational number

[leaden swan]

*nonzero rational

[wind parcel]

lol

[bleak robin]

could someone go through an example with the kronecker symbol with me, lets say Q(root(-7)), for a = 67?

i got 1

[bleak robin]

nvm i found that the FTA doesnt hold

[torn escarp]

trying to gauge the difficulty of a problem I came up with, give it a shot:

Suppose $n,m$ is a solution to $n!+1=m^2$. Show that $n$ is less than the smallest prime divisor of $m$.

[sterile pumice]

Merosity

[sage fern]

||n! + 1 has none of the non-trivial factors n! has , so m^2 doesn't have them, so m doesn't have them?||

||so m doesn't have any non-trivial factors up to and including n, so n is less than the smallest prime factor of m?||

[torn escarp]

yeah that looks pretty good to me

[sage fern]

fun one

[full flower]

is there a way to check that a number is not a multiple of squares besides testing all the squares?
if it helps im taking a cube of an integer + 1 but i want to make sure that this isnt a square or a multiple of a square

[timid pecan]

anyone have any tips to solve this, I'm normally pretty good at number theory stuff but I'm honestly lost for this one

[inner anchor]

Try looking at the residue classes individually (or in pairs)

Eg. Start off by looking what happens if n = 0 or 3 mod 6

[timid pecan]

if it's 0 or 3 mod 6 then we have a multiple of 3 as the sum of the digits so it's divisible by 3 correct? and thus not prime

[inner anchor]

Yes

Very cool

How about 2 or 4

[timid pecan]

hmmm idk

but I get what you're onto

[inner anchor]

Try some small examples

[timid pecan]

I feel like they're divisible by 11

but idk why

I'm struggling to remember divisibility rules other than 3 lmao

[inner anchor]

Lets look at 1111 and try to find if its a multiple of 11

Note that 1100 = 11×100

And so 1111 = 11×100+11

Can you extend this idea

[sage fern]

seems like a trick question?

the fact that it's a repunit has basically nothing to do with it

[timid pecan]

so like for 11111111 we have e.t.c 11 * 1000000 + 11 * 10000 + 11 * 100 + 11

[inner anchor]

Epic

[timid pecan]

so that's gonna be divisible by 11 yeah nice

[sage fern]

oh wait nvm

i can't read

[inner anchor]

I read it wrong first dont worry

[timid pecan]

all good

so does that just leave 1 and 5 mod 6?

[inner anchor]

Yes

But thats all we needed to show

[timid pecan]

great, thanks man

[inner anchor]

Np

[wind parcel]

so when proving that something is a subring and doing the inverse step is it legit just putting negatives in the equation where they negate the original equation given so that it equals 0?

like $a=x+y\sqrt{2}$ and then to prove the inverse $-a+a=0$ so like $-x-y\sqrt{2}+x+y\sqrt{2}=0$

[sterile pumice]

cRaZyNiChOlAs12

[wind parcel]

or for a subring do u only need to prove it is closed by addition and subtraction?

[upbeat wren]

You are assuming negation for real numbers x and y. You must PROVE the negation for the elements of the group.

[inner anchor]

yes

follows from eulers theorem

not sure if 3 is a primitive root mod all 10^n

but thats different from your question

let me check that i understand the question

you wish to show that the powers of three are periodic modulo 10^n?

engineers induction
not like this

have you heard of eulers totient theorem

yes

and for any a coprime to n, we have $a^{\varphi(n)} \equiv 1 \bmod{n}$

[sterile pumice]

Pappa

[inner anchor]

yes

now you can note that in this example, $3^0 \equiv 3^{20} \equiv 1 \bmod{100}$

[sterile pumice]

Pappa

[inner anchor]

and \phi(100) = 40

wait no

ok this is slightly bad

it is 40

well we can show that its periodic

let me think for a moment

okay

i think ive got it

have you heard of the lifting the exponent lemma

its quite common in comp math

also the pattern does not hold

you can check that 3^2500 != 1 mod 10^5

[sacred junco]

how to solve this problem?

[inner anchor]

If it were 1 then 3 would have a period of 2500, which is what your engineers induction predicts

So i can show that the highest power of 2 dividing 3^(4×5^n) is 16

Not sure really

It could be phi(100000) or it could not

I dont think there are any general results that would instantly give you the period

[regal aspen]

@lusty nexus hey

he's talking about LTE if you didn't already notice

[bleak robin]

What is the quadratic field generated by, $$\prod ^{n}_{i=0}\left( \xi -i\right) $$ multiplied by a non-linear factor?

[sterile pumice]

ohNoiAmHere

[light flicker]

What exactly do you mean by this?

[bleak robin]

like i have the polynomial e(e-1)..(e-n)*P(e), where P(e) is nonlinear, is there a way for me to ignore the linear factors?

in making a quadratic field

[light flicker]

I still don't really understand what you're trying to do

Are you looking for the splitting field of this polynomial?

[bleak robin]

yes

[light flicker]

I mean

The splitting field of that polynomial is just going to be the splitting field of P(e) so

[bleak robin]

yea, so thats what i thought, but i wasn't sure cause i couldn't prove it or find it online

thanks :)

[wind parcel]

LEt R be a ring and a,b be in R. (a+b)(a-b)=?

what is this even asking lmfao cause my brain just says immediately to foil but that isnt right

i found a answer on google now but why does it add a and b into the equation? like (a+b)a-(a+b)b why are we allowed to multiply by a and b?

[light flicker]

That answer on google is just foiling or distributing I guess

Foiling is right, it actually follows from the distributive properties of a ring

[wind parcel]

so my textbook asks for the answers if r is not commutative and then if it is like it says just "(a+b)(a-b)" "then what is the answer to a if R is commutative

how would it be that they arent commutative though?

[light flicker]

It's still the exact same

or well, the first step is the same

You're still going to use the distributive law to get (a + b)a + (a + b)(-b)

And then use it again to get a^2 + ba - ab - b^2

So if your ring is commutative, then ba and ab cancel out

but if your ring isn't, then this is all you can do

[wind parcel]

oh that makes since, since if it was commutative ba=ab

gotcha

[light flicker]

right

[exotic plank]

E(15) is isomorphic to $E(3) \times E(5)$ which is isomorphic to $\mathbb{Z}_2 \times \mathbb{Z}_4$ right ?

[sterile pumice]

Otoro

[exotic plank]

Where E(n) is the group of the units (Z/nZ)^x

<@&286206848099549185>

[fervent crest]

Yes

[exotic plank]

Thank you very much

[light flicker]

Can you write out what equation must hold?

Also, this stuff is more appropriate for #groups-rings-fields

[light flicker]

Yes the polynomial is reducible

[torn escarp]

have you learned gauss's lemma?

[light flicker]

Just plug in the numbers that the rational root theorem tells you to, and see that 1/3 is a root

[sacred junco]

Hey

I need help

107*7 = 1 (mod 187)

I take everything to the 7th power

and for some reason when i plug 184 back in, I dont get 6

im not sure what im doing wrong since all my steps seem correct

[light flicker]

It's not true that you can reduce powers by the mod

[light flicker]

It's not quite as straightforward as that

[sacred junco]

Wait what am I missing?

since all the conditions in this theorem are met

[light flicker]

What? It's still true that there's a unique solution

It's just that your method for finding the solution is not valid

[sacred junco]

I'm trying to understand this, why does it work in this case?

and not the case I have above

What's the difference

[light flicker]

Read that first sentence

exponents behave mod phi(105) = 48

In your case, phi(187) = 160

[sacred junco]

oh

[light flicker]

so exponents behave mod 160

[sacred junco]

i remember

[light flicker]

not 187

[sacred junco]

thats my problem

i forgot

thanks for clearing it up

[light flicker]

no problem

[sterile pumice]

beeswax

[grave carbon]

But I'm not quite sure how to use the inductive hypothesis

[torn escarp]

I wouldn't prove it by induction

I just observe that divisors come in pairs and sqrt(n) is the middle

[grave carbon]

Wait, what do you mean when sqrt(n) is in the middle

[glacial shard]

anyone have any ideas on how to show this?

I can tell that for any composite number, (n-2)! would contain all of its factors so it would be equal to itself * an arbitrary x and would therefore be congruent to 0 mod n

but I don't see how a prime number would be specifically 1 mod p

[light flicker]

Have you seen wilson's theorem before?

[sage fern]

i feel like the odd requirement is extraneous

[leaden swan]

Write down the factors of n and order them, sqrt(n) will be in the middle of that ordering

[silver solar]

To Wilson's theorem, yes, but it would seem to me to be a good place to start to tackle this problem

[glacial shard]

no I don't know abt wilson's theorem

[silver solar]

https://en.wikipedia.org/wiki/Wilson's_theorem

[light flicker]

Do you know about inverses mod p?

[sage fern]

pog just proved wilson's theorem independently

very sweet

very lovely

one of these days i will actually learn number theory

[glacial shard]

my bad I went afk I had to take care of something

alright so we just have to divide this by n-1

[light flicker]

Uh

[sage fern]

i mean just prove wilson's theorem it's quite nice

[light flicker]

Do you know that you can divide by n-1

[glacial shard]

I'm not sure im kinda confused

[light flicker]

Mm

One way is to note that n-1 = -1 (mod n)

So if you take wilson's theorem and multiply both sides by -1

[sage fern]

i mean.

everything has an inverse mod p, so you can divide, right? have you covered that stuff?

[grave carbon]

What if sqrt(n) is not an integer? Are we allowed to consider noninteger factors?

[sleek cove]

why would you consider it if its not an integer

sqrt(n) is just an upper bound

[grave carbon]

I sort of see what you mean now. Like for example, n=5, we have d(n)=2 and sqrt(n) is in between 1 and 5. But I’m still unsure how to build a proof around it.

Would we set 1 as our minimum divisor and n as our maximum divisor and then have 1<sqrt(n)<n?

I’m not quite sure how to factor in d(n)

[torn escarp]

show that if you have a*b=n then when a<= sqrt(n) then b>= sqrt(n)

[leaden swan]

What I meant was if you can find a factor x less than sqrt(n),you can always find a factor y=(n/x) greater than sqrt(n)

And for each factor > sqrt(n) you can find a factor < sqrt (n) similarly

i.e,There is a bijection from the set of factors < sqrt (n) to the set of factors > sqrt(n)

[hollow sonnet]

Is there a simple criterion for the sum of two unit fractions to be a unit fraction?

[regal aspen]

yes

Set them up as 1/a + 1/b = 1/c

do a little fiddling, should work out

[hollow sonnet]

I only get a + b | ab, which isn't particularly useful.

[bleak robin]

if 1/a + 1/b = 1/c, then we can see that ab - c(a+b) = 0, for a,b,c unequal to zero, try from here

[regal aspen]

oh nice

That works out really well

[regal aspen]

surely ab = c(a+b) would be better?

much better I think

[bleak robin]

i was thinking ab - ac - bc + c^2 = c^2 or (a-c)(b-c) = c^2

[regal aspen]

isn't mod a and then mod b better?

[bleak robin]

most likely yea

[regal aspen]

Also (a-c)(b-c) = 0

[bleak robin]

i was thinking of getting to 1/n = 1/n+1 + 1/n(n+1)

[regal aspen]

I was thinking 1/2n+ 1/2n = 1/n

[bleak robin]

yea thats probably better

[regal aspen]

mm no yours is pretty good

maybe better

I can't tell

yeah yours is better in terms of motivation

[bleak robin]

can someone help me find solutions for, a^2 + b^2 + c^2 = d^2 + e^2 + f^2 and a + b + c = d + e + f, in the positive integers?

[torn escarp]

hmm interestingly, if (a,b,c,d,e,f) is a solution so is (a+k, b+k, c+k, d+k, e+k, f+k) for an arbitrary k

you can get this by adding 2k of the second equation to the first and 3k^2 to both sides then you get a bunch of a^2+2ka+k^2 + ... which gets (a+k)^2 + ...

this means without loss of generality we can assume something like a=0

[inner anchor]

cant we also get that $ab+bc+ca = de+ef+fd$

[sterile pumice]

Pappa

[inner anchor]

just by $(a+b+c)^2 = (d+e+f)^2$

[sterile pumice]

Pappa

[torn escarp]

sure

[inner anchor]

there is a nontrivial solution

(9, 5, 4, 8, 7, 3)

[torn escarp]

does that follow from what you just wrote or is it something you got randomly

[inner anchor]

no connection

tried starting from pythagorean triples

[torn escarp]

from what I said, using that there are infinitely many more

just subtract or add 1 to every number in it

(1,5,6,2,3,7)

tried to put it in ascending order as best as possible with a=1

and call this like "primitive form" or something

I like what you said about pythagorean triples, we can always just use any two pythagorean triples to produce a solution

well, I guess we also need that extra condition

interesting, I think it can be simplified quite a bit

we can assume they're all relatively prime, this means there's at least one odd number on each side of the equation. If they're the same we can remove them and we just have a sum of two squares on each side.

so let's assume they're not equal, without loss of generality suppose the odd numbers are a,d and a<d

now we can translate by - (a+d)/2 and we will end up with another valid solution

we will end up with a becoming (-n)^2 and d becoming n^2 which again cancels out

so we can focus on just solving b^2+c^2=e^2+f^2

[bleak robin]

thank you thats really helpful

[torn escarp]

oh I should mention, solutions to that last one can be be boiled down to looking at the factorization of an integer in the gaussian integers

the number of ways to factor a number as a sum of two squares boils down to basically checking stuff about what the prime factors are mod 4

[grave carbon]

So, I'm trying to prove $$p^2 \mid n \implies n \nmid \phi(n) \sigma(n)+1,$$ and I'm trying to prove the contrapositive. I tried to write n as a factor of primes $p_{i}$, but I'm kind of stuck. I was wondering if someone is able to help me out with the proof

[sterile pumice]

beeswax

[grave carbon]

<@&286206848099549185>

[leaden swan]

Note that $\phi(p^k)\sigma(p^k)=p^{2k}-p^{k-1} $
Now let's say n=p^k q^m...

Weird

Now if n divides $\phi(n)\sigma(n)+1$

[sterile pumice]

DrunkenDrake

[leaden swan]

That implies $p^k \vert \phi(n) \sigma(n)+1 \implies p^k \vert (p^{2k}-p^{k-1})m +1$ where m is a positive integer (more specially it is $(q^{2m}-q^{m-1})...$)

[sterile pumice]

DrunkenDrake

[leaden swan]

That implies $mp^{k-1}-1=0 \mod p^k$ that is $p^{k-1}$ is a unit in $Z/p^kZ$

[sterile pumice]

DrunkenDrake

[leaden swan]

But that is possible only if k-1=0 since otherwise p^{k-1} and p^k are not coprime

Implying k=1

That is n is squarefree,since this can be repeated with any prime in the prime factorisation of n

This works because \phi(n) \sigma(n) is multiplicative

[grave carbon]

For this, we're using the fact that $$ \sigma(p^k) = \frac{p^{k+1}-1}{p-1} $$ right?

[sterile pumice]

beeswax

[leaden swan]

Yes

Also $\phi(p^k)=p^k-p^{k-1}$

[sterile pumice]

DrunkenDrake

[grave carbon]

Why do p^{k-1} and p^k have to be coprime?

[leaden swan]

If a is a unit in Z/bZ (a,b)=1.
Suppose ak=1 mod b this implies
ak=1+bn for some n which implies 1=ak-bn which implies gcd(a,b) divides 1,i.e., gcd(a,b)=1

(or -1)

[gentle lily]

To begin, let us first "re-word" what the problem is asking for. Instead of proving the fact that the number $2^{2^n} + 2^{2^{n - 1}} + 1$ has at least $n$ $\textbf{prime}$ factors, we can instead prove that it has at least $n$ positive factors, not necessarily prime. This is because, if a value it not prime, it has at least $2$ prime factors, meaning $n$ positive factors will surely suffice.

Now, let us factorize our value. To do so, let $a = 2^{2^{n - 1}}$. Substituting this in, we get the following:
$$a^2 + a + 1.$$
Note that our first term is $a^2$ because
$$2^{2^{n - 1}} \cdot 2^{2^{n - 1}} = 2^{2^{n - 1} + 2^{n - 1}} = 2^{2 \cdot 2^{n - 1}} = 2^{2^{n}},$$
by exponent properties. Let us now create a perfect square by adding and then subtracting an $a$ to get the following:
$$a^2 + a + 1 + a - a = a^2 + 2a + 1 - a = (a + 1)^2 - a.$$
Notice, however, that we can rewrite this expression as such:
$$(a + 1)^2 - a = (a + 1)^2 - (\sqrt{a})^2 = (a + \sqrt{a} + 1)(a - \sqrt{a} + 1),$$
by difference of squares. It is now time to substitute our value back in, giving us
$$(2^{2^{n - 1}} + \sqrt{2^{2^{n - 1}}} + 1)(2^{2^{n - 1}} - \sqrt{2^{2^{n - 1}}} + 1).$$
Now we must ask, what is $\sqrt{2^{2^{n - 1}}}$? We note that
$$2^{2^{n - 2}} \cdot 2^{2^{n - 2}} = 2^{2^{n - 1}},$$
thus $\sqrt{2^{2^{n - 1}}} = 2^{2^{n - 2}}$. Using this, we get the expression
$$(2^{2^{n - 1}} + 2^{2^{n - 2}} + 1)(2^{2^{n - 1}} - 2^{2^{n - 2}} + 1).$$

We now utilize induction to finalize our proof. We begin by testing our base case, $n = 1$. When $n = 1$, we have
$$(2^{2^{0}} + 2^{2^{-1}} + 1)(2^{2^{0}} - 2^{2^{-1}} + 1) = (2 + \sqrt{2} + 1)(2 - \sqrt{2} + 1) = (3 + \sqrt{2})(3 - \sqrt{2}) = 9 - 2 = 7.$$
Notice that this checks out, as $7$ does indeed have at least one prime factor (in this case, exactly one). Suppose that, for some integer $k > 1$,
$$(2^{2^{k - 1}} + 2^{2^{k - 2}} + 1)(2^{2^{k - 1}} - 2^{2^{k - 2}} + 1)$$
has at least $k$ positive factors (by our argument at the beginning of the solution, proving this will simultaneously prove the problem statement). We now prove that, for $n = k + 1$,
$$(2^{2^{k}} + 2^{2^{k - 1}} + 1)(2^{2^{k}} - 2^{2^{k - 1}} + 1)$$
has at least $k + 1$ positive factors. We notice something beautiful here. Our first trinomial in the factorization, $2^{2^{k}} + 2^{2^{k - 1}} + 1$, is exactly $(2^{2^{k - 1}} + 2^{2^{k - 2}} + 1)(2^{2^{k - 1}} - 2^{2^{k - 2}} + 1)$, the expression from our induction hypothesis! Finally, we conclude that $n = k + 1$ does in fact give us at least $k + 1$ factors, as we have $k$ at least $k$ factors from our first trinomial, and at least one factor from our second trinomial! Thus, by mathematical induction, this concludes our proof. $\blacksquare$

[sterile pumice]

LifeSource

LifeSource

[gentle lily]

Did I write this correctly?

[bleak robin]

Im not reviewing the proof because that looks fine, but a stylistic decission i choose to make is to minimize the us of "we can see" and similair expressions and just go to the point, it helps with flow. But it looks good 👏

I guess what im trying to say is the proof is wordy

[gentle lily]

Thank you

[light flicker]

Are you sure it's written as 3 * 0.5? And not 3 * (1/2) or 3 * 2^{-1}?

[sleek cove]

yes im sure

[sage fern]

ig they were just taking 0.5 = 2^-1 = 3

[terse acorn]

Anyone has any tips for this one: For any integer $a \geq 1$, there are infinitely many integers $n$ such that $a \mid \sigma (n)$, where $\sigma$ is the sum of all positive divisors of $n$?

[sterile pumice]

Jing

[terse acorn]

I can only think of using multiplicatity of sigma function

[leaden swan]

Solving for a being prime powers is enough to solve the general case

Let's say a=p^m

Consider n=p^{m+1}k where k is coprime to p

That should be enough to solve the problem

[terse acorn]

Oh thanks for the suggestion. I thought about prime powers, but in the form of a or n as product of prime powers

[leaden swan]

Yea,This generalizes nicely into that

Wait,I thought that was phi

mb

[terse acorn]

No, sigma, the sum of divisors of n. It's also multiplicitive

[leaden swan]

Still you only need to consider prime powers since multiplicative

[terse acorn]

Yeah

[terse acorn]

For "p" in this one, do you in fact mean another prime "q"?

[leaden swan]

Ok,That solution is completely wrong(Assumed that was phi function)

Just take a different prime q,such that p doesn't divide q-1(This is sufficient to make sure that (q-1) does have an inverse in Z/p^mZ)

Now (1+q+q^2...+q^{k}) mod p^m=(q^{k+1}-1)(q-1)^-1 mod p^m

Now you can clearly find a k such that q^{k+1}-1=0 mod p^m(if q!=p)

n=q^k m where k is a number that satisfies that condition and m is coprime to q^k should be enough,I think

[terse acorn]

Thanks, I will think about it

[leaden swan]

Ok,I have a much better proof:
Take q!=p and consider the set
{1,1+q,1+q+q^2,1+q+q^2+q^3...}

Now,There are finite no of remainders under division by p^m

So,There are 2 elements which leave the same remainder by pigeonhole

[terse acorn]

We learned Dirichlet theorem on APs and I thought of perhaps using that

[leaden swan]

i.e.,p^m divides (q^k+q^{k+1}...q^{n}) for some k,n

[terse acorn]

But I think yours works as well. We don't necessarily need to use Dirichlet.

[leaden swan]

How were you planning to use Dirichlet here?

[terse acorn]

That didn't work out very well

[terse acorn]

So you mean if there are two such numbers, m and n for m > n, then p^m divides m - n?

[leaden swan]

Yes

I mean m and n from that set

[terse acorn]

of course

[terse acorn]

Thank you @leaden swan , I just worked it out. It's really a clever and smart argument. It reminds me of some math-competition-flavor problems I have seen.

[terse acorn]

But that only implies $\sigma (m) - \sigma (n)$ is divisible by $p^{m}$, it does not tell us what is the number, say $x$, such that $\sigma (x) = \sigma (m) - \sigma (n)$.

[sterile pumice]

Jing

[leaden swan]

You understood this step?

Now p^m does not divide q^k

Because p!=q

So p^m has to divide (1+q+q^2...q^{n-k}) which is sigma(q^{n-k})

i.e., There's a r such that p^m divides sigma(q^r)

For any prime q!=p

Now,To finish this for general case, let's say a=${p_1}^{n_1}{p_2}^{n_2}...{p_k}^{n_k}$ consider the numbers of the form
${q_1}^{r_1}{q_2}^{r_2}...{q_k}^{n_k}, \text{where } {q_1}!={p_1},{r_1}: {p_1} \vert \sigma({q_1}^{r_1}),q_2: q_2!=p_2,{r_2}: {p_2} \vert \sigma({q_2}^{r_2}) \land q_i !=q_j \forall i!=j$

[sterile pumice]

DrunkenDrake

[leaden swan]

Well that times m, where m is a number not containing any of those prime factors

Well q_1!=q_2(and so on) because then sigma(n) decomposes nicely into sigmas of prime powers

[terse acorn]

Thanks! This is the step I missed.

[terse acorn]

What do you mean by $r_{1} : p_{1}$?

[sterile pumice]

Jing

[leaden swan]

r_1 such that

Should have used |

My bad

q_i =q_j only if i=j,btw forgot to add that

[inner anchor]

Dirichlet is kinda overkill but it will work like this: Note that for any prime $p$, $\sigma(p) = p+1$. Now $a | \sigma(p) = p+1 \implies p \equiv -1 \bmod a$, for which we have infinitely many solutions by dirichlet.

[sterile pumice]

Pappa

[inner anchor]

I also think that all numbers of the form $p^{\varphi \left(a\right)-1}k{,}\ \gcd \left(a{,}p-1\right)=1$ work

[sterile pumice]

Pappa

[terse acorn]

Wow, this is really really short...

[inner anchor]

i cant personally find any errors with it

only problem is that it uses a super strong theorem in dirichlet

[terse acorn]

Well, we covered this theorem this week, so using it is anticipated... One hint from previous problem is "here and in some of the forthcoming problems use Dirichlet’s Theorem."

[inner anchor]

well then its fine ig

[keen ivy]

any help for this question?: x^12 = 23 mod 41, given 7 is prim root of 41
solve for x
I think i found out since 23^40 = 1 mod 41, and gcd(12, 40) = 4, then 23^10 = 1 mod 41 and there are 4 solutions
but im not sure where to go from there

[left sigil]

By calculation, you should be able to find that $7^{4}\equiv23\mod41$. Thus the question becomes to solve $x^{12}\equiv7^{4}\mod41$, given that $7$ is a primitive root of $41$. This should be somewhat easier. @keen ivy

[sterile pumice]

Bannanachair Monarch

[keen ivy]

oh true

thank you, what does 7 being a primitive root imply tho in terms of what you suggested

so x^3 = 7 mod 41?

[left sigil]

The fact that 7 is a primitive root means that every number in $\mathbb{Z}/41\mathbb{Z}$ can be written as a power of $7$. If you know any abstract algebra, it means that 7 is a generator of the cyclic group of order 41, and that 7 has order 41.

[sterile pumice]

Bannanachair Monarch

[left sigil]

That is, $7^{41}=7$, and there is no $n<41\in\mathbb{Z}$ such that $7^{n}=41$.

[sterile pumice]

Bannanachair Monarch

[keen ivy]

Ohh i see thank you!

do you mean phi(41) in the exponent btw?

[sacred junco]

y is that entire K[x]? (K is a field, irr_K(a) is minimal monic polynomial of a over K)

[light flicker]

K[x] is a PID

[sacred junco]

oh ok ye so its sth like since irr doesnt divide g then g = f*irr + element of K therefore element of K is in the ideal so 1 is as well?

[light flicker]

uh, how do you know it's + element of K? I'm not sure that's true

[sacred junco]

oh wait ure right, just of deg < than deg irr

[light flicker]

Think about it like this, since its PID, you know that that ideal is generated by one element, say h(x)

so that means that h(x) divides both irr_K(a) and g(x)

[sacred junco]

ok and irr irreducible so h in K?

or h = irr but cant cuz need to divide g

[light flicker]

yeah

[inner anchor]

Is it possible to say when the equation x^2-dy^3 = n has infinitely many solutions for fixed d and n

im not looking for a complete criterion, as that would probably be exceedingly complicated

but if there exist infinitely many solutions in specific cases

[light flicker]

Does it ever have infinitely many? By Siegel's theorem, elliptic curves only have finitely many integral points @inner anchor

I guess this only works in the case that n is not 0, since otherwise the curve is singular

if n = 0, then you always have infinitely many solutions

[torn escarp]

for fun, when $n=0$ the general solution for integers $k, z$ is $x=d^{3k+2}z^3$ and $y=d^{2k+1}z^2$

[sterile pumice]

Merosity

[torn escarp]

oh the k is redundant, w/e

[shut echo]

Can this be done with Chinese Remainder Theorem?I got f(x)x^100+g(x)(x-2)^3=1 but couldn't proceed

[torn escarp]

nah use euclidean division

I'm not sure how brave that actually requires you to be 😳

maybe there's a trick, where did you get this problem

[shut echo]

yeah there is a trick using p' and stuff
i was wondering if the euclidean way is always this hard

it's from CMI entrance

[shut echo]

https://www.wolframalpha.com/input/?i=PolynomialExtendedGCD[+x^100%2C+(x-2)^3%2C+x+]

[torn escarp]

yeah I worked it out with a calculator too that's why haha

at least that's possible to write down

$$p(x)=\left(\frac{2525}{2535301200456458802993406410752}x^{2} \ -\frac{1275}{316912650057057350374175801344}x \ +\frac{5151}{1267650600228229401496703205376}\right)x^{100}+1$$

[sterile pumice]

Merosity

[torn escarp]

whatever

if I were to try to reverse engineer some trick I'd start looking at the prime factorization of those numbers or something, idk any method

what's the trick with p'? something to do with the repeated root in (x-2)^3?

the denominators are all powers of 2, I'm guessing shift both polynomials by 2 possibly

[shut echo]

p' has a factor of x^99(x-2)^2 so it's some constant times that

Since x^99 and (x-2)^2 are factors of p'(x) and they're coprime

So integrate p'(x) and you'd get p(x)

To find integration constant c and the constant k (p'=kx^99(x-2)^2) we'd use p(2)=2 and p(0)=1

[floral ice]

Let $g(t+s) = g(t)g(s)$ for $s, t > 0$. I should show that $g(\frac{p}{q}) = g(1)^{\frac{p}{q}}$ for $p, q \in \mathbb{N}$. I can get $p$ into the exponent easily however im lost on $q$ any ideas?

[sterile pumice]

Kas.st

[floral ice]

I feel like im missing something number theory related

[light flicker]

how can you get p into the exponent?

[floral ice]

$g(p * \frac{1}{q}) = g(\frac{1}{q} + \frac{1}{q} + ... + \frac{1}{q}) = g(\frac{1}{q})^p$

[sterile pumice]

Kas.st

[light flicker]

Right, now try to do this "backwards" in some sense

you have that $g(1) = g\left(\frac{1}{q} + \cdots + \frac{1}{q}\right) = g\left( \frac{1}{q}\right)^q$

[sterile pumice]

Zopherus

[floral ice]

wow

didnt think of that thanks

[grave carbon]

I am working on this proof, and I was wondering if someone could help me out. I’m not quite sure where to go next. Would it help to write
ak=b?

[fervent crest]

Well it’s probably useful to write the formula for phi a bit differently

Right now they are product of rational numbers

But you want to prove something about integers

It’s better to write $\varphi(p^k)=p^{k-1}(p-1)$

[sterile pumice]

Whoever

[sterile pumice]

DrunkenDrake

[leaden swan]

Where q is a number coprime to all those primes and $\beta_{i} \geq \alpha_{i} \forall i$

[sterile pumice]

DrunkenDrake

[leaden swan]

@grave carbon

[grave carbon]

Why $\beta_i \geq \alpha_i$ and how does that factor $q$ help?

[sterile pumice]

beeswax

[leaden swan]

That's by defn of divisibility

If a|b b should have higher prime powers for primes present in a

Because you can't reduce prime powers by multiplying with an integer

That q is for all the prime powers that exist in b but not in a

Like 2|12 and 12 has 3^1 in factorisation while 2 has 3^0

[grave carbon]

I see. I'll work with this and come back if I have more questions. Thank you!

[crude thicket]

Proof: If p is a prime number descirbed as p =3k-1 k element N, there is a k' element N for that p=6k'-1
I got no idea , how to start this proof. could anyone try to explain me pls

[torn escarp]

look at it mod 2

motivated by the fact that we're trying to show that k is really an even number 2k'

[crude thicket]

so i have to show that 2|6k'-1 ?

[torn escarp]

no, definitely not

6k'-1=p

p is a prime, it's not divisible by 2

I assume you left out that p is a prime not equal to 2

since it's false in that case

2=3*1-1 here k=1 and there's no k'

like I said, look at p=3k-1 mod 2

we're trying to show k is even

[crude thicket]

ok great thx!

[grave carbon]

I’m having some trouble on the inductive step, so I was wondering if someone could help me on this one

[sleek cove]

did the prof/book want you to use induction

[grave carbon]

It was just a hint, but it seems like a good approach

Is there an easier way?

[grave carbon]

Is it something about expanding that product?

[leaden swan]

Induction on number of primes in n?

Like say that result is true if there are k primes in prime factorisation of n

And show that implies the result if n were made up of (k+1) primes

[grave carbon]

Yeah, I'm a little stuck on this step

[sleek cove]

i would have figured you could manipulate one side somewhat "easily" to the other. you usually can w these

[inner anchor]

induction will probably work, as you will only have to sum over all squarefree divisors of n, but cant you just use the fact that $\mu(n) \varphi(n)$ is multiplicative to prove the statement for prime powers

[sterile pumice]

Pappa

[inner anchor]

some sort of inclusion-exclusion will probably come up in the induction

[exotic plank]

question : why are there $2^{n-1}$ quadratic non-residues of $p=2^{n}+1$, where p is prime

[sterile pumice]

Otoro

[exotic plank]

<@&286206848099549185>

[inner anchor]

half of all invertible elements in Zp are quadratic residues and so the other half are nonresidues

for a proof the existence of a primitive root should be enough

[unreal canopy]

Hi there, can anybody help me with this question? It is on analytic number theory: Primes in arithmetic progression

[light flicker]

@unreal canopy what have you tried?

[unreal canopy]

I have managed to find a solution from Tom Apostol's Introduction to Analytic Number Theory. Thank you for the help

[sleek cove]

thank you @light flicker , and @fervent crest

[exotic plank]

For an odd prime p, if $p \equiv 2 mod 3$ then there is p-1 cubic residues and 0 nonresidues. But $(p-1)^{3} \equiv (-1) mod p$ so is p-1 a nonresidue or what does this means

[sterile pumice]

Otoro

[leaden swan]

It means (p-1) is a residue

Because (p-1)=-1 mod p

@exotic plank

[exotic plank]

But isn't the residues congruent to 1 instead of -1 ?

Or is that only the case for quadratic

@leaden swan

[leaden swan]

What's your defn of residue?

afaik, a number p is a cubic residue in mod a if there is a number x such that x^3=p mod a

[exotic plank]

Ohhhh cause in my head Euler's criterion stuck with me so i memorised 1 and -1

Ahhhhhh so $p-1 \equiv (-1)^3 \equiv -1 mod p$ hence a cubic residue

[sterile pumice]

Otoro

[exotic plank]

Gotcha thanks @leaden swan

I have one more question. Why do a lot of these proofs regarding residues start with letting g be a primitive root ? Is this a common technique, because as far as I know, primitive roots are not residues right ?!

[leaden swan]

ig,so

Tho I am not very familiar with this

[exotic plank]

No worries thank you though

[muted notch]

https://www.youtube.com/watch?v=19SW3P_PRHQ

[inner anchor]

Working with primitive roots is quite convenient in this case

Like the product of residues is a residue and so on

Primitive roots are just super nice in general

[exotic plank]

So in a way it simplifies the working ?

[inner anchor]

Yeah

[bleak robin]

Up to a_k-1 to how would I find a soltution in the integers with this equal to zero?

[light flicker]

are you looking for a solution of q that makes this zero?

@bleak robin

[bleak robin]

kind of

[light flicker]

kind of?

[bleak robin]

so i looked only at the case of k = 3, i did something like this;

q^2 - (a + b + c)q + (ab + bc + ca).

Notice that if we pick two integers N and M and want to get q^2 - Mq + N as the interesting factor what we need to do is to solve the system (in integers!) that follows:
a + b + c = M
ab + bc + ca = N
and if you substitute c = M - a - b into the second equation, we get that the condition on a and b is

a^2 + 2ab + b^2 - M(a + b) + N = 0.

That is, (a, b) is an integer solution to the equation

x^2 + xy + y^2 - M(x + y) + N = 0. And solved this new equation.

I want to move this same method up to higher k

[light flicker]

should be -M(a + b) I think

[bleak robin]

yea it is

i misstyped it

[light flicker]

Don't know if anything will work for higher k

[light flicker]

yeah I mean, this kind of question falls into the realm of hard arithmetic geometry questions usually

falting's tells us that in a lot of cases, there are only going to be finitely many solutions at least

[bleak robin]

yea, i found infinite solutions for when it is k = 3 but for the rest im not sure yet

[light flicker]

yeah this seems pretty hard in general

[static stirrup]

Is this the right place to go for talk about sets?

[stiff rivet]

basic questions about sets is probably better in #discrete-math or #proofs-and-logic

[static stirrup]

Thank you.

[full flower]

Let n1 < n2 < · · · < nφ(m) be the integers between 1 and m which are relatively prime to m including n1 = 1. Let
N = n1n2 ···nφ(m)
be their product. Show that either
N≡1(modm) or N≡−1(modm)

how would i get started with that?

it seems similar to wilsons theorm

[bleak robin]

Did you try using Wilson's theorem?

[sacred junco]

the heck this place is called elementary-number-theory and im in elementary school and wth is all this

i came here for elementary stuff xD

[leaden swan]

undergrad≈elementary school

[grave carbon]

^

Anyway, how would I find the number of integers $n \leq 1000$ that have a primitive element in modulo n without using brute force?

[sterile pumice]

beeswax

[fervent crest]

Well integers modulo n has a primitive element iff n is 2, 4, p^k, or 2p^k where p is an odd prime and k is positive integer, so you can first list all primes under 1000 and see what power of it exceeds 1000. I think this is probably the best you can do

[leaden swan]

This might be helpful

product of 2 cyclic groups is cyclic iff gcd of their orders is 1

[fervent crest]

Use the idea of wilson's theorem's proof. An element is either equal to its own inverse or not. If it is not equal to its own inverse then it cancels in the product. So N is just the product of all elements that equal to its own inverse. See that these elements satisfy x^2=1 (mod n). Use chinese remainder theorem to reduce this equation to modulo prime powers. Then show that x^2=1 (mod p^k) has solutions {-1,1} if p odd or p=2 and k=2; {1} if p=2, r=1; and {1,-1,2^{k-1}-1,2^{k-1}+1} if p=2, r≥3. Then use this result to say something about each coordinate of element x in the ring shown in (1) in #elementary-number-theory message. Then conclude

Actually, this is overkill

just pair x with n-x

they are always distinct and coprime with n iff the other one is, and their product is -1 so the overall product must be (-1)^k for some natural number k

[sacred junco]

Hey can someone help me?

I have zero idea how to proceed with this problem

unit means relatively prime to pq

generator means primitive root

nvm this problem is literally guessing and checking ugh

[sacred junco]

that was so obnoxious

[grave carbon]

I’m not really sure how to start this. Would like some help

[light flicker]

@grave carbon try some examples maybe to see what happens?

[proper sleet]

Is there a notation which describes each integer similarly to this:
\begin{itemize}
\item 0 is shown as 0 \
\item 1 is shown as $(0,\cdots)$ \
\item $i$th prime number is shown as $(\underbrace{0,}_{i-1 \text{ times}}, \cdots)$
\item $2^3 \times 3^5$ is shown as $(3,5, \cdots)$
\end{itemize}

[torn escarp]

what's "..."?

and no, probably not, but looks like you just invented it, you don't need permission to make things like this

although it doesn't seem particularly well defined so far

[sterile pumice]

JohnDark

[proper sleet]

... means infinitely many zeroes

[torn escarp]

I see, your ith prime number should have a 1 then, you're making infinite sequences where each entry is the exponent on the prime factorization

[proper sleet]

According to the fundamental theorem of arithmetic, such representation is unique

[torn escarp]

you could extend this to rational numbers too, so you have multiplication of numbers corresponds to addition of these sequences

[proper sleet]

You are correct

[torn escarp]

you could extend it to 0 by putting infinity in all the entries too I suppose too, sure why not

[proper sleet]

It would be 1

[torn escarp]

what would be

[proper sleet]

Wait, infinity?

Sorry, I misread your message

[torn escarp]

sure, 0 is divisible by every prime infinitely many times

well, it's kind of a joke, there's no reason to extend this to 0 I think because it doesn't really have a prime factorization

[light flicker]

https://math.stackexchange.com/questions/898724/show-that-mathbb-zx-and-mathbb-q-0-cdot-are-isomorphic-groups

[torn escarp]

you might also add an extra place to the left which can take on 0 or 1 as a value to represent (-1)^n being positive or negative

[proper sleet]

If such notation already existed, it would save me from the need to explain the notation in detals

Well, thank you anyway!

[torn escarp]

there's nothing to explain

[proper sleet]

I'm going to perform some arithmetic in such notation

[torn escarp]

you're just representing the exponents of a prime factorization in a sequence

[proper sleet]

I'm given a task to show how to perform Gauss-Jordan elimination on integer matrices and show when it is possible at all, which I suppose means that I have to show some magic with divisibility

[light flicker]

Smith normal form might be related to that question

[rocky moss]

May I ask about course of values recursion here or should I probably try it in advanced number theory?

[light marsh]

guys what exactly is zorns lemma

[spare tangle]

What do you do once you have the fundamental solution to Pell's equation? e.g. $x^2−37y^2=1$ and now you want solutions to $x^2−37y^2=27$

[sterile pumice]

WhiteBerry

[inner anchor]

You need a particular solution of the second equation, (a, b). Now (a+b sqrt(D))(x+ysqrt(D)) is a solution, where (x, y) is a solution the first equation

Finding every family of solutions is probably very difficlt

[leaden swan]

https://www.imomath.com/index.php?options=615

This is actually pretty good

[sacred junco]

@next thunder I don't have rights to access the advanced channel, but why don't you just prove that J is an ideal of R using the definition?

I don't think J is equal to R

At least the set of elements is not necessarily equal

J has an additional property that the right product gives the 0 element so why would they be "equal" as you claim?

[chrome bluff]

,iamadvanced

[sterile pumice]

You already have the selfroles Advanced, do you want to remove them? (y(es)/n(o))
(Tip: use ,iamnot to remove roles without this prompt.)

[chrome bluff]

Do that to gain access

[sterile pumice]

Session timed out waiting for user response.

Mar 30, 2021, 6:11 AM

[terse acorn]

Does anyone have any hints for this problem: Prove that among three consecutive integers there is always one with at least two different prime factors, except the triplets 1,2,3; 2,3,4; 3,4,5; 7,8,9.

I tried to use proof by contradiction: Like first two numbers are prime powers, and the third one cannot be, but couldn't prove so. I also thought about sieve method, but we haven't covered that

[inner anchor]

contradiction seems good

by our contradiction assumption we have 3 consecutive numbers, each of which is a prime power

[terse acorn]

But that's Catalan conjecture...

I just saw that

[inner anchor]

not quite

so you know that the middle number has to be even, and is therefore a power of two

[leaden swan]

Ok, Here's a simple proof

Note that a number out of those 3 is divisible by 3

If that number is not a power of 3,we are done

[terse acorn]

also by 2, since 3 consective numbers are divided by 3! = 6

[leaden swan]

Now take cases

[terse acorn]

Sorry, but why is this so?

[inner anchor]

if the first number is even, then so is the third number as well

both would have to be powers of two

which is impossible, for our smallest number is greater than 7

probably here letting the middle number be 2^n and looking at cases when n is odd and even is the way to go

[terse acorn]

yeah thanks, I will think about this approach

[inner anchor]

when n even you have that 2^n-1 is divisible by three and is therefore a power of three

Showing that the only solution to $|3^n-2^m| = 1$ is $n=2, m =3$ is enough

[sterile pumice]

Pappa

[inner anchor]

Which isnt too bad

[terse acorn]

Do you mean we get this ("is therefore a power of three") from assumption?

[inner anchor]

Yes

[terse acorn]

Do you mean that if it's a power of 3, then the number before/after it is even and cannot be a power of 2, so we are done?

[leaden swan]

idk I didn't really think this through

Ye,That works

[inner anchor]

As a full proof?

[terse acorn]

No, as two separate proofs. Do I miss something in other one?

[inner anchor]

im not sure you motivate this without finding the solutions to this: Showing that the only solution to $|3^n-2^m| = 1$ is $n=2, m =3$ is enough

[sterile pumice]

Pappa

[leaden swan]

Yea,Do that

[terse acorn]

With this as a lemma or a special case of Catalan

[inner anchor]

are you allowed to assume catalan

its a bit of a nuke

this can be shown with the classic tools of casebash and checking moduli

[terse acorn]

Thanks. Yeah I'm not sure, so I sent prof an email asking for clarification, but you are right that it can be proved with elementary tools

[bleak robin]

How would I find the number of $i < n$ that can be written $p_{1}^a * p_{2}^b = i$ for two primes greater than zero?

[sterile pumice]

ohNoiAmHere

[sacred junco]

do you have any other requirements?

[bleak robin]

n is prime in one case

and in the other it is prime and written as p_n * p_m

[inner anchor]

you probably wont get anything too nice

when a and b are fixed to be 1 you want to find the number of semiprimes less than n, which is apparently given by this

pi_2 is the semiprime counting function

maybe asymptotics or densities would be more manageable

https://math.stackexchange.com/questions/107228/question-on-semi-prime-counting-functions?rq=1

here is a stackexchange thread that comes somewhat close to what you are asking

[bleak robin]

thank you!

[inner anchor]

also check out the hardy-ramanujan theorem

okay it isnt super close to what you are asking

It does tell you that the density of numbers that have only two prime factors is zero in naturals

[sacred junco]

Can someone explain this?

why does 17 = 1 mod 8, mean this will have for 4 solutions

and is this true for all quadratic questions

[light flicker]

what does DRP mean here?

some quadratic equations only have two solutions

[sacred junco]

discrete root problem

i solved the question on the HW

im confused on why 17 = 1 mod 8, mean that x^2 = 17 (mod 8) has 4 solutions

[light flicker]

idk what you've done in your class but the idea is that

x^2 = a (mod 8) with odd a has solutions if and only if a = 1

and in that case, there are 4 solutions, x = 1,3,5,7

[leaden swan]

Say a is a number which cannot be written as sum of 2 squares. Can a(b^2+c^2) be sum of 2 squares?

[inner anchor]

no

a number can be written as the sum of two squares if and only if the primes of the form 4k+3 in its factorization have even powers

[leaden swan]

Ok,That follows from Z[i] being a UFD right?

[inner anchor]

uhhh

probably

ive just seen an different proof using thues lemma

[sly anvil]

is there anything special about the set of integers whose base 3 representation contains no 1

[torn escarp]

you could also see this as a consequence of the group structure of numbers of the form a^2+b^2

simply put a(b^2+c^2)=u^2+v^2 then b^2+c^2 has an inverse so a = (u^2+v^2)*(b^2+c^2)^-1 which means a is a number of the form a sum of two squares

no nevermind that group structure only exists for rational numbers not integers whoops

[inner anchor]

I thought about this for a second more, and this follows from the fact that the product of two numbers which can be written as the sum of two squares is in turn the product of two squares

So you only need fermats theorem on two squares for primes

Rip you dont get the converse though

[hot cypress]

How can i prove that k!(p-k-1)! Is congruent with (-1)^(k+1) mod p when p is prime? I dont need all done, just give me a hint on what the path is

[inner anchor]

looking at the binomial coefficient $\binom{p-1}{k}$ is a way

[sterile pumice]

ɐddɐԀ

[leaden swan]

That's a very cool soln

[inner anchor]

its pretty nice

also super natural

[hot cypress]

I cant with this one, im stupid

[leaden swan]

You can write a/b mod p as (a/b)(bc) mod p where bc=1 mod p and rearranging this gives you ac mod p=1

If a/b is an integer

[fervent crest]

It should be read as a percentage

So 1/ln(100)=0.217..., so that means about 21.7% of the positive integer between 1 and 100 are prime

That's the best interpretation of that statement I think

[sterile pumice]

ǝᴉdǝᴉʇnɔǝɥʇɐzɹᴉɯ

ǝᴉdǝᴉʇnɔǝɥʇɐzɹᴉɯ

[light flicker]

this is more appropriate for #groups-rings-fields

[final fjord]

whoops

yes

[sleek cove]

it follows from just using the approximation from before. no?

[inner anchor]

Isnt that the weight you need for the weighted counting function to asymptotically grow as fast as n

[light flicker]

the probability that a number about as big as n is prime is 1/log(n)

to answer your second question, this kind of thing happens a lot. You want to weigh something based on how likely it is to occur

Maybe this is bad intuition, but there are a lot of examples in math where when you count some set of objects, you weigh each object depending on how many automorphisms it has

The hurwitz class numbers for example do this, and you can also count how "many" finite sets there are by doing this

https://www.reddit.com/r/math/comments/55raqj/how_many_finite_sets_are_there_there_are_e_of/ explains this a bit further (which is written by someone in this discord)

yes

the post was written by Bunchos Bananas so maybe they could explain further

[sterile pumice]

ɐzɹᴉɯ oɥɔunq

[light flicker]

yeah, that makes sense

[sterile pumice]

ɐzɹᴉɯ oɥɔunq

[light flicker]

2[x/2] differs from x by either 0 or 1

at least, when x is an integer

it doesn't really matter, the difference between x/2 and [x/2] is at most 1

so the difference between x and 2[x/2] is at most 2

[sterile pumice]

ɐzɹᴉɯ oɥɔunq

ɐzɹᴉɯ oɥɔunq

[inner anchor]

Dont you just sub x/2^j into x

[light flicker]

How do you get that psi is bigger than that

Yeah, it's the exact same argument using the upper bound for T(x) - 2T(x/2)

[sterile pumice]

ɐzɹᴉɯ oɥɔunq

[inner anchor]

You can pair up terms like psi(x/3) and -psi(x/4)

The difference is always nonnegative

And so the entire tail is nonnegative

[inner anchor]

This is why analytic nt is the wrong ant

Log x/log 2 = log_2 x, so that - 1 is the largest value of for which psi(x/2^(j+1)) > 0

Also you get the inequality by just doing what is said, adding up all the inequalities and stuff telescopes nicely

Rip

[gentle lily]

Show that if $x,y,z$ are integers such that $x^3 + 5y^3 = 25z^3$, then $x = y = z = 0$.
Let us begin by reducing the equation modulo $5$ to strive for infinite descent:
$$x^3 + 5y^3 = 25z^3 \implies x^3 \equiv 0 \pmod{5}.$$
This tells us that
$$x^3 = 5^{3(e_1 + 1)} p_2^{3e_2} \cdots p_k^{3e_k},$$
for distinct primes $p_i$ (not equal to $5$) and non-negative exponents $e_i$. Thus,
$$x = 5^{e_1 + 1} p_2^{e_2} \cdots p_k^{e_k},$$
telling us that $x = 5x_1$, for some integer $x_1$. Plugging this in to our original equation, we get
$$125x_1^3 + 5y^3 = 25z^3 \implies 25x_1^3 + y^3 = 5z^3.$$
We can reduce mod $5$ again;
$$y^3 \equiv 0 \pmod{5} \implies y = 5y_1,$$
($y_1$ is some integer) by similar reasoning. Plugging this in, we get
$$25x_1^3 + 125y_1^3 = 5z^3 \implies 5x_1^3 + 25y_1^3 = z^3.$$
Given the equation, it is easy to see that $z^3 \equiv 0 \pmod{5}$, so $z = 5z_1^3$. We have
$$5x_1^3 + 25y_1^3 = 125z_1^3 \implies x_1^3 + 5y_1^3 = 25z_1^3.$$
Thus, we have found our infinite descent. We will finish our proof by seeking for a contradiction.

[sterile pumice]

LifeSource

[gentle lily]

First, we will tackle the case where we deal with the smallest positive integer solution. Suppose $x = p_1, y=p_2,z=p_3$ is the smallest positive solution that satisfies our original equation. Recall that, by the Well Ordering Principle, there should always exists such a solution. However, by our infinite descent equation, we get that $x = \frac{p_1}{5},y= \frac{p_2}{5},z = \frac{p_3}{5}$ is also a solution! This is a contradiction, since this value is smaller than the solution we assumed was the smallest.

Next, we deal with the case where our smallest possible solution is negative; specifically, suppose $(-n_1,-n_2,-n_3)$ is the smallest negative solution, where $n_1,n_2,n_3$ are positive integers. Let us scale our original equation with our smallest solution by $125$ as such:
$$5^3 (-n_1)^3 + 5^3 \cdot 5 (-n_2)^3 = 5^3 \cdot 25(-n_3)^3.$$
Since $5^3$ is clearly a perfect cube, we can bring it into the cube, giving us
$$(-5n_1)^3 + 5(-5n_2)^3 = 25(-5n_3)^3.$$
However, since $-5n_i < -n_i$, for $1 \leq i \leq 3$, this solution is smaller than the one we assumed was the smallest! Thus, this case also results in a contradiction.

In conclusion, since we have shown that having non-trivial solutions results in a contradiction, we have shown that only the trivial solution works.$_{\blacksquare}$

[sterile pumice]

LifeSource

[gentle lily]

Is this fine?

[light flicker]

what do you mean by "smallest negative solution"

Also it doesn't seem like you've handled the case where say x is negative but z and y are positive for example

[gentle lily]

Then can't you just use the argument that you can't divide by arbitrarily large powers of 5?

[light flicker]

yeah a similar argument would work

I'm just saying what you've written down does not cover that

[gentle lily]

Let us begin by reducing the equation modulo $5$ to strive for infinite descent:
$$x^3 + 5y^3 = 25z^3 \implies x^3 \equiv 0 \pmod{5}.$$
This tells us that
$$x^3 = 5^{3(e_1 + 1)} p_2^{3e_2} \cdots p_k^{3e_k},$$
for distinct primes $p_i$ (not equal to $5$) and non-negative exponents $e_i$. Thus,
$$x = 5^{e_1 + 1} p_2^{e_2} \cdots p_k^{e_k},$$
telling us that $x = 5x_1$, for some integer $x_1$. Plugging this in to our original equation, we get
$$125x_1^3 + 5y^3 = 25z^3 \implies 25x_1^3 + y^3 = 5z^3.$$
We can reduce mod $5$ again;
$$y^3 \equiv 0 \pmod{5} \implies y = 5y_1,$$
($y_1$ is some integer) by similar reasoning. Plugging this in, we get
$$25x_1^3 + 125y_1^3 = 5z^3 \implies 5x_1^3 + 25y_1^3 = z^3.$$
Given the equation, it is easy to see that $z^3 \equiv 0 \pmod{5}$, so $z = 5z_1^3$. We have
$$5x_1^3 + 25y_1^3 = 125z_1^3 \implies x_1^3 + 5y_1^3 = 25z_1^3.$$
Thus, we have found our infinite descent. We will finish our proof by seeking for a contradiction.

The infinite tells us, given a non-trivial solution $(n_1,n_2,n_3)$, it holds that $\left(\tfrac{n_1}{5},\tfrac{n_2}{5},\tfrac{n_3}{5}\right)$ is also a solution. Notice, however, that this implies that we can divide our solution by five infinitely, which is a contradiction since we cannot evenly divide any finite number by infinity! Thus, the only solution which allows for this to occur is the trivial solution, $(x,y,z) = (0,0,0)$.

This should suffice

[light flicker]

yeah seems fine

you might want to emphasis that (n_1/5, n_2/5, n_3/5) is an integer solution

[gentle lily]

Maybe a bit more white space

[light flicker]

which is why you can't divide by 5 infinitely

[gentle lily]

I kind of hinted at that when I stated "evenly divide" at the end

[sterile pumice]

LifeSource

[warm nymph]

@hollow bramble what was that challenge about that the dude came in here with, did you complete that HTB challenge? Got a pic of proof you solved it?

[hollow bramble]

just check the htb account called ariana or smt

it was the latest crypto

something about ecc+rsa

quite simple lmao

[warm nymph]

@hollow bramble ah I want to try it where your link?

[warm nymph]

@hollow bramble I solved it 🙂 That was easy, I made a fake flag here and did it locally, you can check by decrypting it and finding my fake flag as proof i solved it, interested to see how you did it, can you show me in DM?

Encrypted flag: a752766c41d8a68f42990d226687706878ec07874dfadc36e3dceb5d0d812284
IV: 57ed026bc0da9388e3093318ba195cd1
N: 6827076977564466462577263968415631302860330562726553599817987882255347352992442280551383388422646750100033731018684434197009482516123334730890481178806949
ECRSA Ciphertext: Point(x=842605147643980772943316338732602260884313273856516816980398584164108391704385766783085909112744346456411341661270670057595634379235141819095994733960865, y=5512633349934149752209783896871625235905184988960793639794687086942197310993130029788782138347546856527901890330759779220708609199938110761514847881447732)
Would you like to test the ECRSA curve?
[y/n]> y
Generating random point...
Point(x=5323773559988395618847479461096323703865464530378002129976061900244495764995207144409611273717581587824966347890570619231510007691366227595146878103703901, y=3342787172246370387243051338484351500478558899952472483769367109298099575022387092997406683752049096963603393861368302059887991044708416164218151356235407)

Decrypt that as proof

[hollow bramble]

pls no discussions

theres literally only one way to solve lol

[warm nymph]

@hollow bramble Yeah lets move it to DM

[terse acorn]

I only got to something like $\alpha = s/t$ then $\sum \frac{1}{a_{i}} = s/t * \sum \frac{10^{i}}{a_{i}^{2}}$ and don't know how to go from here. Or is it the wrong approach?

[sterile pumice]

Jing

[torn escarp]

I'm thinking it's going to hinge on the fact that rational numbers have eventually repeating digits which maybe leads into an argument where you can over estimate every possible substring of digits that might appear and it will still converge

[inner anchor]

This exactly

I think that this should work: Let the period of the decimal expansion of $\alpha$ be equal to $n$. Now note that the number of possible substrings in the interval $[10^{n-1}, 10^n)$ is at most $n$, and so our sum is bounded by $\sum_{i=1}^\infty \frac{n}{10^{n-1}}$

[sterile pumice]

Pappa

[inner anchor]

there may be some off by ones but i think the idea is there

[terse acorn]

@inner anchor For example n = 2, so we have [10, 100). Isn't the number of possible substrings is 3? For "98" we have "9", "8", and "98"

[sacred junco]

anyone have any tips for this one?

[leaden swan]

x=y+ k phi(n) for some k

And a^(k phi (n)) is well defined

[sacred junco]

my bad I didn't see this

wdym by well defined?

[leaden swan]

k could be a negative number

In that case a^(k phi (n)) exists iff a^-1 exists

So,you could rewrite a^x as a^y a^(k phi(n))

[sacred junco]

oh right I think I see it from there

damn I get that step but from there I don't see how the totient function plays into anything

since gcd(a, n) = 1, phi(n) is gonna be at least 1

yeah idk where I'm going

appreciate it tho thanks

[inner anchor]

If our rational number is eg 123/999 = 0.123123123..., then the substrings of length 1 are going to be 1, 2, 3, the substrings of length 2 will be 12, 23, 32, and the substrings of length 3 will be 123, 231, 312, because only cyclic permutations are allowed, instead of all permutations

also there is a typo in the thing is posted

$\sum_{i=1}^\infty \frac{n}{10^{i-1}}$

[sterile pumice]

Pappa

[inner anchor]

this is the bounding sum

though i wonder if the converse holds

[sage fern]

so they're (3k+-1)^3

then k^3 and k^2 it's trivial

for k, there's the one factor of 3 from the one factor of 3k

and then that's x3 because the binomial coefficient

so like generally for n, the LCM of everything other than the constant term in the expansion of (nk+-1)^n is n^2? that sounds plausible

because one factor of n from one factor of nk, and one factor of n from n choose 1

[grave carbon]

Could someone point me towards the right direction for the inductive case? Not quite sure what to do with the assumption that $a_n$ coincides with the $n^{th}$ prime.

[sterile pumice]

beeswax

[grave carbon]

And then proving it for n+1

[light flicker]

feel like this problem is missing a condition, you need to assume that the a's are at least 2 otherwise you can just have all the a's be equal to 1

but anyways, you want to use strong induction here basically

assume that a_1, ...., a_n are the first n primes and try to show that a_{n+1} must be the next prime

[grave carbon]

I see

For that, I should be using the gcd condition right?

[light flicker]

Yes

[grave carbon]

Is this valid?

[light flicker]

Uh no?

I'm not even sure what you're trying to do

[grave carbon]

If $a_n$ is the smallest integer such that $gcd(a_i,a_n)$ for all $i<n$, then the same should be true for n+1

[sterile pumice]

beeswax

[light flicker]

I mean, that's how the a_{n+1} are defined yes

but how are you showing that a_{n+1} is the next prime

[grave carbon]

Somehow show that gcd(a_n,a_{n+1}) = 1?

for any n

[leaden swan]

That's given

[light flicker]

Again, that's how you define a_{n+1}

as the smallest integer that satisfies that property

What you're trying to do is show that a_{n+1} is the next prime

[leaden swan]

Assume for all k<=n,a_k is the kth prime. Now,let a_{n+1} not be the {n+1}th prime,which would mean a_{n+1}<{n+1}th prime,which leads to a contradiction

[dusty bough]

hello, can i get some help with this?

i'm not exactly sure how i should do this

i think ill be able to use bezout's theorem here somehow but im not exactly sure how

(a, b) denotes gcd(a, b) btw

[dusk heath]

Ok so that's definitely not the cleanest way of doing it

but you could decompose in prime factors

so like you'd have a = d x prod(p_k^a_k) and b = d x prod(q_k^b_k)

and now try to compute both gcds

[leaden swan]

Or show (a/d , b/d) divides that and vice versa

[dusk heath]

yeah that'd work too, and may be cleaner

[leaden swan]

To show (a/d,b/d) divides that expression, write the steps for computing (a,b) using Euclidean algorithm and divide everything by d

[grave carbon]

Oh thanks

[dusty bough]

yup got it ty

[rare cobalt]

I must calculated a modulo of factors product:
(a1^b1 x a2^b2 x a3^b3 x ...) % (c1^d1 x c2^d2 x ...)
if RIGHT > LEFT = LEFT
else I'don't know
I can't transform theses products into integer
(a, b, c, d are integer)

[quaint geyser]

I'm kinda stuck at 1st part

[inner anchor]

Assume that such an $n$ exists. Now you know that $n$ is divisible by 5, so write $n = 5^k m$, where 5 and $m$ are coprime. Now use the given relation to find a condition on $m$, and then show that the existence of such an $m$ is a contradiction.

[sterile pumice]

Pappa

[hot cypress]

How can i prove that if a≡a^p mod q and a≡a^q mod p then a^pq≡a mod pq whenever p and q are prime?

[hot cypress]

Ok i just saw it btw ctr go brrr

[grave carbon]

I was trying to disprove
$$ \forall n \geq 1, n^2 - n +41 \text{ is prime.}$$
I found a value (n = 105) where the statement holds false, but I was wondering if there is a more efficient way to figure out a counterexample

[sterile pumice]

beeswax

[sage fern]

just get n such that 41 divides n^2 - n

[modern kestrel]

https://gyazo.com/7106fe84f3ba6718e7d735011a272993

i am not too sure about how to solve this. I know that you need Wilson's Theorem

The thing that confuses me is the sequence not being factorial

[meager zodiac]

You can write it as something like this $$1 \cdot 3 \cdot 5 \ldots (p-2) = \frac{(p-1)!}{\prod_{k=1}^{\frac{p-1}{2}}2k} $$

[sterile pumice]

andreO

[modern kestrel]

woah thats weird is that supposed to divide out every other term?

[meager zodiac]

yeah the even ones

[modern kestrel]

got it and i guess from there i would use wilson's theorem?

i know (p-1)! itself is congruent to -1 (mod p)

would i just divide -1 by that product on the bottom?

would that give me a?

[meager zodiac]

Basically, $$1 \cdot 3 \cdot 5 \ldots (p-2) \prod_{k=1}^{\frac{p-1}{2}}2k = (p-1)!$$

So if you can find the multiplicative inverse of the product, you'd be done

[sterile pumice]

andreO

[meager zodiac]

that is find x such that $$x\prod_{k=1}^{\frac{p-1}{2} } 2k= 1 (mod p)$$

[sterile pumice]

andreO

[modern kestrel]

does that essentially mean a number that when multplied by every even term would give a remained of 1 when divided by p?

[meager zodiac]

yup

[modern kestrel]

is there a number that satisfies that condition for every even number?

[meager zodiac]

not every, the product

[modern kestrel]

okay the way i am trying to approach this is to choose a prime number p and seeing how i would form a product with an even number to have a remaineder of 1 when dividing by p

would that be the right way to look at it?

[meager zodiac]

$$\prod_{k=1}^{\frac{p-1}{2} } 2k = 2^{\frac{p-1}{2}} \left( \frac{p-1}{2} \right)!$$

[sterile pumice]

andreO

[modern kestrel]

can you explain how you got to that step from the previous =1 (mod p)

im lost sorry

[meager zodiac]

It's an intermediate step on the way to find such an x

if you notice that the product has the above form, can you now use Wilson's theorem somehow?

[modern kestrel]

how do i deal with the /2

doesnt the right term equal -1 using wilson's??

[meager zodiac]

$$ (p-1)!\equiv 1\cdot(-1)\cdot2\cdot(-2)\cdots\frac{p-1}{2}\cdot\left(-\frac{p-1}{2}\right)\pmod p$$

[sterile pumice]

andreO

[modern kestrel]

okay i get that you are grouping the terms so that the negative congruences match up

[meager zodiac]

basically pair 1 with p-1, 2 with p-2 and so on

yeah

[modern kestrel]

so would you just do the same for p-1/2?

[meager zodiac]

That gives $$(p-1)!\equiv (-1)^{\frac{p-1}{2}}\left(1\cdot2\cdots\frac{p-1}{2}\right)^{2}\pmod p $$

[sterile pumice]

andreO

[modern kestrel]

oh and the right term can be rewritten as the factorial p-1/2?

[meager zodiac]

indeed

[modern kestrel]

but its squared right?

[meager zodiac]

well, the square of

remember we have the whole thing squared

[modern kestrel]

is this supposed to devise a way to substitue what we have originally with p-1 !

[meager zodiac]

yes

you can further write the last step as $$ \left[\left(\frac{p-1}{2}\right)!\right]^{2}\equiv (-1)^{\frac{p+1}{2}}\pmod{p}$$

[sterile pumice]

andreO

[meager zodiac]

but here p = 3 mod 4

so the rhs is just 1

[modern kestrel]

ah so this proves that p-1/2 ! is congruent to just 1

[meager zodiac]

well the square of

yes

[modern kestrel]

you cant just root it right

[meager zodiac]

originally the problem asks for the square of (1.3.5.....) so it all lines up

[modern kestrel]

WAIT WHAT

i will be honest

i did not see the square

[meager zodiac]

no worries

[modern kestrel]

os its just 1?

well isnt there the 2 term

[meager zodiac]

yup

fermats little takes care of that

[modern kestrel]

okay so you would square that

okay so 2^p-1 is congruent to 1 mod p

[meager zodiac]

yup

[modern kestrel]

since squaring it gets rid of the denominator

so you have that instead of p-1/2

[meager zodiac]

yup

[modern kestrel]

so the product is congruent to 1?

mod p\

product squared

[meager zodiac]

yup seems so

[modern kestrel]

got it tysm

number theory has been kicking my behind

[meager zodiac]

anytime 🙂

[modern kestrel]

do you mind if i add you as a friend and if i reach out if i have number theory related questions?

[meager zodiac]

sure

[modern kestrel]

okay ty again

[meager zodiac]

np

[meager zodiac]

that was a fun detour, but I guess a more straightforward way would be to note
$$\left (1 \cdot 3 \cdot 5 \ldots (p-2) \right )^2 = (1 \cdot 3 \cdot 5 \ldots (p-2) )(-(p-1))(-(p-3))(-(p-5)) \ldots (-2)$$

[sterile pumice]

andreO

[meager zodiac]

$$= (-1)^{\frac{p-1}{2}}(p-1)! \pmod{p}$$

[sterile pumice]

andreO

[frosty tide]

whats the name of a number theory problem where you have to find the mod for a given equation to work

$$a=b (mod\ n)$$

[sterile pumice]

gaborit

[frosty tide]

find n

[abstract flax]

Can you use the fact that there are infinitely many primes?

@worn pine

Then just take a prime number with enough digits that even if they were all 1, it would still be greater than k

[torn escarp]

what if every prime greater than some k is of the form 1000..0001

[inner anchor]

That isnt possible right

Due to the density of primes

[worn pine]

Is it right to just say that for any positive integer k, 9998k + 9999 contains an infinite number of prime numbers (due to Derechlit's) and has a sum of decimal digits greater than k hahaha

[torn escarp]

your idea is basically right but you need to fix it a bit

[torn escarp]

lol I think you're not reading the context that came before it

[worn pine]

What part do I need to fix? Thank you so much!!

[torn escarp]

you're sorta double using k here to mean two different things

also why did you pick 9999? whey not 99999 for instance

you need to think about how you're picking these numbers better

[worn pine]

Ohhhhh I get it, it kinda seemed uncanny to just pick numbers out of nowhere haha

Do you have any hints on how I can best make use of Derechlit's to show that the statement is true? thank you!

[worn pine]

still no idea 😢

[bleak robin]

Does anyone have some good papers to read about the splitting property of primes over higher degree polynomials (preferably 5 and up)

[meager zodiac]

Denote $a = 999\ldots 9 \ (k \ 9's)$, and $d = 10^{k}$. $a$ and $d$ are clearly coprime.
Now consider the arithmetic progression: $$ a , a +d, a+2d, \ldots $$ and Dirichlet's theorem.

[sterile pumice]

andreO

[sacred junco]

Is there a clear cut difference for what an affine line and what a projective line is ? Google isn't helpful

P.S. are those conditions for a,b,c define what the case (affine or projective) is ?

a similar case is presented where the equation $y^3 = x^3 + 1$ is affine and is converted to a projective equation by subbing $y = \frac{v}{w}$ and $x = \frac{u}{w}$ to get $wv^2 = u^3 + w^3$ BUT the author adds that the same can be achieved by `inserting powers of w to make all terms cubic' which yields : $wy^2 = x^3 + w^3$

Any idea what is going on here ?

[sterile pumice]

xi64

[torn escarp]

those are the same up to changing out what you're labeling the variables @sacred junco