elementary-number-theory

[brittle root]

wait

i should go to sleep

ig you can factorize into primes

[torn escarp]

I think we can use bezout's identity. There exists integers x,y satisfying ax+by=1 iff gcd(a,b)=1. ||So writing a=cd we have c(dx)+by=1 so we have found integers dx, y meaning gcd(c,b)=1||

[still flare]

Even simpler: if k is a common divisor of c and b, then k is also a common divisor of a and d. Therefore 1 <= gcd(c,b) <= gcd(a,d) = 1.

[pine badge]

Thanks, the part I was lost getting is that you just need to show you have integers x,y.

[torn escarp]

I like it but I have doubts that it relies on knowing gcd(c,b)<=gcd(a,b) when c | a, how would I prove this without basically assuming what we have to prove?

[still flare]

Since the common denominators of c and b form a subset of the common denominators of a and b, this follows immediately.

gcd is by definition the greatest common denominator!

[torn escarp]

I agree but then we could just say this directly, couldn't we?

since gcd(a,b)=1 is the greatest common divisor of a and b, removing divisors from a to make c makes gcd(c,b)=1 too

I suppose in some sense, the concept of gcd being well defined in the first place is being assumed here, when I feel like at this level we're calling it the "greatest common denominator" without really knowing that term is really justified. Like if we had called it "bloop function", then we can't appeal to the label that it's the greatest common denominator.

maybe I'm wrong though, I'm trying to think through the details a bit more, like for other rings and what assumptions are going on here

[pine badge]

I don't have the book im reading with me, forgot how it defined gcd.

[sacred junco]

i have a question

[sacred junco]

prove (n+6)^2 - (n+2)^2 is always a multiple of 6

nvm wrong channel my bad

[torn escarp]

it's false, plug in n=-6 to get an easy counterexample

[brittle root]

i think its for all naturals

rather than for all integers

[torn escarp]

makes no difference

[brittle root]

didnt check so

[torn escarp]

polynomials are periodic

mod n

[sacred junco]

why you countering it?

its maths

[torn escarp]

lol

[dusty dragon]

n = 1 is another counterexample

[sacred junco]

but why do you need to counter it, doesnt the first one work?

oh is n=1 the answer to n

[dusty dragon]

first what works?

that expression is not always a multiple of 6 and there are at least two counterexamples

So you can’t prove it

[sacred junco]

nevermind i have realized why my maths teacher dont let me do proofs, thanks for the help but this is why im getting a U in maths

im ver stupid

byeeeeeee

[torn escarp]

weird troll lol

[sacred junco]

i wasnt trolling, just trying to figure out how to do proofs

see ya later alligator

[verbal cedar]

for what $n$ does a solution to

$x^3\equiv1\pmod{n}$

exist? and how could we find it?

[sterile pumice]

nilpotent nix

[verbal cedar]

solutions other than x=1 i mean 😅

[loud maple]

For any n, any x≠1 such that x ≡ 1 mod n would satisfy the requirements, wouldn't it?

Therefore such solutions exist for all n.

[torn escarp]

you could rewrite it as x^3-1 = (x-1)(x^2+x+1) and so ask when x^2+x+1=0 😛

[loud maple]

Unless you meant to ask, solutions where x ≢ 1 mod n

[torn escarp]

start with figuring out when you can solve x^3=1 mod p

[loud maple]

This approach wouldn't give all solutions, would it?

[torn escarp]

I'm just saying factor out (x-1) to exclude it

but it's more of a joke

[loud maple]

I thought you meant x² + x + 1 ≡ 0

not =

[torn escarp]

I don't use the same notation as you

I just use = to mean whatever ring we're working in based off common sense context detecting

[loud maple]

ah ok

[torn escarp]

the easy thing about this is we know that the order of the multiplicative group here is p-1, so you need 3 to divide p-1 by Lagrange's theorem

so that means p=1 mod 3

