elementary-number-theory

[inland nexus]

ctan:

,1s how do you tell gross income

another trick that can work gross income

another trick that can work mod gross income

another trick that can work mod p$5

[sand rain]

#latex-testing

[torn escarp]

wrong channel, that isn't number theory, try #❓how-to-get-help to make a question channel

[viscid patio]

Euclidean algorithms is correct in that example ? :
`
TEST 1 :

a = 898754
b = -15654
898754 = -15654 x -57 + 6476
-15654 = 6476 x -2 + -2702
6476 = -2702 x -2 + 1072
-2702 = 1072 x -2 + -558
1072 = -558 x -1 + 514
-558 = 514 x -1 + -44
514 = -44 x -11 + 30
-44 = 30 x -1 + -14
30 = -14 x -2 + 2
Test 2 :

a = -156588884
b = -898754
-898754 = -156588884 x 0 + -898754
-156588884 = -898754 x 174 + -205688
-898754 = -205688 x 4 + -76002
-205688 = -76002 x 2 + -53684
-76002 = -53684 x 1 + -22318
-53684 = -22318 x 2 + -9048
-22318 = -9048 x 2 + -4222
-9048 = -4222 x 2 + -604
-4222 = -604 x 6 + -598
-604 = -598 x 1 + -6
-598 = -6 x 99 + -4
-6 = -4 x 1 + -2
`

a mod by 2 numbers can be negative ?

[torn escarp]

-7 = -2*3 + -1

[viscid patio]

-7 = -2*3 -1 ^^

[torn escarp]

is there a way to find all the solutions x,y to ax+by=c with a,b,c pairwise relatively prime?

I was thinking it's as easy as just solving ax+by=1 and then multiply x,y by c, but that's only some of the solutions. For instance, 2x+3y=5 has 2 * 1 + 3 * 1 = 5 and obviously this x,y aren't divisible by 5

[fervent grove]

I mean the thing is that if you have two solutions (x,y) and (x',y'), then ax+by = ax'+by'. Taking (mod b) tells you that x = x' (mod b), so that forms a unique equivalence class; similarly, y = y' (mod a).

In total, once you have a single solution (x0, y0), the other solutions will take the form (x0+b*k, y0-a*k).

(and you can find a single solution using the method that you describe, for example)

[torn escarp]

oh good I knew I was making some silly mistake, I was using c(b,-a) instead of (b,-a), thanks!

[analog raptor]

I need help with this problem, I have tried some modular arithmetic but nothing works. I have no idea how to solve this: Solve over the integers:

Also, it doesn't really want to be factored, not even wolfram alpha factored it.

Honestly, I even tried ChatGPT but, well, nothing.

[sleek spire]

x = 0 y = 0

[analog raptor]

I know that, but how do you prove there are no other solutions?

[glass verge]

Is number theory (as in IMO / competition style number theory) generally assumed knowledge before university?

Or is it taught during university courses?

[sleek spire]

no, not at all

[sleek spire]

yes. most unis have an "elementary number theory" course

[glass verge]

@sleek spire Do you have any recommendations for getting up to scratch ASAP for number theory?

I am taking a course that seems to assume much of it as prerequisite knowledge

[sleek spire]

what course?

[glass verge]

Abstract and linear algebra

Starting with group theory

[sleek spire]

that doesn't require number theory

[glass verge]

da

[sleek spire]

?

[glass verge]

is set theory taught as part of discrete maths?

[sleek spire]

it's usually taught in a precourse iirc

you don't need a lot of set theory for algebra though. just the basics as in union & intersection

[glass verge]

For group theory?

[sleek spire]

yeah

[glass verge]

It seems to be built on set theory from what I observe

[sleek spire]

eh

[glass verge]

I have to pause to look something up like every 2s for my current lecture

for group theory

[sleek spire]

e.g.?

[glass verge]

mainly formal definitions

i.e. what specifically counts as a "projection" mapping

"Up to" statements

"up to isomorphism"

equivalence classes

closure

idempotence

and a few more other examples

[sleek spire]

that's not set theory

[brittle root]

do you follow a textbook? perhaps you can try reading ahead

[glass verge]

Do you recommend taking notes on the textbook too

[brittle root]

ehh i bought my own textbooks so I treasure them very much

what I do is i take notes on the digital copy

[glass verge]

oh I meant like

[brittle root]

(this also lets me scratch out typos and whatnot)

[glass verge]

what I do is have cheap notebook nearby

[brittle root]

and also bits where it says that "the proof is trivial" I can fill in the gaps

[glass verge]

