elementary-number-theory

[torn escarp]

you can put a nice lower bound on it by splitting it up into two equations d=k + (d-k) for k odd, since we know individually we now have the same problem but for k and d-k variables has p^{k-1} and p^{d-k-1} solutions and together every combination will be p^{k-1}*p^{d-k-1} = p^{d-2}.

[haughty lichen]

if we show that infimum of (a+1)*sqrt(2)-(a+1)>0 then we know there exists a b that fulfils the inequality

[fervent grove]

d=2 says that this bound is in fact best possible without actually using information about the prime p. so I guess I'm also asking how information about p would even appear in the proof.
(For d=2, this is somewhat apparent, but less so d=20.)

[torn escarp]

I suppose depending on if p=1 or 3 mod 4

it would change things, cause you have sqrt -1

[fervent grove]

yeah, that's how it gets in for d=2. I don't have data for what d>2 does, but I am not totally convinced that (mod 4) information is sufficient

[torn escarp]

the answer is kind of complicated if I remember, I derived it a few months ago in more generality after watching the second lecture of the 'Quadratic forms and the local global-principle' here: https://www.math.arizona.edu/~swc/

it splits up into 4 cases

I'm about to head off to sleep but I'll look at it tomorrow and see if I can explain it in a less complicated way

[warped halo]

thank you so much!

[cosmic flame]

Hello everyone! Random question, not school related (been out of school for years, I was an accounting major). Was referred here to ask this question. Is there a name for the function that returns the sum of the prime products for n? IE, for n=6, f(n)=5 because the prime factors are 2 and 3 which sum to 5. I would be curious to read about this function.

[haughty lichen]

Either “sum of prime factors” or “sopfr(n)” refers to that function

[cosmic flame]

Thank you!

[torn escarp]

https://www.mathpages.com/home/kmath006/kmath006.htm

[cosmic flame]

Thank you!

[deft verge]

a ^ (1/n) and b ^ (1/n)
are both rational

because x is rational, and because they're relatively prime (so their factors will not interact with each other)

now only way each of those could be rational is if all of their prime factors' exponents are some k*n, for k, natural number

because the exponents must still be natural numbers after being divided by n

[lyric geyser]

would it be possible to use a lemma that the if k'th root of a natural number is a rational number, then the k'th root is natural?

[deft verge]

oh mb I read that wrong

let me read carefully lol

maybe I read it correctly

Yes I think so @lyric geyser

[lyric geyser]

my only concern here is that a/b and x aren't natural numbers, so i am not sure how to use that lemma

[deft verge]

a, b are both natural

x is rational, thus there exists some p, q, such that x = p / q

p, q both being natural bc integers and > 0

[lyric geyser]

yeah then we would have something like $\frac{p^n}{q^n} = \frac{a}{b}$

[sterile pumice]

add

[deft verge]

ye, then remember
a, b are relatively prime
and
p, q are relatively prime

so you get
p^n = a
and
q^n = b

[lyric geyser]

how would i verify that a is only an n'th power of p and nothing else?

like proof by contradiction

[deft verge]

suppose
a = p^n * h
then

$\frac{p^n}{q^n} = \frac{h*p^n}{b}$

[sterile pumice]

bruncho chraa

[deft verge]

thus
$q^n = \frac{b}{h}$

[sterile pumice]

bruncho chraa

[deft verge]

b, h are relatively prime

because h was a part of a which was relatively prime to b

so

h is either 1, or q^n is not a natural number

(q and n both given as natural, this cannot be)

[deft verge]

Okay I also got it without contradiction

(different variables)

for relatively prime (a, b) and relatively prime (x, y), $\frac{a}{b} = \frac{x}{y} \iff y = \frac{xb}{a} \implies a = x$

[sterile pumice]

bruncho chraa

[devout furnace]

this was from a contest which ended 2 days ago

#9 isn’t that bad

but #10 though

how do you even do it in less than 9 minutes

(a^3 + 4b)^3 = 256(a + b)

very cool

now what

a^3 + 4b has to be of the form 8k

a + b is then 2k^3

[devout furnace]

from here we know a and b are both even

so we can let a=2m, b = 2n where |m|, |n| <= 1010 and get:
512(m^3 + n)^3 = 512(m + n)
so
(m^3 + n)^3 = m + n

[devout furnace]

m^3 + n = cbrt(m + n) <= cbrt(2020) \approx 12.5
so |m| <= 10

now casework

now note that if (m, n) is a solution then so is (-m, -n)

[devout furnace]

here are the trivial solutions:
(0, 0)
(0, 1)
(0, -1)
(1, 0)
(-1, 0)
(1, -1)
(-1, 1)
(1, -2)
(-1, 2)

now aside from some of those ^^^ note that m and n can’t be the same sign

so assume m > 0 and n < 0

[devout furnace]

wait wtf
(m, -m^3 - m) is a solution to this

so for each |m| >= 2 there’s at least one solution there

but I think those are the only solutions because the answer is indeed 9 + 2(9) = 27

dang so basically you need to prove (m, -m^3 - m) is the only solution for |m| >= 2

and then you’re done

[devout furnace]

also I don’t see how you just observe this; I only figured it out after guessing and checking the first couple solutions

anyways it took me an hour and that was supposed to be a 9 minute question during the actual contest lol

[warped helm]

Hey! So I've been really stuck on this one topic and I think I've been missing something. It would be really helpful if someone could explain/ outline the steps on how to do something like this:

$x^2= -1 mod 65$

[sterile pumice]

pineapplewhale31

[warped helm]

I know how to do this specific example, but when I try to apply it to other examples, I can't seem to be able to do it at all (pls ping)

[deft verge]

x = i mod 65

Ok
that one should be easy because we know

$-1 \equiv 64 mod 65$

[sterile pumice]

bruncho chraa

[deft verge]

and ofc we know 64 is 8^2

this is more difficult for something like

$x^2 \equiv -1 (mod 73)$

[sterile pumice]

bruncho chraa

[deft verge]

you'll find that

$x \equiv 27 (mod 73)$
and
$x \equiv -27 \equiv 46 (mod 73)$

[sterile pumice]

bruncho chraa

[deft verge]

And it was at this point I believe we were told to just "keep trying numbers" until it worked out

I think the relatively effective way to do it was to go through multiples of 73, like 73, 146, 228, etc.

subtract one (this will now be congruent to -1 mod 73)

and then take the square root

for example

73 * 10 = 730

730 - 1 = 729

729^0.5 = 27

@warped helm

[warped helm]

thank you @deft verge i just had my final in it, but I actually managed to figure it out just before the exam XD if you are interested, you don't have to trial and error it, you can split it into simultaneous congruences of the factors of 65 which makes things a lot easier to deal with

[deft verge]

Can you show me that?

[wanton torrent]

Is this ok, so far?

[torn escarp]

this isn't the approach I'd take since you have that 9 which you can't make out of multiples of 5

I'd think in terms of the euclidean algorithm

in particular I'd concentrate on solving 1=3a+5b, 0=3a+5b, and 8=3a+5b (the last two equations should be obvious to solve, the first you can solve with the euclidean algorithm or just guess by inspection)

then build up all integers >= 8 from these

[wanton torrent]

I still don't know about that

the euclidean algorithm

[torn escarp]

now's probably a good time to learn then

[wanton torrent]

Well ok ty

[sleek cove]

even if you wanted to do it your way, case 1 is done without any work

[deft verge]

to solve for x, you need to divide by 63
which you can do my multiplying by the inverse of 63
the inverse of 63 is a number that when multiplied by 63 will be congruent to 1 (mod 143)

this also happens to be x

You can use the Extended Euclidean algorithm to find this, if you talked about it in class

[fervent grove]

Is there a definition of "primitive" (with respect to polynomials) that doesn't actually require looking at the coefficients of the polynomial?
I kind of get the feeling that primitive doesn't "really" care about the exact coefficients but only the behavior of the polynomial because, say, f(x) is primitive if and only if f(x-a) is primitive for some shift a. However, I don't know how to codify this intuition.

[torn escarp]

I guess one thing to focus on is that both define the same extension field

[prime sparrow]

No zero degree divisors other than 1? I don’t know if that is what you mean when you want a definition without coefficients.

[fervent grove]

oh hmm that makes sense

[urban peak]

im trying to find which odd numbers can appear in primitive pythagorean triples

just by looking at a list of ppts i believe that all odds are able appear but i have no idea how to prove it

[shadow eagle]

Is it possible to prove infinitude of primes using just the process of Sieve of Eratosthenes? I found one paper from Romeo Mestrovic from 2018 titled "Euclid's theorem on the infinitude of primes: a historical survey of its proofs (300 B.C.–2017)" which references to one online forum posting (page 10), that B. Joyal had proven IOP that way. Unfortunately the forum post can't be found anymore. (edit: wrong paper)

[shadow eagle]

Pythagorean triplets cant have all odd numbers or one odd and two even. Is this what you are asking?