(you'll have to look at the p=3 case separately though)

tthen you can build up to whatever power by Hensel's lemma and combine the distinct powers of primes by the chinese remainder theorem

maybe check out the Carmichael function, it's basically a better version of Euler's totient function when thinking about the orders of elements

I think I've said a lot, but one important thing to keep in mind is if you have a solution to f(x)=0 mod n, and p divides n, then you also need f(x)=0 mod p. It turns out a lot of the problem can be simplified by just looking at how to solve it at each prime divisor of n.

[verbal cedar]

ah this is incredibly helpful! thank you

[verbal cedar]

i'll be sure to check out all those topics. this makes sense too. i'm sensing a common theme that whenever a question about mod n comes up, mod p is the best place to start.

[torn escarp]

yeah definitely

feel free to ping whenever about this sorta stuff I can explain more or walk through some examples

[fervent grove]

is there actually an efficient, deterministic way to solve x^2 + x+ 1 = 0 (mod p) when p = 1 (mod 3)?
my idea was to just guess random elements and take them to the power of (p-1)/3. about 1 in 3 times this will work.

[leaden swan]

Well you can just do
$x^2+x+1= (x+\frac{1}{2})^2+\frac{3}{4}\$
So the equation reduces to
$(x+\frac{1}{2})^2=-\frac{3}{4} \mod p$

[sterile pumice]

Drake

[leaden swan]

Here 1/x means multiplying with inverse of x(and that exists because we are dealing with a field Z/p)

@fervent grove

[fervent grove]

ok but how do you find a square root of 3

oh right I forgot

shanks tonelli

ok this makes sense

[leaden swan]

I mean shouldn't you be doing square root of -3 if that's your approach

[fervent grove]

sure fine

it's the same question

I think taking square roots still requires you to find a quadratic non-residue

which requires guessing to do efficiently

but I guess this is better by a constant factor

[leaden swan]

Is this a computational problem?

If so then compute what number corresponds to -3/4 in Z/p

[fervent grove]

yeah my question is to efficiently compute this
my objection to your approach is that even finding square roots deterministically is nontrivial

https://en.wikipedia.org/wiki/Tonelli–Shanks_algorithm is basically the algorithm I'm familiar with

[torn escarp]

You could also use the quadratic formula to get the -3

[boreal lagoon]

Is there an elementary proof of "p=3 mod 4 => -1 quadratic nonresidue" that doesn't invoke Euler's identity?

[fervent grove]

if -1 is a quadratic residue, then we can find x such that p | x^2+1. If p is not 2, then x =/= +1, -1, so x (mod p) has order 4 . It follows that p = 1 (mod 4).

take contraposition to get the desired statement

[boreal lagoon]

Damn, you're right, it went over my head that being a residue would imply an order 4 element. Thanks.

[torn escarp]

Sort of related, I don't know if this is efficient, but it's deterministic for a similar problem. $\left(\frac{p-1}{2}\right)!^2 = -1 \mod p$ when $p=1\mod 4$. Maybe there's a similar formula for a third root of unity?

[sterile pumice]

Merosity

[torn escarp]

the formula comes from Wilson's theorem when p=1 mod 4, the second half of (p-1)! can be split off and rewritten as ((p-1)/2)!

can we directly steal this trick when p=1 mod 3 and break (p-1)!=-1 into 3 or 6 pieces maybe?

maybe something similar

I'm guessing 6 because we actually have p=1 mod 6, and we're guaranteed these roots of unity hanging out if w is a primitive 3rd root of unity: {1, -1, w, w^2, -w, -w^2} so trying to imagine them partitioning out the rest of the numbers somehow in a useful factorization for us

[fervent grove]

I feel like whatever approach is taken here needs to be able to deal with the fact it's basically proving QR for the prime 3 right

so something nontrivial needs to be done

[torn escarp]

here's one proof I'm looking at. Since Euler's criterion is $$\left(\frac{-3}{p}\right)=(-3)^\frac{p-1}{2} \mod p$$ we can prove QR for $-3$ by using the fact that $\sqrt{-3}=\omega-\omega^2$ for $\omega$ a primitive 3rd root of unity. In order to do that, we can look at $$(-3)^\frac{p-1}{2}=\pm 1 \mod p$$ by multiplying through by $\sqrt{-3}$ and looking at $$\sqrt{-3}^p = \pm \sqrt{-3}\mod p$$. So, pulling it together, $$\sqrt{-3}^p = (\omega-\omega^2)^p = \omega^p-\omega^{2p} = \pm \sqrt{-3} \mod p$$. The sign will be $+$ when $p=1\mod 3$ and $-$ when $p=2 \mod 3$.

[sterile pumice]

Merosity

[torn escarp]

I dunno if there's anything useful here to extract, but trying to keep closer to algebraic manipulations as I can

also I realize I'm being super terse, like I'm going into an extension field and casually not mentioning it

[fervent grove]

is this the Gauss sums proof?

it looks like it :/

[woven oracle]

hello folks

is this relation

$(a + b)^{r} \equiv a^{r} + b^{r} \text{(mod r)}$

[sterile pumice]

texaspb

[woven oracle]

a theorem of any sort?

[regal ore]

I think you can search “freshman’s dream”

[loud maple]

This holds if r is prime

[woven oracle]

alright

thanks guys!

[sleek spire]

frobenius endomorphism

[unkempt void]

Lol

[torn escarp]

binomial theorem

[torn escarp]

can you link the article

I'm guessing they're just using the fact it's a valuation on Z to show it's a valuation on Q, so it's not circular

[wheat tinsel]

How would you guys approach this?

ok I think I got it

uh wait no

ah yes

2^(pi(x)) gives an upper bound on the number of square free integers below x

done

[unkempt void]

Nice

[torn escarp]

I believe this proof of infinitude of primes is originally due to Erdos

[verbal cedar]

how could I go about solving

$2n\mid \alpha(n-2)$?

[sterile pumice]

nilpotent nix

[verbal cedar]

when $n\equiv2\mod4$, i found $\alpha\mid\frac{n}{2}$

[sterile pumice]

nilpotent nix

[verbal cedar]

but i can't figure out the other cases

looking for solutions of $0<\alpha<2n$

[sterile pumice]

nilpotent nix

[regal ore]

(Referring to alpha as a for easy typing)

Case a is even
2n|(a/2)(2n) - 2n = a(n-2)

Case a is odd
from given, we have a(n-2) is even so n-2 is even -> n is even
let n = 2k
2(2k)|a(2k-2) -> 2k|a(k-1)
we have k-1 is even so k is odd
Let k = 2m + 1 so n. = 4m+2
2(2m+1)|a(2m)
2m+1|a(2m)
2m+1 and 2m are relatively prime, hence 2m+1|a
So n = 4m+2 and a some multiple of 2m+1 = n/2 works

[white lion]

I assume that s=1 and t=10 is the smallest integer solution but how do I write 1 in terms of prime facotriaxztrion?>

[west glade]

60*1 is not the same as 126*10

[sleek spire]

t = 0 s = 0

[white lion]

GOSH DARN IT

[sleek spire]

is the smallest solution

[white lion]

how did you figure that out?

[west glade]

I mean if you wanna be cheeky like that then obviously you can pick s and t very very negative. clearly not what is meant here

[white lion]

i read the question wrong

lol

[west glade]

5 is definitely a prime factor of the LHS, cause it's a factor of 60. so it also needs to be a prime factor of the RHS. it doesn't divide 126, so it has to divide t. with an approach like this you can find which prime factors have to divide s and t at least

[white lion]

thanks!

[white lion]

I got 210 and 10

is that correct?

[west glade]

uhm

a zero too much there maybe?

[white lion]

I got the anwser I just broke the two equations into its prime factors and filled in the gaps

[west glade]

210 tho?

[white lion]

nah it was 21 and 10

[west glade]

yes that looks correct

[white lion]

yeah 🙂

[boreal lagoon]

What is the significance of the Jacobi symbol if it doesn't give you complete information on the solutions of x^2=a mod n (for a,n coprime resiude=>(a|n)=1, but not the converse)?

[torn escarp]

it's much easier to compute since you don't need to find the prime factorization

oh and I sort of took it for granted, but you still have that (a|n)=-1 when a is not a quadratic residue mod n

so if you only care about showing something is a nonresidue, this is the way to go.

[full crater]

good book for elementary number theory for olympiads

[boreal lagoon]

That doesn't justify it, you could dream up any number of expressions that are easy to compute.

[boreal lagoon]

That is clear to me, yes, I was asking about its further uses.

[fervent grove]

often the jacobi symbol is used as an intermediate step amid quadratic residue computations, where things work as you [want]

for example, if you wanted to compute (140|701) or something, you would like to just flip this as (701|140) by quadratic reciprocity for the jacobi symbol

but (701|140) does not make sense as a quadratic residue because the denominator is no longer prime!

so to do this kind of flipping, one has to use Jacobi symbols

one might object that we can just factor 140 into primes before flipping, but in practice factoring the numerator every time we want to apply quadratic reciprocity is much slower than using quadratic reciprocity for the jacobi symbol

in particular, using quadratic reciprocity for the jacobi symbol is about as fast as the Euclidean algorithm, which is as fast as it gets

here's another fun application of the jacobi symbol: https://en.wikipedia.org/wiki/Solovay–Strassen_primality_test
(in practice people don't do primality checking like this anymore because there are better tests, but I think this is something that every number theory student should see)

[sleek spire]

what's a good elementary number theory book that focuses more on computation than proofs?

I've heard that gauß's nt book focuses on computation

but I'm not sure where to find it

[still flare]

I like "Elements of Number Theory" by Gareth and Josephine Jones, which has a fair number of computational exercises, and talks about computational techniques such as the Sieve of Eratosthenes, primality tests, and others. It covers a nice chunk of elementary number theory.

[severe pewter]

If the number 301 in decimal is represented by 1221 in base b, then 442b =

how do I solve something like this

[loud maple]

Represented by 1221 in base b means that it is equal to 1b³+2b²+2b+1

And then you solve the equation for positive integer values of b, satisfying b>2(since 2 is a digit in base b).

[severe pewter]

how do I solve for b when the exponents are different here

[torn escarp]

you can factor 1221 as 11 * 111 in base b, and since 301 = 7 * 43 you can pick out the smaller factor is 7=1+b so b=6

[severe pewter]

I dont understand that

where did you get 11 * 111 and 7 * 43 from

[torn escarp]

I factored 1221 and 301

[severe pewter]

7=1+b

wherer did you get this from

[torn escarp]

11 in base b is 1+b

[severe pewter]

how do you know

[torn escarp]

the string "11" is a base b number, which means that it's 1 * b^1 + 1 * b^0

[severe pewter]

is this another method from this

because that way makes sense '

just Im having trouble solve the cubic equatio n

[torn escarp]

it's the same idea, that's what a base b string representation means

in base 10 the string 1221 would mean 1 * 10^3 + 2 * 10^2 + 2 * 10^1 + 1 * 10^0

in base b the string 1221 would mean 1 * b^3 + 2 * b^2 + 2 * b^1 + 1 * b^0

[severe pewter]

right

so how do I solve for b here now

[torn escarp]

what I did is factored this as (b+1)(b^2+b+1)

(just saying it in a different way, but it's the same thing)

(b+1)(b^2+b+1) = 301 = 7 * 43

7 and 43 are prime numbers and since prime factorization is unique, it forces b+1 and b^2+b+1 to be both of these numbers

I know 7=b+1 and 43 = b^2+b+1 because 43 > 7 and b^2+b+1 > b+1

[torn escarp]

to elaborate on this, whenever I'm asked to factor a cubic I try the rational root test, b^3+2b^2+2b+1 means I should try b=1 and b=-1

[severe pewter]

i saw that

i swear the test for -1 is valid here

[torn escarp]

-1 is a root

that means (b-(-1)) factors out

[loud maple]

In this specific case, one obtains b³+2b²+2b=300
since b is a positive integer, we have b<7 because 7³=343
Also notice that b³ is even, which implies b is even.
So you only need to check 2,4 and 6, which gives 6 as the answer.

[main ermine]

if a and b are coprime integers, are a and na+b coprime for any integer n?

[loud maple]

Yes

[brittle root]

not for n=b. then we have

a(b+1)

[main ermine]

ah yeah ofc but except for those edge cases

is there a proof for this?

my number theory skills are quite lacking lmao

[brittle root]

well if a and b are coprime

we can find integers s and t such that

as+bt=1

not sure if this will help

[loud maple]

na+b would then be b(a+1)

Not a(b+1)

[brittle root]

yeah whoops

hmm

[loud maple]

They are always coprime, no 'edge' cases exist

[brittle root]

wow that was a hilarious algebra mistake

[loud maple]

Let p divide a, if p divides na+b then p divides na+b -n×a, which is b

then a and b are not coprime

Which is a contradiction

[main ermine]

ah i see

thank you

one more question

is this true: c is coprime to ab iff c is coprime to a and c is coprime to b separately

[brittle root]

the forward direction is easy to see

let me think a bit for the reverse

yes

if we consider prime factorizations

[main ermine]

i can see why (c,a)=1 and (c,b)=1 implies that (c,ab)=1, since we just look at the prime factoriztions

actually i can also see the other direction too

nvm LMAO

[brittle root]

you answered your own question

[main ermine]

yeah sorry about that lol

[brittle root]

no thats good actually

haha

[main ermine]

[sleek spire]

<@&268886789983436800>

[dim ice]

this is wrong right.
ive forgotten how i would prove this. i might have to go through my lecture notes from last year

[sacred portal]

I think it's sorta right

bc if u substitute a for b + kn

[dim ice]

could you explain to me pls

[sacred portal]

you should be able to say a mod n = b

so a = b +kn

[sacred portal]

so (b+kn)^3 mod n

which if u expand and simplify gets u b^3

then for the right side you go (b+kn)^2 mod n * (b+kn) mod n

so b^2 (b+kn) modn

[dim ice]

ah

[sacred portal]

so b^3

[dim ice]

yeah i gots it

thats neat

thanks

[sacred portal]

np

[livid birch]

can i get a nudge on this pls

[still flare]

Proof by contradiction.

[rugged pelican]

anyone know what we learn in 8th grade math

[trail tendon]

No

[livid birch]

ok i got that last one

but can i get a different nudge on the claim here

tinkering with the ineq. hasnt given much

i feel like some calc bullshit could prove this lmao

[torn escarp]

well n^2 and (n+1)^2 are composite and the primes have to be... somewhere

[livid birch]

i guess take the prime decomposition of each

say n^2 has i primes in its decomposition and (n+1)^2 has j

[torn escarp]

nah

[livid birch]

[torn escarp]

it's basically the pigeon hole principle

[livid birch]

im gonna put something in a pigeon's hole if i have to do any more of this

not actually i just wanted to make that joke, this isn't that bad

[torn escarp]

lol whatever floats your boat

like maybe it helps to think about as, the intervals (n^2, (n+1)^2) completely cut up the real number line into infinitely many pieces

and all you're excluding are perfect squares, which are composites

so who cares?

[loud maple]

What is this study resource you're using, where well-known open questions are exercises?

[livid birch]

it's a textbook

the open question is motivation, the actual claim is weaker

[livid birch]

proof: who cares

[torn escarp]

maybe try to think of it by contradiction if that helps, assume there are only finitely many, what does that look like?

[loud maple]

Yeah that claim is trivial

Especially given the hint

[livid birch]

[loud maple]

man, what did I say to deserve being called a small brain

:(:(

[livid birch]

it's not you it's me

[loud maple]

bruh

[livid birch]

but i guess a finite number of such n would contradict that there are infinite primes

[torn escarp]

yeah

lol

[livid birch]

but is it enough to just state that...

like it's kinda obvious

[torn escarp]

[livid birch]

profs are so funny

[torn escarp]

nah you're over thinking it, be throrough if you're really paranoid

[livid birch]

my algebra prof constantly says in lectures "yeah prove this for yourselves if you feel like it, just stare at it for a while"

[torn escarp]

yeah see, we're staring

now it's obvious, ez

[livid birch]

and other profs fully expect detailed well structured proofs for everything

maybe i'll submit principia mathematica as my proof of 2+2 = 4

[torn escarp]

no u

[livid birch]

merosity prof?

[torn escarp]

no lol

[livid birch]

https://tenor.com/view/lag-cat-gif-24195317

[torn escarp]

if you want to get obtuse and use analysis you can try saying the sequence floor(sqrt(p_n)) is increasing and bounded above...lol

ok goodnight don't complicate it, much less overcomplicate it

[urban kiln]

Good book to learn number theory

?

[jagged snow]

I recall hearing, once, that you can measure how effective a base is at representing a number by computing some sort of function on the number of digits it needs to represent a number and the number of values those digits can have, and if you do that, balanced ternary comes out on top for most numbers. Is this real, or did I make it up, and if it's real what's it called?

[turbid ether]

Radix Economy?

Not sure if it's exactly what you're looking for but seems close and a good start

Cost measurement for digit representation

[jagged snow]

I think that's exactly it, thank you

[dense scroll]

Does anyone have a hint for this one?

[still flare]

Think about prime factors

[dense scroll]

ahhhh 42 = 2 * 3 * 7 and there isn't any factor of power 2 or 3

so 42 can't divide a^2 and b^3

thanks!

[verbal cedar]

just want a hint, not a solution. we have that a and b are coprime, and their gcd divides 2a and 2b.
so 2a=k1d and 2b=k2d. from there, i'm stuck...

[still flare]

Consider gcd(2a, 2b)

[brisk skiff]

what are some common ways of proving numbers of a certain form are perfect squares? ik abt congruence to 0 or 1 mode 4 but what else

[loud maple]

There are many ways of showing that numbers of a certain form are not perfect squares.

Congruence relations such as the one you have mentioned above.

[brisk skiff]

Do you know any ways besides the one I mentioned?

[loud maple]

all perfect squares are congruent to 0 or 1 mod 3

all perfect squares are congruent to 0,1 or 4 mod 5

all perfect squares are congruent to 0,1,2 or 4 mod 7

There exist similar relations for cubes, fourth powers, and so on

[brisk skiff]

Alright, thanks

[blissful silo]

Perfect squares are never prime number+4, with one exception: 9=5+4

[wooden glen]

That's true.

(And easier to see if you think of it as "a perfect square minus 4 is always composite, with these few exceptions ...")

[sterile pumice]

nilpotent nix

[verbal cedar]

is this a sufficient proof that gcd(ka,kb)=kgcd(a,b)?

[still flare]

Yes

[verbal cedar]

thank you 🙂

[verbal cedar]

if a positive integer d divides 2, then d must be 1 or 2 right? since any positive divisor must be less than or equal to whatever it's dividing

[sleek spire]

yes, if something divides something else then it must be a divisor

[dusty dragon]

More generally, you can replace 2 with any prime p and that statement still holds true

[odd mural]

Hey there! I appreciate any help people could give me on this number theorem problem. Assume m is given by another person and is the product of two large primes, so you don’t know the euler totient function of m. How do you calculate f(x)= 2^(2^x) mod m in polynomial time without first calculating phi(m)? I know how to calculate g(x) = 2^x mod m

[west glade]

just square it over and over, no?

[fathom nymph]

dynamic programming in linear time?

whats the significance of the two large primes?

[odd mural]

if you know the prime factorization you’d be able to calculate phi(m), and then you can calculate a multiple of the period of the function, which makes the problem easy

[odd mural]

I’d like to know it for a large x (like a googol), and I dont have the computing power to calculate a googol steps, or is that not what you meant?

[west glade]

well I mean eventually you do repeat yourself

[odd mural]

how does that work?

[west glade]

you said polynomial time. polynomial time in what. x?

even linear time in x will be ages for x a googol

[fathom nymph]

the series you get by putting x = 1,2,3... is 2, 4, 16, 256... Each number is the square of the previous number. So you just iterate over x and square the last value mod m

thats in O(x) which is polynomial time

regardless of how long x=googol will take

[west glade]

(well ignoring that squaring and reducing also takes a bit of time)

[odd mural]

I don’t get it

[west glade]

being able to calculate it faster seems essentially equivalent to calculating phi(m). so I doubt that works

[fathom nymph]

which part?

[odd mural]

sorry my phone battery died

[odd mural]

wouldn’t it take 10 times longer if x increased by 10 times? I thought that was called exponential time

[west glade]

no

that's linear

if it increased by something like 2^10 then it would be exponential

[odd mural]

oh okay. Is there a way to do it faster?

[west glade]

well at least eventually you repeat and then you know the cycle and everything after that is easy. would require you to store your results tho

but I doubt there is an easier way cause like I said earlier, you can probably calculate phi(m) using this which is famously hard

but maybe I'm wrong, who knows

[odd mural]

thanks. I’m pretty sure it repeats after a very long time for a large phi(m) though, 2^x repeats after a divisor of phi(m), so 2^2^x should not repeat soon either for a large m, but I’m not sure how often it repeats

[torn escarp]

I don't think you can do much better than just square 2 in x steps

is this polynomial? @odd mural

[quaint hare]

Can I write sufficiently large primes p as (l + m)/2 = p, where l,m distinct from p are either primes or 1?

[unkempt void]

Yes, take l = m = p

[west glade]

just assume goldbach

[odd mural]

thanks, and im not sure if its polynomial time, the way I understood time complexity was that if the time complexity increases polynomial when the amount of input bits increases linearly, the algorithm is of polynomial time complexity, but apparently my understanding of it is wrong

[north garnet]

Can anyone give me a hint as to how to start this problem?

What is the smallest nonzero value of $|\frac{x}{36} - \frac{y}{31}|$, where x and y are integers?

[sterile pumice]

Umiguess4000

[still flare]

Multiply by 36 x 31 to get a nice thing to minimise, and apply knowledge of common divisors.

[north garnet]

oooh, ok. I'll try it out and see where i end up. Thank you!

[brittle root]

you very well know what it is

do not troll.

unless you're asking about the additive group of order 2, and even then you should know.

[unkempt void]

It is still 2

[indigo sage]

Does anyone know how to do math for educators

[wheat tinsel]

Given a finite simple continued fraction, how do you compute its value?

I mean, suppose you are given [1;2,3,4,5,57,345,4]

you could "undo" the continued fraction step by step and eventually convert it into a fraction a/b with a,b integers

but I was wondering if there is a faster method

@sterile spoke idk if you were gonna answer

[indigo sage]

Do you find what the difference is

[wheat tinsel]

are you asking me?

[indigo sage]

Yes for example for this

U find what’s not included right

[wheat tinsel]

I will restate the question, because maybe it was not clear

Let $A=[a_1; a_2,a_3,\dots,a_n]$ be a finite simple continued fraction. What's the most efficient way to calculate $A$? Would it be to "undo" the continued fraction and so express $A$ as a quotient of the form $a/b$, with $a,b$ integers, and then do regular division, or is there a more clever way?

[sterile pumice]

Croqueta

[torn escarp]

I think there's a recurrence relation on the numerator and denominator you can use which might make it more convenient to write a program I suppose, idk

[sleek spire]

from wikipedia

but I'm not sure this is helpful since there's a floor in it

[wheat tinsel]

You usually use that to give the continued fraction expansion given a real number

but I want the opposite process. I guess you can do it like that too, but doesn't seem any better than just "undoing" the continued fraction

[still flare]

Look at Gaussian brackets on the wikipedia page

[wheat tinsel]

Thanks

I think I'm missing something on continued fractions anyway

I believe the main purpose is to give rational approximation to irrational numbers. But to produce a continued fraction you already need to know the irrational number you want to approximate to some degree of accuracy

well I guess the thing is giving rational approximations with denominator and numerator as small as possible

then continued fractions do make sense

[torn escarp]

I think the main reason people care about infinite continued fractions is they give you the solutions to Pell's equation, and one reason to care about those is that they are units of the real quadratic number rings

[fervent grove]

I mean continued fractions are useful for other reasons too :/

I think there's some algorithm which breaks RSA when the decryption key is relatively small which uses continued fractions as a key step

it is also of general use to be able to look at a real number approximation and be able to guess if it's a rational number

(I have used such an algorithm myself a few times on math contests which allow programming because one can often just approximate the answer and then figure out what the rational number was supposed to be)

[wanton lance]

So I have an issue, I been doing the HWs and going to lectures for my number theory class but we have an exam on thursday and looking at the previous years exams that just got pusblished, it looks stupidly hard. I find myself lost in trying to solve many of the problems and so I'm here looking for advise to study. What're some really good consice resources that you guys reccomend?

[stiff rivet]

sounds to me like you are already doing everything correctly

going through homework and previous exams

alternate ressources will always differ and might not be too helpful

you can take your favorite book on the topic and do more exercises there 🤷

[wanton lance]

I suppose so

I think I just need to grind out a bunch of problems then

[livid birch]

this question is being super vague

what could b) be referring to

[brittle root]

3 * 3 = 3^3

perfect square probably

,calc sqrt(5625)

[sterile pumice]

Result:

75

[brittle root]

yep

[livid birch]

:O

i knew that

[livid birch]

3 is the identity

[brittle root]

I mean for 1a)

you probably typoed

[livid birch]

i did

[brittle root]

I'm guessing for b) they want you to state that

5625 is a perfect square

because all the exponents are even

[livid birch]

yeah that was probably it lol

i just forgor

[brittle root]

yeah

maybe u lack sleep

[livid birch]

what makes you think that

you're right but like

[brittle root]

you forgot something basic

like that ain't it

get yourself some sleep

,ti sebbb

[sterile pumice]

The current time for stμ₂dying is 10:00 PM (EST) on Wed, 08/02/2023.

[brittle root]

okay you better be offline in 1h

sleeping

or I'll put out a hit on you

[livid birch]

look at my previous ,ti's

[lean oasis]

Hi

How do I solve $4^a+4^b=p(p+1)$ for $a, b, p$ nonnegative integers ?

[sterile pumice]

Eduardo291299

[torn escarp]

is p a prime number?

I suppose if not, without loss of generality you can make a>=b and then factor out 4^b

$4^b(4^{a-b}+1)=p(p+1)$ looks like we have solutions when $b=a-b$

[sterile pumice]

Merosity

[torn escarp]

might be some more edge cases to think about, good luck, goodnight

[urban kiln]

Why is 3×4 = 6×2

[lean oasis]

I need to understand this part of the proof

[sacred junco]

@urban kiln 3x4=12 and 12=6x2. Or if a=b and b=c then a=c. So 3x4=6x2. 🙂

[urban kiln]

I was referring to how difference between 6-2 is more than 4-3

so graph of equal product isn't straight line and is a hyperbola

xy=c

Is it possible to make it straight line? By changing axis scale

to something similar to x^2

@sacred junco

[sterile pumice]

stéphane

[urban kiln]

Yes

12 was just a example

[sacred junco]

you can write this in the form $\frac{x^2}{a^2}-\frac{y^2}{b^2}=1$ if you want.

[sterile pumice]

stéphane

[urban kiln]

Why isn't slope constant

[sacred junco]

it is the form in a basis with a=(1,1) as a vector of the basis

[urban kiln]

Ok

[sterile pumice]

stéphane

[urban kiln]

I don't really understand what that is

[sacred junco]

Do you want me to explain to you what it is ? 🙂

[urban kiln]

Yes that would be nice

[sterile pumice]

stéphane

[urban kiln]

R is real number?

[sterile pumice]

stéphane

[urban kiln]

Oh so R^3 would be be 1,8,27...

On graph

[sterile pumice]

stéphane

[urban kiln]

3D graph?

[sterile pumice]

stéphane

stéphane

[urban kiln]

What is this stuff called?

I am in 12th grade now

[sterile pumice]

stéphane

[torn escarp]

yeah you can change to X=log x and Y=log y and you get X+Y=log c which is a straight line of slope -1

[verbal cedar]

am i allowed to say this?

[verbal cedar]

and then by euler's theorem those reduce to just x=1 mod m and n. since this is satisfied for x=1, then x=1 mod mn is the unique solution mod mn?

not sure how to best articulate that reasoning

[torn escarp]

yup that works

[torn escarp]

it's the chinese remainder theorem

[verbal cedar]

cool ty

[eternal wraith]

if i have integers m,n and i want to show that their gcd = 1

and i know there are integers x,y such that mx+ny = 1

does this in any way imply that the gcd of m and n is 1?

[west glade]

yes

mx+ny = d is solvable iff gcd(m, n) divides d

[eternal wraith]

ohh awesome thank you so much

and at the same time that implies that (x,y) = 1 right?

[west glade]

yes

if you switch the roles of m,n and x,y

[eternal wraith]

woah thats cool

[ashen oriole]

I'm trying to prove the following:

If x satisfies $x^n + a_{n - 1}x^{n - 1} + \cdots + a0 = 0$ for some integers $a{n_1}, \ldots , a_0$, then x is irrational unless x is an integer.

However, if we consider $9x + 3 = 0$, then $x = -1/3$, which is neither an integer or irrational. Does anyone know what I am misunderstanding here about the theorem? Is it only valid for $n \geq 2$?

[sterile pumice]

TopDreg

[sacred junco]

9x + 3 isn't of the form x^n + a_{n-1}x^{n-1} + ... + a_0

the leading coefficient isn't 1, and, even if you divide out by 9 to get a monic polynomial, you won't have integer coefficients

[ashen oriole]

oh gotcha, thank you!

[torn escarp]

tricky rational root theorem

[ashen oriole]

[sacred junco]

so this is where mero hangs out...

[torn escarp]

shi... 👀

I keep all but 9 channels muted to prevent myself from procrastinating too much

this is a relatively dead channel so I hide out here

[verbal cedar]

does 9604=4(7^4) not have a preimage under the totient function?
since 9605 is not prime, that won't work, and 7 can't be a prime divisor of the preimage n because 7-1 does not divide 9604. i checked the other primes of the form 2^k1*7^k2+1 and none of them worked either, since you're always still left with a 7. it seems impossible, but I'm not 100% sure on my reasoning.

[loud maple]

If the goal is simply to determine whether 9604 has a preimage or not, then one could use the fact that ϕ(n)≥2×(n/6)^(2/3)

To obtain an upper bound on possible preimages. And then run a program to find if n exists such that phi(n)=9604

And we also have n-√n ≥ phi(n), giving us a lower bound on n

Although I don't know of any 'good' method that is neither computationally intensive nor program-assisted

[leaden stratus]

If I have a number N and I need to see if I can find K distinct odd numbers that can sum to up N. Is there a property I can use to see if that's possible?

If N is odd, but K is even I know that won't be possible. If N is even and K is odd I know that won't be possible as well

[still flare]

Hint: there is a lower bound for the sum of k distinct odd numbers, if you mean for them to be non-negative.

[leaden stratus]

i'm working on these programming problems that require mathematical observation and i'm so lost 😦

yes non-negative

oh

i was thinking of an upper bound (? idk if this is correct term). like if K is too big then it won't work

[still flare]

I think you should look at the hint's suggestion first

[leaden stratus]

the lower bound would be the sum of the first K distinct odd numbers?

so 1 + 3 + 5 + 7 + ...

okay i got it. the lower bound is K^2

which is what the summation of the first K odd numbers is

OMG. it worked!

how.....

how can you prove that if you have a number where N and K are the same parity. and N > K^2, you can always form N with K distinct odd positive integers

what in the world

[wooden glen]

Well, you've just seen how to make K² -- then you can make any larger number simply by increasing the last term appropriately.

[leaden stratus]

OHHHH. I see it

16 -> 1, 3, 5, 7
18 -> 1, 3, 5, 9

man i need a mastery of numbers

this is pretty cool stuff

[rocky crane]

Design a function f(x,y) that takes in two numbers x and y and calculates the number of odd numbers between them whose last digit is not 5. Given that x<y & x and y are both natural numbers.

[torn escarp]

Make a function g(x) that counts the numbers less than x, and use inclusion-exclusion with multiples of 2 and 5, then make f from this

[sudden narwhal]

If m is odd then m is 1 mod 2, and if m's last digit is not 5 then m is not 5 mod 10. In other words, m mod 10 is either 1, 3, 7, or 9. So to compute f(x,y), find which remainder x and y fall on mod 10 and count how many appearances of 1, 3, 7, or 9 appear between them

[sudden narwhal]

Something like 4 * (floor(y/10) - ceil(x/10)) + (error term), where the error term is contrained to [0,8] depending on x mod 10 and y mod 10

[stoic lantern]

Are there any recommended texts for elementary number theory? I’m taking a course but my professor is not a very good lecturer, and the recommended textbook does not seem very good

[torn escarp]

what book are they recommending

[stoic lantern]

Let me find it, one sec

Number Theory by George Andrews

It’s not bad but I’m wondering if there are better books

Honestly I’m not so sure the book is bad, I think my professor just sucks at creating a course around it lol

[torn escarp]

I'm unfamiliar with the book, so idk

[stoic lantern]

Unfortunate

[verbal cedar]

wait am i insane or is b not true for p=2

1^2 isnt 0 mod 2

[wooden glen]

Characteristic 2 claims another victim.

You're right.

[verbal cedar]

thank you! I'll let the rest of the class know lmao

[shy heron]

are there any websites that can generate random question on rational numbers?

[sleek spire]

wolframalpha problem generator maybe?

[wooden glen]

Is there a smallest rational number x with the property that x^m >= (n/m)^n whenever n/m (with n,m > 0) is the area of a polygon with rational corner coordinates that fits within the unit circle?
That looks pretty random, doesn't it?

[pulsar cloud]

I was told that its the number of integers between 1 and n inclusive not 1 and n-1

[wooden glen]

The two definitions make phi(1) be either 0 or 1.

And phi(1) needs to be 1; otherwise phi(n)·phi(m) would not equal phi(nm) whenever n and m are coprime.

[pulsar cloud]

that is true

[wooden glen]

phi(1)=1 is also what we get from "number of units in the ring Z/nZ", since 0=1 is a unit in the zero ring.

[pulsar cloud]

Z/Z is the zero ring ?

I guess it makes sense since Z/2Z is just 0 and 1

but I thought a ring with unity cant have 0=1

[sleek spire]

a field can't have 0 = 1

a ring can

[sleek spire]

yeah

[pulsar cloud]

I see

[wooden glen]

We need to let the zero ring be a ring, because otherwise quotients by arbitrary ideals wouldn't exist. There's no useful concept of quotients of fields, though, so in that case other reasons not to want 0=1 weigh heavier.

(And we need to let the whole ring be an ideal, because otherwise sums of arbitrary ideals wouldn't exist).

[still flare]

Are you doing algebra for grad school? If so, yeah

If not, no not at all

[livid birch]

what am i doing wrong here

[torn escarp]

maybe break it down mod 2 and mod 5 instead, work them out separately, then combine with the CRT

you're skipping one special case

[livid birch]

i guess a better question is why mod 10 isn't enough

[torn escarp]

what can n mod 5 be

[torn escarp]

it is enough, you're just wrong by overlooking one of them

[livid birch]

7 mod 5 = 2

[torn escarp]

one of them is not like the others

[livid birch]

https://tenor.com/view/bigbird-one-of-these-things-is-not-like-the-others-gif-11251276

[torn escarp]

mod 5 might be more clear to see

once you see it there, you'll be able to easily go back to mod 10 and see your mistake

so list out, what are the possibilities for n mod 5

[livid birch]

ohhh wait

is this something about being mod pq

the choices are 0,1,2,3,4

[torn escarp]

ok cool and what's fermat's little theorem say? (not that we really need to use this, just convenience at this step)

what are those raised to the 4th power

[livid birch]

i know FLT but i wanna do it without it

the question appears in my book before it's introduced

[torn escarp]

sure, do however you like, it's not too seriouss

[livid birch]

im not sure what im missing tho

[torn escarp]

don't think

you're thinking too hard, this isn't an intellectual thing

[livid birch]

[torn escarp]

square everything in the list

then square them again

just a fast way of getting the 4th power, that's nothing special

just do it already

show me what you get

[livid birch]

yeah you get the actual answer which is 0,1,5,6

[torn escarp]

0^4, 1^4, 2^4, 3^4, 4^4

mod 5

[livid birch]

but why is that right but mod 10 isn't

[torn escarp]

this is wrong idk what this is

[torn escarp]

just write out what all these are mod 5

just do that

we can think later, it'll be obvious later

[livid birch]

0, 1, 1, 1, 1

[torn escarp]

yesssss

so that means it's 0 mod 5 or 1 mod 5

[livid birch]

[torn escarp]

if you forget that one exception, you'd think they were all 1 mod 5

so 1 mod 2 and 1 mod 5 makes 1 mod 10

that was what you said

but you forgot when it's divisible by 5

1 mod 2 and 0 mod 5 is 5 mod 10

example: 5*5 = 25

5^4 = 5 mod 10

[livid birch]

ah so this is why it's incomplete

[torn escarp]

yeah, you were skipping over 5^4 thinking it was 1 mod 10

[livid birch]

so in other words mod 10 isn't enough because there are two cases where n is equiv 5 mod 10

also - should it have occurred to me to take mod 5?

like i saw last digit and i thought mod 10

[torn escarp]

it is enough

you just skipped 5 or computed it wrong

[livid birch]

i mean 5^4 mod 10 is 5

[torn escarp]

yeah

do you still feel like it's not enough for some reason or you see now

if it helps, in general if gcd(a,b)=1 then stuff you reason out mod ab is exactly the same information as the stuff you reason out mod a and mod b separately, but considered together

[livid birch]

somewhat feels like it's not enough

but im still probably thinking too hard

maybe going from proving the ham sandwich thm this morning for hw to this is giving me whiplash

i guess on a dif note

any hints for a

[leaden swan]

Have you tried taking mod y!

That reduces your equation to $x! = 0 \mod y!$

[sterile pumice]

Drake

[livid birch]

ohhhh because z! must have y in it

[leaden swan]

Yea

[livid birch]

i saw the hint obv but hadnt connected those dots

[leaden swan]

After that it's pretty straightforward

Well you need one more inequality

[torn escarp]

well you could look at 1^4, 3^4, 5^4, 7^4, 9^4 as:

mod 10 they are 1, 1, 5, 1, 1
or
mod 2 they're all 1 and mod 5 they're 1, 1, 0, 1, 1

There's only one number from {0,1,2...,9} mod 10 that's 1 mod 2 and 1 mod 5, that's 1. There's also only one number that's 1 mod 2 and 0 mod 5, that's 5.

hopefully that demonstrates the difference - although maybe you have to believe me that this number is actually unique.

in general if you have gcd(a,b)=1 with x mod a and y mod b, then there is a unique number z mod ab such that z=x mod a and z=y mod b.

[analog raptor]

I have a question: Solve in Z the equation: x1^6 +...+x6^6 = 6x1...x6+1.

Z = the set of whole numbers

[west glade]

consider mod 7

[wooden glen]

Hmm, all that seems to give us is that exactly one of the unknowns is coprime to 7.

No, not even that, since (1,1,1,1,1,2) is also a solution mod 7.

[analog raptor]

that's the first thing I did (motivated by Fermat's little theorem) but I don't think it's very useful

The LHS can be whatever mod 7

And the RHS is tricky to control mod 7 (maybe only if one of the numbers is divisible by 7)

[west glade]

oh yeah I made a mistake in my head

[analog raptor]

yeah all good

I tried also mod 5 but doesnt seem to do anything either

Mod 6 seemed okay aswell, but n^6 gives 0, 1, 3, 4 (mod 6) and again not that useful

[west glade]

but well about that, I think it can only be 1 or 6. if it is not 6, then at least one of the numbers is divisible by 7 and therefore RHS is 1, so LHS is also 1

or am I making a mistake again?

[analog raptor]

oh i think you are right

lemme think

[west glade]

so either one of them is coprime to 7 or all of them are

that second case is annoying but the first one might at least be doable

[analog raptor]

yeah i'll try that

btw what I also found interesting

is that the A-G inequality i "almost" what the problem is

so going by that intuition all of the number must be "somewhat close" to one another

since the equality is only true when they are all equal

but again I dont think that does anything

[analog raptor]

honestly I couldn't figure out either case, I don't think this finishes the problem

[west glade]

yeah I don't see anything currently either. interesting problem

maybe some application of symmetric polynomials? but I don't really know anything about using them

[analog raptor]

my teacher gave us this problem in the category of number theory so i believe it's something with modulos or something like that

I doubt it's sth else but could be

tell me if you find something interesting 😄

[wooden glen]

Mod 2 and mod 3 give us some information: An odd number of the unknowns are even. Either 2 or 5 of the unknowns are divisible by 3.

We cannot hope for a "there are no solutions" resolution, because at least (±1,0,0,0,0,0) and its permutations works in Z.

[livid birch]

how might i approach 24

for starters im not even sure which part it’s asking to solve - im assuming x right?

[fervent crest]

Yes

[loud maple]

x²-a² ≡ 0 mod p

and p is prime

[analog raptor]

Not sure if that helps a whole bunch

[livid birch]

so do we use that x^2 \cong 1 mod p?

[loud maple]

1? How?

[livid birch]

i forgot to finish that statement lmao

but that that is only true for +,-1

[loud maple]

factorise the expression, and use the fact that p is prime to come to a conclusion

(b) follows easily from (a)

[wooden glen]

Agreed. It would feel more promising to attempt adapt the proof of the AM-GM inequality to show a lower bound for the difference, but I keep getting lost in the calculations.

[verbal cedar]

is this like... a joke? i don't see how calculating 1001! would be any less computationally intensive than just checking divisors

[analog raptor]

It's weird, really. Tell me if you get anywhere with the AM-GM, but I tried and couldn't.

[wooden glen]

It's more of a conceptual argument that it is possible to know for sure that such-and-such number is composite, without knowing any factor of it.

I would expect what you quoted is part of a lead-up to something like the Miller-Rabin primality test, which can get concrete proof that such-and-such is not prime faster than trial division in practice.

[verbal cedar]

i suppose so. are there some clever techniques that make factorial computing... efficient i guess? such that this would be useful. maybe taking the remainder mod p after each multiple might work, and stopping if you get 0

[livid birch]

so it should just be plus or minus a

didnt mean to ping my b

[loud maple]

Yes

[livid birch]

[wooden glen]

Not to my knowledge. If I remember correctly, the fast primality tests tend to be based on Fermat's little threorem rather than Wilson's theorem, but the toy example here has the didactic benefit of being determinstic, so one can come to terms with "a proof of compositeness doesn't necessarily tell us what the factors are" before having to wrap one's head around techniques for finding such proofs of a more realistic length than the Wilson-based computation.

[verbal cedar]

aha i see. that is quite interesting, thank you 🙂

[torn escarp]

for what it's worth, a sorta standard trick for checking divisibilty by 11 is to do an alternating sum of the digits and see if it's divisible by 11, 1-0+0-1=0

[sacred junco]

[livid birch]

can someone double check the second part pls

[livid birch]

mero

[torn escarp]

how do you know if a and b are between 1 and (p-1)/2 (inclusive) that their squares are distinct?

also I think your first line should be p distinct equivalence classes or somethin 😛

[livid birch]

oh that should follow from the first claim

but i should probably state that right

[torn escarp]

I don't know if it does, the proofs I have in mind require more work

[livid birch]

non zero

though you're right that i should specify that

[torn escarp]

I think the second sentence also caught me a bit off guard by how it's worded, I didn't understand why you were saying 0=p mod p and stopped a sec, but when I kept reading I sorta saw what you were getting at, but still a little vague

idk just trying to help a bit

[livid birch]

yeah i was hesitant about saying that

but it also felt weird to just say -k equiv p-k

that feels more random to me at least

[torn escarp]

I think you can omit it entirely since you're saying this from the start now

[torn escarp]

to try to clarify what I mean, the first part tells you that the elements of {1,...,(p-1)/2} has the same squares as the elements of {(p+1)/2,...,p-1} but that doesn't necessarily mean the squares of {1,...,(p-1)/2} will be distinct, that requires more

[livid birch]

i see

[torn escarp]

maybe it also helps to see an example where this happens too when the modulus isn't prime, mod 8 you still have k^2=(8-k)^2 but k=1 and k=3 both pair up with 7 and 5 respectively, with all 4 satisfying 1^2=3^2=5^2=7^2 mod 8

[livid birch]

i mean i wanna use that this is a field

but this isnt an algebra class

[torn escarp]

in some ways that's good and some ways that's bad yeah

the good news is they really haven't given you too many things to use, so that cuts down on the space of stuff to look at, what theorems have they taught you so far?

[livid birch]

we're following a book by kraft and washington

never seen it before this class

ive been meaning to make a big list of theorems and tricks but ive yet to do so

we just covered CRT and then FLT, but this was after the scope of this hw

FLT, not CRT

[torn escarp]

yeah, I'm trying to remember the trick for this myself, since I don't think it's obvious

[livid birch]

you do a lot of NT?

[torn escarp]

if you pick a,b from the set {0,...,(p-1)/2} then a^2-b^2=0 mod p factors as (a+b)(a-b)=0 but since a and b are smaller than or equal to (p-1)/2 each then a+b <= p-1

so a+b can't be divisible by p

but obviously a-b isn't divisible by p either if they're distinct from that set too

I just was thinking there's an easier way but maybe I'm misremembering cause I was thinking of appealing to something like fermat's little theorem or polynomials having unique factorization mod p, but that requires more proving too lol

[torn escarp]

yeah, I guess so

[livid birch]

tangential but do you buy any chance have a list of lil tricks and thms? or is it all mental

[torn escarp]

I don't have a physical list or something typed up, I don't know if I could really write anything much out either tbh

[livid birch]

all good yeah i figured, im just making one to help study for the inevitable midtemrm

[torn escarp]

the main book I suggest for this sorta stuff is Silverman's Friendly Introduction to Number Theory

I think most NT is like, trivia and probably not really worth memorizing either haha

[livid birch]

that's what it feels like

which is weird to be doing alongside my alg. topology class lol

[torn escarp]

yeah, I don't know much about algebraic topology, there are pretty pictures in hatchers book but I never really could get myself motivated to do it

what sorta stuff interests you in that class?

[livid birch]

yeah i just mean it feels like very different flavors of math

[livid birch]

im still just trying to expose myself to as much math as i can before applying for grad school

||coming at the cost of some grades but alas||

[torn escarp]

cool, good plan

[livid birch]

last one mero, and ideas

trying to use hint obv

i accidentally showed that are 100 squarefree integers lol

[loud maple]

How did you prove this?

[wooden glen]

The hint implicitly uses the CRT.

[torn escarp]

I feel like I'm reading the question wrong, did they mean show that every sequence of 100 consecutive integers can't all be square free?

every sequence of 4 integers has some non square free number in it, maybe it's past my bed time

[wooden glen]

I read it as wanting a proof that there is some n such that each of n, n+1, n+2, ..., n+99 is divisible by some nontrivial square.

[torn escarp]

oh, ok I can see that, I was thinking 1,2,3,...,100 was all you had to do since they're not all square free 🤪

[livid birch]

is it just obvious from CRT?

wait

[wooden glen]

Once the hint clicks, fairly obvious yes.

[livid birch]

take all those n,n+1, ... mod some x^2, by CRT a solution exists?

[wooden glen]

Yeah, as long as you pick different (mutually coprime) x for each.

[livid birch]

that's where the 100 primes come in right

[wooden glen]

Yes.

[livid birch]

and that x that solves the system, is the first of the 100 non square free integers right?

[wooden glen]

You mean the n that solves the system. But then yes, if you've set it up right.

[silver burrow]

what do yall do when a proof just sounds so obvious

[fervent crest]

I thank the author for giving me an easy statement to understand and continue with my day

[silver burrow]

but its on an assignment

like i have to write the proof

like the thing sounds trivial

[west glade]

Well then just write it down

[silver burrow]

no but like

how

like it just seems true like i cant say why

it just is

[wheat tinsel]

If you cannot write a proof, then you can't say its obvious

[brittle root]

post the question if you want help

[verbal cedar]

could someone help get me started on these? i'm not sure how i could use the division alg for this.
i have other ideas for how to do them, but i'm not sure how the div alg factors into them.
a) if p+2 is prime and p>3, then p=5 mod 6 (bc p=6n+-1 for p>3), so 3 divides (p+1) so 9 divides (p+1)^2 so p^2+2p=-1 mod 9
b) we need to show that 2^n=-1 mod 7 does not have a solution for n. the order of 2 is 3 in mod 7, so we could just brute force show that n=0,1,2 mod 3 are not solutions, but that's not very satisfying imo.

[verbal cedar]

anyone?

[torn escarp]

idk, seems like what you did was good, i don't know what they're looking for

[dense stag]

Hi, I want to try out number theory during my break between semesters (between first and second semester).
I got recommended some german book (Alexander Schmidt Einführung in die algebraische Zahlentheorie), the first chapter is about divisibility and the first exercise of the sub-chapter is:
"show that (2,3,7) is the only triple of natural numbers >=2 such that the product of two + 1 is divisible by the third"

2x3+1=7 and 7 divides 7 and so on.

So I have 2<=a,b,c , also I think the numbers have to be coprime and I know that e.g. c divides ab+1
I tried writing down the definitions, but Im missing a key idea to rule be able to rule out every other triple.
This leads me to a few questions:
Does anyone have a slight hint for the exercise?
Im very much not familiar with number theory. Are there like general tips on how to approach these elementary number theory problems?
Would you consider this exercise as easy? Im asking this because if its a somewhat tricky exercise maybe I should find some easier ones first. If its as easy as it gets, I will just continue with these then and try to get used to it.

[leaden swan]

Are the triples all supposed to be prime

This holds for all triplets of the form (p,q,2) where p and q are odd primes if that's supposed to be your constraint

@dense stag

[dense stag]

Any natural number bigger or equal to 2
c divides ab+1
b divides ac+1
a divides bc+1

These are the contraints.
Maybe it wasnt clear the way I translated it.

[leaden swan]

This is definitely not easy

[violet fox]

not sure if this is the correct channel, forgive me if it isn't but can someone explain why these are equal

just picked ln arbitrarily

[sleek spire]

a^b = exp(bln(a))

[leaden swan]

These are like more standard intro nt questions

[sleek spire]

how do you do 25 without algebra

[leaden swan]

Just like p * q^-1?

[sleek spire]

wdym?

[leaden swan]

I guess reduce to lowest common form and deduce an representation

Well also show that it didn't really matter that we reduced it to lowest common form, because the factors cancel anyway

[sleek spire]

I have no idea what you're talking about

[dense stag]

What book is this from?

[leaden swan]

suppose x>0 x=p/q for gcd(p,q)=1 for p,q>0. Write down the prime factorization of p and q. Now p and q^-1 will have no common prime factors since gcd(p,q)=1

[sleek spire]

what does this have to do with 25

[leaden swan]

A Computational Introduction to Number Theory
and Algebra - Victor Shroup

[leaden swan]

How does that not give you a factorization for x

I don't think it's that much more effort to show said factorization is unique

[sleek spire]

ah I see

[leaden swan]

ngl this feels like an Olympiad problem

[dense stag]

As per his wikipedia he went to IMO in his youth, so maybe they are.
Either way as of yet theyre too hard for me.

[leaden swan]

I think you need some kind of weird trick to solve this

[dense stag]

Can you recommend the book you posted the exercises from? I would use that then to do some exercises

[leaden swan]

Well I started using it today

Can't say anything. So far looks good

Although it's targetted at people who want to get into cryptography

This might be helpful for general NT
#book-recommendations message

[dense stag]

Thanks

[gilded breach]

How to express 11 as the sum of distinct odd primes?

[torn escarp]

does the sum need more than one number in it

since odd+odd=even you know you'll need at least three numbers

what's the smallest sum of 3 distinct primes?

[gilded breach]

12

Distinct odd primes

No, it's 15 I guess

[torn escarp]

yeah

the only direction you can go is up from here

[torn escarp]

so it's not possible unless you consider a single number as a sum of 1 number like I said here

[gilded breach]

But in the text it says it was proven that any integer n>9 can be written as a sum of distinct primes

Maybe it's a single number sum

[torn escarp]

yeah, in that case every prime is just a sum of itself haha, kind of silly but

[gilded breach]

Fits the theorem

[torn escarp]

distinct odd primes?

[gilded breach]

Yes, that's what it's written

[torn escarp]

ok cool

[gilded breach]

Thanks for responding

And for help

[torn escarp]

yup you're welcome 👍

[unkempt void]

Now prove that every integer > 9 can be written as the sum of two primes

[torn escarp]

check out chen's theorem if you've never heard of it before

[leaden stirrup]

pathagoraean theorym is the best theory

[sleek spire]

?

[unkempt void]

So true

[lean sandal]

hey, can anyone help me see where i went wrong in my solution (trying to lift, using hensel's lemma) https://cdn.discordapp.com/attachments/1077102592770973777/1077104802766532618/image.png

[torn escarp]

everything looks good up til the line where you write a_2, I don't know what you're doing to get that

are you using $a_{n+1}=a_n-\frac{f(a_n)}{f'(a_n)}$?

[sterile pumice]

Merosity

[lean sandal]

isn't it $a_2 = a_1 - f(a_1)*f'(a_1)$?

[sterile pumice]

nomnom

[torn escarp]

nope

it's the exact same formula as newton's method

a good thing is you've already checked f'(2) != 0 mod 7 so you know it's invertible which in some sense is where it comes from

[lean sandal]

i see, 1 sec lemme check my prof's notes real quick

maybe he made a mistake

is what he is doing wrong here? (removed image cuz idk if prof allows to post his notes)

[torn escarp]

bar must mean inverse to him

[lean sandal]

ohh

[torn escarp]

no idea what that notation means, never seen that before

[lean sandal]

wait yeah

im dumb

thanks

[torn escarp]

but it'd fit haha

yeah you're welcome

[white lion]

hey can anyone point me to a resource where I can find a more clearer proof of this therorem

I don't get it from if 1=<m<=n then... m=qp^k onwards

firstly, if m is less than or equal to n then how does that assumption bring about m=qp^k

because qp^k is just the largest multiple of p^k not exceeding n

and m is just a generic number that's less than n, it could be 2p^k,3p^k,4p^k for all we know.

for reference || denotes exactly divides and [a] would be the greatest integer not exceeding a (The Greatest Integer Function)

[torn escarp]

weird, idk where a clearer proof is, but I agree this seems pretty bad

[white lion]

Ok phew I’m not the only one😅😅

[white lion]

any proof other than this will work tbh

[torn escarp]

well to me it seems almost self evident, so tell me if this is enough of a proof for you:

n! is the product of all numbers from 1 to n, and multiples of p come every [n/p], similarly for p^2 coming every [n/p^2], etc

idk what else they're saying there that isn't just a more verbose way of saying this

but maybe what I've said is too terse lol

[sleek spire]

does 2x + 7y = 70 have any solution where x is not 0?

[torn escarp]

x=35

[white lion]

Thanks

[torn escarp]

you're welcome

[white lion]

You’re active on this channel you specialize in number theory? @torn escarp

[torn escarp]

seriously though, this is covered by Bezout's lemma, you can find all solutions to 2x+7y=gcd(2,7) and then multiply through by 70

[torn escarp]

I don't know if I'd describe it as specializing, I enjoy thinking about nt and end up here more often than I probably should... lol

[white lion]

oh ok lol

what are your thoughts on probabilistic nt it seems interesting too me any recommendations?

[torn escarp]

not something I know much about, any result in particular you saw that makes you ask?

[white lion]

Nothing special, just already proven theorems proved using tools from probability

[torn escarp]

like the probability two numbers are relatively prime is 1/zeta(2) = 6/pi^2 (as long as we think of probability as being the one from thinking of the natural density)

I imagine analytic number theory is probably useful

[white lion]

Probably lol, probablility theory is measure theory

In a way…

[torn escarp]

maybe ask in one of the probability theory channels

[white lion]

Will do thanks

[torn escarp]

or advanced number theory channel potentially

good luck

[white lion]

Thanks 🙏

[torn escarp]

hint: what is x divisible by?

[verbal cedar]

...can i just say that a^6=1 mod 7 by Fermat, so (3^n)^6-(2^n)^6=1-1=0 mod 7 so it's divisible by 7 and therefore not prime?

it also looks like 5 divides it but i can't see a proof for why. i can reduce it down to 3^2n-2^2n by fermat again but idk what i can do afterwards
if n is even then a^(2n)-b^(2n)=0 mod 5 by fermat
if n is odd then i think we can also do something with fermat

[leaden swan]

a-b divides a^n - b^n

@verbal cedar

[stiff rivet]

your argument also works

you can see divisibility by 5 also by reducing to 9^n - 4^n = 0 mod 5

(you have to ensure that the number is never 5 or 7 with those arguments though)

[verbal cedar]

i thought about that first but assumed "there's no way we can just do that right? otherwise this is just trivial" lol. but we can just do that and it works?

[verbal cedar]

i see. 9=4=-1 mod 5 so it zeros out pretty clearly

[verbal cedar]

could you explain what you mean by this? which number do you mean

[stiff rivet]

3^(6n) - 2^(6n)

because of course 7 = 0 (mod 7), but 7 is prime

[verbal cedar]

ahah i see that makes sense. being divisible by a prime doesn't mean it isn't prime (if it is the prime itself). thank you for your help 🙂

[livid birch]

how does this problem work

that's scratch work from prof there but i dont see how to approach this

(also dont get what the work is, not very clear)

CRT?

[west glade]

I guess your prof is just writing down some examples for which at least one of the properties holds. Maybe they want you to spot a pattern

Think about the prime factorization of perfect powers

And yes I think CRT at some point

[ancient heath]

Let $m=4^n-1$ be a positive integer. If $4^n\equiv 2 \mod{2n}$ then show that $2^{m-1}\equiv 1\mod{m}$.

[sterile pumice]

Goosebumps

[ancient heath]

anyone knows how to start the proof? i don't think the prof allows proof by induction in this context

[torn escarp]

maybe it's clearer to see if you substitute n $n=2^a3^b5^c$ and then plug it into each and solve the congruences on the exponents, for instance $a+1=0 \mod 2$, $a=0 \mod 3$, $a=0 \mod 5$. So here you can use the CRT (or sorta just guess) to get $a=15$. Then repeat for $b$ and $c$.

[sterile pumice]

Merosity

[loud maple]

Substitute m=4^n -1 in the last expression, the answer follows almost immediately

[ancient heath]

i got $m\equiv 1 \mod{2n}$ how do i continue from this?

[sterile pumice]

Goosebumps

[ancient heath]

i was wondering if i should use fermat's little theorem to prove the last expression or is it unnecessary?

[livid birch]

any chance you can rephrase this

why's that work

[west glade]

n will have a prime factorization. n=2^a 3^b 5^c * (maybe other primes) where a,b,c are integers (might be 0)

if k is a square, then all the exponents in the prime factorization need to be even

if k is a cube they all need to be multiples of 3

with this you can work out what a,b,c need to be mod 2,3,5

[livid birch]

how do we know that those other primes need to be there from the start?

or do we just start with a factorization into 2x3x5 hoping for the best

[torn escarp]

cause the exponents themselves are 1 and need to be fixed up to be a multiple of 2,3, and 5

other primes are excluded cause p^0 already has 0 divisible by 30

[livid birch]

can we walk thru it super quick

we start by letting n = product of powers of 2,3,5 right

[torn escarp]

yup

[west glade]

we aren't saying that 2,3,5 have to be included (yet). for all we know yet, a,b,c could be 0

if you want you can also write the other primes down

you will just see that they dont end up mattering

[livid birch]

so how do we get the "2n is a square" into it

[livid birch]

this should have been b = 0 mod 3 right

[torn escarp]

noooo

we have the same 3 congruences for a,b, and c separately

9 congruences in all

[livid birch]

oh

[torn escarp]

maybe an important thing to clarify is, N is a perfect k-power iff the exponent on each prime p is a multiple of k

so I'm considering each prime power individually

[livid birch]

hrm

[torn escarp]

for instance, p^3 * q^6 is a perfect cube because it's (pq^2)^3 we just needed to look at p^3 and q^6 individually to see that

no integer power of 5 is going to change the power of 2 for instance

in n = 2^a 3^b 5^c

[torn escarp]

show me where you get stuck when you substitute in, what do you get after you plug it in?

maybe it helps to write it this way and plug that choice of n in to these: 2n=x^2, 3n=y^3 and 5n=z^5

[dapper void]

does anyone need help

[grave bough]

I always do, but wtv

[gaunt sedge]

I’m struggling to understand why we need to find the inverse of 8 mod 3^2

When we are working in mod 3^4

[west glade]

what? context?

you should still work mod 3^4

who says you need to work mod 3^2

[gaunt sedge]

What I wrote was misleading, I think I am supposed to find it mod 3^4 but in this case it’s enough to find the inverse mod 3^2

[west glade]

Not really. The inverse mod 3^4 is different

Or well I suppose you can lift it or something but that seems overcomplicated

[wooden glen]

Well, inverting 8 modulo 9 is particularly easy.

And since we're going to multiply the result by 9 anyway, the upper two base-3 digits of 8^-1 mod 81 are going to disappear anyway.

So we get 72 for 9·8^-1 mod 81 immediately.

Inverting 8 modulo 81 is not that bad either, though -- we immediately notice that 10·8 == -1 (mod 81), so 8^-1 modulo 81 must be -10.

Multiplying that by 9 gives -90 == -9 == 72 again.

[torn escarp]

another trick that can work mod $p^n$ for arbitrarily large n is to use a geometric series, $$\frac{-1}{8} = \frac{1}{1-9} = 1+9+9^2+\cdots \mod 3^n$$

[sterile pumice]

Merosity

[old oyster]

i mean if it was 2 or 0 mod 4 then it would be even

and the only even prime is 2?

so it has to be 1 or 3 mod 4 no?

[old oyster]

idk then

[gaunt sedge]

I found it pretty cool that when u halve numbers 0 or 2 mod 4, u get even or odd numbers respectively

[inland nexus]

how do you tell gross income?

and net income?

,help

[sterile pumice]

A brief description and guide on how to use me was sent to your DMs!
Please use ,list to see a list of all my commands, and ,help cmd to get detailed help on a command!

[inland nexus]

,list

[sterile pumice]

My commands!

Use ,ls to obtain a briefer listing, and use ,help <cmd>to view detailed help for a particular command, or ,help to view general help.

If you still have questions, talk to our friendly support team here.

Meta

View or set meta-information about me.
​ ​ ​ ​ ping: Check heartbeat and API latency.
​ ​ ​ ​ help: Bot and command usage information.
​ ​ ​ ​ list: Lists all my commands!
​ ​ ​ about: Shard status and bot statistics.
​ ​ invite: Sends the bot's invite link
​ ​ donate: Donate to help keep the bot running
​ ​ prefix: View bot prefixes and set a personal prefix.
​ support: Sends the link to the bot guild
feedback: Send feedback to my creators

Page 4/4