and jot down anything interesting (oftentimes ends up being most things0

otherwise

[brittle root]

not sure if your lecturer is expecting you to read ahead

(which imo is not great pedagogy but oh well)

[regal aspen]

x^2 = z
z^3 + zy + y^3 = 0; z >= 0
(z+y)(z^2 + zy + y^2) + zy = 0
(z+y)(z^2 - zy + y^2) = -zy
(z+y)((z + y)^2 - 3zy) = -zy
(z+y)^3 = zy(3(z+y) - 1)
Let z + y < 0 -> y < 0. Contradiction since y(3(z+y) -1) > 0

Thus, z + y > 0. For y >= 0 as well, we obviously obtain (0, 0)
Thus, we are left with z > abs(y), y < 0

Let z = abs(y) + 1 ->
z^3 + y^3 = (z)^3 - (z-1)^3 = -3z^2 + 3z - 1
This implies 3z^2 - 3z + 1 <= zabs(y)(After doing sign shenanigans). Since zabs(y) < z^2(y < z), this is false
Hence Proved

I made way too many arithmetic errors kekw

[analog raptor]

Interesting, I solved it also in the meantime. It factors with the formula a^3 + b^3 + c^3 -3abc = (a+b+c)(a^2+b^2+c^2-ab-bc-ca), after multiplying both sides with 27. After doing that we get (3x^2+3y-1)(9x^4+9y^2+1-9x^2 y+3y+3x^2)=-1, and we have two cases (-1, 1) and (1, -1) for the expressions in parenthases. Again, we only get x=y=0.

[regal aspen]

I must be missing something because I don't see how it factors to that? How did you get rid of x^2y?

Or rather, could you tell me what your a, b, c are?

[analog raptor]

a = 3x^2 b=3y c=-1

No

wait

i edited it

[regal aspen]

Ah yeah that makes sense thanks

[fluid flax]

is this the right place to ask about this ?

2 math engines gives ne 2 different results when they try to simplifie and I am getting a different result

[sleek spire]

#prealg-and-algebra

[lean sandal]

when solving congruence equations, e.g. x^3 + x = 0 (mod n), can we gurantee that the number of solutions will be at most 3 in this case (since the degree is 3)?

[wooden glen]

Not in general, only if n is prime.

(Because in that case Z/nZ is a field, and then we know nonzero polynomials can only have as many roots as their degree).

[lean sandal]

i see, thanks!

[wooden glen]

But for example x² == 1 (mod 8) has four solutions.

[lean sandal]

oh ye thats true

[torn escarp]

challenge: find an n when it has 4 or more solutions 😎

[lean sandal]

LOL

[wooden glen]

x² == 1 (mod n) has 4 or more solutions unless n is 1 or a prime or twice a prime.

[lean sandal]

makes sense

[wooden glen]

Oops, need to exclude powers of odd primes and two times powers of odd primes, too.

[gaunt sedge]

does anyone know why do we check -7 mod 8?

my attempt: 8 = 2^3, so by showing -7==1 mod 8, we know x=1 is a solution to the congruence when n=3.
for n>3, all i can say is that if x is a solution to the congruence mod 2^n, then it's also a solution mod 2^3. i was hoping the converse would be trivial/easy, but i dont think it is so im stuck :(

[wooden glen]

I would expect some kind of explanation of the line of thought to appear in the lines/paragraphs above the one you cropped from the middle of some longer text.

Since arguments that are expected to be understandable without any context rarely begin with Next, ....

[gaunt sedge]

yeah my bad

ill post the full question and answer; for context, we have just done hensels lemma

[polar patio]

oh yeah Legendre's symbol

[gaunt sedge]

hmm 1 mod 8 shows up in (2/p) ...

[unkempt void]

I like how they don't really prove it's WLOG

[gaunt sedge]

Yeah i just assumed that since we just need to show the existence of solutions, its enough to find a particular case that works for an arbitrry n

[sleek spire]

if a + b = k then gcd(a, b) | k

does this follow from bezout?

[still flare]

You do not need bezout to prove that, you only need the definition of the gcd

Any common divisor of a and b also divides any integral linear combination of a and b

[sleek spire]

ah I see because if a = xs and b = xz then a + b = xs + xz = x(s + z)

thanks

[wanton viper]

Hallo,
im working with elliptic curves over finite fields and have trouble proving that if a point has an order greater than 4*sqrt(p) that there will be a unique multiple of that between the hasse interval. Has anyone any hints?

[sleek spire]

this belongs in #advanced-number-theory

[wanton viper]

Oh, im sorry :( i didnt know where to draw the line

[white lion]

I want to show that, the "nearest integer to a is [a+1/2]" when I looked at the proof for this excercise, it says "it is sufficient to show that |[a+1/2]-a|< or = 1/2

for reference [a] denotes the greatest integer not exceeding a or the greatest integer function

what i want to know is how do I prove that the nearest integer would be at a distance of at most 1/2?

It makes intuitive sense for me since I worked out some examples but it's been a struggle trying to prove it.

and if anyone would also mind helping me with this as a bonus I noticed through some examples I went through that if we do |[a+n]-a| it will always be less than or equal to 1/2 if n< or =1/2 (didn't prove it but its obvious from examples I made)

[leaden swan]

a can be in [[a],[a]+1/2) or in [ [a]+1/2,[a]+1)

In the first case, closest integer is [a]

In second case, closest is [a]+1

Note that [a+1/2] gives the exact same result

@white lion

[white lion]

wdym by this?

[leaden swan]

Well if a is in the first range
a+1/2 is in the range [[a]+1/2, [a]+1)

So [a+1/2] is [a]

[white lion]

yeah

[leaden swan]

Similarly consider the second rangd

[white lion]

Oh alright, got it, so when in the first range the nearest integer is [a] = [a+1/2] and in the second range the nearest integer is [a] +1 = [a+1/2]

Thanks so much.

[surreal solar]

Hi, I've got a few problem assignments I would like some help with? If anyone could point me in the right direction that would be appreciated

This one is numbered 2 but I've made more progress in this one

I expect it's something simple like this, but although I feel I have the correct answer, I don't know how to get to the answer

I've tried looking up a formula for arbitrary multinomial expansion, but I'm not making any progress in that area, and I'm not sure that's the right direction to go

The other question is this one, which involves proving that each PPT (Primitive Pythagorean Triple) a, b, c can be defined by a unique s and t

[stuck shore]

pretty interesting problem. just testing a few numbers, the right side isn't even always an integer unless p is prime.
#help-19 message

oh right that's just FLT

[tranquil shoal]

wait what how

[stuck shore]

p is an odd prime

2^p = 2 mod p

[wooden glen]

FLittleT, not FLastT.

[tranquil shoal]

oh

[regal aspen]

@gleaming mesa Hint: https://en.wikipedia.org/wiki/Wolstenholme's_theorem

The 1 + 1/2...1/p-1 = 0 mod p^2 to be exact

[verbal cedar]

any suggestions for evaluating $(16!)^2\bmod{37}$?

[sterile pumice]

nilpotent nix

[leaden swan]

Well you can rewrite that as
1 x 2 x 3 x 4 x ... 16x 21 x 22 x 23 x...36 mod 37

Compute (17 x 18 x 19 x 20) mod 37

Use Wilson's theorem and you are done after moving around some terms

@verbal cedar

[regal aspen]

23?

I thought the same thing, but I wasn't sure how you could be sure about 23, 29, etc. being representable

And the fact that a number like 27 would require 9 * 3, and 33 would require 11 * 3, making it impossible to represent both

[rose trout]

so we do summation u(n)/n^2 where n goes from 1 to x, we split this sum as sum_ u(n)/n^2 where n goes from 1 to infinity minus the sum_u(n)/n^2 where n is more than x. we appoximate the second term by big O: O(1/x). why cant we simply write the whole sum from 1 to x as O(1/x) ???????
u(n) is mobius function

[gilded breach]

How to find prime factors of the form 4n+3 of the number 4(3.7.11)-1?

I manually did and found 71 = 4*17+3

Is there a way to find it out from the numbers given without manually calculating?

[sleek spire]

what is 3.7.11

[gilded breach]

3 * 7 * 11

[gilded breach]

Is your cover photo from Big Bang Theory intro?

[sleek spire]

inside job

[fathom lagoon]

I want to find x such that $21927^{18453} \cong x mod 6$
now 21927 => 21 and 21 mod 6 = 3 and 3^2 mod 6 = 3 => idempotency => so x = 3

[sterile pumice]

SilberSeele
Compile Error! Click the reaction for more information.
(You may edit your message to recompile.)

[fathom lagoon]

$213927^{18453} \cong x mod 6$
now 213927 => 24 and 24 mod 6 = 0? so x = 0?

[sterile pumice]

SilberSeele

[livid birch]

this is wrong right

i was told it was 4 not 5

but don't we need to add that 1?

[still flare]

You wrote $2 ^{1234} = (2^{10})^{123} + 4$, but this is wrong. What is right is $2 ^{1234} = (2^{10})^{123}\times 2^4$.

[sterile pumice]

Boytjie

[livid birch]

oop

mero strikes again

wait it's boytjie

how dare i

boytjie strikes again

[still flare]

what

[livid birch]

the answer is still 5 it seems tho

[still flare]

That's bc the answer is 5

in fact let's ask wolfram

,w 2^1234 mod 11

[sterile pumice]

Results provided by WolframAlpha

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

Requested by Boytjie#0953

[livid birch]

If $p$ is a prime number and $a$ is a positive integer, show that $a^{(p-1)!+1}\equiv a$ (mod $p$).

[sterile pumice]

sebbb

[livid birch]

can i get a nudge on this pls

or does it follow directly from wilson's thm

[lean sandal]

i think u can just use fermats

$a^{(p-1)!+1} \equiv (a^{p-1})^{(p-2)!} * a \equiv (1)^{(p-2)!} * a \equiv a \pmod{p}$

[sterile pumice]

nomnom

[fervent grove]

beware of a=0

[livid birch]

it's positive integers all good

[fervent grove]

then beware of a=p

[rose trout]

Is there an iff condition for Fibonacci

[livid birch]

wdym

[verbal cedar]

you're going to have to be way more specific

[rose trout]

Ok so given a bunch of numbers identify which are Fibonacci numbers

Basically code this such that the complexity is as fast as u can

[leaden swan]

Well you can find the largest Fibonacci number less than or equal to n for any given n

[rose trout]

Never mind found it

Idk why they never mention this is any book!

[white lion]

How would I go about solving this question, I attempted the standard linear congruences method for the first question it would be 15050 congurent to x (mod 81) implies x is congurent to 15050 (mod 81)

but it didn't work

[regal aspen]

Can you a bit clearer on what you did? For the first question, would it not suffice to find the remainder of 15050 when divided by 81?

[white lion]

just the standard way you'd solve a lnear congurence with an unknwon value but yeah I guess this works too

what about for these huge numbers surely there must exist some sort of trick or method to solve these

[regal aspen]

You simplify everything as much as possible:
30409 becomes 46, 363 becomes 15, 6740 becomes 16\ etc. etc.

When it seems to get complex, simplify again

[white lion]

simplofy 30409 to 46 how would that work?

[dense ridge]

remainder by 87

[hidden bolt]

please can someone check if my solution is right? If not what am I overlooking here?

[regal aspen]

Seems alright

[hidden bolt]

alright

[regal aspen]

Wait wait wait

Nvm I read it wrong sorry

[hidden bolt]

um...

[leaden stratus]

is i'm given N = 8 and K = 7. is there an easy way to find the largest number between [1, K] that can divide N without a remainder?

i was thinking of using prime factorization possibly

[unkempt void]

I know you've done it, but just wanted to point out I don't think Wilson is particularly helpful because elements of (Z/pZ)^x have order p-1, not p

Even though Wilson was honestly what came to mind for me first too xd

[sacred junco]

can someone help/guide me with this please 😭?

[wooden glen]

Perhaps, if you explain a bit more about what you find difficult about it.

(There's a fair chance that you're overthinking it because of the overcomplicated problem statement -- if you can think of any way to understand the task that feels much too easy to be right, then that is actually it!)

[sacred junco]

okay um i just don’t know how to go about answering it. i think i understand base expansion to an extent but this question has just stumped me

do they want an example of a real integer (like a number)? that seems too easy and idk how to work out that number to begin with anyways

[wooden glen]

They just want the largest integer that can be written with two binary digits.

[sacred junco]

wouldn’t that be 99? i think i’ve misinterpreted it wrong 😭

[wooden glen]

It would be 99 if they asked for the largets integers that has no more than two digits in base ten. Here they're asking the same in base two.

[sacred junco]

okay i think i’m foggy on the basics of bases. i know that 2^0 =1, 2^1=2, and so on and i know how to convert between base 10 and another base such as 8

but it’s stuff like this question which has stumped me because i am missing some fundamental piece of knowledge

[wooden glen]

No. You're overthinking it.

Do you know, for example, how to write the integer five in base two?

[sacred junco]

yeah it would be 5/4 and then dividing the answer by 2^1 and repeat. i can’t explain it well but i know how to do it yes

[wooden glen]

What do you get the answer (to "five in base two") to be?

[sacred junco]

101

[wooden glen]

Right. And since that has three digit rather than the two it's allowed to, five is not one of the numbers you're asked to find the largest of.

Every number larger than 5 will be at least as long in base two, so they won't qualify either.

So the only candidates left will be 0, 1, 2, 3, and 4.

Which of those give at most two digits when you write them in base two?

And which numbers among those is the largest?

[sacred junco]

ohhh

[sacred junco]

i worked it out. it’s 3!! because it’s 11 written in base two

tysm you explained it so well. i can’t believe i didn’t get it

[wooden glen]

Eyup!

[sacred junco]

you’re very good at explaining. thanks again!! :))

i’m assuming the answer is just ‘3’? nothing else has to be added?

[wooden glen]

That's what I would write.

[sacred junco]

okay great, thanks 😊

[abstract hornet]

https://tenor.com/view/tyler-the-creator-tyler-fortnite-falling-gif-26313918

[wooden glen]

Please avoid random gifspam outside #chill.

[chrome lily]

when you are using the Euclidian algorithm to find the gcd of two numbers, what do you do when the first division results in 0

are they automatically Relatively prime to eachother

[sleek spire]

one of them is a multiple of the other

[rancid tartan]

Does this look alright for a proof that Fermat's last theorem is true if you can assume that it is true for primes and 4?

[wooden glen]

You don't need to repeat anything for all prime factors of the exponent.

If x^n+y^n=z^n has no nontrivial solutions, then it is clear that x^(kn)+y^(kn)=z^(kn) cannot have nontrivial solution either.

So it is enough to prove FLT for enough exponents that every number >=3 is a multiple of at least one of them.

And every natural number >=3 is divisible by either 4 or some odd prime.

[rancid tartan]

Makes sense

[abstract delta]

hi

can someone help me get smarter at math LOL

can someone help me study for the state test

[carmine tide]

Try the relevant channel under pre-university or open a help channel (see #❓how-to-get-help)

[abstract delta]

ok

thx

[gaunt sedge]

Context: quadratic rings

[sleek spire]

can you remind me what a quadratic ring is

[gaunt sedge]

My question is in the proof of this

[sleek spire]

the proof of lemma 8.3?

[gaunt sedge]

I think they contain all algebraic integers of the quadratic field Q(sqrt(d))

[gaunt sedge]

But this was also something we proved

[gaunt sedge]

Yeah I will write it up gimme a sec

[sleek spire]

do you know gauß' lemma?

[gaunt sedge]

Also this was the definition of R, sorry I left it out

[gaunt sedge]

Don’t think so, at least not by that name

[sleek spire]

polynomial ring over a ufd is a ufd

oh wait is that an alpha

or an x

[gaunt sedge]

Alpha

[gaunt sedge]

My bad again, alpha can only take one of two values, written in green here

Here’s my attempt of the proof below

After the red underline, is everything still correct

I was confused because I was trying to show that Q equals one of the prime integers. Which I couldn’t figure out because the p_i may not be irreducible so we can’t conclude RHS is a reordering of the LHS.

[gaunt sedge]

Nope, we didn’t do anything on polynomial rings

[wild mesa]

Is there a formula for the number of factors of a non negative integer n?

[sterile pumice]

DraK

[leaden swan]

Where p varies over the set of primes

and v_p(n) is the largest power of p dividing n

Well if n is 0, it would be infinite

This works for positive integers

@wild mesa

[wild mesa]

What If n=10, would It be (1+1)(1+1)=4?

[leaden swan]

Yes

1,2,5,10

[wild mesa]

Oh

Clever

Thanks

[safe halo]

Is it possible that a prime number is larger than the sum of the 2 preceding prime numbers?

[eternal plinth]

Let p be a prime of the form $4k + 1$ such that $p = m^2 + n^2$, where m and n are integers and m is odd. Suppose q is an arbitrary prime factor of m. Find the Legendre symbol $(\dfrac{q}{p})$. Use this to find the Legendre symbol $(\dfrac{m}{p})$.

[sterile pumice]

Glory

[eternal plinth]

hi! was wondering how do i start for this problem?

[unkempt void]

Oh interesting - ig if you've not seen then this would be stronger than bertrands postulate

[glass verge]

how do you prove that Every common divisor of $a$ and $b$ is a divisor of $gcd(a, b).$

[sterile pumice]

normalAtmosphericPa=101,325

[leaden swan]

Well do you know the definition of gcd in terms of prime powers?

Or well that would usually be how gcd is defined

[glass verge]

nop

[safe halo]

yeah

[sleek spire]

write down the definitions of those things

that should make it clear I hope

[tight eagle]

How do I find the general solution of a Diophantine equation ax+by = c where a and b are not relatively prime to each other

like 25 and 5

[unkempt void]

you can divide through any common factor

so like, if you wanna solve ax + by = c and if h is the hcf of a and b, then either

1. h doesn't divide c - then there are no solutions, since h would divide the LHS but not the RHS
2. h does divide c, so you can divide through by it and then you have (a/h) x + (b/h) y = c/h and a/h, b/h are coprime so you're gucci

In fact this is why we basically only care about the case where a,b are coprime

[tight eagle]

is coprime the same thing as relatively prime

[unkempt void]

yes.

[tight eagle]

oh ok

[unkempt void]

Sorry, I should've used the same language you used

(Though coprime seems more common overall anyway)

But I hope that's clear

[tight eagle]

oh yea thanks, but essentially I want a and b to be coprime so I can use ax + by = 1

[unkempt void]

Yup yeah

That's why you gotta divide through the hcf

And then bezout machine goes brrr

[tight eagle]

Ok makes sense thanks

[unkempt void]

Np

!

[tight eagle]

Can someone verify my proof

if I didn't ,make a mistake I ended up proving gcd(2n+3, 3n+1) = 1 which implies it always divides 7

[unkempt void]

Hm well the gcd is not always (take n=2), so something must have gone awry

Also in the last line, you seem to be giving an equality between multiple statements - you should rewrite that

I sort of doubt you need the Euclidean algorithm (assuming that is what you are using)

I would take a fairly different approach and not use induction, actually.

@tight eagle

I also don't fully understand your working (what are rk etc)

[tight eagle]

oh

r_k = gcd(2k+3, 3k+1)

[tight eagle]

I just skipped to the last step of the euclidean algorithm for gcd(2k+3, 3k+1)

[unkempt void]

Ah

[tight eagle]

@unkempt void how would you do this question, im kind of stuck

I just keep wrapping back around to the euclidian algorithm

[unkempt void]

Hm so like

Suppose a divides 2n +3 and 3n+1

You need to show a divides 7

Agreed?

Now the n is annoying here, of course

So try to get rid of it

If you see the trick it comes out in one line

Lmk if u get stuck but have a go

[tight eagle]

@unkempt void

Like so?

[unkempt void]

Yup perfect!

Well done.

Very clear

[tight eagle]

I guess I was overcomplicating it before huh

[unkempt void]

Yeah i think this is simplest but it makes sense why you'd try induction

[tight eagle]

thanks a lot once again :]

[unkempt void]

Np

This is often a nice thing to try btw like

if you have some a,b,c and a divides b and c

Often it can be useful to consider convenient linear combinations of b and c

Like here

So like you can also see that the GCD divides -7n I guess

Well that isn't very enlightening lol

But if the numbers worked out differently maybe it would be lol

[tight eagle]

ah okkkk

im just working through a long list of practice problems prepping for an exam

hopefully I wont have to come back here too often 😩

[torn escarp]

I'd do the euclidean algorithm,
gcd(2n+3, 3n+1)
subtract first from second
gcd(2n+3, n-2)
subtract second from first two times
gcd(7, n-2)
at this point you know the gcd can only ever be 1 or 7

and actually we can be exact, the gcd is 7 when n=2 mod 7, and 1 otherwise

[livid birch]

can i get a hint on a) pls