[paper lion]

https://math.stackexchange.com/a/1153069/694763

Might be what you're looking for.

[shadow eagle]

Thanks @paper lion, I did find that also. The given answer uses the properties of density of periodic sets, and you don't need SoE at all. I was hoping the B. Joyal proof would indicate the infinitude arises from steps in Sieve, and not division properties of natural number, and thus extendable by modifying the Sieve beyond the divisibility rules.

[paper lion]

I'm not very well-versed with the technical details here, but would look up for something in the morning. Let me know if you stumble across something!

[shadow eagle]

Yes I did contact the author of the paper, if for some reason he has more information on the proof. Did not receive response yet, but I'll let you know if I find something.

[paper lion]

Thankyou!

[shadow eagle]

@urban peak oh you asked if all odd numbers can appear? As PT are form a = m^2 - n^2, b = 2mn, c = m^2 + n^2, where n,m are natural numbers, then setting n = m-1 => m^2 - (m-1)^2 = m^2 - m^2 + 2m*1 - 1^2 = 2m - 1, so all odd numbers do indeed appear

[lyric geyser]

for $m, n$ relatively prime and $p, q$ relatively prime, and $m, n > 1$ and $p, q$ > 0 would it suffice to say that $m^q = n^p$ cannot occur because the prime factorization of $m$ and $n$ are different, so even after raising them to those powers they cannot be equal?

[sterile pumice]

add

[torn escarp]

yeah

[lyric geyser]

does that sound too handwavy? i feel like i could word it better

i am trying to prove that ln(m) /ln(n) is irrational with a contradiction

[fervent grove]

You can show this claim from contraposition: if m^q = n^p, then m and n should share a prime divisor after dissolving everything into prime factors

[mystic herald]

help

[leaden swan]

Sir, That's physics

[vital mist]

Let N= 115737. Show using the Sieve of Eratosthenes how to find all prime numbers between 10N and 10N+100.

[sleek cove]

apply bezout's identity @mystic herald

[echo zephyr]

Im try to show that the gcd(f_n,f_n+1) of fibonnaci sequence is always equal to 1

specifically, im trying to do so by induction

but, Im getting stuck on the induction step

and maybe im doing something wrong but it goes something like this: (sorry my work is messy)

[winter bear]

can you show how you are getting stuck?

[echo zephyr]

This is my work so far

Im basically using the notion that if m and n are coprime then af + bn = 1 for some a and b

or trying to, atleast

[winter bear]

bezouts? i mean you would have to modify it a bit along those lines ig

you are probably better of using like, euclidean algo

like gcd(a,b) = gcd(a-b,b)

[echo zephyr]

The thing is im not too comfortable with that yet

but i will

also, doesnt my reasoning lead to the opposite conclision?

1 + af_k can only = 1 if af_k = 0

[winter bear]

well you need some a,b doesnt need to be the same for the two pairs

so like af_

af_k +b f_(k-1)= 1 implies a' f_(k+1) + b'f_k = 1

and u dont need a= a' or b=b'

my hint along this line would be to just combine the f_

f_k terms on ur inductive step

so you are asking wether there is a (a,b) such that a f_(k+1) +b f_k = 1? thats the same as asking wether af_{k-1}+ (a+b)f_{k} = 1 for some a,b

[echo zephyr]

The reason i combined the terms like that is because we do know by the induction hypothesis that af_{k-1} + bf_k = 1 for some specific a and b

So i get that the a and b could be different when you increment, but if you take an a and b for a known case of a and b, specifically the a and b for k and k-1, then a brick wall seems to be hit

[winter bear]

alright let me help you along

lets say $af_{k-1} +b f_k =1$ for some a,b. Now $a' f_{k+1} +b' f_k = 1\implies a' f_{k-1} +(a'+b')f_k =1$

[sterile pumice]

JohnDS

[winter bear]

so can you find a' and b' that works here

[echo zephyr]

Oh oh oh

i see

i seeeeee

sorry you had to kinda spell it out for me xD

[warped halo]

hi

can someone help me find how this is can be proved to be an ideal of R

like i got the addition part of it

im just confused about the second multiplication part i have to prove to show that its an ideal

[abstract flax]

Well, how is multiplication defined for your ring?

[winter bear]

im geussing the product is just component wise multiplication

[abstract flax]

geussing

[winter bear]

in which case what did you try @warped halo

yes geussing

[sleek cove]

goosing

[shadow eagle]

I'm gaussing most of the time

[warped halo]

um to show that its an ideal of R i have to show that for some a,b belongs to R a-b belongs to I and that for some r belongs to R and a belongs to I, ra belongs to I

how do i prove the ra part

[stiff rivet]

you take an arbitrary element of R and an arbitrary elements of I and multiply them

[torn escarp]

no because it is talking about the congruence relation

mod is really not uniquely defined

there's an entire equivalence class of possible values, for instance what would you say 1/2 mod 5 is? @sacred junco

1/2 is one possible answer, but there's an entire equivalence class of possibilities like 3 = 1/2 mod 5

3=8 mod 5 too

3=-2 mod 5 as well

they're completely indistinguishable when you start talking about modding out, for instance

2 * 1/2 = 2 * 3 mod 5

have you learned of fermat's little theorem maybe?

you can think of 2^(5-1) = 1 mod 5 but you can look at it for one integer power less as 2^(5-2)=2^-1 mod 5 if that helps

as long as the denominator of the fraction doesn't divide n, you can do it

which is what they mean by b and n being coprime

yeah you're welcome

[torn escarp]

if m is prime, then you need a to not have m as a factor, otherwise it's 0 mod m and has no inverse at all

there are two directions to go here, euler's theorem that if a and m are coprime then a^phi(m)=1 mod m and this works for any m, not just prime

but the other direction is if you're wanting to compute inverses, you can compute them with euclid's algorithm

[sharp stream]

Guys, just to clerify general notation [x] is whole part of x? In example [3.2]=3?

[torn escarp]

yeah, it's called the integer part or greatest integer function

[sharp stream]

Thanks :3

[torn escarp]

you're welcome

[sleek cove]

:3 hehe

[deft verge]

how does it work with signs

[-5.9] -> 5?

[torn escarp]

it rounds towards 0, [-5.9] = -5 @deft verge

[deft verge]

o yeah I missed the sign
still glad to hear it's not -6

[torn escarp]

yeah, it's distinct from the floor or ceiling functions which round towards -infinity and +infinity respectively

[fervent grove]

wait I've definitely seen older texts use [.] to mean floor because of typing

might be something to watch out for, or maybe I'm crazy

[torn escarp]

well they're the same as long as you're looking at positive numbers so it's not really that big of a deal

[green ivy]

no, greatest integer function of [-5.9] will round up to -6

as it is greatest integer less than the number inside [ ]

[green ivy]

It should be -6

[torn escarp]

I'm going by this here: https://oeis.org/wiki/Integer_part

[green ivy]

You can check this out as well

https://cnx.org/contents/ysm8oGY0@64.8:p28zIztF@9/Greatest-and-least-integer-functions

Also, the greatest integer function is also known as Step Function, because it's graph is like this

[sleek cove]

i prefer the greatest decimal part

[steady nest]

what are the squares mod 7?

i know it's 1,2,4 but i don't understand how it's the answer

1 is always a square

2^2 = 4 mod 7 so i guess that's a square?

3^2= 9 mod 7 = 2 mod 7? Apparently this is also a square?

but then why wouldnt 4^2 = 16 mod 7 = 2 mod 7 be a square then?

[torn escarp]

it is

it's already in your set, you just said 2 was a square

3^2=4^2 mod 7

once you get up to halfway, you can write 4 = 7-3 = -3 mod 7

so it's more obvious to see it as saying 3^2=(-3)^2 mod 7

[steady nest]

hmm

but why is 2 a square though?

[torn escarp]

you just explained it

3^2 = 9 = 2 mod 7

[steady nest]

ah i see

[torn escarp]

all we care about in modular arithmetic is effectively the numbers 0, 1, 2, 3, 4, 5, 6 since they are representative of all other integers up to adding a multiple of 7

[steady nest]

i know that by some thm that i can't think of, the size of multiplicative (z/pz)^x is 6. so there must be 3 squares and 3 nonsquares

3,5,6 are nonsquare because none of the elements in {1,2,3,4,5,6} return 3 mod 7, 5 mod 7, or 6 mod 7 when squared (respectively)? EDIT : 0 shouldn't be there since it's multiplicative

[torn escarp]

yeah, for a prime Z/pZ forms a field and so the only element that's not invertible is 0

the fact that they split half and half is a separate thing to prove depending on how you want to look at it

one way is to think that since (Z/pZ)^x is a cyclic group it has a generator so call it g and then every element is g, g^2, g^3, g^4, g^5, g^6 and that's everything

and so the even powers are squares, everything else isn't, so that's half and half

[torn escarp]

yeah that's true

0 is a square but it's not a square in (Z/7Z)^x since 0 is not in the group because it has no multiplicative inverse

