elementary-number-theory

[scarlet smelt]

how to find a sequence where, say, 6 elements alternate sign from this relation? Can you show an example?

[primal pewter]

if you substitute n=6 in my solution (note that I had a typo in the expression of M; it's fixed now), you get M=F[5]/F[4]=5/3 and m=F[6]/F[5]=8/5

so you want a and b such that m < a/b < M; and my suggestion was to choose a/b such that a/b = (m+M)/2

we have (m+M)/2 = (8/5 + 5/3)/2 = 49/30

so simply pick a=49 and b=30, for which you get 49,-30,19,-11,8,-3,5,2,7,...

note that the we got 7 terms to alternate, which is fine

[primal pewter]

indeed, you are right

so I guess all the indexes should be decreased by 2

[brisk shard]

@dusky aspen You can look at the base 2 representation of 2336.

,w 2336 in binary

[sterile pumice]

Results provided by WolframAlpha

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

Requested by chai.t.rex

[primal pewter]

yes

[scarlet smelt]

Ohk

[scarlet smelt]

does the rest of the solution also change because of this change?

[primal pewter]

just the indexes, so we have

a/b > max{F[2]/F[1], F[4]/F[3], ..., F[2floor(n/2)-2]/F[2floor(n/2)-3]}
a/b < min{F[3]/F[2], F[5]/F[4], ..., F[2floor((n+1)/2)-3]/F[2floor((n+1)/2)-4]}

and so M=F[2floor((n+1)/2)-3]/F[2floor((n+1)/2)-4] and m=F[2floor(n/2)-2]/F[2floor(n/2)-3]
and I guess now we have to inspect the case n=3 separately (otherwise M is undefined)

she originally asked: "How do I find a sequence where the first n terms alternate signs?"

which to me only means that we want the first n terms to alternate, without any additional constraints, but I agree it would be an interesting question to ask for a sequence in which exactly the first n terms alternate

for this, we further need the condition (-1)^(n+1)x[n+1]>=0

the three conditions are necessary and sufficient

[primal pewter]

we don't have a/b=7/2;
the condition is 3/2 < a/b < 2
for which I chose a/b = (3/2 + 2)/2 = 7/4

yes, we want the signs to be + - + - + +

or well, (+ or 0) for the last one

I don't think so

[primal pewter]

maybe there is still an issue with the indexes; I don't see it, but I'll look into it tomorrow

[primal pewter]

@eternal sequoia I think it's better to split the problem into two cases: n odd or n even
basically I tried to merge them (that's why we have those floors), and my guess is that the issue is somehow hidden in this

Say n is even, so n=2k. And assume k>1.
x[1]=a>0
x[2]=-b<0

We have x[3]>0, x[4]<0, ..., , x[2k-1]>0, x[2k]<0.

we recall that x[n] = F[n-2]a - F[n-1]b, so the above conditions give us

a/b > F[2]/F[1]
a/b < F[3]/F[2]
a/b > F[4]/F[3]
a/b < F[5]/F[4]
...
a/b > F[2k-2]/F[2k-3]
a/b < F[2k-1]/F[2k-2]

equivalent to saying that a/b > max{F[2]/F[1], F[4]/F[3], ..., F[2k-2]/F[2k-3]} and a/b < min{F[3]/F[2], F[5]/F[4], ..., F[2k-1]/F[2k-2]}

and as I said in a previous message, one can show (using Cassini's identity at some point) that F[2]/F[1] < F[4]/F[3] < ... < F[2k-2]/F[2k-3] and F[3]/F[2] > F[5]/F[4] > ... F[2k-1]/F[2k-2]

therefore the necessary and sufficient condition for at least the first n=2k terms to alternate is F[2k-2]/F[2k-3] < a/b < F[2k-1]/F[2k-2]

I hope it works now

and in order to be exactly n instead of at least n, we add the condition x[2k+1]<0, i.e. a/b < F[2k]/F[2k-1];
so the necessary and sufficient condition for this problem is F[2k-2]/F[2k-3] < a/b < min{F[2k-1]/F[2k-2], F[2k]/F[2k-1]}=F[2k]/F[2k-1]

and I just realized something interesting; instead of choosing (m+M)/2, we can do something nicer
there is this cool fact that if A/B < C/D, then (A+C)/(B+D) is between them; so we can just pick this instead

and I think this fact can also be used for proving F[2]/F[1] < F[4]/F[3] < ... < F[2k-2]/F[2k-3] and F[3]/F[2] > F[5]/F[4] > ... F[2k-1]/F[2k-2]

Basically we see that F[2]/F[1] < F[3]/F[2], and then (F[2]+F[3])/(F[1]+F[2])=F[4]/F[3] is going to be between, so we have F[2]/F[1] < F[4]/F[3] < F[3]/F[2]; then we extend to F[2]/F[1] < F[4]/F[3] < F[5]/F[4] < F[3]/F[2], and keep repeating

so anyway, I only checked the case n even. The case n odd is similar.

[primal pewter]

@eternal sequoia b=F[13], not -F[13]

yes

[primal pewter]

@eternal sequoia there were mistakes with the indexes; I corrected them now

so for the at least n part we have the condition F[2k-2]/F[2k-3] < a/b < F[2k-1]/F[2k-2]
we can choose a=F[2k-2]+F[2k-1]=F[2k] and b=F[2k-3]+F[2k-2]=F[2k-1]

and for the exactly n part choose a=F[2k-2]+F[2k] and b=F[2k-3]+F[2k-1]

[primal pewter]

@eternal sequoia are you sure you didn't mix n and k? for n=10 you have k=5

because all I did was for the case n=2k

n even

[scarlet smelt]

I couldnt do it for odd numbers

[surreal tangle]

How many subsets of ${1,4,9,16,...,100} $have a sum of 360?I know you can find the coefficient of $x^{360}$ in $P(x)=(1+x)(1+x^{4})(1+x^{9})...(1+x^{100})$ to get the number of subsets, so how do I go about this? I know one trick where you evaluate P at all the 360th roots of unity and then add them up, but that just seems like shifting the problem from one tough thing to another. Any ideas?

[sterile pumice]

smidgin

[surreal tangle]

Just realised the sum of all the elements of that set is 385, so maybe manually finding the number of subsets is possible but what if I wanted to generalise this? Is it even possible to generalise to something like {1,...,n^2} and the sum of the subset must be some other natural number k?

[patent acorn]

it's definitely doable mostly-manually, there's a nice trick that makes it really easy to brute force once you see it

for arbitrary k and the squares 1-100 i got a computer to find the number of subsets that sum to each k and it's 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 2, 2, 0, 0, 2, 2, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 2, 1, 0, 0, 2, 2, 0, 0, 2, 3, 1, 1, 2, 2, 1, 1, 1, 1, 1, 0, 2, 3, 1, 1, 4, 3, 0, 1, 2, 2, 1, 0, 1, 4, 3, 0, 2, 4, 2, 1, 3, 2, 1, 2, 3, 3, 2, 1, 3, 6, 3, 0, 2, 5, 3, 0, 1, 3, 3, 3, 4, 3, 2, 3, 4, 4, 2, 0, 3, 7, 4, 0, 3, 6, 4, 3, 4, 3, 3, 4, 3, 3, 3, 1, 4, 8, 4, 0, 5, 8, 4, 1, 2, 5, 5, 3, 2, 5, 6, 3, 3, 6, 5, 1, 4, 7, 4, 1, 4, 7, 5, 3, 3, 6, 7, 4, 1, 5, 7, 2, 3, 6, 4, 3, 7, 6, 3, 4, 4, 6, 6, 2, 1, 8, 9, 2, 2, 6, 6, 4, 5, 4, 4, 5, 5, 6, 5, 2, 3, 9, 8, 2, 2, 8, 9, 3, 2, 5, 6, 5, 5, 4, 4, 5, 4, 6, 6, 2, 2, 9, 8, 1, 2, 6, 6, 4, 4, 3, 6, 7, 3, 4, 6, 3, 2, 7, 5, 1, 4, 7, 6, 3, 3, 5, 7, 4, 1, 4, 7, 4, 1, 5, 6, 3, 3, 6, 5, 2, 3, 5, 5, 2, 1, 4, 8, 5, 0, 4, 8, 4, 1, 3, 3, 3, 4, 3, 3, 4, 3, 4, 6, 3, 0, 4, 7, 3, 0, 2, 4, 4, 3, 2, 3, 4, 3, 3, 3, 1, 0, 3, 5, 2, 0, 3, 6, 3, 1, 2, 3, 3, 2, 1, 2, 3, 1, 2, 4, 2, 0, 3, 4, 1, 0, 1, 2, 2, 1, 0, 3, 4, 1, 1, 3, 2, 0, 1, 1, 1, 1, 1, 2, 2, 1, 1, 3, 2, 0, 0, 2, 2, 0, 0, 1, 2, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 2, 2, 0, 0, 2, 2, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1 which doesn't look particularly hopeful in terms of there being some simple pattern to compute them

[surreal tangle]

Yeah i agre with this, i doubt its generalisable

Thanks for the help

I think 360 was chosen on purpose, because you had to remove elements whose sum was 25(385-25=360) from the set {1,4,9,16,..,100} and everyone knows about the 3^2+4^2 and 5^2, so you have 2 subsets

[primal pewter]

Come on... I figured you are xuetao...
I mean... you joined this server specifically to bump her questions, which I don't mind, but my concern is that you probably want to get others do your homework.
I gave you a comprehensive solution for the case n even. For n odd the solution is essentially the same.

if you are genuinely interested in the problem and understood the solution I gave, the case n=2k+1 is just a matter of a substitution;
all the steps are the same

[glass verge]

When the Chinese remainder theorem says that there is a unique solution to the system of congruences, does it mean a unique congruence $x\equiv a mod m_1…m_n$ (and hence a whole modulo class of solutions) or a unique number solution by itself, ie, $x=4$?

[sterile pumice]

normalAtmosphericPa=101,325

[open mist]

"unique modulo N"
So only one class of equivalence mod N
i.e. the solution set is of the form {x + kN, k in N}

[pliant heath]

Is it possible to write this way?

[fleet bone]

if u want to brute force prolly use the fact the subset must contain atleast 7 elements as if it has k elements

then the maximum value of sum is (10)^2+9^2+...+(11-k)^2

infact in 7 the sum is 371

so a lil bit of checking will boil the problem into 8 and 9 ,10 element

for 9,10 its obvious what to do

for 8

it basically boils down to solving an equation like a^2+b^2=c

if modulo checking doesnt work

just bound

ok even better c becomes 25

so 3^2+4^2 well known

so u get 1 for 8 element subsets

for 9

as 25=5^2

1

and for 10 obviously none

and for 7 by checking i dont think there is any as well

so 2 ig

[surreal tangle]

Yeah, thats what i had said in the next message

[surreal tangle]

The sum being 360 gives you good sets

[fleet bone]

oh srry forgot to read it

[dusk vessel]

I tried this in the help sections but to no avail

assume that we must check that $$t = \frac{(2n+1)L}{2V} - C$$ for every value on the interval (0, T), how can we create a function $\beta(t)$ which sums each of the instances that the condition is true from 0 to T.

I understand that if the condition were instead $$t = \frac{(2n+1)L}{2V}$$, then we could simply find the number of odd numbers from 0 $\to$ $\frac{2TV}{L}$, but trying a similar method with the constant proved to be wrong. Also if you could please prove 0 $\to$ $\frac{2TV}{L}$ thius piece as well

Thank you

[sterile pumice]

£ ςΓσΔηκεΓζ

[dusk vessel]

which I guess is essentially a summation of the amount of integer multiples fall into some interval\

[surreal tangle]

[errant otter]

Not sure how to prove:
if x is odd and divides a-1, then gcd(x, a+1) = 1

x = c(a-1) for some integer c

x = 2k-1 for some integer k
(2k-1)/c + 2 = a+1
.... so?

so c must be odd ig

wait...

oh

a-1 mod x = 0
a+1 mod x = 2

[dusty dragon]

yeah, it boils down to basically the following:

1. x | a - 1 => a - 1 = cx
2. a + 1 = cx + 2.

Then you have

Let d = gcd(x, a + 1). d | x and d | (a + 1) implies d | ((cx + 2) - x)
=> d | x(c - 1) + 2
=> d | 2
=> d = 1 (why can't d = 2?)

[errant otter]

cuz x odd

[dusty dragon]

yup

[errant otter]

now here's smth funny if anyone wants to help me out with this 🤡

tldr

find the maximum value of $k$ such that $x^k$ divides $\sum^n_{i=0} a^i$, where $x, a, n$ are given, $x$ is odd and $x$ divides $a-1$

[sterile pumice]

Kiameimon | Welt Rene

[errant otter]

well geometric series simplifies the first part to

$x^k$ divides $\frac{a^{n+1} -1}{a-1}$

[sterile pumice]

Kiameimon | Welt Rene

[errant otter]

(target is to find some closed form formula for k)

and since x divides a-1...

and furthermore x is odd

[errant otter]

$cx = a-1$ for some $c$... so $c x^{k+1}$ divides $a^{n+1}-1$

wait

wrong way around

.... ehhh

[sterile pumice]

Kiameimon | Welt Rene

[primal escarp]

Use lifting the exponent lemma on a prime that divides x

[glacial ridge]

how do i find all integer solutions k so that (800-k^2)^(1/2) is a natural number

[weary rune]

let $800-k^2=m^2$ for some integer $m$

[sterile pumice]

elrichardo1337

[weary rune]

ie find all k so that that expression under the square root is a perfect square

from here this is just Pythagorean triples

[glacial ridge]

is there a better way

[open mist]

a quick analysis modulo 8 shows that either k, m in {0, 4} mod 8, or k, m in {2, 6} mod 8
So that reduces the search space
But still, pythagorean triples

of which there aren't so many since 30² = 900 so you don't really need to look at such large integers

[wintry locust]

$\lambda(5^4) = lcm(\lambda(5^2), \lambda(5^2))$

[sterile pumice]

shsgd

[wintry locust]

why is this not valid?

lambda being the Carmichael Lambda function

[dusty dragon]

lcm(lambda(a), lambda(b)) = lambda(lcm(a, b)), right?

lcm of 5^2 and 5^2 being 5^2

[wintry locust]

ah right, brain not braining i guess

also, how can one prove lambda(256) = 64

[dusty dragon]

lambda(256) = lambda(2^8) = 1/2 * phi(2^8) = 1/2 * 2^7 = 64

where phi is the standard Euler totient function

it helps that 256 is a power of 2 with the power being at least 3

so you can just use the recurrence for the Carmichael lambda function

[wintry locust]

hmm, the solution given was much different

[dusty dragon]

maybe you haven’t derived the recurrence

[wintry locust]

what do you mean by recurrence

[dusty dragon]

https://brilliant.org/wiki/carmichaels-lambda-function/

You can evaluate the lambda function on powers of prime using the Euler totient function

[wintry locust]

yeah I get that

but the solution given threw me off

that is

"From Q7 we have that lamda(256)|64. To prove the equality, we find an odd number 'a' such that a^32 =/= 1 (mod 256), the following calculation shows that a = 5 has this property:"

5^1 = 5, 5^2 = 25, 5^4 = 625 = 113, 5^8 = 113^2 = 12769 = -31, 5^16 = (-31)^2 = 961 = -63, 5^32 = (-63)^2 = 3969 = -127 =/= 1

why would finding an odd number a such that a^32 =/= 1 (mod 256) prove the equality?

[dusty dragon]

because it shows that lambda(256) ≠ 32 which implies that it also can’t be any power smaller than 32; if it did, then a^32 = 1 (mod 256) for all a coprime to 256

so it must be 64

[wintry locust]

and 32 was chosen as its the second largest factor of 64? So since lambda(256) | 64 then it is a factor of 64, if its not <= 32 it must be 64

[dusty dragon]

yea

[wintry locust]

right

[grand umbra]

Find natural numbers m n r such that m! × n! = r!

(r > 10)

[proper folio]

can someone please explain why they are able to sum over all the divisors

Basically, are they saying that $F(d)=\sum\limits_{e\mid d}F(e)$

[sterile pumice]

Kalgar

[proper folio]

how?

[dusty dragon]

it comes from the lemma that they described; specifically, if a^d = 1 (mod p), then you know that a^e = 1 (mod p) iff. e | d. So the number of residue classes for which a^d = 1 (mod p) must come from the divisors of d

each element a must be contained in exactly one of these residue classes because the order of an element is unique

[proper folio]

Oh hi Gerld

[proper folio]

I mainly don't get this statement:

"In particular, for every divisor $d$ of $p-1$, the number of residues mod p such that $a^d\equiv 1 \pmod p$ is the sum over all the divisors $e$ of $d$ of the number of residues $a$ such that $\operatorname{ord}_p(a)=e$"

[sterile pumice]

Kalgar

[proper folio]

what is the "residues" referring to?

the $a^d$ right? Or is it just the $a\in{1,...,p-1}$ itself?

[sterile pumice]

Kalgar

[proper folio]

sounds ... so verbose, and confusing

[dusty dragon]

it just refers to a

[proper folio]

" the number of residue classes for which a^d = 1 (mod p) must come from the divisors of d
"

why?

[dusty dragon]

a^d = 1 (mod p) implies a^e = 1 (mod p) where e | d

[proper folio]

yeah

I am struggling to make the jump from that lemma to your conclusion there

[dusty dragon]

so if you have some a satisfying a^d = 1 (mod p), then it is also true that a^e = 1 (mod p) for some divisor e of d, the smallest of which is ord_p(a).

[proper folio]

oh

wait is e supposed to be the order

[dusty dragon]

not necessarily the order here, just some divisor

the way we count the elements is by the order

[proper folio]

or are you trying to say something like, we know that the order | d

but we will look for the order by doing e | d for any divisor e

[proper folio]

count what elements?

"a"s?

[dusty dragon]

yep

the point is that if a belongs to S = {a : a^d = 1 (mod p)}, then a must belong to {a : a^e = 1 (mod p), e = ord_p(a)}

[proper folio]

and so conversely

if $a$ satisfies $a^e\equiv 1 \pmod p$, then it should also satisfy $a^d\equiv 1 \pmod p$ right?

[sterile pumice]

Kalgar

[dusty dragon]

yep

that's not difficult to show

d = ek and so if a^e = 1 (mod p), then a^d = (a^e)^k = 1 (mod p)

[proper folio]

wait I'm still sort of confused

this is the lemma

it's for the order specifically

how are you able to generalise it to any random e | d

[dusty dragon]

the order is what's interesting

for an element a, the order modulo p is unique

and also you know that the order divides d

so a belongs to the set {a : a^k = 1 (mod p), k = ord_p(a)}

[dusty dragon]

and this is a subset of S that we defined here

ok here's another way to look at it

the idea is that S can be partitioned into sets defined exactly by the possible orders that divide d

[glass verge]

Why?

Do I just need to remember this

Or is there something that makes it obvious?

[dusty dragon]

order of an element is unique

so if ord_p(a) = k_1 and ord_p(a) = k_2, then k_1 = k_2

now consider the sets defined by {a : ord_p(a) = k} with k | d

by the uniqueness of the order, these sets are disjoint

you now need to show that the union over all such sets is S

[glass verge]

How :/

[proper folio]

lol

isn't this just the same problem flipped around

oops

replying from other acc d

[dusty dragon]

You want to show [\bigcup_{k \mid d} {a : \operatorname{ord}p(a) = k} = S.]
To show the forward containment direction, let $a \in \bigcup{k \mid d} {a : \operatorname{ord}_p(a) = k}$. Then $a \in {a : a^k \equiv 1 \pmod p}$ for some $k = \operatorname{ord}_p(a)$. Since $k \mid d$, then $a^d = a^{k\ell} = (a^k)^{\ell} \equiv 1 \pmod p$ which implies that $a \in S$.

To show the reverse containment direction, let $a \in S$. Then $a^d \equiv 1 \pmod p$. You know that $a^{\operatorname{ord}_p(a)} \equiv 1 \pmod p$ and $\operatorname{ord}_p(a) \mid d$, so it appears in one of the sets in the union.

[glass verge]

Not very intuitive

[proper folio]

Is every element of $\mathbb Z _p$ a primitive root?

every non-zero element*

[sterile pumice]

Kalgar

[still flare]

Is -1 == 4 a primitive root of Z_5?

[proper folio]

oh

no b/c $4^2\equiv 1$

[sterile pumice]

Kalgar

[brave citrus]

how many way to place all 2n marbles into an nxn board such that in a row and column, there are exactly 2 marbles?

[rustic tulip]

I’m trying to write a C program code for finding the gcd using eulcidean division algorithm

[rustic tulip]

is this correct? also how do i copy the value of r, just before it becomes zero

[versed olive]

Think of what happens to the value of r the step before that in which it becomes 0. Let’s call this value of r, r_n-1, and analyse how we’ve obtained it through the algorithm. We have some r = r_n-2 != 0, so the programme executes the while loop, the r takes the modulo of some a and b and becomes r_n-1. Then a <- b, b <- r_n-1, therefore, at the end of the iteration, there are two variables storing r_n-1, namely r and b. We have r=r_n-1!=0, so while loop executes. We get r <- a%b = 0, a <- b = r_n-1, b <- 0. r=0 so the loop doesn’t execute. So, we want it to return a = r_n-1. Also, since you’re working in C, I assume this is within a function? or perhaps part of the main()? you have to attribute to r some starting value before the while loop, so that it doesn’t give you a cannot compare null with number value (I think C doesn’t equal null with zero, however even so it’d be wrong since it won’t enter the loop at all). So give r some random value greater than 0 to begin with. It doesn’t matter which, since it’d take the value of a%b before using that value eslewhere

[rustic tulip]

Actually

It turns out that gcd is copied in a

when r=a%b=0

a=b still happens

[versed olive]

b=a? How so? You mean a <- b?

[versed olive]

Yes

[versed olive]

Yes, but the b remains your desired value, r from before, so your a takes the value of the previous rest

[analog laurel]

Stuck on proving the following:

Let m,n coprime. If a = b (mod m) and a = b (mod n), then a = b (mod mn)

[still flare]

Your first thought should be Bézout’s lemma whenever you see “let gcd(a, b) = …” and indeed I suggest that you think about how you might use it here

[analog laurel]

I have and im stuck

Please do help

[analog laurel]

Hello?

Bezout says xm+yn=1

How does that help

[shrewd gust]

You can rephrase this as: n | a-b and m | a-b for n,m coprime. Can you show that it then follows that nm | a-b?

[proper folio]

hollup

for this proof to work

doesn't it require there to be infinitely many $2^p-1$?

[sterile pumice]

Kakaka

[proper folio]

but it's not known whether there are infintely many mersenne primes

oh wait

dont need to be prime oops

[simple trellis]

either im jus a dumbass or yall are suiper smart bc i jus dont remember alg being so hard

[sleek cove]

this is number theory

[tough copper]

i'm having trouble understanding what GF(28) = GF(2) [x]/(x8 + x4 + x3 + x + 1)

means

[dusty dragon]

GF(p^k) is the finite (Galois) field containing p^k many elements; there's only "one" such field, up to isomorphism. Here, we're looking at the finite field containing 2^8 elements, which is isomorphic to the field of polynomials over GF(2) modulo x^8 + x^4 + x^3 + x + 1

[silent halo]

not sure if this is a hard question. but let's say $\frac{x}{y} = \frac{u-150}{v-150}$. $x,y$ are known. what are some ways to check if there is an integer solution $(u,v)$, and getting them?

[sterile pumice]

Dominic

[silent halo]

lets also say $x,y,u,v$ should be positive and at most 1000

[sterile pumice]

Dominic

[charred roost]

(u = x + 150, v = y + 150) is a solution

[sacred junco]

when working with Quadratic Residues, if we took for example p = 7 and the quadratic residues modulo 7 is the number that is congruent to the squares of the number from 1-6, which would be modulo 7, this would be given as x^2 = n (mod p) where x is an integer and if no such integer x exists then n is a non-residue quadratic modulo p.... Am I getting that right?

[bronze rock]

For $r \in \mathbb{Z}^+$, $s \in \mathbb{Z}_{\geq 0}$ we express can express gcd($r$, $s$) as $nr + ms$ for some $n, m \in \mathbb{Z}$

Are the integers $n$ and $m$ unique?

[sterile pumice]

BlazingSaber

[coral venture]

No

It's especially easy to construct a counterexample if s=1

For example s=1, r=2

Then n=1, m=-1 and n=2,m=-3 both work

[bronze rock]

fair!

wait, they don't come out to be equal, do they?
(1)(1) + (2)(-1) = -1
(2)(1) + (-3)(2) = -4

[coral venture]

I flipped the order i wrote r and s

[bronze rock]

my bad

[coral venture]

More like my bad

[mystic sinew]

To check if a number is prime, it’s enough to check each integer until sqrt{n}

I’ve seen the proof of it by method of contradiction

I’m wondering, is it possible have a much smaller upper bound?

[still flare]

No, because the number n = p^2, where p is some prime, achieves this bound.

[mystic sinew]

You mean for n=p^2, it must iterate till p to obtain the first factor which is exactly sqrt{n}=p right?

[mystic sinew]

thus any claim of having a lesser upper bound will contradict to this

did i get that right?

[still flare]

Yup

[sonic wharf]

I can't figure out how to find the p-adic norm of x+y. Any advice?

[still flare]

There's no formula for ||x + y|| in terms of ||x|| and ||y||. You can only observe that ||x+y|| <= min(||x||, ||y||).

In fact I think it's a good idea to produce values x, x', y, y' with |x| = |x'| and |y| = |y'| but |x+y| =/= |x'+y'| to show that no formula exists.

A hint for this: you can stick with the integers.

[sonic wharf]

alr I'll work with that

ty

[urban dust]

Isn't there a polynomial time upper bound better than sqrt(n) for primality testing?

https://en.wikipedia.org/wiki/AKS_primality_test#History_and_running_time

[coral venture]

Yes

[open mist]

Yes

[coral venture]

The discussion was about which integers you had to check when primality testing by trial division

[sacred junco]

hi

need help with encryption

[rustic tulip]

Every composite number n has a prime factor $\leq \floor{\sqrt{n}}$

[sterile pumice]

.doc

[rustic tulip]

Please check if my proof is correct

Since n is composite, there exists $a,b \in \mathbb{Z}$ such that $n=ab$

[sterile pumice]

.doc

[rustic tulip]

Suppose both $a,b >\sqrt{n} \implies ab>n$

[sterile pumice]

.doc

[rustic tulip]

contradiction

Suppose both $a,b <\sqrt{n} \implies ab<n$

[sterile pumice]

.doc

[rustic tulip]

contradiction again

Thus either $a\leq \sqrt{n}$ or $b \leq \sqrt{n}$

[sterile pumice]

.doc

[rustic tulip]

Is the reasoning correct?

[rustic tulip]

Shouldn’t the or be an exclusive or?

[west glade]

just because xor is correct doesnt mean that or is false. also xor wouldnt be correct here if a=b and n=a^2

[west glade]

you dont need this

what you havent shown is that n has a prime factor <=sqrt(n). just that it has some factor <=sqrt(n)

[coral venture]

Quadratic residue

[coral venture]

Look at n!+3 mod 4

And m^2

yes

if n>=4, what is the remainder of n!+3 when divided by 4?

exactly

so what can you conclude about n?

no

you just proved that n >= 4 is impossible

cause a number can't have two different remainders when divided by 4

m^2 can be 9, 4, 1, yeah

you just have to check the cases where n=1, n=2 and n=3

[left jackal]

this?

[dusty dragon]

the order of 10 in Z_7, often written as ord_7(10)

[dusty dragon]

yeah we just say it has infinite order

[mystic sinew]

n is a composite number, if there exists $a,b < n \in \mathbf{Z}$ such that $n=ab$

is this the correct defintion of a composite number?

[sterile pumice]

Dubs

[patent acorn]

5 is a composite number, because a = -1 and b = -5 are both less than 5 and multiply to 5

[mystic sinew]

i should have written N

i think primes only makes sense for positive integers

[patent acorn]

in that case it works

[mystic sinew]

do we classify negative numbers as composite numbers?

[normal heart]

'-1 is the smallest prime number'

[silver perch]

Wow, that's crazy

[mystic sinew]

#help-16

please check my proof posted

please be nitpicky as possible, trying to improve

\textbf{\large Theorem: }For any composite number $n > 2 \in \mathbf{N}$, there exist a prime divisor less than $\sqrt{n}$.

\textbf{Proof:} Since n is a composite number, there exists $a,b < n \in \mathbf{N}$ such that $n=ab$
suppose a,b $ >\sqrt{n} \implies n=ab>n$ which is a contradiction.
$\implies$ is either a or b, is less than $\sqrt{n}$

Assume WLOG, $a<\sqrt{n}$, by fundamental theorem of arithmetic, there exist a prime p such that $p \mid a$. but $n=ab \implies a \mid n$. by transitivity of divisibility relation $\implies p \mid n$

[sterile pumice]

Dubs

[coral venture]

Let n=9

Then the only prime divisor, 3, is not less than sqrt(9)=3

[sacred junco]

Yeah it should be a ≤ √n instead of a < √n since WLOG √n can be prime as well if a is prime and a = √n

Other than that, the proof seems fine

[boreal lagoon]

Just to double-check, if p\nmid m, then k=p-1 and m is congruent to (-1)^{p+1} mod p, right?

[coral venture]

yes

[primal pewter]

@shy scaffold do mod 8 instead

the squares modulo 8 are 0,1,4

then notice that you can't get 7 mod 8

[patent acorn]

i have no idea where you got 4x or 4(n^2+n)+1 from, but yeah you can just square all the numbers and see what you get

0^2 = 0, 1^2 = 1, 2^2 = 4, 3^2 = 1, 4^2 = 0, all the numbers past that point are negatives of other numbers we've already checked (5 = -3, 6 = -2, 7 = -1) and therefore have the same square as their negative, so it's just 0, 1, 4

ok well (2x)^2 is not 4x

i... guess you can do that, but it doesn't seem that useful, it's easier to just enumerate the integers mod 8 and try all of them

[noble obsidian]

How do you define p^m / p mod k if p is not a unit?

This should be p^{m-1} but how do we show this is the case?

p is not necessarily prime

[primal pewter]

||if it's not necessarily a prime, then don't denote it by p||

I don't really think we can define that fraction as a "fraction modulo"

to define a/b mod n, you need b to be coprime to n, so that a/b would just mean ab^(-1)

but this can't really be extended to gcd(b,n)>1, so I think that fraction is merely a fraction in the usual sense

[coral venture]

This would be a scuffed and pretty useless definition because a=p^m (mod k) wouldn't imply a/p = p^m/p (mod k)

[noble obsidian]

Oh really

[coral venture]

e.g. p=3, m=3 and k=12

[noble obsidian]

The main reason why i ask this is because ok consider Z_m and the principal ideal (p_1…p_m). If a is expressed in prime factorization of these primes up to powers how do I show that a is in the ideal.

[primal pewter]

Or I think there should be a way to introduce fractions with non-units denominators if we use localization, but I'm not sure if it's useful in number theory. For example, localize the ring A=Z/6Z by S={1,2,4}

it just creates peculiar identities, such as 1=1/4

[noble obsidian]

I said just consider the element a/(p_1…p_m) to be your scalar multiple in the ideal.

But i guess one just has to be brutal with it and say take all powers minus one.

[primal pewter]

@shy scaffold I think this works:
first notice that |S| can be k+1 if you choose S={the odds} (or S={k+1,k+2,...,2k+1})
now let's prove |S| cannot exceed k+1

if 1 is in S, then pair the numbers like this: {1,2}, {3,4}, {5,6}, ..., {2k-1,2k}, {2k+1}
from every set we are allowed to choose at most one element, so |S|<=k+1 in this case

if 2 is in S, pair them by difference 2, and the conclusion should be the same

...
repeat this up to the case:
if k is in S, pair the numbers like this: {1,k+1}, {2,k+2}, ..., {k,2k}, {2k+1}... same conclusion

And now the case when none of 1,2,...,k belong to S. In this case S is a subset of {k+1,k+2,...,2k+1}, so |S|<=k+1.

[nova vine]

Show that $\gcd(n,n+2)=1$ if $n$ is an odd integer, namely, two consecutive odd numbers are coprime.

[sterile pumice]

Godspell

[nova vine]

Let's assume for the sake of contradiction that, if $n$ is an odd number, then $gcd(n,n+2) \neq 1$. Then that means $gcd(n,n+2) = k$ where $k \neq 1$ and $k$ $\in$ $\mathbf N$.

Then, by Bezout's lemma, there exist integers $x$ and $y$ such that $(n)x + (n+2)y = k$.
\begin{align}
(n)x + (n+2)y = k \\
nx + ny + 2y = k \\
n(x+y) + 2(y) = k \\
\end{align}
Therefore, we get the Bezout's identity $n(x+y) + 2(y) = k$ since $x$ and $y$ are integers. Which gives us $gcd(n,2) = k$.
Now, if $n$ is even, we get $gcd(n,2) = 2$, but that is a contradiction since we assumed that $n$ is odd. 

So, when $n$ is odd, $gcd(n,2) = 1$, and our statement that when $n$ is odd, $gcd(n,n+2) = 1$ is proved.

[sterile pumice]

Godspell

[nova vine]

can someone please proof-read my proof

[coral venture]

You don't need to assume the contradiction

But yeah it's fine

[nova vine]

awesome, thanks!!

[west glade]

you should try showing separately that gcd(a,b)=gcd(a,b-a). you dont need bezout for that

also thats not how bezout works

from gcd(a,b)=c you can conclude that there exist integers x,y with ax+by=c, but from ax+by=c you can only conclude that gcd(a,b) divides c

@nova vine

[nova vine]

ahh interesting

so should i do something like,

$gcd(n,2) = c|k$

[sterile pumice]

Godspell

[nova vine]

and then try to prove that c = k ?

[west glade]

you should try this

thats what your attempted proof boils down to anyway

[nova vine]

ahh i get it

[nova vine]

it would become $gcd(n,n+2) = gcd(n, 2) = k$

[sterile pumice]

Godspell

[nova vine]

right?

[west glade]

yes

[nova vine]

and then the rest is same except i'll have to remove the illegal abuse of bezouts in the latter parts

@west glade thanks!!

[empty iris]

\begin{grad} \label{Functions5}
Fix (k \in \mathbb{Z}^{+}). Explicitly construct an injection (\varphi : \mathbb{N}^{k} \to \mathbb{N}). Prove that your function is an injection. [\textbf{Note:} You may use, without proof, that (i) there are infinitely many primes, and (ii) every positive integer admits a unique factorization into a product of prime powers.]
\end{grad}

\begin{proof}
Using the function (\varphi : \mathbb{N}^{k} \to \mathbb{N}) as follows: For a (k)-tuple ((n_1, n_2, \ldots, n_k)) in (\mathbb{N}^{k}), define (\varphi(n_1, n_2, \ldots, n_k) = 2^{n_1} \cdot 3^{n_2} \cdot \ldots \cdot p_k^{n_k}), where (p_k) is the (k)-th prime number.

To prove that (\varphi) is an injection, assume two different (k)-tuples, ((a_1, a_2, \ldots, a_k)) and ((b_1, b_2, \ldots, b_k)), such that (\varphi(a_1, a_2, \ldots, a_k) = \varphi(b_1, b_2, \ldots, b_k)). This implies that (2^{a_1} \cdot 3^{a_2} \cdot \ldots \cdot p_k^{a_k} = 2^{b_1} \cdot 3^{b_2} \cdot \ldots \cdot p_k^{b_k}).

Using the unique prime factorization theorem, the only way the equation can hold is if (a_1 = b_1, a_2 = b_2, \ldots, a_k = b_k). This means that different (k)-tuples map to different natural numbers, confirming that (\varphi) is injective.
\end{proof}

[sterile pumice]

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

[empty iris]

Can someone proof read this?

[low ingot]

looks good 🙂

[wraith reef]

A while ago I was helping to unload a moving truck and it occurred to me that if x is an integer, x^2 + 1 isn't a multiple of 3. I wanted to make a video explaining it in as entertaining a way as possible, what do you guys think?https://youtu.be/Jpg9utCVCy8

[limpid palm]

does anyone know some interesting things about lucas numbers

[tepid wraith]

If there are two natural numbers a and b and define a set S:{an+bm: m,n in Z, an+bm>0}, I have applied WOP to show that set S non-empty and d is the smallest element in S. Then how to show that element d is the gcd of a and b?

[quaint gate]

well you want to show that it divides both a and b

try dividing a by d

find what the remainder would be

[limpid palm]

pika do u have a awnser for ma question?

[quaint gate]

nope never heard of lucas number

[limpid palm]

there are like ... 1 3 4 7...

[tepid wraith]

you mean construct a=dq+r?

[quaint gate]

the division algorithm yes

[tepid wraith]

Then i have d=ax+by=(dq+r)x+by=dqx+rx+by.

[tepid wraith]

but I don't see any relation between d does not divide a and something that means d is not smallest?

[quaint gate]

u want to argue that r is 0

is a-dq a linear combination of a and b?

[quaint gate]

what inequality does r satisfy

[tepid wraith]

r<d

[quaint gate]

so r=a-dq<d?

look a linear combination of a and b that is less than d a contradiction

well not really a contradiction

But you get the point

[tepid wraith]

still feel confused, r<d seems not work

I mean not helpful for this one

[tepid wraith]

because I tried that before, and seems not work for me when I express it in a=dq+r

[quaint gate]

d is the smallest positive linear combination of a and b right?

[tepid wraith]

I want to prove that the gcd is in the set S

i know that d is the smallest element in set s

[quaint gate]

do you agree with this?

this is how you defined your d

[tepid wraith]

actually in our course, we can not use the fact that gcd is smallest linear combination now

[quaint gate]

dawg

[tepid wraith]

they want me to prove d(the smallest element) divides both a and b

[quaint gate]

you are showing that the smallest positive linear combination (which is d as you defined) is the gcd

[tepid wraith]

but I have a confusion here

[quaint gate]

we already established that from here on #elementary-number-theory message

[tepid wraith]

the issue is if the gcd of a and b must be in the set S

[quaint gate]

yes

[tepid wraith]

but I really don't know how to show gcd of a and b really must be in the set S

[quaint gate]

you want to show that d is the gcd

d is in the set by the well ordering property of naturals

Every nonempty subset of N has a least element

if a set has a least element then that element belongs in the set

There are two things you want to show after you have defined d to be the minimum of S. 1. d divides both a and b
2. d is the greatest such divisor

[tepid wraith]

Then how to proceed? because I feel confused how can I show it is the gcd

[quaint gate]

First show 1.

we said divide a by d using division algo

So you said a=dq+r, 0<=r<d

Is that right

[tepid wraith]

OK

[quaint gate]

what does it mean for d to divide a?

what should r be?

[tepid wraith]

r=0

[quaint gate]

so we want to show that

but remember how d was defined

is it a linear combination of a and b?

[tepid wraith]

d is

[quaint gate]

yeah so what about r then?

is r a linear combination of a and b?

[tepid wraith]

it should be, a=dq+r, r=a-dq

so r<d?

then it is?

[quaint gate]

so you said d is the smallest positive integer that is a lineat combination of a and b and now you have this r that satisfies 0<=r<d which is also a linear combination of a and b. r has to be 0 right otherwise r would be >0 and < d and in S

[tepid wraith]

I think I have got it

[quaint gate]

d was the minimum of S but now you have r<d in S

[tepid wraith]

since r still larger than 0

[quaint gate]

yeah now do that for b too

And then do 2.

,ti

[sterile pumice]

The current time for darkpikachu_. is 02:35 AM (+0545) on Thu, 01/02/2024.

[quaint gate]

[tepid wraith]

Then since d is the common divisor within set S, we suppose gcd(a,b)=d' and since d is in the set S, we have d=ax+by, and we can find that any form of ax+by is divided by d', therefore, d is divisible by d'

[tepid wraith]

d is one of S, so d' divides d

[quaint gate]

no

for that start by assuming that there is some other integer d' that also divides both a and b

your hint is: write down what it means for d' to divide a and for d' to divide b

you want to show that d'<=d. Good luck

[tepid wraith]

so since d'|a and d' divides b, therefore d'|am+bn. Then I am thinking that d is in the form of ax+by and d>0, so I think d'|d, do you think if there are some mistakes here?

[quaint gate]

well u know d is a linear combination of a and b and it looks like you've figured it out that you can show d'<=d by showing that d' divides d. Try writing a and b in terms of d'

[tepid wraith]

I actually want to say, since d is in the form of ax+by, so a=d't, b=d's, then ax+by=d'tx+d'ty=d, so d'|d, which means d must be the gcd

[quaint gate]

yeah

[tepid wraith]

so If I first just assume that gcd is d', and d is in the set S actually means d=ax+by, any form of ax+by is divisible by d' implies d=ax+by is divisble by d', therefore d must be gcd

[quaint gate]

no you are showing something that you constructed (which happens to be a common divisor) is actually the greatest common divisor so you pick any other common divisor

why would you assume d' osjust the gcd

Lol you would have to prove that d is d' then and you get absolutely nowhere

just assume d' is any other common divisor and show that d is necessarily>= that

[tepid wraith]

you mean suppose greatest common divisor is something that is constructed by myself?

[tepid wraith]

since we need to show d is gcd, then by contradiction(that's the most natural that I come up with) but I don't know if we can assume something is gcd of a and b

[quaint gate]

no you constructed d wgich to this point you have shown is a common divisor

suppose d' is any other common divisor then show that d is actually bigger. that proves that d is actually the GREATEST common divisor

[tepid wraith]

I actually want to say d is smallest element in the set S, so I write d=ax+by( this one is correct right?)

[quaint gate]

you defined d to be the minimum of S

[tepid wraith]

so d (smallest element is constructed)

[quaint gate]

yes

then you showed that it divides a

And then you showed that it divides b

now you want to show that it is the greatest number with this property. Notably d is the greatet element of the set of all integrrs that divide both a and b. Take any element d' of this set and show that d' divides d to finish the proof.

[tepid wraith]

your proof must be correct. The issue is why the construction of d(the common divisor d)can imply the assumption of gcd d' is not applicable?)

[quaint gate]

Taking d' to be the greatest common divisor and then showing that d is>=d' is a very wacky thing to do. You can still finish the proof this way, it isn't wrong tho

doesn't feel right to me

[tepid wraith]

OK, I got it

[sacred junco]

Does this proof sound correct?

[grand umbra]

prove that sqrt(1sqrt(2sqrt(...sqrt(2023)))) is irrational

[native monolith]

Generally when a question features a year you can replace it with a letter such as n.

So prove:

$\sqrt{1\sqrt{2\sqrt{3...(n-1)\sqrt{n}}}}$ is irrational.

Because of that perhaps induction is the way to go?

[sterile pumice]

Max

[severe ermine]

Find the remainder of division 202420242024...2024 (2024 written 2024 times) by 45

I have no idea how to solve it

like

i tried to google

but the only thing i found is how to find remainder if you divider is a "simple number" like 2, 3, 4... up to 10

[patent acorn]

i think basically just, modular arithmetic

also the fact that it's several of 2024 written next to each other, is the same as just multiplying by various powers of 1000 and then adding it all up

[severe ermine]

can you give me a link to a great video about the topic?

[primal pewter]

@severe ermine just find the remainders when the number is divided by 5 and 9 respectively

then you can find the remainder when divided by 45

[severe ermine]

uh

can you show me a simple example?

[primal pewter]

use divisibility rules
for 5 you look at the last digit (187 --> last digit 7 --> residue 2 modulo 5)
for 9 you look at the sum of the digits (187 --> 1+8+7 --> residue 7 modulo 9)

once you know the number modulo 5 and 9, you can find it modulo 45 by working it out, or by guessing and using CRT (Chinese Remainder Theorem)

to find it modulo 45 you can do something like this: if the number is 2 mod 5, then we can write it as 5a+2; and if it is 7 mod 9, then it is 9b+7;
5a+2=9b+7 => 5(a-1)=9b => b=5k, for some integer k
combing back, 9b+7 becomes 45k+7, so the residue is 7

or you simply guess 7 (by noticing that it is indeed 2 mod 5 and 7 mod 9) and say that this is the residue mod 45 according to CRT (which guarantees the unicity)

[severe ermine]

I dont understand b=5k

like

why?

[cold tendon]

Can anyone help me?

Efficiency of the Euclidean Algorithm. Take any nonzero integers a, b with 1 ≤ b ≤ |a|, and let n be the number of steps needed in computing gcd(a,b) as defined above. Let fjbe the j-th Fibonacci number. Prove that if b ≤ fj, for j ≥ 2, then n ≤ j − 1.

[leaden stream]

since 9b = 5(a-1) you have 9b is a multiple of 5. As 9 is relatively prime to 5, b must be a multiple of 5. So set b=5k

[green sentinel]

having trouble with this

I get that you could write this as k gcd(a, b) j = kb = ag = gcd(a, b) i g

which could simplify to kj = ig by cancelling out gcd(a, b), tho i don't see how that could help, alternatively could divide everything by b and get k = (a/gcd(a, b)) * g/j

which could work if u can prove g/j is a whole number, but struggling to do that

[white lion]

is there any other given your missing?

[green sentinel]

nope

it's 3b here

[white lion]

ok

[white lion]

@green sentinel my rough guess is what would happen is we know that a/gcd(a,b) | a, hence a/gcd(a,b) | kb, but gcd(a/gcd(a,b), b) = 1 therefore a/gcd(a,b) | k

[green sentinel]

is the logic for that that like, kb = (a/gcd(a, b)) * z and if we divide both sides by b, because gcd(a/gcd(a,b), b) = 1 we know we can't directly divide (a/gcd(a, b)) by b since they have no shared factors except 1, so if we want the whole thing to be equal to a whole number the only other option is z/b has to be a whole number?

also wait is gcd(a/gcd(a,b), b) = 1 actually true?

[patent acorn]

no

gcd(8, 4) = 4, gcd(8/4, 4) = 2 != 1

[green sentinel]

yah

nvm then

[green sentinel]

still completely lost lol

[dusty dragon]

Set d = gcd(a, b) and apply Q2 and part (a) together.

||From part (a), we have that gcd(a, b) | a, gcd(a, b) | b which implies that gcd(a, b) | kb, and a | kb. Therefore, a/gcd(a, b) | k(b/gcd(a, b)). But from Q2, a/gcd(a, b) and b/gcd(a, b) are relatively prime so a/gcd(a, b) | k.||

[surreal tangle]

this might be helpful

In short, if b≤fj, the largest possible value of n will be when you take b=fj and a=f(j+1) in which case we will just be finding gcd(fj,f(j+1)) which takes j-1 steps

So n will always be smaller than or equal to j-1

[cold tendon]

Thanks

[cold tendon]

I watched but i dont get how to prove that worst case is when b=fj?

[surreal tangle]

Because the "next best" worst case will happen when b=f(j-1) and a=f(j)

And this case isn't as worse as the case when b=f(j) and a=f(j+1) because it takes j-2 steps to find gcd(f(j), f(j-1))

@cold tendon

[cold tendon]

You mean to use induction to prove it?

[surreal tangle]

No, is it clear from the video that when b≤f(j) then the worst case is when b=f(j) and a=f(j+1)?

[cold tendon]

For me its not clear

[surreal tangle]

Ok, did you see the (13,8) example?

[cold tendon]

Yeah

[surreal tangle]

Did you notice that the quotient was always 1?

[cold tendon]

Yeah

[surreal tangle]

ok, so suppose we wanted the division algorithm to last n steps. My claim is that the smallest two numbers (a,b) that will allow us to achieve an n step division algorithm are (f(n+2), f(n+1)). we know all the quotients should be 1 to increase the number of steps in gcd finding as much as possible, so when we apply the division algorithm :
a=b(1)+r1
b=r1(1)+r2
r1=r2(1)+r3
...
r(n-3)=r(n-2)(1)+1
r(n-2)=1(r(n-2))+0
Now to make it more clear, let's define t(n+1-k)=r(k) with t(0)=0 and t(1)=1 and substitute this everywhere, our equations turn into:
a=b+t(n)
b=t(n)+t(n-1)
t(n-1)=t(n-2)+t(n-2)
...
t(3)=t(2)+t(1)
t(2)=t(1)+t(0)
We find that the t(i)s follow the recurrence relation t(i)=t(i-1)+t(i-2). We know b=r1+r2=t(n)+t(n-1)=t(n+1) and a=t(n+1)+t(n)=t(n+2), also notice that t(n) is the same as f(n), so a=f(n+2) and b=f(n+1) as we desired

[cold tendon]

Thanks i get it

[silent gyro]

Im going through a book on elementary number theory and I just finished a section over primitive roots, and I'm wondering what are the applications of them

[open mist]

Primitive roots in Z/pZ ?

There's lots of advantages to knowing a group is cyclic
That includes algorithms that rely on finding one to then do things with it

[white lion]

I was what n smooth mens in a number theoretic context but what does it mean for an integer to just be smooth?

[tepid gate]

I'm trying to think of how one would prove that for all n>8 either n or n+1 has a prime factor >3

I'm wasting my time trying to go at it by modulo 6 aren't I?

[primal pewter]

yes

also, as a general tip: never think about modulo something that is not a power of a prime

now, regarding the problem: assume the contrary; so the numbers have the form 2^a*3^b... but they are coprime, so one of them is a power of 2, and the other is a power of 3

you'll have two equations to solve: 1) 2^x + 1 = 3^y and 2) 3^x + 1 =2^y

overkill: Catalan (the only consecutive perfect powers are 8 and 9)

but luckily the equations are solvable by hand using some congruences and factorizations

[urban dust]

Generally speaking, they are a useful tool for proving results in number theory.

[errant otter]

so uh I came across a bit of an interesting problem- what is the largest possible size of a subset of {1, 2, 3, ... , n} such that all elements in the subset are coprime?
the set of all primes <= n works, but I'm unsure as to whether this is indeed optimal.

or are there other possible constructions aside from solely prime numbers which attain the same maximum/more than that of the set of primes <= n?

ima code a bruteforce for n = 20

not sure how I'd prove it for set of primes

maybe cuz it's not true and there actl is smth else more optimal, or because I'm dum

[dusty dragon]

1 is always included so the problem reduces to finding the largest subset of {2, ..., n} such that each pair of elements in the subset are coprime

[errant otter]

funny

unless I coded my bruteforce wrong, for n <= 20 it was indeed primes <= n

[errant otter]

mmmmmmmhm/

[dusty dragon]

the set of primes is indeed optimal for the problem; let S be any subset of pairwise coprime integers. Define the function f : S -> P_n that assigns each element s in S with the smallest prime factor of s

show that f is an injection

i.e. |S| <= |P_n|

[errant otter]

Oh.... damn...

that is neat.

Injection because if it were not we'd have contradiction cuz gcd is not 1 (since they share a prime factor)

[dusty dragon]

yea pretty much

[errant otter]

thanks man

[dusty dragon]

nws

this might actually be a cool problem for my algorithms class

because this is a very natural 'greedy' algorithm

[white lion]

Im trying to solve this problem $x^{245} \equiv 1243$ (mod 412) using the discrete logarithm but I keep running into absurdities, first I reduced the equation to $x^{41} \equiv 7$ (mod 412) and then broke it into two more easier equations $x^{41} \equiv 7$ (mod 4) and $x^{41} \equiv 7$ (mod 103). and tried using discrete logs individually to get the anwser but for the first equation there are no solutions and the second one is to hard to compute. am I missing someting?

[sterile pumice]

jayz

[patent acorn]

x^41 = 7 mod 4 definitely does have a solution

for x^41 = 7 mod 103... there's a convenient property of 41 mod 102 that will make this a lot easier to compute

[white lion]

1^2 = 1, 2^2 = 4 =0, 3^2 = 9 = 1

[white lion]

like what exactly? what I meant computation hard was that since we know that 2 is a primitive root mod 103 i did..... Ind(x^41) = Ind(103) (mod phi(n)) this is hard to compute

we would get 41 Ind (x) = Ind(103) (mod phi(n)) but ind(103) is hard to find

[white lion]

wait lol nvm phi(4) is not 3 that was my mistake

[green sentinel]

forgot to respond but thanks for the help btw! I think where I was stuck was actually using that fact regarding relative prime numbers, but ended up discovering it has a trivial proof w bezout's identity

but yah thank u sm

[distant needle]

I believe this is elementary nt but I’ll remove it if not

My question is how did they go from the first to the second thing in 3.1

[dusty dragon]

Let $n = p_1^{\alpha_1} \dots p_k^{\alpha_k}$. If $d \mid n$, then we have that [d = p_1^{\beta_1} \dots p_k^{\beta_k},] where $\beta_i \in [0, \alpha_i]$ for each $i = 1, \dots, k$

[dusty dragon]

(it might help to think about why)

[distant needle]

oh that makes sense

ok thank you

yeah if you think about numbers like sets, d is a subset of n

[umbral ginkgo]

Does anyone know to prove the formula for geometric series a different one from the classic one where you multiply by the last term? (a visual / intuitive one)

[nova vine]

How do I go about proving this statement?

[nova vine]

<@&286206848099549185>

i dont know either to be honest, but i believe we either use the result from the first statement and prove the second, OR prove the second without taking help of the first statement's result

i dont understand from here

[white lion]

how was it?

[gaunt sedge]

What’s my mistake?

[lilac elk]

a good book with theory and exercises for self-study in elementary number theory?

[green sentinel]

dum q but how do i go about solving b here

im assuming i need to find a value c such that x = c mod 18 and x = c mod 37

and that that'd b my answer

but does chinese remainder theorem actually give an algo for solving that?

[shell minnow]

Yes

Look at the proof again

[white lion]

An Elementary introduction to Number Theory by Calvin T.Long

the excercises and exposition are excellent

get the third edition

coding excercises aswell if youre into that

[young tundra]

I was trying to solve this water jug problem, I have a jar of size 5, j5, and another of 3, j3. I want to measure 4. The approach is easy, I just fill j5, pour whole into j3. Empty the j3, and pour the remaining 2L water of the j5 to j3. Then, we have 2L in j3, and 0L in j5. Just fill the j5, and pour 1L out to the j3. Now, we have 4L in J5.

Now, people have mentioned that this can be solved using GCD. I can imagine that there is a big bucket, I can just pour water to the bucket from my jugs or take water out of the bucket. So, it is something like (-2) * 3 + (2) * 5 = 4. Therefore, it is possible to achieve the target capacity. Pouring water twice using the J5, and pouring out twice using J3.

What I am not able to understand is that how we can consider that there is a big bucket and we are pouring water in and out from it since that the bucket can also contain more water than the whole capacity of both of the jars?

[young tundra]

Induction proves that each jug can have a linear combination of a and b in them.

[coral venture]

Niven

[marble tusk]

Are there any statistics about whether primes, when treated as random variables, are independent?

I mean, like, if x is prime, does that say anything about the probability that x+2 is prime?

[west glade]

showing that the probability is >0 implies twin prime conjecture I think. so I doubt anything is known about that

ignoring the question what such a probability should even mean

[weary rune]

my thoughts on how to approach this are to let $a=p^2m$ and $b=p^2n$ for relatively prime $m,n$ then case on whether $p$ doesn't divide $n,$ $p$ but not $p^2$ divides $n,$ or $p^2$ divides $n$

[sterile pumice]

elrichardo1337

[weary rune]

but i'm not sure if that's entirely airtight

owait $p$ being prime is important

[sterile pumice]

elrichardo1337

[weary rune]

bc then i should be able to cast this in terms of prime factorizations?

[surreal tangle]

Yeah you should make two cases one where a=p^{k}m and b=p^{2}n with n,m relatively prime and k≥2 and another one where a=p^{2}m and b=p^{k}n (once again k≥2 and m,n relatively prime) and you'll get that the first case yields gcd(a^2,b)=p^2 and the second case gives the other two possibilities of gcd(a^2,b)=p^3 and gcd(a^2,b)=p^4.

[weary rune]

yea aight

thanks

[nova vine]

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

[sterile pumice]

Godspell

[nova vine]

I found that this summation ends up being n with the help of some examples. Can someone explain to me how?

$\varphi(d)$ is Euler's totient function

[sterile pumice]

Godspell

[nova vine]

<@&286206848099549185>

[still flare]

This is well-known; find a sample proof here.

Tl;dr phi(d) counts things coprime to n/d, hence eventually we get everything in the range 1 to n.

[nova vine]

got it, thankyou!

[weary rune]

does it suffice to:

1. claim that $t$ has a unique inverse mod $n$
2. set $ta_i\equiv ta_j\pmod{n}$ for some $i\ne j$ and then show that it leads to the contradiction $a_i\equiv a_j\pmod{n}?$

[sterile pumice]

elrichardo1337

[primal pewter]

yes

[weary rune]

aight aight

[spare tree]

hi ashmeet

[ivory stratus]

what is 12 multiply by 21

if someone got it right u have a point to solve how?

1st: solve 12 multiply by 21

\2nd: take a photo to show proof

thank you

[weary rune]

wrong channel?

basic arithmetic is not "elementary number theory"

[ivory stratus]

ohh sorry

[weary rune]

but hop over to #prealg-and-algebra if you need help

[ivory stratus]

because im new

[weary rune]

all cool

[orchid spade]

How would we calculate the bounds on this

The big O and big omega

p are prime numbers

Lesser than n

[cunning stump]

I'm trying to prove(idk if this is true) that given any two prime numbers, P1<P2
there are two possibilities:

1. there exists P3, P4 between P1 and P2 s.t (P3 - P1) = (P2 - P4) + 2
2. there exists P3, P4 s.t P3 < P1, P4 > P2, and (P1 - P3) + 2 = (P4 - P2)

[unique cypress]

Use geometric series then notice that what do you get is greater than the harmonic series

And the rest should be obvious (compare to an integral etc)

[orchid spade]

Ohh

So expand (1-1/p) into 1 +(1/p)+(1/p^2) +...?

[patent acorn]

there's probably a trivial counterexample involving 2

[cunning stump]

Sorry I forgot >2

I think I checked about 10,000 primes from 11 onwards

and it was true for all of them

[orchid spade]

Is this what u were saying @unique cypress

[unique cypress]

Express (1-1/p)^(-1) in terms of geometric series

[orchid spade]

And how will it help

[unique cypress]

Just do it

[orchid spade]

We will get a product of several geometric series

[orchid spade]

I've written it on paper infront of me rn

[unique cypress]

yeah which is greater than the harmonic series

[cunning stump]

This can help the visualization.

[orchid spade]

Which harmonic series?

[cunning stump]

given P1, P2, P3/4 exist in one of the variations

[orchid spade]

I'm trying to find a O(f(n))

[surreal tangle]

How did you come across this?

[unique cypress]

not the actual harmonic series but more like the harmonic series up to some constant say k<z

[cunning stump]

I was trying to prove something else and this would help that lol

but I'm not really interested in the something else

[surreal tangle]

I mean it helps to know where the problem comes from since this seems like a tough one to prove

[orchid spade]

I still dont get it, which harmonic series are you talking about

[unique cypress]

$\sum_{k<n} \frac{1}{k}$

[sterile pumice]

Deltoid

[orchid spade]

Ok, why that series in particular?

That series will be a lower bound,

[unique cypress]

Yeah

[orchid spade]

Yea but why

How can we prove it

[surreal tangle]

Also, 3 and 5 is infact a counterexample. Obviously they won't satisfy the first condition since there are no primes b/w 3 and 5. The second condition forces P3=2 so we are trying to find P4 such that (3-2)+2=P4-5 =>P4 = 8 which isn't a prime

[cunning stump]

It messes up when one of the primes is 2

but

it is not a counter example

[orchid spade]

What u r saying is actually the exact question I had been given

How did u arrive at having this series as the lower bound?

[cunning stump]

because I didn't say P3/P4 cannot be equal to P1/P2

[patent acorn]

i think this is equivalent to the goldbach conjecture

[cunning stump]

for example in 3, 5(P1, P2), you can define P3=5, P4=P2=5
then 5-3 = 2 = (5-5) + 2

[patent acorn]

yeah it is
the condition here is equivalent to saying that P3 + P4 = P1 + P2 + 2

in other words, the claim is that for any number that can be written as the sum of two primes, that number plus 2 can also be written as the sum of two primes

so by induction it follows that they all can

[cunning stump]

ah

so it's an unsolved problem

lol

[surreal tangle]

P3<P1 and P1<P2 according to your message

How can P3=5=P2 then

[cunning stump]

sorry just writing on discord makes it messy

<= was my intention....

[surreal tangle]

Ah

[cunning stump]

it's my bad

I just don't notice the symbols on discord properly lol

[surreal tangle]

So I wasn't that far off the truth when I said it seemed tough to prove

[thick panther]

hey, could i get a hint for this please? χ(n) is just legendre written as a character

wait nevermind i got it

[sacred junco]

Let $n$ be a positive integer. If $2^n - 1$ is prime, then $n$ is prime.

[sterile pumice]

Alex Turner

[sacred junco]

This is one of the challenge problems in my abstract algebra text

so far I have fleshed out some concrete examples to get a feel for the statement

also I tried contradiction but I think I am not able to frame the argument properly

suppose n is not prime

then it is a composite number which can be broken down into further product of primes

suppose we index the primes like $x_1, x_2, . . . , x_k$

[sterile pumice]

Alex Turner

[sacred junco]

I don't know what to do from here

[west glade]

lets say n is even

then n=2k and 2^n-1=2^(2k)-1

is there something you can do with that expression?

[sacred junco]

hmm

my instinct is to factor out smth

[west glade]

good instinct

follow it

[sacred junco]

the algebra is a bit messy

I don't remember the binomial expansion

[west glade]

lets write 2^(2k)=(2^k)^2

why binomial expansion?

[sacred junco]

nvm

please continue

[west glade]

lets call 2^k=a

then we have a^2-1

[sacred junco]

okay

[west glade]

a^2-1^2

[sacred junco]

(a+1)(a-1)

[west glade]

yes

and neither of a+1 or a-1 are equal to 1

so then 2^n-1=(a+1)(a-1) is not prime

[sacred junco]

hmm I see

[west glade]

and now you need to find a way to generalize this for n not even. for example n=mk

[sacred junco]

so ig that amounts to factoring out smth

what that is, is smth I am thinking about

ill try the m = 3 and see if there is a pattern

so for the general case it is (a^m - 1) from which we can factor out (a - 1)

right?

[west glade]

yes

[sacred junco]

now we need to do the n being odd case

$2^{2k} . 2 = 2^{2k + 1}$

[sterile pumice]

Alex Turner

[torn escarp]

I like this, what do you get when you divide a^m - 1 by a-1?

[sacred junco]

some positive number

for m = 3, it's $a^2 + a + 1$

[sterile pumice]

Alex Turner

[quaint gate]

try dividing the polynomial x^n-1 by x-1

[sacred junco]

oh right

[west glade]

or you can think of the geometric series

[sacred junco]

so it is $a^{m-1} + a^{m-2} + . . . + a + 1$

[sterile pumice]

Alex Turner

[quaint gate]

what's the remainder after dividing?

[sacred junco]

0?

[quaint gate]

yeah

x-1 divides x^n-1 basically

[sacred junco]

contradicting that it's a prime

[west glade]

unless a-1 or (1+a+...+a(m-1)) equals 1

[sacred junco]

hmm

[west glade]

can that happen?

[sacred junco]

for that to happen for the right term seems less likely (due to so many terms)

for (a - 1) to be 1, a needs to be 2

😵‍💫

I will chew on this...

[west glade]

well a=2^k

when is that equal to 2?

[sacred junco]

k = 1

[west glade]

so if we can write n=mk with both m and k not being able to 1, then we can do the above argument

and show that 2^n-1 is not prime

[sacred junco]

oh I see

[simple thorn]

I know how to show this using division algorithm

But apparently there's a different proof that uses this fact

Not sure how it works

[grand parrot]

for an undergrad number theory course

would I need to actually prove $m|\sum_{j = 1}^k {k \choose j} m^j$ or can I just state it?

[sterile pumice]

nchoosek

[grand parrot]

if I can just state it I'm done with my proof

the original question is

https://i.imgur.com/hEnJorh.png

I guess proving it is trivial

$\sum_{j = 1}^k {k \choose j} m^j = m \sum_{j = 1}^k {k \choose j} m^{j - 1}$ this works I think

[sterile pumice]

nchoosek

[coral venture]

Where are you getting the binomial coefficients from?

[grand parrot]

like my proof itself?

[coral venture]

Yeah

I don't see how those arise when considering n^k-1

[surreal tangle]

He probably substituted m+1=n

[grand parrot]

ye

[surreal tangle]

Then you want to prove that m divides (m+1)^k-1

[coral venture]

Smart

[grand parrot]

https://cdn.discordapp.com/attachments/1197779247058669649/1208714625785536612/IMG_1813.jpg?ex=65e44a37&is=65d1d537&hm=9c7f738d708e9ef7d5596f18db5dd1c6e2d2ebdd0d40882213430863a7961221&

neat little proof

unless its wrong

LOL

ignore eraser shavings

[surreal tangle]

And yes no you can use the binomial theorem, but there's an easier way, with proving the formula with a geometric series sum

[surreal tangle]

Its correct

[grand parrot]

easier for people who know what that is xdd

[coral venture]

it's just $a^n-b^n=(a-b)(a^{n-1}+a^{n-2}b+\dots+b^{n-1})$

[sterile pumice]

Daniel

[coral venture]

this is extremely useful in many situations

[grand parrot]

I knew that form, I actually still don't see how it works here

[surreal tangle]

You should've used k instead of n

[quaint gate]

a=n, b = 1, n = k

[grand parrot]

ohhh

right i was still stuck on my m + 1 thing

[grand parrot]

guys what would you rate the difficulty of this problem for an undergrad course

https://i.imgur.com/QoBNACA.png

its starred so i was expecting to not even manage it but i got it in like 10 mins I think

is it just not that hard

or am i on fyreeee

i mean its in the 2nd chapter of the book so yk how hard can it be but the other problems starred next to it look much harder for some reason

ohh wait

I have not yet 😄 LOL

oh wait maybe

actually lemme put it in here maybe you guys tell me if this is sufficient

I have:

For any $n > 2$, $2^n -1 = \sum_{k = 3}^{n - 1} (2^k) + 7$ and $2^n + 1 = \sum_{k = 3}^{n - 1} (2^k) + 9$.

$\sum_{k = 3}^{n - 1} (2^k)$ clearly only contains factors of 2, but 7 is a prime, and 7 does not divide 9. Therefore for any $a, b > 2$, $2^a -1$ does not divide $2^b + 1$.

tbh I'm not sure about this

well I'm pretty sure I'm right but the wording is it convincing enough to be a proof idk

[sterile pumice]

nchoosek

[primal pewter]

I don't see why the conclusion should follow from that argument.

[grand parrot]

yeah reading it again

im kinda not even sure i have the right idea now LOL

got too hyped up

[primal pewter]

if you want a hint: ||use Euclidean division for a and b|||

[grand parrot]

naw not yet

oh, trichotomy bitch! I think I got it

its something like

if a = b then 7 doesn't divide 9 we're done

[primal pewter]

that's still not valid

if you have something like x + y | x + z, it does not mean that y | z

[grand parrot]

if a > b then $\sum_{k = 3}^{a - 1} (2^k) + 9 = \sum_{k = 3}^{b} (2^k) + \sum_{k = b}^{a - 1} (2^k) + 9$

[sterile pumice]

nchoosek

[grand parrot]

oh wait

sure up to b it cancels out I still don't know if k = b through a -1 + 9 is divisible by 7

[grand parrot]

i dont see how thats what i was saying

[primal pewter]

because you are trying to get a contradiction from the fact that 7 does not divide 9

but this is not going to help

[surreal tangle]

By the way, \sum_{k=3}^{b}2^{k} does not only contain factors of 2.

[grand parrot]

ye bad wording

[surreal tangle]

Take b=4 for example

[grand parrot]

prime factors of 2 is correct right?

[surreal tangle]

Still no, you can't really say anything about what numbers divide \sum_{k=3}^{b} 2^k other than the fact that 2^3 divides it

[grand parrot]

fak ok this is actually hard then

so I'm not even on the right track? like this is a bad path for sure?

[surreal tangle]

In this example, 3 also divides 2^3+2^4=24=8x3

[surreal tangle]

You should see the hint that filip has written down for you

[grand parrot]

i mean i will if i give up

but like

i wanna solve it

[surreal tangle]

Right, so this doesn't seem to work

What other ideas do you have?

[grand parrot]

this was my first so lemme think

one of my biggest problems is not being able to come up with counterexamples to my own dumb ideas

like figuring out 2^3+2^4 = 24 = 8 x3 would have saved me some time lmao

[surreal tangle]

Its always a good idea to check small cases of any general claims you make in a proof

b=4 was the smallest possible case

[grand parrot]

ok its fuckin 5am

im tired

and stuck imma do this tmrw

this where I got but I cant find a contradiction not even sure if this is right path anymore either

Since $2^a, 2^b$ are even numbers, they are of form $2^a = 2m, 2^b = 2n$ for some $m, n > 0$.

So $2^a + 1 = 2m + 1$ and $2^b - 1 = 2n - 1$. $2n - 1 \vert 2m + 1 \implies 2m + 1 = (2n -1)z$ for some odd $z > 0 \in \mathbb{Z}$.

If $m = n$, then $2m + 1 = (2m - 1)z$ and $\frac{2m + 1}{2m - 1} = z$, but we have a contradiction since z is a positive integer and $\frac{2m + 1}{2m - 1}$ is rational.

If $m > n$, then $m = n + r$ for some $r > 0$ and $2m + 1 = 2(n + r) + 1$. So we have $2n + 2r +1 = 2n - 1 +2r + 2 = (2n -1)z$ and $1 + 2(r+1) = (2n -1)z$

turns out the problem was actually pretty hard for me lmao

[sterile pumice]

nchoosek

[grand parrot]

bois i havent gone back to this yet but was this even right track?

or is representing $2^a$ as $2m$ not helpful for what we're trying to prove?

[sterile pumice]

nchoosek

[primal pewter]

not helpful

[grand parrot]

thanks

I guess its time to read the chapter in the book lol

[timid sedge]

Which book are you using?

[runic token]

you can probably use infinite descent here

like

go for contradiction

set 2^a term over 2^b term and set equal to k_0 or something

and just use parity to show k_n is always decreasing but always positive

yeah like re-sub the next index for an odd term

etc

[primal pewter]

setting a=bk+r does the job

[runic token]

oh right

🤕

[grand parrot]

intro to number theory by Niven

[sacred junco]

Zukerman?

[rustic tulip]

$\frac{1}{3} + \frac{1}{6}$

[sterile pumice]

.doc

[rustic tulip]

When adding, finding the lcm of the denominators doesn’t give me to the least reduced form in one step

I feel like this happen whenever sum of numerator becomes multiple of the lcm

is there something more to it?

[surreal tangle]

Not just multiple, even if the sum of numerator becomes a divisor of LCM, you won't get least reduced form in 1 step

I don't think there's anything more to it

[rustic tulip]

right, the gcd must be 1

[surreal tangle]

Yeah

[rustic tulip]

I read online that using lcm when to find addition of unlike fractions gives it in reduced form

[surreal tangle]

Yeah that's untrue, this is a counter example

[rustic tulip]

idk, can there be a one step procedure?

[surreal tangle]

Any procedure would require you to find the LCM in one of the steps, so there can't be a one step procedure

Again it depends on what operations take how many steps. For example finding the LCM itself has some steps in it, so do you count finding the LCM as 1 step or many steps?

[rustic tulip]

I’m not necessarily counting step as in counting for an algorithm

if gcd of num and denom is not equals to 1

Then we require to cancel again and that counts as step

[surreal tangle]

Then the question becomes vague, but however you define "step", 1 step isn't possible

[rustic tulip]

I get the idea

my question is more of a pedagogical one

[ember oxide]

How would I approach this question?

[ancient crow]

if you want to use their hint you should first prove for a=b (mod n) f(a)=f(b) (mod n)

then, see how you can apply that - you might need another fact (about polynomials) to complete the argument

[primal pewter]

also, the polynomial in the problem should be assumed to be non-constant

[viral mist]

Has anyone seen this identity before? If so, is it known under some other name because I can't find anything about it online under the given name of "Newton's Identity".

[still flare]

I've seen it before but never heard a name for it. Not everything has a name. Do you have a question about it beyond that?

[viral mist]

I was also trying to get some intuition for why it's true.

It's not obvious to me why it works.

[still flare]

Think about what the left and right side are counting. The left side counts pairs of subets of {1, ..., n}, one of size r and one of size k, the first being contained in the second. That's the first thing I see it counting.

The right side looks like we first pick a subset of size r, then pick the 'rest' of a set of size k.

So in the first instance we're counting $(A, B)$ where $A \subseteq B$ and $|A| = r$ and $|B| = k$, and we can transform this into what the second thing is counting by sending it to $(A, B \setminus A)$.

[sterile pumice]

Boytjie

[still flare]

Tl;dr: when we choose a set of size r and a larger set of size k, this is equivalent to choosing k-r elements outside of the first set r.

[viral mist]

Wow this is really helpful, thank you! I'm still trying to wrap my head around your explanation. So wouldn't the left side count pairs of subsets of two different sets {1, ..., n} and {1, ..., k}?

[still flare]

Sure but that's an unhelpful interpretation

It's way more helpful to see it as first selecting a subset B of {1, ..., n} of size k, then selecting a subset A of B, this time of size r.

The pairs (A, B) are then the count.

[viral mist]

Ooh I get it now. That's a really smart interpretation. Thank you!

[vapid karma]

hey guys, what do you think would be the best approach for this problem

i was thinking induction but i think it’ll get messy

[sacred junco]

Yall if you don’t mind me asking I noticed that x/ln(x) is seemingly always lower than pi(x). I know that according to pnt x/ln(x) approaches pi(x) as x approaches infinity but is x/ln(x) for all numbers higher that 0 a lower bound to pi(x)?

[ember oxide]

Which fact would that be?

[ancient crow]

once you've proven the lemma, you find that f(x)=p for infinitely many x and some fixed prime p

then, f(x)-p has infinitely many roots

what does this tell you about the degree of f?

(assuming f is non constant)

[ember oxide]

Wouldn't it be 0?

[ancient crow]

yes but f's non constant so we get a contradiction

[ember oxide]

Ah right, got it.

[ancient crow]

there is a very nice combinatorial interpretation for both problems

for the first one consider || the number of ways to make n^2 teams of size n from a group of n^3 people ||
for the second one consider ||the number of ways to make n teams of size n^2 from a group of n^3 people ||

the intuition being n * (n^2) = n^3 and the general structure of the quotient

if you'd like a purely number theoretical approach, I'd consider using || legendre's formula for the p-adic valuation of n! ||

(||legendre's formula ||is relatively straightforward to prove if you haven't seen this before)

[ember oxide]

I was trying to solve this with the Legendre's formula but got stuck with the (n+2)! term cuz it produces a +1 when doing $\floor{\frac{(n+2)}{2}}$

[sterile pumice]

Acatalepsy

[ancient crow]

I'm not sure what the notation is

what does L3n mean

[ember oxide]

That's a factorial, from an older book

[ancient crow]

oh I see thanks

[ancient crow]

does this help you?

[ember oxide]

Where did you get the 3?

[ancient crow]

n!(n+1)!(n+2)!=(n!)^3(n+1)^2(n+2)

[ember oxide]

Makes sense. How would I apply it to prove the fact about power of 2 though. Unless I can rewrite v2((n+n+n)!) in that format

[narrow night]

1+1 +2

[surreal tangle]

Maybe I'm missing something obvious but I don't see why this has to be true

[runic token]

what that's basically saying is wlog let q\not|a

assuming (x,y) is gcd(x,y)

[runic token]

this is for $\neg (q|a\land q|b) = \neg q|a \lor \neg q|b$

[sterile pumice]

valley

[runic token]

or something

[surreal tangle]

q can not divide a and still have gcd not equal to 1 though

Oh fuck im so sorry q is a prime