[brisk skiff]

If g is a primitive root then g^(p-1) is the only power of g from 1 to p-1 that is equal to 1

so that suffices for g^j = +1 (mod p)

[livid birch]

yeah i got that one

but not the -1 case

[torn escarp]

you could use fermat's little theorem and the fact that x=0 mod ab implies x=0 mod b

actually I think I'm making a mistake there

[livid birch]

took a break and am back

trying contrapositive rn

[livid birch]

different but is this correct

[brisk skiff]

You could use contradiction

If it was congruent to something else

Then when you square that you get some number other than j=p-1

Sorry 2j

And g^2j would have to be congruent to 1 (mod p) because g^j congruent to -1 (mod p)

But that’s a contradiction

Because of the definition of a primitive root

(If 2j is something other than 0 mod p-1)

[tight eagle]

Im trying to use wilson's theorem to solve for an inverse

I saw somewhere I it implies (17-1)! is congruent to 1 (mod p)

but wouldnt it be congruent to (p-1) not 1?

nvm figured it out

but now I want to know is x = (15)!*(-5) a specific solution

would saying x = (15!)*(-5) + 17m for any integer m give me a general solution?

[verbal cedar]

but 16=-1 mod 17. so it is its own inverse

idk i feel like wilson's is really not suited for this

so i did problem 1 fine. but im struggling with problem 2. i don't know if mod 63 has any primitive roots? wolfram says it doesn't but i'm not sure