[steady nest]

Ah ok I understand now! thanks for the help!

[torn escarp]

cool you're welcome

[wispy creek]

how did they get that ?

[wispy creek]

hello ?

no ? ok

[sacred junco]

If n is odd, then the answer is 4 times the number of distinct factors of n. Else if, n =m2^k where 2 doesn't divide m, then the answer should be k-1 times the number of distinct factors of m.

[wispy creek]

thats not answering how

[sacred junco]

honestly no idea

n=5 does not even hold

Just read the other response

I think it's just wrong

take any odd prime number

[wispy creek]

oh yeah thats true

for n = 5 it seems there's 4 solutions

but they say it should be 8

https://math.stackexchange.com/questions/1063627/diophantine-equation-x2-y2-n/1063656

[wispy creek]

the other response just says how to get the solutions

not how many there are

😔

[fervent grove]

Once you know how to get the solutions, you should be able to count them

For example, with n=5 (or odd in general), the point is that we are essentially counting the number of distinct divisors of n

n with powers of 2 requires a bit more work

[wispy creek]

shouldnt we be counting divisors between sqrt(n) and n

[fervent grove]

I'm not sure what you mean

[wispy creek]

factorize $n$ as $n = pq$ where $1 \leq q \leq p \leq n$. The solutions to equation are $(x, y) = \br{\frac{p + q}{2}, \frac{p - q}{2}} = \br{\frac{p + \frac{n}{p}}{2}, \frac{p - \frac{n}{p}}{2}}$. The number of possible $p$'s will determine the number of solutions. Now, $p \mid n \implies p \leq n$. Also $p \geq q = \frac{n}{p} \implies p \geq \sqrt{n}$. As there are a finite number of $p$'s that satisfy $\sqrt{n} \leq p \leq n$, the number of solutions is also finite.

[sterile pumice]

soαρ

[fervent grove]

I think we can set x-y equal to any divisor

[wispy creek]

i was working on the previous prob

[fervent grove]

Are you restricting x and y to be positive?

[wispy creek]

yes actually

[fervent grove]

Yes, then that will change things

Actually let me think a second

Techincally we can let x and y vary over all integers and then divide by 4 at the end, right?

or am I silly :/

(unless n is a perfect square, in which case the y=0 only has 2 solutions)

[wispy creek]

vary over all integers ?

wouldnt that yield n^2 / 4 number of solutions

[fervent grove]

Like, even if you're only interested in counting positive integer solutions to x^2 - y^2 = n, you can still forget about the positivity to solve first, and then divide your number of solutions by 4

[fervent grove]

Well, not all x and y will work

[wispy creek]

oh ic what u mean

yeah i misinterpreted what u meant

[fervent grove]

There is some technicality to deal with when n is a perfect square or a negative of a perfect square, but you get th eidea

[wispy creek]

yeah makes sense

but i dont know how to work it out without the restriction of positivity tho

[fervent grove]

I mean, this is described in the first response, right?

[wispy creek]

like u said, "the point is that we are essentially counting the number of distinct divisors of n"

i dont get that exactly

[wispy creek]

yeah

[fervent grove]

How many distinct divisors of n are there? Set x-y to one such positive divisor, and then x+y is theother

When n is odd, these are the same parity for free

(namely, they are both odd)

[wispy creek]

oh

are we sure that we're not gonna run into double counting of sorts ?

[fervent grove]

Distinct solutions (x,y) will yield distinct [divisor pairs] (x-y, x+y) and vice versa

You can prove this if it worries you

[wispy creek]

hmm that does make sense

i thought about for a while and it makes a lot of sense now. thnx for the help @fervent grove

[fervent grove]

no problem

[sleek cove]

yw

[leaden swan]

Let x^6-12=k^2
Then (x^3-k)(x^3+k)=12

Just take cases

And show no such k is possible

[sacred junco]

(x^3-k)(x^3+k)=12 is ez enough

or no?

and vice versa

but probably same thing since x^3

[worn pine]

hi! can i ask for help for this problem? :))

i think that the order of n is 2k and i was able to get n^(2k) = n^(2^(s+1)) = 1 (mod p) from the given but i don't know how this proves that the order is indeed 2k

[prime sparrow]

This will prove the order divides 2k, hence is some power of 2. Can you see what to do now?

[worn pine]

yup, i got it now, thank you so much!!

[steady nest]

Hi, could someone explain this?

I just don't understand the "multiplication by the inverse" and how that results in 1 mod p

[prime sparrow]

Fermat’s little theorem says: a^p=a mod p. So multiplying by a^-1 we get a^(p-1)=1 mod p

[steady nest]

oh, that was surprisingly simple.

Thanks!

[prime sparrow]

Np

[proven rune]

How's Niven's textbook for number theory? I'm taking a class that uses this textbook and am wondering if I need any other reference book besides it.

[sacred junco]

if the course uses it then I don't think you will need any other one lol??

and we dont know anything bout the class or what you already know sooo

[lime pier]

posted this in abstract algebra channel bc i'm working on it for an algebra problem but realizing this is actually a num theory thing whoops

I'm trying to find the integral solutions to the equation $4x^3-27=y^2$ but I'm having a hard time getting much further than showing that $y$ must be odd. I don't have too much experience with Diophantine equations so any help would be appreciated!

[sterile pumice]

panoramatopia

[fervent grove]

This is an elliptic curve, more specifically an instance of Mordell's equation (a solution to your equation induces y^2 = x^3 - 432). I don't have a full solution written down, but I'll say (1) there are similar examples here https://kconrad.math.uconn.edu/blurbs/gradnumthy/mordelleqn1.pdf, and (2) you might get a better response in #advanced-number-theory

It's also possible there is an elementary solution I've missed

[lime pier]

oh yeah my professor did mention that that specific elliptic curve tied into this problem

i'll look more into the mordells paper thank you

[fervent grove]

I'll also say that (if I had to guess), this equation's classification of integer solutions is going to be most like Theorem 3.4, but I'm having trouble working out the details

[stoic inlet]

Hey, i have a advanced question about modular calulations, can someone get me started on how i calculate:

$$ x \equiv x^{25} \mod 65$$

[sterile pumice]

Luka835

[stoic inlet]

I was thinking about writing it like x^25 - x = 0 mod 65, and then splitsing it up into mod 13 and mod 5

[sleek cove]

okay

[stoic inlet]

Can’t someone help me with this?

[fervent grove]

What exactly is the question? Are you trying to find the x for which x = x^25 (mod 65)?

Or are you trying to do something else?

[stoic inlet]

Yeah: solve for x 🙂

[sleek cove]

x=0, next question please

[stoic inlet]

What? No, thats an incomplete answer

Why are u so mean?

[raven moon]

some ppl here are funny

[sleek cove]

what have u done after subtracting x

[fervent grove]

what did you try after splitting this up?

[sleek cove]

stop copying me :(

[dawn zodiac]

x=1 also xd

and x=64

[lucid yarrow]

after splitting this as mod 5 and mod 13, we have $x^25=x mod 5$, $x^25=x mod 13$.

phi(5)=4, phi(13)=12. note that any x works. since if x is co prime then x^4=1 mod 5 => x^24=1 mod 5 => x^25=x mod 5.
similarly, x^12=1 mod 13 => x^24=1 mod 5 => x^25=x mod 5.

if x is not co prime we easily see it is 0 mod prime. hence x^25=x=0 follows

[dawn zodiac]

xd

x=1,0,64

;0

[lucid yarrow]

any x works right?

[dawn zodiac]

2 also works

i think

[lucid yarrow]

yes! every x works

x=1,2,3,4...

[dawn zodiac]

oh

good question

x=0,1,2,...

[stoic inlet]

Thanks a lot! 🙂

[atomic gale]

Hey so I'm a bit confused here. I got part a down just fine. But in part b, where they say the "Using part (a)" how do they know that?

Like how do they know that because part a was proven correct, that 2x6x10x14x...x(4n-2) >= 2^n(n!)?

[fervent grove]

They're asserting that 2^n > (2n)! / (n! n!) [this is wrong]

can you see why this is true and/or why it's what we want?

[atomic gale]

Not really. Honestly this whole "induction" thing is still super confusing to me.

[fervent grove]

This step is not using any induction

[atomic gale]

Oh.

[fervent grove]

The product $2\cdot6\cdot\ldots\cdot(4n-2)=\frac{(2n)!}{n!}$ from (a), right?

[atomic gale]

Oh wait.

[sterile pumice]

dfoiler

[fervent grove]

sorry continue

[atomic gale]

Oh so since it equals that we want to prove that it is greater than 2^n(n!)

[fervent grove]

Yes!

[atomic gale]

Ooooooh okay. I thought they just somehow automatically knew it was.

I was confused by the wording.

[fervent grove]

ah no problem

[atomic gale]

But I did wanna ask about induction.

[fervent grove]

wait I think I'm wrong

[atomic gale]

Oh.

[fervent grove]

but ok

wait gimme a sec

[atomic gale]

Okay.

[fervent grove]

ok no I'm not wrong, I'm just silly

the "Using part (a)" is asserting something we want to prove, not something that we know to be true

anyways

[atomic gale]

Okay I think I got that.

So the whole general idea of induction.

So we start off with a general case of f(n=1).

And if that holds to be true we can move onto step 2, which is f(n=k).

Which we are temporarily assuming to be true.

So if we take this thing, f(n=k), that we are temporarily assuming to be true, and it also holds for f(n=k+1), then that means that our original assumption of f(n=k) is true which also means that the basic f(n) is true.

Is that the right idea?

[fervent grove]

I think your logic at the end is a little frazzled

[atomic gale]

Okay.

[fervent grove]

The idea is that we show "statement holds for n=1" and we show "if statement holds for n=k, then statement holds for n=k+1" [put quotes around statements]

This much you have correct

It is a bit difficult to intuit why this tells us statement holds for all positive integers n, but we can kind of see this like a process

[atomic gale]

Wait

[fervent grove]

waiting

[atomic gale]

I thought it was the other way around.

Or wait

Never mind.

I misread again.

[dusty dragon]

You can imagine the process as proving to someone you can climb a ladder

In order to climb a ladder, you need to show that you can climb the first step (this is the base case)

Then, imagine that at some point you’ve climbed k steps. Well to show that you can climb the ladder, you’ll need to show that you can climb the next step

If you can show this, then by virtue, you’ve shown it to be true for 1, 2, 3, …, n steps (assuming your base case begins at 1)

[atomic gale]

Okay I think I get it logic wise.

Thanks!

[lucid yarrow]

It is also like a car race. 1.) u need some initial velocity. 2.) and some acceleration to always keep pushing.

[sleek cove]

what

[finite hatch]

What

[sweet mist]

what

[sleek cove]

nyani

[lucid yarrow]

f(1) true initial velocity. f(n) true implies f(n+1) true implies f(1)-> f(2)-> f(3) true.. - acceleration.

[sleek cove]

but cars stop

[outer brook]

Curious about a problem that I thought about, is there idea behind finding the last n digits of a number (say a^m) ?

Like is there a nice closed form way of getting those last digits of an exponentiated number?

[sage fern]

just memorise the cycles ig

only the last digit of a will ever matter

[fervent grove]

This can be computed in log(m) time using exponentiation by repeated squarings. As alluded to above, if you only keep track of the digits you care about (if you only want the last 10 digits, you only ever have to store the lsat 10 digits), then this can be done in constant memory as well.

I doubt there is a "closed-form" way of doing this

[lofty pasture]

Hopefully this isn't too basic but is there any function that given a natural number n, calculates the exact distance to either the next prime number (the first prime > n) or the previous prime number (first prime < n)? EG some function where I can input say "31398" and I will get a response of "71" for the next prime distance, or "1" for the previous prime distance?

I have been digging around for a few months now and it seems the status quo is to use a sieve function, and generally iterate from n up or down until you can factor out a prime. I haven't come across anything that can just take a number and then calculate the distance to the next or previous prime.

[leaden swan]

No

Brute force is the only way

[lofty pasture]

Thanks I figured as much, but I wasn't sure.

[leaden swan]

We can't even find a prime p given the right number n such that p>n

If you want to implement some sort of code,a hash table is probably your best friend

[lofty pasture]

Putting aside computational complexity for a minute - if there were a brute-force function that could say "hey, the next prime is x many digits thataway" (even if it computationally takes longer to figure out than just factoring out each number along the way) - are there any known algorithms? Like an algorithm that can look at the number 7, and without factoring out 8, 9 and 10, instead work out the next prime is +3 digits away? Or would that be fairly novel?

[leaden swan]

Definitely is novel

[lofty pasture]

Put another way if there was a function "getDistanceToNextPrime(n)" and "getDistanceToPreviousPrime(n)" that could figure out the distance from the properties of n alone, would that exist currently in any form, regardless of computational expense?

[leaden swan]

If that's the case just iterate till you get a prime?

It's horrible but it works

Primes are not very well behaved

[lofty pasture]

true

[leaden swan]

What are you trying to do?

[lofty pasture]

Nothing in particular, I'm just interested in prime numbers. But I work from home and as a hobby so I don't have any faculty or anyone to talk to, so it's good to bounce ideas off people online.

I've written a function that can take n, and give me the nearest prime > n or < n

without stepping through one at a time and factoring out each candidate

but... I don't know if I've just found another way to do something mundane that everyone in maths knows about

[inner anchor]

Can you explain what your function does more concretely

If it does what you say it does then its quite novel i think

[lofty pasture]

I'll set up a github, give me a little while, and I am now just quadruple checking my logic now that you say that, because "novel" in this context is scary. I'm kinda hoping this is just something mundane taken out of context.

[wooden crater]

why do you hope its mundane?

[gilded jacinth]

Probably afraid of getting shut down or rejected or something. Which is kinda depressing because new novel things can come from anywhere

And if it isn’t new or novel then who cares, the heart of it is just someone that likes this stuff trying to contribute and explore on their own

[lofty pasture]

sorry I wasn't planning to show code today, bear with me just doing some formatting

Sorry I couldn't get away from javascript and had to use a custom mod function* as js doesn't do modular arithmetic properly: https://github.com/AlexanderParker/nextprime.js/blob/main/nextprime.js

To summarise if you "Find all modulo of "-n" for factors 2..n and return the lowest missing mod value + original input - this is our next prime number"

Or to go backwards (find p < n) - Find all modulo of "n" for factors 2..n/2 and return the lowest missing mod value + original input - this is our previous prime number

but basically all I keep seeing are people saying there's no way to figure out how to get from n to the next prime or n to the previous prime, but (even if it's computationally onerous) here is a way to look at all of the factors of n, and figure out the distance to the nearest prime in either direction

which is why I hope this is in fact mundane, so I can learn something

If this is just eratosthenes sieve in another form again I swear... 😛

[spring thicket]

I don't think this number is necessarily prime.

[lofty pasture]

Ok

[spring thicket]

Wait...

Ok I'm not exactly sure how this works but

[lofty pasture]

just a sec

[spring thicket]

How does the notation of mod even work?

If you do modx(n) then you're not necessarily finding the distance between x and n

I may have misunderstood

[lofty pasture]

this is just a screenshot of numbers 0 is in the middle horizontally, 0..infinity to the right, 0 to negative inf to the left

rows contain mods of 1..n etc

anyway look inside some of the highlighted boxes, negative or positive

[spring thicket]

So it would be like 0 0 0...
0 1 0..
0 1 2..

[lofty pasture]

on the negative side, missing mods are the distance to the next prime

[spring thicket]

Highlighted boxes are the distance to the next prime?

Wait that wouldn't work

[lofty pasture]

no sorry my bad for being unclear

[raven stag]

hello!

[lofty pasture]

green cells are factors - where n mod f === 0

the bordered areas are some prime numbers and their factor mod remainders

[raven stag]

how do I prove every irreducible element in a bezout domain is a prime element ?

[lofty pasture]

the missing remainders are the distance to the next factor

[spring thicket]

Understood

[spring thicket]

The remainders that aren't green?

They're all distances to the next factor if you count 0 as a distance

[spring thicket]

I'm not sure what this means, sorry

[raven stag]

should I ask this in another channel? (sorry if I interrupted your convo)

[lofty pasture]

yeah so 0 is commonly a facto

r

[raven stag]

oh

[lofty pasture]

like, 4 mod 2 is 0

that's ok you guys carry on, maybe we should take this aside?

[spring thicket]

I don't understand them though

[spring thicket]

Maybe the question channels? but I'm not sure how fast you will get a response

I am new here

Ok so this graph looks at every factor, not just prime factors

Ohhhh

I see

[lofty pasture]

yeah I have graphs that look at prime factors

[spring thicket]

Ok I understand

Black rectangles

Lead down to rows that are prime factors

Correct?

[lofty pasture]

sorry I was trying to explain then another user wanted to use the channel which is why I got sidetracked and suggested maybe taking the discussion elsewhere. I'm new here too so I don't want to flout the conventions etc.

[spring thicket]

Oh

[lofty pasture]

But ok so across the top we have natural numbers, 0 is in the middle and negs are on the left and positives on the right

[spring thicket]

Yes

[lofty pasture]

on the vertical axis we have n mod f

actually really it's n mod n

n .. mod n

[spring thicket]

Yes

So far I understand

[lofty pasture]

ok so look in the negative mods on the left, if you look at n mod -2 for example...

actually

sorry I mean where n > 2

look at say, -15

[spring thicket]

Sorry I have to eat, I will be back

[lofty pasture]

what is the missing remainder?

ok well I'm off to bed

goodnight 🙂