[tight eagle]

didn't I find the correct solution though?

also my mistake I was not solving for the inverse, I was solving for the congruency 16x is congruent to 5 (mod 17)

[verbal cedar]

yes, but why write the solution that way, with an ungodly huge number, when you could have multiplied by -1 and gotten x=-5 mod 17?

technically, it is correct... 15!(-5)=12=-5 mod 17. but... why

[tight eagle]

so you're saying I could have just used the fact that 16 is congruent to -1 (mod 17) and then multiplied both sides by (-5) to get x = -5

[tight eagle]

I just learned Wilson's Theorem and Fermat's little theorem so maybe the point of the textbook exercise is just the application of the theorem

[verbal cedar]

did it actually tell you to use wilson's for that?

[tight eagle]

No

but it was the questions for the brief chapter introducing the 2 theorems

but yes I guess I got caught up in a unnecessarily complicated solution to a simple problem

[verbal cedar]

this was on a hw in my class from a few weeks ago. if you want practice with wilson's. these weren't too bad

[tight eagle]

oooh, interesting thanks

[verbal cedar]

np

[verbal cedar]

oh wait am i supposed to split it up into x^3=1 mod 7 and mod 9 and use the primitive roots in those modulos?

[livid birch]

do these look right

[unkempt void]

What is -g

[livid birch]

oh my b

[unkempt void]

or is g just like

any primtiive root

[livid birch]

only given is that g is a primitive root for p

[unkempt void]

Sure

[livid birch]

and p is an odd prime

[tight eagle]

Can someone help me with this

[unkempt void]

Well the first one doesn't show -g is a primitive root

it seems to just show that (-g)^4k =1

[tight eagle]

I tried using fermat's little theorem and Euler's but I keep getting stuck

[unkempt void]

which is the case for any element of (Z/pZ)^x

[livid birch]

oh

i thought that was the same as showing for p-1

[unkempt void]

And i think the same is true for the next

[unkempt void]

wdym

[livid birch]

p - 1 = 4k + 1 -1

no?

[unkempt void]

Yes

But showing a^{p-1} = 1 mod p doesn't show that a is a primitive root mod p

since that holds for any element by flt in fact

[livid birch]

ohhhhhhhhh

it needs to be the smallest such integer

right?

[unkempt void]

ye

[livid birch]

whoopsie

what am i missing then

[unkempt void]

Well idk you basically haven't shown anything ;-;

[livid birch]

i havent seen numbers in so long that some fell in my lap and idk what to do with them

[unkempt void]

Tbh how would I do this lol

[livid birch]

my brain is just "htpy equivalence" this "fundamental group" that

[tight eagle]

@unkempt void can you give me a hand

I feel like my brain is melting from trying to solve this inverse

[livid birch]

ok this is the preceding claim

which i'll assume means it's related

[unkempt void]

Hm so i guess there a couple of things to try with this hm so

[unkempt void]

you can use euler's theorem to like simplify 17^22 first

[livid birch]

since 23 is prime^

[unkempt void]

Or you can find an inverse to 17 and play around w that ig but probs harder

huh 23 is irrelevant, this is mod 21

[tight eagle]

this is what I got with Eulers

[livid birch]

o my b

twin primes moment

[unkempt void]

Uh 17^22 is not 289^21

[tight eagle]

wait oops

hold on

[unkempt void]

But

If you use 289^11

then yup, Euler applies deliciously

Lol

[livid birch]

scrumptious

[unkempt void]

Also like

Well or does it

Uhhh

Yeah it does

[tight eagle]

wow mental truly exploded to write 17^22 = 289^21

[unkempt void]

Nah dw

[unkempt void]

ye noice lemme think

Well

I think the +/- is not enough

to like that claim seems too weak

[livid birch]

yeah i didnt see any connection

but idk

i'll brb

gotta relocate

[unkempt void]

Np

this is making me realise I have forgotten elementary number theory lol

oh wait

[tight eagle]

wait but now im stuck in mod 11 but I want a solution in mod 21

[unkempt void]

So a hint is to consider writing -1 = g^a for some a and see what value a takes

[unkempt void]

Wait why mod 11

You should calculate mod 21

So you wanna calculate 289^11 mod 21

What does Euler's theorem tell you?

[tight eagle]

doesnt euler's set me to mod (m) where m = 11

[unkempt void]

It does tell you to do anything lol like

[tight eagle]

since I did 289^2^11

[unkempt void]

It says 289^φ(21) = 1 mod 21

in this case (since we are working mod 21)

You don't wanna just change the number - you wanna see what is says about 289 mod 21

[unkempt void]

Try to see what this tells us

[tight eagle]

oh

wait I et it

*get it

[unkempt void]

Yeah dope

[livid birch]

not sure how this helps

[tight eagle]

Can someone look at my proof to see if it works

sorry for ss quality

[unkempt void]

Hm so in general for a cyclic group with generator g

of order n

when is g^k a generator

[tight eagle]

5. (RSA) With the encryption pair (N,E) = (33,11) determine the decryptor D.

How do I solve this?

[tight eagle]

I figured it out and got D = -9

is that correct? Cause I verified my solution and it said D = 11 which is -9 +4m for m = 5

[loud moon]

@tight eagle it's the same thing because D (and E) can be taken modulo phi(N), and in this case phi(33) = 20 and -9 = 11 (mod 20). usually you take the smallest positive value, here 11, as the representative of that residue class modulo 20

(you can also do slightly better and take D modulo lambda(N) where lambda is the carmichael function, in this case lambda(33) = 10 so D = -9 = 1 (mod 10) actually still works, which funnily enough shows that in this case the RSA parameters do absolutely no encryption, i.e. m^11 = m (mod 33) for any message m)