(I'll give you a hint for after - 2. Which is the distance to the next prime)

anyway, enjoy your meal! Thanks for the chat.

ok I might stay up another hour, as it's nearly 6am. Why not. Why not be awake for longer! Bring it on.

[spring thicket]

It's best for you to sleep, friend me so we can speak about this later

[lofty pasture]

ok

I think it's pretty cool that there is a compass pointing from any number n to the nearest prime, even if you do have to calculate the mod of every factor of n.

https://docs.google.com/spreadsheets/d/1XWS4Ic8DL-KvVc3AqsS7T3yYMW8B2iS1LtMPZROn4os/edit?usp=sharing

[viscid wave]

Hi

I have a (trivial?) proof I need help with

The “if” direction is trivial

But idk how to prove “only if” part

Like, how do I prove “doesn’t imply” rigorously?

[sleek cove]

what do u mean by doesnt imply

are you trying to do contradiction or contrapositive

[swift shard]

Indeed there is no such thing as "doesn't imply". Instead, if:
A is "ka = kb (mod n)"
B is "a = b (mod n)"
C is "gcd(k,n) = 1"

Then the original statement is:
(A → B) ⇔ C

It sounds like you are trying to prove the only if with a contrapositive? So:
~(A → B) → ~C

We can use a logical identity to make more sense of this:
~(~A U B) → ~C
(A ∩ ~B) → ~C

So we can instead prove:
If ka = kb (mod n) and a ≠ b (mod n), then gcd(k,n) ≠ 1

@viscid wave

[viscid wave]

Wait I just realised, is providing 1 counterexample enough

Lol

Is this not the contrapositive of the “if” statement?

I wish to prove the “only if” part

…so, a counterexample should be enough right

[sleek cove]

nop

[swift shard]

nop to both. This is the "only if" and you want to show this for any a,b,k,n.
@viscid wave

[urban peak]

how can i prove that $(x+1)^p \equiv x^p+1 \pmod{p}$

[sterile pumice]

kingphilip77

[leaden swan]

Binomial theorem

[urban peak]

oh yeah thanks that is easy

how can i use that to prove $x^p \equiv x\pmod{p}$

[sterile pumice]

kingphilip77

[torn escarp]

induction

[leaden swan]

You should i^p=i mod p implies
(i+1)^p=i+1 mod p

[leaden swan]

Using this result

[torn escarp]

I think of (x+1)^p = x^p + 1 mod p as like x^p = (x-1)^p + 1 = (x-2)^p + 1+1 = ... = 1+1+...+1 = x, slowly taking out 1 from x one piece at a time

[wispy creek]

cant u just use fermats little theorem and multiply by x on both sides

[regal aspen]

Same question, but why multiply by x?

(x+1)^p mod p = x+1. x^p mod p = x. So x+1 = x+1 mod p?

Or is FLT not allowed?

[sacred junco]

mods invasion

[devout furnace]

this holds in all commutative rings of characteristic p

[plucky basalt]

Hello, are the corolaries of Wilson's theorem also biconditional?
So like (p-2)!=1 (mod p)
And
(p-3)!= (p-1)/2 (mod p)
If and only if p is prime
I think yes but I wanna be sure

Pls ping when answered

[regal aspen]

Pretty sure yes. The idea behind Wilson's theorem is that the inverses mod a number is unique. However, for composite numbers, the factors don't have an inverse.

(p-2)! = 1 mod p is just a consequence of the fact that (p-1) = -1 mod p so we get that (p-2)! * (p-1) = 1 mod p, so (p-2)! must be 1 mod p. This can also be understood via inverses mod p.

@plucky basalt

[dusky glacier]

$n^2 = 3m^4 - 4e^4$

[sterile pumice]

Yes ツ

[dusky glacier]

any integer solutions here? (m,e) = (m,4) = (m,n) = 1

i suspect not

[inner anchor]

Havent checked the deets but mod 3 + infinite descent seems good

[dusky glacier]

ok thank you!

[torn escarp]

mod 4 infinite descent also works and is a little faster interestingly

I don't have any criteria to judge which method of infinite descent should be faster beforehand, but I'll think about it, seems like it might be something possible to judge beforehand

in particular, I am just guessing that we could predict it's faster because 4=2^2 and so stepping through exponents with 2 and 4 would get you there faster than 3 which would roughly take twice as long for things to match up

[plucky basalt]

Thanks

[sterile pumice]

cannatt

[wispy creek]

is there any sort of extension/generalization of gcd(a, b)*lcm(a, b) = a *b ? like with more variables or something.

[torn escarp]

you can sort of invent one

if you look at gcd and lcm as being the min and max of the exponents in the prime factorizations of a,b respectively

then you can make one for n variables that picks the nth one when they're arranged in order

for 3, as an example:
$$\gcd(a,b,c) = \prod_p p^{\min(v_p(a), v_p(b), v_p(c))}$$
$$new(a,b,c) = \prod_p p^{mid(v_p(a), v_p(b), v_p(c))}$$
$$lcm(a,b,c) = \prod_p p^{\max(v_p(a), v_p(b), v_p(c))}$$

[sterile pumice]

Merosity

[torn escarp]

then $\gcd(a,b,c)new(a,b,c)lcm(a,b,c) = abc$

[sterile pumice]

Merosity

[torn escarp]

makes sense? @wispy creek

[wispy creek]

it does make sense but it sounds very non-useful

[torn escarp]

I agree

the only use I've been able to find in is answering your question 😌

[wispy creek]

kek

also whats up the v_p(a) stuff

[torn escarp]

I guess it also kind of redistributes the factors so that gcd(a,b,c) <= new(a,b,c) <= lcm(a,b,c) and would always work that way, if we're looking to try to cook up some use for this maybe that's a way to think about it

it's the power of p dividing a

v_2(12) = 2 and v_3(12) = 1 for instance

[wispy creek]

ic ic

[torn escarp]

it's called the p-adic valuation

[wispy creek]

ofc ur using p-adic notation

[torn escarp]

lol

[wispy creek]

aight thanks for the help. ill go read some more

[torn escarp]

yeah, I guess something else to look for now that you got me thinking is

gcd is easy to compute with the euclidean algorithm for 2 numbers so you can compute the lcm(a,b)=ab/gcd(a,b)

can we also do something similar for multiple numbers?

[wispy creek]

computing lcm in this way for multiple numbers ?

[torn escarp]

like compute gcd(a,b,c) then now we are stuck with only abc/gcd(a,b,c) = lcm(a,b,c)*new(a,b,c) so we need to do something else to split these apart

like in general what's the algorithm for getting all these functions evaluated as easily as possible when you have n variables?

[wispy creek]

yeah u can definitely do it. i did it with some code

hold up lemme find it

[torn escarp]

not just lcm but also the other functions like 'new'

[wispy creek]

[spark shuttle]

how can i start to prove $\frac{1}{k+1} \binom{n+1}{k} \binom{n}{k}$ is an integer?

[sterile pumice]

peter17

[fervent grove]

for lcm, we can write lcm(a,b,c) = lcm(lcm(a,b),c), so efficient computation is possible (say, inductively)
the approach you suggest can also get you new, but only three variables
I wouldn't be surprised if being able to do something like new is infeasible in general

[torn escarp]

I imagine it's probably always possible to write it in terms of smaller ones and write a formula for the relation

[fervent grove]

What is "it" here?

[torn escarp]

what do you mean

it's an open ended problem I suggested to soap who was asking about generalization of the gcdlcm identity

feel free to find whatever algorithms compute these functions as fast as possible

[fervent grove]

I imagine it's probably always possible to write it in terms of smaller ones and write a formula for the relation
literally what is it referring to here

are you talking about new?

[agile kraken]

1=1

1+1

[soft dust]

Find $\gcd(a^{2^m}+1,a^{2^n}+1)$. Hence, show that there are infinitely many primes.

[sterile pumice]

Five23

[soft dust]

I thought I'd find the gcd to be 1, like in the case of Fermat Numbers (a = 2) and hence could show that there are infinitely many primes like Pölya did with Fermat Numbers, but dont know how to proceed here to find the gcd

[sterile pumice]

Five23

[soft dust]

Two (in line 2)*

[prime sparrow]

Do you still want a hint?

[soft dust]

Anyone?

[inner anchor]

prove that $a^{2^m}+1$ divides $a^{2^n}-1$ for $n > m$

[sterile pumice]

Pappa

[inner anchor]

the rest is hopefully clear

[soft dust]

Yeah

Thanks

[soft dust]

I think the rest is pretty much like working with Fermat Numbers once we have proven this result

[inner anchor]

That works probably

I just thought of using euclids algo

[soft dust]

I meant that it was similar

[soft dust]

This F_n - 2 here is 2^(2^n) - 1 and is very similar to a^(2^n) - 1, and hence I thought of a similarity

[wise oyster]

So ive been thinking about trying to find all n such that the all the residues that are invertible mod n are their own inverse

n=12 is an example

but im running out of ideas on coming up with conditions on n

[inner anchor]

crt is a good place to start

[wise oyster]

should i first be solving x^2=1 (mod p) then?

cause that only has solutions for x=1, x=-1

hmmm

[inner anchor]

p^k

Prime powers

[wise oyster]

okay so i can see how that works out for my n =12 case

im having trouble arguing anything for the general case though cause idk how to simplify all the multiplicative inverse you have to calculate when applying crt

if i could then it might be easier to find a condition on when $\pm H_1N_1\pm H_2N_2\pm ...\pm H_kN_k$ is coprime to n

[sterile pumice]

Little Narwhal

[wise oyster]

where the Hs are the inverses we calculate and the Ns are the products of the intermediate modulos

(so n/q where q is one of the full prime powers)

[inner anchor]

cant you just do it like this: Note that if $x^2 = 1 \mod n$, then $x^2 = 1 \mod p^k$ for all maximal prime powers $p^k$ dividing $n$. Now simply by size considerations we must have $p^k = 2, 4, 8, 3$

[sterile pumice]

Pappa

[inner anchor]

ok that isnt very clear

but hopefully the idea is understandable

[wise oyster]

why do you say that by size considerations those are the only available prime pwoers?

that's definitely the key idea im missing

[inner anchor]

if p != 2 then just look at 2^2

[wise oyster]

i dont follow

[inner anchor]

if p != 2, then 2 is in your reduced residue system

[wise oyster]

right

[inner anchor]

now you need 2^2 = 1 mod p^k, but 2^2 = 4 and so p^k = 3

[wise oyster]

i see

lemme try and reproduce that for the other prime powers

[inner anchor]

sure

[wise oyster]

my only problem is with p^k=4?

oh no nvm

right yes i see

and so now i need to prove these are the only possible prime powers

ill give it a think

thanks tons

ah i see

if p=1 mod 4 then p^k = 1 mod 4 and since squares are =0 or 1 mod 4 there are no solutions to the required congruence. We can't have p=0 or p=2 mod 4. If p =3 mod 4 then p^k = (-1)^k mod 4. For even k we get the same as before. For odd k we need the square to be 0 mod 4 and now i need to think some more

[torn escarp]

dare I comment a bit of intuition, that if you think in terms of x^2-1=0 having roots mod p^k as k gets larger is basically putting you closer to being in the p-adic field, and a field only has at most 2 roots for a degree 2 polynomial, so it's kind of conspiring against you

[wise oyster]

i should have guessed p adics would show up when i saw you typing

[torn escarp]

lol

don't forget about hensel lifting, you can take solutions mod p^k and raise them mod p^(k+1) and it turns out that they are unique within a ball (in the p-adic topology) of radius dependent on the size of the derivative

[wise oyster]

hmm fair

[torn escarp]

for p>2 it's straight forward that the solutions x^2-1=0 mod p are uniquely determined mod p^k for all k>1 is why I say that

[wise oyster]

right so i only need to look mod p then since i can use hensel's lemma to lift to p^k?

[torn escarp]

exactly

[wise oyster]

so if i can rule out all prime bigger than 3 like that and then rule out the higher powers of 3 id be done

[torn escarp]

and since you know each step of hensel lifting uniquely determines the next digit in the base p expansion, it means you have only 2 solutions mod p become only 2 solutions mod p^k

[torn escarp]

yeah exactly

[wise oyster]

ill give it another think later honestly im not progressing mentally right now cause im just tired

but thanks for the help

[torn escarp]

yeah you're welcome

hensel's lemma and the chinese remainder theorem help simplify down a lot of modular arithmetic and make answering similar questions like you just asked more tractable, definitely worth thinking about and appreciating

[wise oyster]

yeah im aware of that i just wasnt sure how to approach this here in particular, i think im mainly just missing practice

[sacred junco]

idk look at 2^n

[torn escarp]

I'd probably focus on every divisor of N will be of the form a*b=N with a <= sqrt(N) and b>= sqrt(N),

I can't see the future, I can't tell you if it helps you or not

all I'm saying is I'd focus on it for at least as long as I'd think it seems useful, if it doesn't then I'd throw it out and try something else

[torn escarp]

I think I came up a proof using that trick

by induction suppose $\Omega(k) \le \sqrt{k}$ for all $k < N$. When $N$ is prime it is obvious that $\Omega(N)=1 \le \sqrt{N}$, so we can assume $N$ is composite. (Also notice this takes care of our base case). Now let's look at factoring $N$ into two smaller nontrivial factors, then $\Omega(N) = \Omega(ab) = \Omega(a)+\Omega(b) \le \sqrt{a}+\sqrt{b} \le \sqrt{ab} = \sqrt{N}$. To prove the inequality $\sqrt{a}+\sqrt{b} \le \sqrt{ab}$ we can without loss of generality assume $b \ge a$ and since $a$ is nontrivial $a > 1$ and we have $b \ge \frac{a}{(\sqrt{a}-1)^2}$ which we can square root to get $\sqrt{b} \ge \frac{\sqrt{a}}{\sqrt{a}-1}$ then multiply through to get $\sqrt{b}(\sqrt{a}-1) \ge \sqrt{a}$ and then we have $\sqrt{ab} \ge \sqrt{a}+\sqrt{b}$.

[sterile pumice]

Merosity

[haughty lichen]

Am I missing something? sqrt(a)+sqrt(b)<=sqrt(a*b) inequality isn’t true (for example a=3 and b=2)

Neither is b>=a/((sqrt(a)-1)^2)

[torn escarp]

haha probably not, it was just wishful thinking on my part

maybe the argument can be saved for sufficiently large values or something

[winter bear]

yeah it works for sufficiently large a,b

since this is eqv too

1 <= (sqrt(a)-1)(sqrt(b)-1)

[torn escarp]

I haven't thought it through, but I think it might be possible to rework the proof instead of with an inequality on k<N instead make each step of induction be the set of all numbers with exactly m prime divisors, with the base case of all primes like I did

ok this cleans it up to do it that way, unless I'm being too reckless with my inequalities again 😎

Suppose $\Omega(k)\le \sqrt{k}$ when $\Omega(k)\le m$. Then $\Omega(pk)=\Omega(k)+1 \le \sqrt{k}+1 \le \sqrt{pk}$. This is true when $1+\frac{1}{\sqrt{k}} \le \sqrt{p}$ so the only case this causes an issue is when $p=k=2$ but we can check manually that $\Omega(4)=\sqrt{4}$.

[sterile pumice]

Merosity

[sterile pumice]

*-*

[sleek cove]

it doesnt hold for k=3 either!!! wtf mero

[torn escarp]

[opal falcon]

p adic expansion through inverse limits

In Z_(7) how to find 7-adic expansion of 2002 through inverse limit approach?

[torn escarp]

same way you would find the base 7 representation of the number

[opal falcon]

that I know..but I want to do it without finding base 7 representation

[torn escarp]

look at it mod 7 to get one digit, then subtract it off and divide by 7 and repeat

[opal falcon]

I want to completely go through inverse limits definition

[torn escarp]

alright, what's your definition of an inverse limit

it's going to be the same thing because the reduction mod p is the homomorphism

[opal falcon]

https://ocw.mit.edu/courses/mathematics/18-785-number-theory-i-fall-2019/lecture-notes/MIT18_785F19_full_notes.pdf

example 8.15

in that they have not provided criteria to find out uniquely a_n

a_{n+1} = a_{n} mod p^n is used

now how would this help me to find a_1 and then subsequent a_{n+1} uniquely. For example 2002=(0,42,287,...)

[torn escarp]

they are unique because a_n is unique in the set {0,1,..., p^n - 1}

[opal falcon]

why 42 is coming, why not 35 or 28 etc

[torn escarp]

42 is 2002 mod 7^2

this representation is not the digits in the base p expansion, just the representative mod p^n

then the a_2 = a_1 mod p condition is seen as 42 = 0 mod 7 here

[opal falcon]

if a_1=0 then a_2=a_1 mod p, therefore a_2=0 mod p , but we also know a_2 lies in Z/49Z so we have many options that is 7,14,21,28,35,42

[torn escarp]

only one of those is 2002 mod 7^2 though

[leaden swan]

Why not just define a_n=k mod p^n in p adiac expansion of k

[torn escarp]

,calc 2002 % 7^2

[sterile pumice]

Result:

42

[torn escarp]

,calc 2002 % 7

[opal falcon]

hmm I know that is coming from the usual expansion of base p

[sterile pumice]

Result:

0

[torn escarp]

,calc 2002 % 7 ^3

[sterile pumice]

Result:

287

[opal falcon]

Thanks merosity...but from the theory given above in the notes...they are just refering to a_{n+1}=a_n mod p^n , that is why I could not think that I need to check 2002=42 mod 49

[torn escarp]

well you can compose morphisms

a_{n+2} = a_n mod p^n as well, or even higher

think of the mappings going on

I have to go sort of soon but maybe Salicina can help more if you need it, you're welcome 👍

[opal falcon]

hmm i understand that these are like successive projections...but I could not follow from notes anything more than just checking on a_2=a_1 mod 7 and then how to find that unique a_2 in Z/49Z. But since u mentioned that we also need to see that 2002=a_2 mod 49. This was new to me. Thanks for your time and help Merosity.

[torn escarp]

yeah you're welcome, is this part of a course you're taking or you're self studying?

[opal falcon]

self studying from the notes to self study automorphic forms lectures of kevin buzzard...😷

[torn escarp]

haha cool sounds fun

if you want someone to study automorphic forms with when you get to that point let me know

[opal falcon]

yeah I am at a very beggining stage..because I have never took such courses during my uni. So had to come back to basics first.

Sure..That would be very nice. I will try my best to understand the prerequisites and then reach automorphic forms stage. I am new here and I am happy to find this server.

Yes ...I have only finished first lecture yet 😅

[torn escarp]

keep asking questions and participate in stuff you should be good, lots of people to learn from here that like talking about all this sort of cool stuff

[opal falcon]

Great!...silly question...but by any chance you know how to change my nickname here?

[torn escarp]

lol I don't think you're allowed to but I don't know the rules have changed more lately

I think you can ask to have your name changed

basically to deter people from trolling I guess, not sure why they have that

I gotta go now, but seeya around hopefully

[opal falcon]

Take care Merosity. 👍

[leaden swan]

You need to have active role,I think

Send enough messages in the right channels and you will get that role

[opal falcon]

Thanks , I will wait to find relevant questions to post here and wait for the active tag

[wispy creek]

how would i deal with the case when the primes are not distinct

[torn escarp]

not sure what you're wanting to do here, like determine exactly the power of each prime dividing n!? @wispy creek

[wispy creek]

im trying to prove (m-1)! = 0 (mod m) when m is composite

and m >= 6

the proof in ss only takes care of the proof when the primes are distinct

[torn escarp]

oh I see

[wispy creek]

https://math.stackexchange.com/questions/164852/if-n-ne-4-is-composite-then-n-divides-n-1

i found this which works but i was wondering if u could expand on the proof in the ss

[torn escarp]

I guess I don't know why they did it that way

I suppose the main thing is once you know it works for distinct prime factors, then it should be easy to extend for repeated prime factors

I guess the extreme case is when m=p^a * b since (p^a * b - 1)! has to be shown to be divisible by p^a

I don't think I can say anything much better than Bill Dubuque says there tbh

[wispy creek]

also umm its hard for me to say this but...

how do i show that

[torn escarp]

looks like he explains it 2 lines down from there

[wispy creek]

wtff im blind

[torn escarp]

funny this same inequality basically came up yesterday

[torn escarp]

here

[wispy creek]

dang

must be a popular inequality

[torn escarp]

lol

no clue I haven't consciously considered it before, just a consequence of factoring to make things work because you know your numbers are of a certain size

[urban peak]

How can I use the Descent Procedure for a non-prime?

i am asked to use the procedure to write 65 as the sum of two squares starting with 14^2+57^2=53*65

i thought it only worked for primes 1 mod4 so idk what to do

[torn escarp]

well 53 = 49+4, so I'd probably divide that way

at least I assume 'descent procedure' is something like computing (14+57i)/(7+2i)=a+bi and then getting its norm

[urban peak]

how would that allow me to write 65 as the sum though? im using Fermat's Descent procedure and it will give me my chosen prime as a sum of two squares

problem is it only works for primes 1mod4

[keen furnace]

@urban peak 65 isn't the sum of two squares, so I'm not sure what you're asking?

[urban peak]

im not sure either -- my textbook asks me to darry out the argument (for Descent procedure) for 65 starting from the equation 14^2+57^2=53 *65 to express 65 as the sum of two squares

[urban peak]

a quick wolfram alpha tells me that 65 is the sum of two squares. trivial one is 8, 1

[torn escarp]

what is the descent procedure

I described what to do but I guess that wasn't clear

my bad

[keen furnace]

Oh 13 is 1 mod 4 whoops

[sleek cove]

hurb

[keen furnace]

I'm not sure what starting from that equation means. But the descent procedure works by factoring 65 = 5 * 13 and writing both of those as the sum of two squares

[urban peak]

fermats descent procedure. its a procedure that just gives us two squares that are equal to our prime 1 mod4

i will try the 65=5*13. didnt even consider it but seems like it is exactly what they want

[keen furnace]

Then using the usual identity to write their product as a sum of two squares

Yeah, I'm just not really sure what they mean by starting with that equation

[torn escarp]

if you want 65 as a sum of two squares then you should work from 53=7^2+2^2

otherwise it doesn't make sense using what they give you, if you're just going to side step it

[keen furnace]

I'm not sure how you would work backwards from the descent idea though, solving for the variables doesn't seem feasible

[torn escarp]

$14^2+57^2=(7^2+2^2)*65$ is the same as saying $N(14+57i) = N(7+2i)65$ is how I see it

[sterile pumice]

Merosity

[urban peak]

why would i start with 53 if i am trying to find two squares that sum to 65? looking at these examples i am fairly certain you start with the prime you want to find the additive factors for

[torn escarp]

I'm assuming the descent procedure is effectively equivalent to just dividing the complex numbers and looking at the norm

but you're memorizing it as a special formula called this procedure

[urban peak]

you might be right, i have no idea how the procedure is derived or what it actually means. textbook doesnt say anything

[torn escarp]

$\frac{14+57i}{7+2i} = 4+7i$

[sterile pumice]

Merosity

[torn escarp]

so 4^2+7^2 = 65 when you look at the absolute value squared

$$65 = \frac{14^2+57^2}{53} = \left|\frac{14+57i}{7+2i} \right|^2 = |4+7i|^2$$

[sterile pumice]

Merosity

[torn escarp]

maybe it helps to write it out like this

try walking through this with general numbers like x+iy and a+bi and see if the result is the same thing as the descent procedure

[cloud oracle]

For the miller-rabin test, we write a prime number as $p = {2^k}q + 1$, where q is odd. What is the proof that all prime numbers can be written in this form?

[sterile pumice]

RisenSteam

[keen furnace]

This only works for odd prime numbers. Using this, you can see that p - 1 is even, then just keep factoring out powers of 2 until you get an odd number. Alternatively, you can think about the prime factorization of p - 1. This has some power of 2, then the rest are powers of odd primes, which is odd.

@cloud oracle

[cloud oracle]

Thank you

[opal falcon]

Does any know about book or texts which give properties for generalized exponential integral of the form $$\int \dfrac{z^t}{t^y}dt$$ where $y>0$?

[sterile pumice]

Suraj Singh Khurana

[torn escarp]

I guess I'd look for things related to the gamma function since it's pretty similar to that

[opal falcon]

It is related to incomplete gamma function actually

$\frac{t^{-y} (-t \ln (z))^y \Gamma (1-y,-t \ln (z))}{\ln (z)}$

[sterile pumice]

Suraj Singh Khurana

[torn escarp]

yeah, just a few substitutions in the integral form for the incomplete gamma function to derive this

[opal falcon]

but this formula is not allowed for z=1. I wonder how to make this meaningful for z=1 and also for other values of z

[torn escarp]

well z=1 is a different integral

$\int \frac{dt}{t^y}$

[sterile pumice]

Merosity

[torn escarp]

so that's not too bad

[opal falcon]

Incomplete gamma function is defined through an integral and how do we make sense if my z is say -0.2 or something

[opal falcon]

I know that is elementary but I wish to find a formula which makes sense for z=1 and for other z as well

[torn escarp]

I suppose through thinking about the log in the complex plane

[torn escarp]

I wouldn't worry about this kind of thing if I were you, this sort of thing happens all the time

like the integral of x^n has an exception at n=-1

[opal falcon]

yeah but then the usual definition of incomplete gamma through integral works ? when z is -0.2 then the second argument becomes complex

[torn escarp]

where it doesn't follow the power rule

I don't know, I'd start looking into the incomplete gamma function to see where it's defined or if it can be analytically continued or has a pole or something

depends on why you want to do that in the first place I guess too

well, this isn't really #elementary-number-theory even though it's loosely related to analytic number theory I imagine that's how you got to it, probably better asking in #real-complex-analysis or #advanced-analysis about the incomplete gamma function

[opal falcon]

Yeah basically i will ask $\Gamma(s,x)$ for x complex is defined in what way?

[sterile pumice]

Suraj Singh Khurana

[torn escarp]

I'd say don't be too concise otherwise it will sound too technical for someone to help you with

I'm not sure but I think if the incomplete gamma function is defined for negative values then it should mean the regular gamma function is too

[opal falcon]

I understand. I think it is quite specific. Just would be lucky to find someone used to incomplete gamma function.

The regular gamma function doesnt have the second argument. The second argument represents where we cut the integral

from there we get upper incomplete gamma function and lower incomplete gamma function

[torn escarp]

like the way I'm seeing it is I know it's a simple substitution to go from your integral to an incomplete gamma function and from there it boils down to seeing where that converges which is probably the same points the regular gamma function converges

unless something weird happens in that finite interval

[tacit peak]

0 is a natural number

[urban peak]

Im trying to prove this problem for $\gcd(b,m)=1$. Suppose that $\gcd(k,\phi(m)) > 1$. Show that either $b$ has no $k^{\text{th}}$ roots modulo $m$, or else it has at least two $k^{\text{th}}$ roots modulo $m$.

[sterile pumice]

kingphilip77

[urban peak]

to be honest i have no idea how to start or an idea of what idea i could use here

[proven rune]

Can anyone give some further hints? My current reasoning is that -1 in the multiplicative group corresponds to (p-1)/2 in Z_p-1. but not sure what's next.

[winter bear]

right if -1 corrosponds to that, what would a 4th root corrospond to

[proven rune]

I'm kind of stuck on this. If 4x is congruent to (p-1)/2 (mod p-1), then 8x is congruent to (0 mod p-1) ? but then I only know there's an element of order 8, which property a lot of group has.

[winter bear]

yeah you have an element of order 8 correct

what does that tell you about p-1

[proven rune]

It's at least 8? I feel like I'm heading in the wrong direction/

😢

[winter bear]

well do you know lagranges theorem?

that the order of an element divides the order of the group

[proven rune]

oh that makes sense! I know the thm but in the the context of this problem, lagrange hasn't been introduced so far... there got to be another way?

[winter bear]

oh yeah sure

well i gave you the main idea that 8 should divide p-1

can you figure out a way to prove that

[proven rune]

if 8 doesn't divide p-1 there must be some contradictions? I guess it's closely related to Lagrange's thm. Maybe I should just refresh my memory on how it's proved.

[winter bear]

sure, but in this case its a bit easier to get that directly from the congruence

[proven rune]

thanks! I'll try to come up with a proof that doesn't use Lagrange.

[maiden token]

help

what is all the solutions in positive integers to m! + 5 = n^3

im pretty sure its only 5

but how to prove it

[torn escarp]

https://en.wikipedia.org/wiki/Brocard's_problem

[keen furnace]

I think this problem is easier than Brocard's problem. Notice that once m becomes 10 or larger, the left hand side can't be a cube since its only divisible by 5 once. You can see that the left hand side is always 5 mod 25 for m at least 10. That just reduces it down to a finite search

[atomic gale]

Hey so how did they get 9 and -2 for x and y here?

I assume they're following this rule.

[upbeat wren]

use the GCD-related ... hint ... algorithm.

oh wait what are you allowed to use?

[atomic gale]

I mean that is the answer. Like I was even told by the professor that that answer was correct and would be a correct answer using that rule.

I just need to know how they got the 9 and -2

I assume it's something to do with the 2 and 9 in front of the 2 parts of the gcd

[upbeat wren]

Yeah, you know that the coefficients must work for all choices of integer a. One way to go about it is find the coefficients for examples of different integers a until you are sure you have the right ones. This is a "cheap trick".

a = 1 --> (3, 13) ... 9(3) - 2(13) works.

Then you make sure for the general case.

The thing is what if the question is show (a^2 + a^4 + a^6, 2b^2 + b^4) = 3k? When the question is about linear components that might mean something in some cases, but I'd avoid rules like that at this level. Questions can get challenging quickly.

[atomic gale]

Once again, I have the solution to this problem but I'm confused how to get to the answer.

Namely how they figured out why to do 3a+2-3a

[sacred junco]

Well, if d is divisor of a and b then it is also a divisor of a-b

this was pretty natural in this case

[atomic gale]

I figured that. I just wasn't 100% sure since these are all I have.

[sacred junco]

g) says exactly that