[verbal cedar]

so my professor accidently gave us this question despite us not learning euler's criterion or quadratic residues yet lol. i'm still trying to understand it though, and i was able to do all the parts except c. could someone give me a hint for how euler's criterion could help me do this? reading the wikipedia page, i'm not exactly sure how to apply it or what it does/how it works

[white lion]

Is my proof correct? I showed d = b not |b| how can I do so?

[unkempt void]

d|b and b|d doesn't imply d = b

[white lion]

because b is not necessarily a positive number?

[unkempt void]

Well

I mean this is true in general that x|y and y|x doesn't imply x=y

[white lion]

What’s true in general?

[unkempt void]

Like x could be -y

[white lion]

If both d and b is positive then it would be equal tho

[unkempt void]

So yeah you get d=|b|

[white lion]

So I am right ?😅

[unkempt void]

About what exactly lol

[white lion]

I’m so confused rn😂

[white lion]

My proof is correct?

[unkempt void]

No your proof isn't correct for the reason I said

[unkempt void]

.

[white lion]

Yeah gotcha

Thanks @unkempt void

[unkempt void]

Np

[white lion]

@unkempt void is this correct?

[unkempt void]

Wait how is d > 0 a theorem

Isn't that just a convention or definition

[white lion]

It is part of a theorem that the d is the least element of set of positive integers ax+by

[unkempt void]

Also you seem to be using "there exists" to mean "for some", which is nonstandard

Ah ok

[white lion]

Right right

Thanks for the input

[unkempt void]

But lemme read now

Owo

Yeah that's good

I would say like

Well

I think if you just keep the original proof and add another line then that'd be better

Like you have b|d and d|b

Which implies d is +/- b

Since d is positive, we therefore have d =|b|

That is essentially what your second go at it does though

[white lion]

Alright perfect thanks a ton 👍

[verbal cedar]