[atomic gale]

But that's + though.

[sacred junco]

-1 is an integer

[atomic gale]

Ooooooooh.

Okay that makes sense.

So in my case x=-1 and y=1

[sleek cove]

shore

[atomic gale]

I get this for the most part but how did they get the 9 and -7 at the end?

[torn escarp]

oh that's the easiest part thankfully

[atomic gale]

Cool

[torn escarp]

it's solving the special case when 56x+72y=0

since solutions of this can be added to any solution without changing it

so divide out 8

7x+9y=0

then x=9, y=-7 will make this 0

[atomic gale]

How do we know to do that and not x=-9 and y=7?

[torn escarp]

doesn't matter cause it's all multiples of that

[atomic gale]

Oh so it can be either?

[torn escarp]

yeah

[atomic gale]

Okay cool

[torn escarp]

when you plug it in and work it out, you'll see the t part cancels out to make 0 by design

yeah

[prime sparrow]

Hint: what does R look like modulo the integer grid? (Ie: looking at the space formed by equating two points in the plane when they differ by integers on both coordinates)

[prime sparrow]

Ok i’ll try to be a little more explicit, Imagine sliding all the squares of the integer grid into the unit square, and move the parts of R in the square along with them, in this unit square we now have all the parts of R somewhere. If R never intersects any integer translation of itself, do you see that none of the pieces will overlap once we move them will in the unit square?

[fringe bear]

1 + 1 = 11

right?

[torn escarp]

memes go in #chill

[fringe bear]

ok chill

sus

1 + 1 = sus

[torn escarp]

here's a different approach, you can think of translating the shape to any point 1 unit away as moving the center to a point on the circumference of a circle. We can imagine now rotating that shape around the circle, which is equivalent to just moving one shape a unit distance and then rotating them both in the same angle and same speed and look for intersections. The largest shape you can do this with will fit inside a circle of radius 1/2, and since pi/4<1 it means you can't do that with a shape of area 1.

[spark shuttle]

yeah i agree. R wont overlap in the unit square

[prime sparrow]

Ok but now if R’s area is >1 this will be impossible as we have now fit R into a square of area 1. So by contradiction R intersects an integer translation of itself

[torn escarp]

you're not compressing anything, you're more just rolling it over on top of itself

[prime sparrow]

imagine we have R drawn on the cartesian plane, now imagine cutting up the cartesian plane into 1x1 squares where the vertices of the squares are the points that are integers in both coordinates. Place all these squares on top of each other on the square whose bottom left vertex is the origin. These squares may have parts of R on them and I’m saying that if no integer translation of R intersects R, none of these parts of R will overlap with another on this square at the origin

[wispy creek]

cant we end the proof after the red part has been shown ?