eulers criterion is used to determine when something is a quadratic residue right? how could i use that to show 2^2, 2^p, or 2^(2p) is not 1 mod 4p+1 (assuming it's prime)?

[loud moon]

consider the implications of 2 not being a quadratic residue mod q (we can show that 2 is indeed not always a quadratic residue due to the form of q, for example for 29 = 4 x 7 + 1)

[verbal cedar]

so if there's no solution to x^2=2 mod q, then we can't do
(x^2)^(2p)=1=2^(2p)
is that the basic idea?

[loud moon]

no, that doesn't really work, just because a != b doesn't mean f(a) != f(b) in general... but since the question mentions Euler's criterion, have a look at what it says if 2 is not a quadratic residue

[verbal cedar]

oh wait i think i see
2^(2p)=2^(q-1/2)=-1

sorry I'm distracted i need to look at it again or else I'm just spewing nonsense lol

[loud moon]

no that's correct, so now what can you conclude about the order of 2 mod q

[verbal cedar]

oh right so if it was a quadratic residue then it can't be a primitive root because then it has order dividing 2p so not 4p=q-1.
and if it's not a quadratic residue then it obviously can't have order 2p because then 2^2p=-1.

but I'm still not quite seeing how to conclude that 2 and p don't work either...

[loud moon]

think about the ideas of Lagrange's theorem

[loud moon]

yes, although the question asks you to show that the order is not 2p, so we don't need to consider the case where it is a quadratic residue - we only need to show that it is possible for it to be a nonresidue for at least some choices of q (for example using supplements to the law of quadratic reciprocity) and if it is, then the order can't be 2p

you can also be lazy and rigorously complete the questions using a bunch of counterexamples, but I doubt that's what the professor had in mind lol

[verbal cedar]

oh if it was order 2 or p, then 2^2p would be 1 as well right?

[verbal cedar]

we haven't even defined a quadratic residue or what quadratic reciprocity is, so i think the idea is supposed to be relatively simple.
and yeah i don't think he just wants counterexamples.

[loud moon]

yep that's right

[verbal cedar]

sorry could you explain why we don't need to consider if 2 is a quadratic residue? if it was, then it can't be a primitive root. so how do we know it isn't a quad residue?

sorry for all the questions, this is all new to me. i really appreciate your help 🙏

[loud moon]

you're right, I worded that poorly; what you want to show is that 2 must be a primitive root mod q, so you need to show 2 is not a quadratic residue. you can do this quickly by using the supplement of the law of reciprocity, and observing that because q = 4p +1 where p is odd (and prime) then q != +/- 1 mod 8

that is, this argument only works because p is odd (the fact that it is also prime helps with figuring out the orders as well)

(I assume that your professor would have otherwise shown you the law of reciprocity before posting the assignment, so that you can use it)

[verbal cedar]

haha nope, unfortunately. he's a great professor, but he makes mistakes when formulating hw questions. he came up with this himself but forgot we hadn't covered any quadratic residue stuff yet.
but i read some of the Wikipedia page for the law of reciprocity, so i see how the definition of q means it's not congruent to ±1 mod 8 so 2 is not a quad residue.

and because it's not a quad residue, 2^2p=-1 by Euler's criterion, so the order of 2 cannot be 2p, and by extension it can't be 2 or p.
is that a good summary?

[loud moon]

yep that's exactly it

then you can mop up the case for 4 easily and you're finished

[past chasm]

Alrighty, I'll also put this here for help, how do I approach this?

Like my initial thought is to get 28 when i mult 4 and 7 and say it's 0, but don't know if that's right

[loud moon]

yeah you can immediately observe that the middle term with the large exponents is a multiple of 28 so it disappears modulo 28, simplifies it a bit already. then the problem breaks down into two things:

1. simplifying 33^146 mod 28
2. solving 4x = C mod 28 for some small number C (think about the CRT)

[verbal cedar]

thank you so much for all your help!!! i really really appreciate it ❤️

[past chasm]

alright, think i might be seeing it cuz 33 is just 5mod28, 25 is 3 mod28 and 27 is just 1mod28,

Yeah

Thanks

❤️

[quiet mesa]

@rough cradle are these all integers?

[rough cradle]

x y z are odd integers and a b are the ones without factors

common factors*

I know how to do this generally I just dont know how to represent a and b

I was taught to replace all the variables with ones I can work with

[quiet mesa]

hmm, I don't see an obvious way of rewriting that

feel free to repost the question here, and see if anyone else has an insight

[rough cradle]

xa^2 + yab + zb^2 ̸= 0

all good

Ill just leave this for last I have a bunch of problems to work through

usual case of being taught something then get a question thats 10x harder than any example you can reference

[quiet mesa]

so actually here's a thought

if you consider the eq xa^2 + yab + zb^2 = 0, you can divide through by b^2

and get xa^2/b^2 + ya/b + z = 0

then set t = a/b, to get xt^2 + yt + z = 0

ill let you play around to see if you can get anywhere with that

[rough cradle]

ok so I think I got it

is it true that if two numbers dont have a common factor they must either both be odd or one is even and the other is odd?

[dusty dragon]

if they were both even, then 2 is a common factor

[gaunt sedge]

Hi, I have a question

I have tried considering the norm of r but the +1 gets in the way

[gaunt sedge]

Oops, context: trying to prove infinitely many irreducible elements in R (by contradiction), so the list above is assumed to be all of the irreducible elements in R.
I know that every element in R is either a unit of product of irreducible elements.

[spare rivet]

good day all, please how do i convert A454 from Hexa to it's BCD equivalent

[hollow zenith]

what's BCD

[leaden swan]

Binary Coded decimal, ig

[wheat tinsel]

Let P(x)=ax^2+bx+c, with a,b,c integers. Then P has a rational root if and only if b^2-4ac is a perfect square.

Is there an analog of this for cubic polynomials?

mmh I guess the problem is that you can have one rational root and two non-rational roots

[sleek spire]

there's the cubic formula

we know that the nth root of an integer is either an integer or irrational

[wheat tinsel]

yes but I dont think the things that fall inside radicals need to be perfect powers or anything

but you have sums and nested radicals

this is much more complicated

[dusty dragon]

Just looking at the discriminant when we move to the cubic case isn’t strong enough to deduce whether there exist rational roots. If the discriminant is a perfect square, then it tells you that either all three roots are rational or none of them are rational.

[eternal plinth]

May i ask is there a way to express a number as the sum of four squares?

And how about expressing a prime as the sum of two squares? Or is it plain trial and error

[white dome]

What about 3?

[white dome]

There is a result by Lagrange which answers this question

[eternal plinth]

Wdym

[eternal plinth]

Can u elaborate more on this?

[white dome]

Look up "Lagrange's four-square theorem". I don't know the proof for the statement though.

[white dome]

Is 3 a prime? Can 3 be expressed as the sum of two squares?

[eternal plinth]

yes 3 is a prime but it can't be expressed as the sum of two squares

i know that a prime can be expressed as a sum of two squares iff the number is not 3 mod 4 and the power of each prime factor that is in the form 4k+3 must be even

nvm i got it

thx!

[wooden glen]

I think Glory is asking not just whether four squares that add to a given numbler always exist, but also about an efficient way to find those four squares?

[eternal plinth]

yeah i was referring to this question

[white dome]

Ok. I don't know how to do that in general. Maybe you can start by looking at the remainder mod 4 and see from there how many odd numbers you need.

[fervent grove]

I believe that there exist algorithms for this based on lattice basis reduction (like all good number-theoretic algorithms)

here are some other suggestions: https://mathoverflow.net/q/259152/473811

[wide turret]

When is a_1^2 + ... + a_m^2 = 4 for integers a_i?

Is it either 1+1+1+1 or 2^2 ?

And nothing else

[sleek spire]

(-2)^2

2^2 + 0^2

2^2 + 0^2 + 0^2

[wide turret]

Sorry I meant positive integers

[sleek spire]

are you french

[dense fern]

how do you show the order of any integer m \in Z_n has order n/gcd(m,n)

[leaden swan]

You can conclude <m>=<gcd(m,n)> where <x> is the cyclic group generated by m in Z_n

And then it's easy to see that <gcd(m,n)> has n/gcd(m,n) elements

@dense fern

[leaden swan]

For this use bezout's

[dense fern]

gcd(m,n)^{n/gcd(m,n)} = 1?

[leaden swan]

No

I am not sure how that folloes

[dense fern]

ye im confused

[leaden swan]

Do you know what a cyclic subgroup is

[dense fern]

i mean if its cyclic it'd be the identity after some multiples

[leaden swan]

Well ok you are using group theory terms here

^ is + in Z_n

And 1 is 0 in Z_n

If I understand that correctly,then yeah that's correct

[dense fern]

but i thought i was dealing with multiplication

[leaden swan]

That's definitely not the order in the multiplicative group

[dense fern]

hmm ic

[leaden swan]

Consider Z_10 and element 8, 8^(10/2) cannot be 1 mod 10

Because 1 is not divisible by 2

[dense fern]

but yeah since gcd(m,n) = am+bn for some a,b \in Z this implies gcd(m,n) \in <m>.

[leaden swan]

The other inclusion should be obvious

[dense fern]

ofc

[dusky nebula]

hi i want to check something, not sure if it belongs here

for the power set of any monoid M that is a subset of N U {0}, is the identity element of the power set {0} and is any element A of the power set an atom of the power set if |A|=1

[dense fern]

what is an atom?

[dusky nebula]

an atom is an element of a monoid such that if two elements x & y of the monoid are combined by the operation *, and x*y=this element, then at least one of x & y is the identity element in the monoid

here the power set of the monoid is also a monoid

[dense fern]

oh similar to a prime or irreducible element

[sterile pumice]

NupurJ

[lone rain]

here, p is prime

[leaden swan]

Well the same way you solve linear equations in R?

[lone rain]

oh goodness me. i am sleep deprived it seems

[leaden swan]

If x_1 and y_1 are solutions ,you get that (ab'-a'b) x_1 = (b'-b)

Similarly you get a thing for y_1

If F_p weren't a field ig you can have multiple x_1 s satisfying this?

[lone rain]

thank you!

[leaden swan]

Well actually this can have more than one solution if a=a' and b=b'

(ab'-a'b) x = (b'-b)
(a'b - ab')y = (a'-a)

If ab'-a'b is nonzero, you get (x,y) to be unique

If ab'-a'b = 0, you get b'=b and a'=a

And ax+by = 1 has p solutions(each solution is generated by varying x from 0 to p-1 and finding the corresponding y if b is nonzero)

[sacred junco]

does anyone know how to do a question like this? i just don’t understand how to work it out

[unkempt void]

One thing is that it suffices to check x and y between 0 and 5, since we're doing modular arithmetic

In fact, since you have x^4 and stuff, it suffices to check 0,1,2,3 (since 4 = -2 mod 6 and 5 = -1 mod 6)

That makes it a little check

Or you can use more technology like Fermat's little theorem

[sacred junco]

with modular arithmetic the highest value that it can take is one below the value right? why is that?

[boreal lichen]

because modulo is about remainders here with division by 6. Intuitively if you would have “remainder” 6 it would in reality be remainder 0, since you can divide this number by 6. (the quotient q and the remainder r of a divided by n means
a=nq+r and 0<=r<n (nonnegative integers))

[sacred junco]

ohh right. thanks for explaining

[brazen night]

How do I prove for prime $p$ that if $x=a ; \text{(mod $p$)}$ and $x= b ; \text{(mod $p-1$)}$ then $x^x=a^b;\text{(mod p)}$

[sterile pumice]

Orthonormal

[leaden swan]

$x^x = (a^{((p-1)k+b)}) \mod p
= ((a^{p-1})^k * a^b) \mod p
= a^b \mod p$

[sterile pumice]

DraK

[blissful marlin]

due to FLT we have that a^{p - 1} = 1 (mod p) for any integer a and prime p, does this mean that all integers are primitive roots mod p?

[unkempt void]

No

What is the definition of a primitive root

[blissful marlin]

a number for which the order of it mod p is p - 1

[west glade]

and what is the definition of order

[blissful marlin]

least number which is 1 mod p

ah

least

[west glade]

yep

[blissful marlin]

thank you

[west glade]

well least positive exponent yada yada

[blissful marlin]

what

[west glade]

you said least number which is 1 mod p. it's the least positive exponent k so that a^k=1 mod p

[torn escarp]

That's false, it's not true for any integer a

a must not be a multiple of p

[sterile pumice]

Orthonormal
Compile Error! Click the reaction for more information.
(You may edit your message to recompile.)

[unkempt void]

You seem to have made two mistakes applying flt under I'm misunderstanding

You went from 3^(3^2022)) to 3^2022

[leaden swan]

So how do you solve systems of congruences where the moduli are not coprime.

So Take the system
$x = a \mod m, x= b \mod n$
Then you can find n',m' such that nn' = gcd(m,n) and mm' = gcd(m,n). My gut instinct is to consider the number
$\frac{a}{gcd(m,n)} mm' + \frac{b}{gcd(m,n)} nn'$ but this feels like it will not work if gcd(m,n) doesn't divide a or b

[sterile pumice]

DraK

[leaden swan]

Well also how do you recognise if the system has a solution at all generally

[wooden glen]

Well, you're out of luck unless a == b (mod gcd(m,n)).

[high hinge]

What does the inverted T mean in this context?

[wooden glen]

Otherwise let gcd(m,n)=g, a = Ag+k, b = Bg+k. Then solve

X == A (mod m/g) X == B (mod n/g)
and set x = Xg+k

[unkempt void]

Often means coprime

Are they using \ to means divides lol

[wooden glen]

Oh, it's Iverson brackets, then.

[high hinge]

Yes lol

[high hinge]

Oh that would make sense thanks!

[unkempt void]

Np

[leaden swan]

Ok that's clever

[wooden glen]

The typography looks like Concrete Mathematics, too.

[unkempt void]

That's what I assumed too lol

Feels a bit idiosyncratic

[high hinge]

Actually, in this context would that mean k divisors of D that are coprime with the divisors of m ?

[leaden swan]

Well it's the count of numbers coprime to m/d

[high hinge]

Ok thank you 🙂

[sacred junco]

I want to prove/disprove this conjecture:
Let x_0=a/b for coprime posints a,b, with floor(x_0)>=2.
Define x_(n+1)=x_n * floor(x_n) for all integers n>=0
Then, for some k>=1, x_k is an integer

I worked out some small cases and suspect it's true
I've tried proving that for all primes P_i, we eventually have floor(x_k) is congruent to 0 mod P_i

Since if I had that then I could repeatedly apply this until we get all the primes in the prime factorization of b, which would finish it

[sacred junco]

Not sure how to make progress with this though

[junior swallow]

where did this -5 come from? and why are we allowed to reduce (8^12)^8 to (1)^8? is it because that's the remainder you get when you divide 8^12 by 13?

[sacred junco]

Yes, FLT gives you 8^(13-1) congruent to 1 since 13 is prime
Also 8^12 congruent to 1 mod 13 implies
(8^12)^8 congruent to 1^8 mod 13

Also 8 is congruent to -5 mod 13

[sacred junco]

<@&286206848099549185>

[leaden swan]

I have a feeling you will need analytic NT for this

[terse fog]

Could anyone give me a sketch of how to prove a quadratic form si universal if it represents zero?

I am assuming the quadratic form is non-degenerate, and have reduced it to the diagonal case, i.e. of the form a_1x_1^2+...+a_nx_n^2

[sacred junco]

Would #advanced-number-theory be a better channel?

[leaden swan]

I think so

[coral locust]

Can someone please help me with this???

[pine badge]

Which natural numbers can be represented as x = lcm(a,b,c) Where 0<a<b<c<x ?
Obviously numbers with more than three divisors and more than one prime factor.

[fervent grove]

I suspect that anything which is composite and not the square of a prime will do

[pine badge]

I think even not a power of a prime, ex. 27.

[fervent grove]

ah that's right

[sacred junco]

If x and y are integers, 6 divides x, and 20 divides y, then you'll always get a solution

So infinite sols

[covert thistle]

hello

i am need of number theory help

im currently trying to publish and am stuck

as per the guidelines of 1.1 of https://www.ams.org/journals/mcom/2003-72-241/S0025-5718-02-01418-7/S0025-5718-02-01418-7.pdf if i were to dynamically program the function C() to maximize asymptotic prime density over a distributed architecture i could theoretically find integers larger than the one presented in this paper and smash these polynomials through factorization algos

i don't think this is too advanced just a touch of programming

[hollow zenith]

if you're working on something to publish and are serious about it

get someone at your school to help you

and gauge what is worth publishing and such

[covert thistle]

yeah im no longer in school its kinda fucked because it only all connected the other night

[rose trout]

Use the inequality for the gif

n<= floor(n) <n+1

[sacred junco]

are you able to publish without being in uni?

[sleek spire]

why shouldn't you

[sacred junco]

red tape?

would depend on the journal

[barren garden]

i've made too many failed attempts at proving this properly...

show that every nonzero integer n may be uniquely represented in the form sum c_j 3^j with j=0 to s where c_s ≠ 0 and each c_j is equal to -1, 0 or 1

i understand intuitively what to do, particularily that if any c_i = -1 we have that 3^{i+1} - 3^i = (3-1)3^i = 2*3^i so we just get a base-3 representation of n, but i'm not sure how to actually do this formally

if only one c_i could be -1 it is easy, but the problem is that i'm not sure how to show that this idea still works for any set of c_i's

i haven't touched this for quite some months since i spent the entire last summer break and much of christmas break agonizing over being so close to a solution but unable to write it down lol, but it's been lurking in the back of my mind

[barren garden]

i know also that i can take the base-3 representation of n, sum b_j 3^j from j=0 to t, and then set d_j = b_j - 1 to get n = (sum d_j 3_j from j=0 to t) + (3^{t+1} - 1)/2, but i'm not sure if that'll lead anywhere, due to the (3^{t+1} - 1)/2 term

if only there were no 1/2 factor

[dusty dragon]

There are two parts that you need to show: existence and uniqueness. Existence can be pretty easily with induction on n. The tricky part is uniqueness. To show this, assume you have two representations of n. Then subtract one from the other and show that the coefficients of these two representations are equal

[barren garden]

uniqueness i'll deal with when i come to it, i think it's precisely the induction part i don't know how to structure

[dusty dragon]

Ah

[barren garden]

i'm comfortable with induction over all n, but weirdly i can never seem to wrap my head around induction on finite n...

i know that makes no sense, i don't make much sense generally

[dusty dragon]

So suppose that there is a representation for $n$ - say, [n = c_0 \cdot 3^0 + c_1 \cdot 3 + \dots + c_s \cdot 3^s.] Then we have that [n + 1 = (c_0 + 1) \cdot 3^0 + c_1 \cdot 3 + \dots + c_s \cdot 3^s.]

[dusty dragon]

This is all fine unless c_0 is already 1

[barren garden]

OH

[dusty dragon]

If $c_0 = 1$, then [n + 1 = -c_0 \cdot 3^0 + (c_1 + 1) \cdot 3 + \dots + c_s \cdot 3^s]

[barren garden]

it did not occur to silly me we should consider n+1, i was just thinking of starting with some repr with digits in {0,1,2} and reducing it to a different repr with some of the digits now in {-1,0,1} and then doing induction on that new repr but with the same n

thank you very much open, i think i've got it

[dusty dragon]

[leaden swan]

Well you need to cascade that further

What if c_1 were 1

[eternal hornet]

Hello, does anyone know how to prove the following identity for the Möbius function?

$\sum_{i \leq n} \mu (i) \floor{\frac{n}{i}} = 1$

[sterile pumice]

Miyo

[dusty dragon]

Well yes, but the same principle applies

[torn escarp]

I'd guess write the floor as another sum (possibly over divisors), switch the order of summation so it looks more like a dirichlet convolution or something like that

[torn escarp]

you've made some mistake, you can't have composite numbers in the bottom of a legendre symbol (although there are generalizations that do, walk before you can run)

show your steps

hmm hard to tell if you're doing it right, if you'd doing reduction mod 263 you can just cut out more and do that in a single step

like going from (3000/263) = (107/263) is fine

so you determined 107 is a prime = 3 mod 4 and got this, this is good:
(3000/263) = (263/107) = - (156/107) = -(49/107)

although there's an important rule you should know of

(ab/p) = (a/p) (b/p)

(this is how I would have started solving it from the start, but let's just go with your way since it's almost done)

so you can write (49/107)=(7^2/107) = 1 (it's literally a square so it's +1, a quadratic residue)

that make sense?

so (3000/263) = -1

---

How I did it was starting from the completely multiplicative property by factoring in the beginning:
(3000/263) = (2/263)(3/263)(5/263) = (+1) (-(263/3)) (263/5) = -(2/3)(3/5) = -(-1)(-1) = -1

in the first = sign I implicitly threw away (2^3/263) = (2/263) (2^2/263) = (2/263) since (2^2/263) = 1 (a square is +1)

[torn escarp]

doesn't matter if it's +1 or -1 since it's squared

but more importantly (a^2/p)=1 because a^2 is a quadratic residue

there's no reason to keep going after that point

[eternal hornet]

Thanks, in the end I was able to do it by induction, pretty neat

[jolly robin]

Hopefully this is the right channel, can someone explain generating functions to me? For a sequence a_n is the generating function just "another way" to express the sequence?

I just dont understand how for the sequence 1, 1, 1, 1, ..., the generating function is this:

Wouldnt that generate the aforementioned sequence for x=1?

[leaden swan]

Not quite

Ok so imagine the series {a_i} as the infinite tuple (a_1,a_2,a_3...a_k,...)

Now a generating function is kind of about mapping this tuple to a formal power series

@jolly robin

So (1,1,1...) gets mapped to the element (1)1+(1)x+(1)x^2...

If you are talking about ordinary generating functions

[jolly robin]

ohhh

...but why though

[leaden swan]

Because formal series have more properties than regular tuples

For example you can take infinite sums like this

So an use case for generating functions is solving homogeneous linear recurrences with constant coefficients

[jolly robin]

Allright so for a_n=1/n you would have 1/1 * x+1/2 * x^2 and so on?

[leaden swan]

Yes that's the ordinary generating function

[jolly robin]

Well apparently -log(1-x) is also the generating function for 1/n

[leaden swan]

Yea

[jolly robin]

but how do you get that

as in

-log(1-x)=1/n for any x?

no thats not the right way to put it

[jolly robin]

so it would be 1/1 * -log(1-1) + 1/2 * -log(1-2)?

thats what i dont understand really

how does -log(1-x) give us any term out of 1/n

[jolly robin]

so i got that f'(n)=1/n. is that why?

[leaden swan]

Well look up the power series of -ln(1-x)

It can be derived by considering $\frac{1}{1-x}= \sum_{i=0}^{\infty} x^i$ and integrating on both sides

[sterile pumice]

DraK

[jolly robin]

how could i integrate the RHS?

[jolly robin]

is that wrong though?

[leaden swan]

Well wrt x

You integrate termwise

And then add them all together

[jolly robin]

oh, yeah, that was a stupid question lmao

[livid birch]

how do you find the legendre symbol mod a composite

like (47 / 209)

209 = 11 * 19

[leaden swan]

You want the Jacobi symbol?

Legendre symbol is defined only for primes

[livid birch]

o

my question reads "does x^2 = 47 mod 209 have solutions"

[leaden swan]

Well use CRT

Does the system x^2=47 mod 11, x^2=47 mod 19 have solutions

x=5 mod 11, x=3 mod 19 should solve it

Now reconstruct the solution mod 209

[leaden swan]

In general decompose into a system and check if the number is a quadratic residue for each modulus

[livid birch]

oh so we can just break up (47 / 209) into (47 / 11) and (47 / 19)?

[leaden swan]

Well both should be 1 individually

[livid birch]

i mean like

[leaden swan]

Yes

[livid birch]

is that equality valid

oh okay

[leaden swan]

Because CRT

[livid birch]

i knew it worked in the "numerator"

gotcha ty

[leaden swan]

Now your question would be "what if you have prime powers"

And for that,this works
https://mathoverflow.net/questions/223430/relationship-between-quadratic-residues-modulo-a-prime-and-quadratic-residues-mo

So 47 is a quadratic residue for 49 iff it's a quadratic residue for 7

[leaden swan]

It's valid only if the splits are coprime

[livid birch]

on a different note, any pointers?

[leaden swan]

For a) you can consider only 1!+2!+3!+4! mod 5

[livid birch]

oh that's true

that makes that easier lol

[sleek spire]

can I think of $\bZ_p$ as $\varprojlim \bZ/p^i\bZ$ or is that a bad intuition

[leaden swan]

That's how D&F defines Z_p

[sleek spire]

yeah that's what I'm saying

but there's this p adic analytic way of defining them

but yeah they're isomorphic as rings and homeomorphic as spaces

[leaden swan]

Ok,so consider n>5
Then the sum is 9(17+80k). If this were to be a perfect square, 17 has to be a quadratic residue of 80. But this forces 17 to be a quadratic residue of 5,i.e., 2 to be a quadratic residue of 5,which is impossible by observation.

[sleek spire]

<@&268886789983436800>

[north pagoda]

we allow requests for tutoring

just not unsolicited ads

we discourage them, though; easy to get scammed and we claim no responsibility or ability to reclaim funds

[torn escarp]

hold up you can do @livid birch 's problem for part b directly from part a, since you know for n>=5 it's 3 mod 5 which isn't a QR. then just write down the few other cases for n<5 to check

[leaden swan]

lmao, that was obvious

Well ig my answer kinda uses that in a sense

I basically did (9^(-1) 3) is not a quadratic residue of 5

Which is iff 3 is not a quadratic residue of 5

[torn escarp]

yeah you weren't wrong I don't think just like went out further than you had to

since -1 is a QR in Z/5Z both 2 and 3 are NRs

cause 2=-3 yea

[sterile pumice]

LeftySam

[livid birch]

i just realized this later but is b) asking for a square mod 5 or square in general?

hi mero

[leaden swan]

square in general

[turbid ember]

guys pls help me in help-2

[regal aspen]

@leaden swan Zura?

[leaden swan]

Zura ja nai katsura da(Sorry for the ping)

[unkempt void]

You can delete latex stuff for a short period after posting but not long thereafter

[torn escarp]

hey 😛

[livid birch]

[torn escarp]

yeah, it doesn't matter since proving something isn't a square mod n means whatever integer it came from couldn't have been a square either

[livid birch]

and that's why a) proves the n \geq 5 case right?

[torn escarp]

yeah exactly

[livid birch]

def overlooking something simple but any hints on a?

i know obv that x is a square mod p if x^(p-1/2) = 1 mod p

[unkempt void]

Lol p sure I did a q almost identical to this

Well the easiest way to me is just to use standard facts on (2/q), but idk if that's too much firepower

[wheat tinsel]

that is interesting tbh

[livid birch]

well i rewrote it as asking if 2^p = 1 mod q

but idk if that gets anywhere

[wheat tinsel]

ye but its not obvious why that should be true

[unkempt void]

Well

[wheat tinsel]

it is equivalent to p being a nonsquare btw

[unkempt void]

That's what you wanna show in b)

Lol

[livid birch]

oh i hadnt even noticed lmao

theyre equivalent questions then

[unkempt void]

yh i assume you're meant to use a different method and then deduce (using euler's criterion) that 2^p \equiv 1 mod q

[wheat tinsel]

this is weird cuz at some point you have to use the fact that p=3 mod 4, ie, q=-1 mod 8

[livid birch]

arent there a few choices mod 8?

[wheat tinsel]

wait nvm

i said nonsense

[livid birch]

,av croqueta

[sterile pumice]

Croqueta#3385's Avatar

Click here to view the image.

[livid birch]

interior crocodile alligator

[wheat tinsel]

ah no I did not

if p=4k+3 then 2p+1=2(4k+3)+1=8k+7, so q =-1 mod 8

[livid birch]

oh then we can just go by what potato said

potat

[wheat tinsel]

but like this is circular reasoning

from what I remember, proving that 2 is square mod p iff p=+-1 mod 8 would not make it easier if p=2q+1, with q=3 mod 4

(I interchanged the names of p and q)

[wheat tinsel]

Ok so couldnt help because busy with other stuff

But I feel extremely tempted to say that for primes p it is impossible that 2p+1 divides 2^p+1

At least for p =3 mod 4 or something

[wheat tinsel]

P=5 counterexample btw but p=1 mod 4

[livid birch]

how does this make sense

i already proved this

dont b and c contradict each other

[normal heart]

why do b and c contradict each other?

S can be 0...?

disclaimer: I didn't follow the previous questions