why do we need the blue part ?

[leaden swan]

Yea,you don't need the blue part

[wispy creek]

aight thnx for the clarification

[wispy creek]

in order to prove ϕ(mn) = ϕ(m)ϕ(n) when gcd(m, n) = 1. they set up a bijection between these two sets

in order to prove the surjectivity of this map, they prove chinese remainder theorem

this just guarantees a solution. dont we have to show that its relative prime to mn so back in the domain set ?

like if the solution is a number thats not in the domain, the map cant be surjective

[leaden swan]

So you accept Chinese remainder theorem is correct?

If x=a mod m and x=b mod n and a and b are coprime to m and n respectively x=c mod mn will have c coprime to mn,assuming c->(a,b)

You can show that by explicitly constructing c

[wispy creek]

if its not too complicated can u show how i would construct that ?

wait lemme try it out first

wait is this incredibly simple ?

[leaden swan]

Yes

Assuming you know what a multiplicative inverse is

[wispy creek]

c = a mod m and c = b mod n. so c is coprime to m and n(cuz a, b coprime to m,n). hence c coprime to mn

is this right ?

[leaden swan]

Ye,That works

[wispy creek]

[leaden swan]

I was thinking of explicitly constructing c

But that's not necessary apparently

[wispy creek]

u mean unnecessary ?

[leaden swan]

Mb

[wispy creek]

oh ok

[leaden swan]

If you want,I can give you the construction

[wispy creek]

kk sure

cant hurt to know how to construct it

[leaden swan]

Let mm'=1 mod n and nn'=1 mod m
Then amm'+bnn'=a mod n and b mod m.

Yea, It's very simple

You know m' and n' exist because (m,n)=1

And apply Euclidean to get m' and n'

[wispy creek]

wow

very nice

[leaden swan]

Or you can use this

[wispy creek]

how do u use eulers theorem to find multiplicative inverse

oh i think i know

[leaden swan]

one of the b_i is 1

So some b_j a=1

[wispy creek]

a's inverse in mod m would be a^(phi(m) - 1)

[leaden swan]

That works too

But for that you need to prove (a^phi(m))=1

[wispy creek]

nice. im starting to get the hang of NT

[leaden swan]

For that you need to show (Z/n)* is a group

Which requires that every element in (Z/n)* has a inverse

[wispy creek]

ye they proved eulers theorem in the prev chapter

[leaden swan]

How did they prove it

[wispy creek]

set up a map, which is multiplication by a and proved its bijective

then multiply all the numbers

cancel out some stuff and ur left with eulers theorem

[leaden swan]

Ok,That works too

But if you actually want to compute the inverse,you would use euclidean