[livid birch]

oh wait

S = 0

oopsie

[rain fog]

...

[surreal solar]

Hi, I have an question about Gaussian integers, specifically to prove that Gaussian integers that satisfy a particular equation are coprime. Would it be better suited here or in #advanced-number-theory ?

[normal heart]

#advanced-number-theory i think

[surreal solar]

Thanks, reposted there, and please tag me if you can help me!

[verbal cedar]

how does one "say" this in words? like how do you say (a/p)

[leaden swan]

Legendre symbol?

[verbal cedar]

so "Legendre symbol a b over p equals Legendre symbol a over p times Legendre symbol b over p"?

[normal heart]

You dont need to say "legendre symbol" if we know you are speaking in the context of number theory

[neat abyss]

collatz

[kindred basin]

3x+1, x/2

Please help

[shell minnow]

its true

But the proof would take too long to write out...

[muted kestrel]

but we can approximate a proof by cases

[runic token]

guys i think i proved collatz 🤓

[timber bone]

#advanced-number-theory

[runic token]

OH SHIT

[queen axle]

collatz

[humble hamlet]

collatz

[trim ledge]

which one is probability?

[wooden glen]

#probability-statistics

[reef sun]

Any two numbers can be co-primes when the highest common factor is only 1 right?

[leaden swan]

That's the definition of coprime yes

x,y are coprime iff gcd(x,y)=1

[loud moon]

that's phrased rather weirdly but yes two numbers are coprime if their greatest common divisor is 1

oh oops it didn't scroll down, sorry

[lean gust]

collatz conjecture I love it :)

my prof taught chaos and fractals, and taught the conjecture and also has a few papers written in it