elementary-number-theory

[limber charm]

I thought the term was relatively prime but coprime is much easier to say

[lilac elk]

was collatz conjecture solved?

why is this channel named like that?

wait. I got it

april's fools

what was the original name of this channel? number theory I think

[lean gust]

Ya, and no collatz not solved

[kindred basin]

No it's solved

I proved it

For all {x in R: x > 0}

[lilac elk]

Some claim to have solved but internet is too short to write the proof here 😅

[teal zealot]

https://math.hawaii.edu/wordpress/new-course-with-course-number/

[verbal cedar]

anyone know if there's a formula for the sqrt of -1 mod p=8k+5?

[leaden swan]

Find a generator of (Z/p)^{\cross}

If this is g, g^{{p-1}/4} should be what you want

Apparently x= ((p-1)/2)! works

[verbal cedar]

interesting. i had (p-1)/4=2k+1 but i hadn't seen a relationship between which elements got mapped to 1 or -1. makes sense that if it equals 1 then it can't be a generator.

[leaden swan]

This works because you can square and rewrite terms so that this becomes (p-1)!

And that is -1 by Wilson

Take p=5 for example, x would be 1*2

x^2 would be 1*2*1*2

=1*2*4*3 mod 5
= 4! mod 5

[verbal cedar]

awesome tysm! 🙂

[sterile pumice]

LeftySam

[sleek spire]

commutativity and associativity are obvious

for closure you just have to check that all properties of a dirichlet character still hold

do you know what commutativity and associativity mean

yeah

and the complex numbers are a field

so they are commutative and associative

[sterile pumice]

LeftySam

[sleek spire]

,, (\chi \circ \chi') \circ \chi'' = \chi \circ (\chi' \circ \chi'')

[sterile pumice]

LeftySam

[sleek spire]

yes

you're overthinking this

[sterile pumice]

LeftySam

[sleek spire]

yes

[sterile pumice]

LeftySam

[runic gull]

hey I have an interesting exercice: Let $a$ and $b$ be two strictly positive natural number such that $a^n-1|b^n-1$ for all $n$ in the set of strictly positive natural integers; show that there exists $k$ a strictly positive integer such that $b=a^k$

[sterile pumice]

weeb_destroyer

[rugged moth]

,texsp Let $b=a^kpm$ where $p(\neq 1)$ is prime. Then $a^n-1 | b^n -1 , \forall n$ means $a^n-1$ and $b^n$ are relatively prime for all $n$. But taking $n=\varphi(n)=p-1$ we see that $p | a^n-1$ and clearly $p|b^n$ contradicting assumption.

[frank vine]

No the reasoning is false

[rugged moth]

where am I mistaken

[frank vine]

There are two cases p|a and p|a^(p-1)-1

[rugged moth]

p doesn't divide a by assumption

[frank vine]

There are two cases in fermats theorem

[frank vine]

So the assumption is false this is what we can deduce

[rugged moth]

[frank vine]

We deduce that whatever prime may be such that p|b you have ultimately p|a

[rugged moth]

don't see where your are getting at

ok the solution is incomplete, it just says there's no prime diving b but not divining a, doesn't say it's aⁿ

[frank vine]

Listen this is the only thing you can deduce because we deduce that b cannot be written as a^k.pm with p not dividing a so p must be dividing a

@rugged moth this is the only result that the contradiction leads to

Well I think the exercice seems to be challenging I think its from “polythechnic and ENS” entrance oral exams, the best schools in france known for their selectiveness, one simple substitution wouldn’t solve the problem

[unkempt void]

Inch resting

[pale raven]

Ok I'm probably doing this all wrong because I've had no formal number theory training but I'm thinking difference of squares. If b = a^k, then a^n - 1 | a^kn - 1. If k is a power of 2, you can factor a^kn - 1 using difference of squares, a^kn - 1 = (a^(k/2)n - 1) * (a^(k/2)n + 1) and repeat until one of the terms is (a^n - 1), which satisfies divisibility.

[unkempt void]

Oh wow that is an interesting problem

Seems you need some analysis to do it lol

[frank vine]

Yeah probably

[unkempt void]

not sure how you would do that in an oral exam lol

but ye it's on stack exchange lol noice

okay well you nerd sniped me for a while :)

[frank vine]

You only proved that b=a^k satisfies the condition but not that this is he only one that canbe satisfying it

[pale raven]

so I need to show that b must be a^k?

[frank vine]

Yeah

[brazen night]

Does the following make sense:
Given exponents $e_1,e_2$ and the congruence $a=_nb^{e_1}$ where $n$ and $b$ are coprime and that $gcd(e_1,\phi(n))=gcd(e_2,\phi(n))=1$, we can know that $gcd(a,n)=1$, so $a^{-1}$ exists in $Z_n$. Then in $Z_n$:
$$1=aa^{-1}=a^{-1}b^{e_1}=a^-{e_1x+e_2y}b^{e_1}=b^{-e_1(e_1x+e_2y)+e_1}=b^{e_1(-e_1x+e_2y+1)=b^{e_12e_2y}$$
Then
$$1^{e_2^{-1}=1=b^{2e_1y}=a^{2y};\text{mod n}$$

So we can say that $2y=k\phi(n)$ for some $k\in\mathbb{Z}$?

[sterile pumice]

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

[pearl vault]

hi
i desperately need some help
i have a supervision in 15 minutes and i cant solve one of the questions from my problem sheet
can one of you please help me out?

[normal heart]

Fix your latex first?

[sterile pumice]

LeftySam

LeftySam

[wanton lance]

I've found out that m=2 but from here, I'm not sure what else I am supposed to be doing

[torn escarp]

seems to me that's all they want you to do, and show your work

probably they wanna see you say something about how you simplified it using the chinese remainder theorem, euler's theorem or fermat's little theorem, that kind of thing

[wanton lance]

oh hm

oki

[sacred junco]

A store sells a chair at a lower price than usual, which is $99 . If an amount of $8137 of these chairs is sold, and the discount on the price is an integer, how many chairs were sold?

How can this problem be solved using the division algorithm theorem and operations defined only in Z?

[fossil fog]

Are there any mathematical systems (which are used and not just made up as an example) where distributivity is a one-way thing?

I feel like it would be possible, since having something factored out of a group of values could represent something that decays partially in information when distributed out, leading to a lack of symmetry.

Almost like subset behavior but with information/descriptions

[rugged moth]

absolute jumble of words

[fossil fog]

Okay what I’m saying is imagine $a$ as a descriptor where when factored out means a category like tree, but when distributed means something more specific like apple tree (i can’t think of a less stupid example), so $a(x + y)$ has more information than $ax + ay$.

[sterile pumice]

JJCUBER

[fossil fog]

I’m forcing the example of such an environment where this would be the case, but I feel like there would be some real numerical systems that involve a quirk like this.

[fossil fog]

Wait I think I swapped it; the factored out item would likely be more descriptive, since I’m saying that distributing leads to decay of information.

Though I guess distribution could also be one way in the opposite direction

[unkempt smelt]

Hi, I'm stuck on this question

Let m be an integer, let X_m = {p = n^2 + m^2 | n is a natural number} be the set of primes of the form n^2 + m^2. Prove that the Dirichlet density of X_m is 0 for each fixed m.

I know that usually due to Fermat we have that p = x^2 + y^2 iff p = 1 (mod 4), but that seems different to here

[dawn epoch]

Can somebody help me with this basic question? Is it always true that if i have a rational number p=m/n where both m and n are even, then p can be further simplified to a fraction where the numerator and denominator are not both even?

Or the idea of talking about rational numbers is that they already have to be simplified?

[torn escarp]

yeah you can always simplify a rational number p=m/n so that m and n have no prime factors in common (2 in particular to your question)

it'll still be the same rational number, so for instance 10/6 and 5/3 are the same, it's just 10/6 is not the simplest representation of it

hopefully that answers your second question, but to be clear, it doesn't have to be simplified completely before you call it the rational number

[torn escarp]

I think the biggest issue is the fact that the = sign is symmetrical, so a(b+c)=ab+ac is really read exactly the same as ab+ac=a(b+c) and so distributing and factoring are two sides of the same coin

however it's very possible to have number systems where x+y could be factored two or more ways, x+y=w(b+c)=z(b+c) so even though b+c part is the same, w is not equal to z

not sure if that aligns with what you're interested in or not

[livid birch]

i know that sigma(n), the function that is the sum of all positive divisors of n, is multiplicative

i have to show that $\sigma(p^a)$ is odd if and only if $a$ is even.

[sterile pumice]

not sebbb not stμ₂dying

[livid birch]

for the forward direction, can we say sigma(p^a) = sigma(p)^a as a result of multiplicativity

[leaden swan]

That sounds very wrong
\sigma(5)=6 while \sigma(5^2)=31

[livid birch]

oop

[leaden swan]

multiplicativity splits like that only for relatively prime numbers

[livid birch]

ohhhh right right i forgot about that condition

nvm ignore mee

[leaden swan]

You will probably just do induction

Well not induction,just counting mod 2 should work

[fossil fog]

I guess imagine that it’s an environment where => is typically used (loss/generalization of information is often necessary in this system to get anything meaningful maybe?).

[fossil fog]

It seems like it does somewhat fall into the category I was interested in; would you be able to give some examples of this phenomenon by chance? One off the top of my head is the concept of eigenvalues, though I doubt that’s what you were referring to.

[torn escarp]

I suppose you could do induction, but we could just look explicitly at the sum and reduce mod 2, sigma(p^a) is a sum of a+1 odd numbers after all.

[leaden swan]

.

Yea that would be (a+1) mod 2

[torn escarp]

gotcha, missed that

[torn escarp]

sure, any ring with zero divisors, cause if you write b+c=d then you have wd=zd and so (w-z)d=0 and neither w-z or d are 0.

so that could be a ring of matrices, although this is more like #groups-rings-fields or something, not really number theory stuff

at least for this second part, the first part of having an asymmerical equals sign or whatever will probably not be very well received there, but that's my guess lol

[proven temple]

I don't know if this is the right place to post this question, but in my thermodynamics and statistical mechanics class we had a geometric series in a proof which reminded me of the beautiful proof of the sum of a geometric series G where you take G-rG and cancel out all the terms in the middle. For infinite geometric series I could use the finite geometric series formula and say r^infinity=0 for r<1 but i could also do G-rG again. G=A+Ar+Ar^2+Ar^3+... and rG=Ar+Ar^2+Ar^3+... and so G-rG=A and rearranging we get G=A/(1-r). However, this proof seems to be valid even for r>1, although it falls apart for r=1. This would seem to imply that divergent series would equal some finite number which doesnt make sense. For instance if A=1 and r=2 i get G=1/(1-2) or G=-1 which seems to imply 1+2+4+8+16+...=-1???? If I write out the sums and subtract them like in the proof for the formula i get G=1+2+4+8+16+... and 2G=2+4+8+16+... and so G-2G=1 and G=-1 which to me almost looks convincing but it doesn't make sense for a divergent series to equal some finite number. I haven't redefined what equals means so it isnt like some semantic thing either so its straight up saying a divergent series equals some finite number which doesnt make sense. What mistake have I made for this to happen?

[normal heart]

You cant in general switch the order of summation in a series that's not absolutely convergent

#calculus

[proven temple]

what does order of summation mean here?

[normal heart]

Means when you subtract the two series you switched the order of the sum to cancel out the summands

[proven temple]

to be clear do you mean to evaluate G-Gr for series that are not absolutely convergent i must evaluate it as (A-Ar)+(Ar-Ar^2)+(Ar^2-Ar^3)+...=A(1-r)(1+r+r^2+r^3+...) which actually diverges and not as (A-0)+(Ar^2-Ar^2)+(Ar^3-Ar^3)+... ? Also if it doesn't take too long, how do you prove that changing order of summation for series that are not absolutely convergent is not legit? Also does this mean that if I have a sum of a series that is not absolutely convergent and switch the order of the summation of some or all of the terms, the sum of that series is no longer the same thing as the sum of the original series? Would adding zeroes in the geometric series totally change what the sum means? Would the sum of the geometric series G=0+1+2+4+8+16+... be totally different from the sum of the geometric series G=1+2+4+8+16+... ? If i swap two terms would that totally change the sum of the geometric series aswell? Is it legitimate to say that (1+2+4+8+16+...)-(0+2+4+8+16+...)=1 which means one divergent geometric series minus another different divergent geometric series equals 1?

[torn escarp]

there's more than one way to handle this, there's the idea of analytic continuation, but since you asked it in number theory, the way to do it is to instead think of it as modulo powers of some power.

so specifically if you look at 1+2+4+... mod 2^n we can see that all the infinitely many higher powers are 0 mod 2^n, and what you're left with is:

$$1+2+2^2+...+2^{n-1} = \frac{2^n-1}{2-1} = 2^n-1 = -1 \mod 2^n$$

[sterile pumice]

Merosity

[torn escarp]

so this sorta infinite series is actually valid in these kinds of scenarios, and just releasing the restriction of forcing yourself to look at a finite approximation gets you the 2-adic numbers in this case

whereas mod 2^n arithmetic is a ring, the 2-adics is a field, a kind of alternate reality that contains the rational numbers but is distinct from the real numbers

[proven temple]

is it reasonable to argue that mod infinity arithmatic is the same as the rational number line? if so what stops you from making an argument that as n approaches infinity you get this sum equaling minus one, with the sum existing in the rational number line at n=infinity and not some finite ring, so it looks like a divergent series equals -1?

[unkempt void]

Wdym by mod infinity arithmetic lol

[livid birch]

what's the point of something like the mobius function

i know that's vague, but how useful is its multiplicativity

(im assuming that's why it's useful but idk how that extends to anything beyond being a good example)

[jade isle]

hey guys

any number theory formulas that can count for numbered lists

The perfect squares from $1$ through $2500,$ inclusive, are printed in a sequence of digits $1491625...2500.$ How many digits are in the sequence?

[sterile pumice]

darkwarriormentality

[jade isle]

i could just count this

but thats a pain

is there a quciker method

[sleek spire]

I'm not sure if this is what you meant by counting, but 3 perfect squares have 1 digit, 6 have 2 digits, 22 have 3 digits, and the rest have 4 digits

3 + 6 * 2 + 22 * 2 + (50 - 3 - 6 - 22) * 4 = 135

[jade isle]

How did u derive that

[sleek spire]

counting lol

4^2 = 16

10^2 = 100

[jade isle]

See counting is a pain

[sleek spire]

32^2 = 1024

qed

[jade isle]

@sleek spire what bout n digits

[verbal cedar]

question is
"find (5/17) using
a) Euler's criterion
c) a primitive root (part a will be helpful)"
so 5^8=-1 mod 17. thus the order of 5 does not divide 8, but the order divides 16 by Euler's/Fermat's theorem. so must the order of 5 be 16 making it a primitive root? is that right?
wouldn't that imply that any quadratic non residue is a primitive root? i feel like I'm seriously missing something obvious

or making a dumb mistake. probably that

[wooden glen]

Is "(5/17)" meant to be a Legendre symbol?

[wooden glen]

That sounds right. The multiplicative group modulo 17 is cyclic of order 16 = 2^4, so it contains only generators (i.e. primitive roots) and double-somethings (i.e. quadratic residues).

[leaden swan]

What if you have 2^k =1 for some k < (p-1)/2

[wooden glen]

Then 2 is not a generator, and must therefore be a quadratic residue.

[leaden swan]

There are (p-1)/2 quadratic non residues, but you only have phi(p-1) generators(Because (Z/pZ)^{\cross} is cyclic)

So there are definitely some quadratic non residues that are not generators

[wooden glen]

No. (17-1)/2 = 8 and phi(17-1) = 8, and there are 8+8 = 16 nonzero residues.

[leaden swan]

Ok here it works

But I don't think it works in general

[wooden glen]

It works here because 17 is a Fermat prime.

[leaden swan]

Ok agreed

[leaden swan]

Well this works iff (p-1)/2=phi(p-1).(quadratic non residue =>generator). So only for fermat primes

[verbal cedar]

so where would my logic break down for a non Fermat prime?

[wooden glen]

When p-1 is not a power of 2, its totient will be less than half of p-1.

(And you don't get more quadratic residues to compensate for that).

[verbal cedar]

so if a^k≠1 mod p that doesn't necessarily imply that the order of a mod p does not divide k?

i should probably think about this after i get out of class lol

[leaden swan]

That is true yes

[wooden glen]

The general setting (for an odd prime 2k+1) is that you know the multiplicative group is cyclic of order 2k -- that is, it is isomorphic to Z/2kZ. You don't know exactly how that isomoprhism works, but you can find out whether an element maps to an odd or even number, by raising to the kth power. That produces something that maps to either 0 (if your original element was even) or k (if it was odd), and you know that the element of the multiplicative group that maps to 0 is 1.

[verbal cedar]

true that the implication is false, or the implication is true?

order of a mod p divides k implies a^k=1 mod p
so that would be the contrapositive?

[leaden swan]

Order of a will always divide such k

[verbal cedar]

oh i think i'm starting to see now. (8/19)=-1, and the order of 8 must divide 18, so it can be {2,3,6,9,18} (it is actually 6). by eulers criterion 8^9=-1 mod 19, so the order can't divide 9. that only rules out 3 and 9. so the order can still be 2 or 6, and not be a primitive root (which it isn't).

meanwhile, (5/17)=-1, and the possible orders of 5 divide 16 means {2,4,8,16}. but 5^8=-1 mod 17 so the order can't divide 8, which rules out everything except 16. and the key reason it works here is because all the divisors of p-1 (besides p-1 itself) also divide (p-1)/2. that being because p-1=2^4.

sorry i know thinking about it in terms of abstract algebra is probably better, but i wanted to see it from a number theory perspective lol

[leaden swan]

Yeah that works

But that just tells you there is a possibility that quadratic non residue need not be a generator for non fermat prime case

It doesn't show that there WILL be quadratic non residue non generators

[verbal cedar]

yeah exactly

[sacred junco]

If c = 3n + 1 or c = 3n - 1 for any n in Z, then it is not possible to write c as a linear combination of 45 and 1251
How can I prove this proposition? Can I say that because the hypothesis applies for any n in Z, I can use n = 0 and notice that 1 or -1 cannot be written as a linear combination of 45 and 1251? (im only working with integers)

[loud moon]

what property does a linear combination of 45 and 1251 have?

[livid birch]

a little bit silly but im stuck here atm

[leaden swan]

Didn't you like ask this before

[livid birch]

oop

i mightve

oh i did and you suggested induction my b

[leaden swan]

.

That sum should be (a+1) mod 2

Which is 1 iff a is 0 mod 2

[livid birch]

i got it ty

[verbal cedar]

take mod 2 of both sides

[charred mountain]

Please check out my new free open source software for complex analysis of infinite products and infinite series, Ive been working on these proofs for the past 3.5 years and have developed this fractal software for my paper on the Riemann hypothesis and Special Infinite products. Please let me know if you are able to apply my work to anything useful. I believe this mathematics will change the world. You can read my paper by downloading it from the repository, it is the pdf file called Divisor_waves_and_their_relationship_to_the_riemann_hypothesis.pdf

https://github.com/Leoleojames1/Special-Functions

The final conjecture of the paper proposes new equations for quantum mechanics which may show new results for wave functions

I will say there are components of the paper such the the identity between the Euler mascheroni and pi which are incorrect however I am currently trying to resolve that. I would suggest reading the section about the function b(z) and realize that the further you go into the paper the more recent and complex the proofs become so there is more room for error.

[livid birch]

related to what i asked before but

im a little stuck at the end there

im assuming i need to show that \alpha is 1 right?

[charred mountain]

Use this:

[charred mountain]

😛

[leaden swan]

It doesn't matter what \alpha is

\sigma(2^\alpha) will always be odd

The question is really about "show v_p(n) should be even except for p=2 and v_2(n) can be anything"

v_p(n) is greatest power of p dividing n

[livid birch]

i got that one thank you drak

working on this now but im not sure it's right

[livid birch]

nvm im p sur eit's right

[livid birch]

https://math.stackexchange.com/questions/3192900/prove-f-mu-f

im having trouble understanding the answer here

how do we get that second equality?

also i doubt it but is this #advanced-number-theory

[leaden swan]

$\sum_{d | k} \mu(d)$ will be 0 if $k > 1$

[sterile pumice]

DraK

[livid birch]

how so

ohhhh wait wait

[leaden swan]

Well if k=$\prod {p_i}^{\alpha_i}$ , then
$\sum_{d | k} \mu(d) =\prod ( \sum_{j=0}^{\alpha_{i}} (\mu(p_i^j))$

[sterile pumice]

DraK

[leaden swan]

Think of the sum of divisors formula

This should work out the same way because multiplicativity

[livid birch]

you mean sigma(n)?

[leaden swan]

Yes

[livid birch]

i was gonna say that since we're taking k,n to be coprime mu will only count certain things but that's incoherent lol

[leaden swan]

Which book do you get these problems from

[livid birch]

prof gave it to us

he takes some problems out of apostol but idk if this one is in there

oh ig this one is from there my b

[wooden glen]

Please don't use this server to post announcements of you own work. The channels are intended for discussion and would become unusable for that purpose if everyone who makes something post several long ads for it. There are better dissemination channels for actual new work than Discord servers.

[charred mountain]

got any suggestions for better places to post? ive been looking

the only other place that really gets a lot of attention is reddit

[wooden glen]

No, but that doesn't change the fact that they are out of place here.

[charred mountain]

i understood that the first time bro

you told me to post elsewhere i asked where

[livid birch]

is this enough

[normal heart]

it follows immediately from what

[livid birch]

i have that as a thm in our textbook

[normal heart]

well then ok

[livid birch]

hold up

[normal heart]

cuz usually in an elementary proof like this you should quote what you're deducing from

[livid birch]

[normal heart]

yeah, then it's ok

[livid birch]

is this right?

[unkempt void]

Slight typo in the second maths bit but otherwise seems fine ye

Only thing is r and s can both be 1

[livid birch]

thank u potat

[livid birch]

is this asking for induction on m or n??

im guessing m

[livid birch]

https://tenor.com/view/levar-burton-reading-rainbow-google-that-shit-google-gif-15062945

fuck it

[leaden swan]

Induction on m

[livid birch]

im pretty sure it's still true

[leaden swan]

This feels like it has something to do with symmetric polynomial identities

[livid birch]

this is from yesterday but im still not quite sure i follow

i see why the sum of mu(d) for k > 1 is 0

so are we just adding on 0's? in the third equality?

[leaden swan]

Apparently to get to this form

Basically manipulate symbols till you get to the dirichlet form

[regal cloud]

can someone give me some examples of non-Diophantine sets over the natural numbers?

[unkempt void]

#advanced-number-theory

[past light]

Hey, do anyone of you guys know a intuitive proof of the Bezout's Theorem? I'm kind of struggling understanding one proof.

[verbal cedar]

that an integer linear combination that gives 1 means they're coprime? it'd be helpful if you could explain where you're having trouble understanding

[subtle garnet]

Hey I was wondering if someone could point me in the correct direction here. Atatched below is a question I am trying to solve. I have already started the problem but, I'm currently stuck

I observed that every Primitive Pythagorean Triple (a,b,c) could be expressed as:

a = st
b = (s^2 - t^2)/2
c = (s^2 + t^2)/2

Where s > t, both are positive integers and gcd(s,t) = 1

The question asked about ordinary Pythagorean Triples so I changed it:

z = gcd(a,b,c)

a = z(st)
b = z((s^2 - t^2)/2)
c = z((s^2 + t^2)/2)

I then immediately observed that if k = a = z(st), there can only be finitely many ways to factor k into valid combinations of z,s and t, therefore there can only be finite Pythagorean triples in this case. However, I'm still stuck on the case where k = b or k = c. If someone could give me some hints or even better point me towards some helpful resources, that would be helpful 😊

[torn escarp]

I think you can prove the case for c by thinking of the geometry of the situation

[subtle garnet]

That makes sense, since with a fixed hypotenuse (c), the triangle's legs (a and b) must be shorter than the hypotenuse. Therefore, when a and b are integers, that must mean there can only be a finite number for the two, since they have an upper bound

Thank you very much!

Now for b. I think I can simply state that the same argument for a also holds for b, as it is just another leg of the triangle. Is that true? Or would I still need to prove something else for b?

[livid birch]

$$\text{ord}_n(b^i) = \frac{d}{\text{gcd}(i,d)}.$$

[sterile pumice]

not sebbb not stμ₂dying

[livid birch]

can i get a nudge on proving this pls

d = ord_n(b)

i is just any integer

im probably forgetting some fact about d*i / (i,d)

[normal heart]

$\text{ord}_n(b^i) \mid \frac{d}{(i,d)}$: Consider $id=\text{lcm} \times \gcd$.

[sterile pumice]

cflau_

[normal heart]

$d \mid (i,d) \text{ord}_n(b^i)$: Consider Bezout

[sterile pumice]

cflau_

[livid birch]

remind me what you mean by bezout?

[normal heart]

there exist a,b integers such that ax+by=gcd(x,y)

[livid birch]

hmmm

so the question is really that the order of b^i is the lcm of i and d

[normal heart]

not really

lcm/i

[livid birch]

oh i was thinking that (b^i)^{d / (i,d)}

then id / (i,d) = lcm(i,d) no?

[normal heart]

well yeah, that proves order of b^i divides d/(i,d) right, or did I get you wrong

[normal heart]

cuz d/(i,d)=lcm/i, and the question says order of b^i=d/(i,d)=lcm/i, there's probably a miscommunication between us or something haha

[livid birch]

ohhhh yeah my b

[unique cypress]

Hey may anybody work me through this step? It is concluded from a lemma, which I don't quite understand. Thank you in advance.

I don't quite know if this is appropriate for #advanced-number-theory or #elementary-number-theory ...

[normal heart]

It's just changing the order of summation, then note the inner sum (after changing the order of summation) is over the set S (fix n).

[I think both adv and elementary are appropriate]

[unique cypress]

Sorry I don't quite get it. I find myself struggling with manipulating the sums. I have no problems with the sums being infinite but manipulating finite sums with gcd is just...

[normal heart]

What do you get after switching the order of summation?

[unique cypress]

(After switching) Inner sum is the divisors (d|n) of the function f((kn/d/)n)? If you are hinting for the lemma then I don't get the relationship really

[normal heart]

Another way to think about it is the combined sum is over all d such that (d|n) and (d, k) =1, and 1 <=k<=n, and this is exactly the condition in the definition of the set S

[mossy rampart]

Let $n,k\in\mathbb{Z}$ with $k\geq 2$. If $(n-1)|(n+1)^k$, then does $\(n-1)|(n+1)$? If no, then give a counterexample

[sterile pumice]

Évariste

[hearty osprey]

Is it possible to prove the small fermat theorem using addition?

Ljke n^p=n...*n p times

Which is n, n^p-1 times added together

Idk.. i feel like it should be somehow obvious using addition and simplifying modulo p to get n

Ig thats the recurrence proof with the binomial theorem, but idk i feel like it was a hack

I tried the case n=2, p=3....nothing seems obvious

[unique cypress]

I see thank you for clarifying it. Indeed, if you start reading the sums from left to right it matches the lemma. But I have a slight doubt. You see when the lemma says kn/d|d? Which part of the equation shows that kn/d divides d? I see the similarities in the inner values of f(x) namely kn/d. Does kn/d implies that it is divides d?

Other than that thank you again 😄

[normal heart]

That | doesnt mean divide, it means "such that"

The same as the symbol : when we define sets

[unique cypress]

Ohhh

I mixed stuff then 😅

Yeah now it makes total sense after realizing this

[sleek spire]

is there even a number n such that n - 1 divides n + 1 that is not 1, 2, or 3

[torn escarp]

great question

$$\frac{n+1}{n-1} = \frac{n-1+2}{n-1} = 1 + \frac{2}{n-1}$$

[sterile pumice]

Merosity

[sleek spire]

yeah lmao just what I thought

[unique cypress]

same

My book just assumes that the reader knows such not obvious results like this

Why is that true?

[torn escarp]

how many times are you multiplying n by itself?

[unique cypress]

I used this fact to prove this claim

[unique cypress]

n^n ?

[torn escarp]

more simply do you know why $$d(n)=\sum_{t|n}1$$

[sterile pumice]

Merosity

[torn escarp]

nope, that would be different than t|n since that means you look at a term for each divisor t of n

[unique cypress]

Yes it follows from the definition of divisors functions when alpha = 0
$$\sigma_{\alpha}(n)=\sum_{d|n}d^{\alpha}$$

[sterile pumice]

DespairΔBullet

[normal heart]

That would be overkill, the formula for d(n) above is by definition

[unique cypress]

It is an overkill

[normal heart]

Anyway, if you know that formula, you could deduce this

[unique cypress]

What formula?

[normal heart]

d(n)=sum...

the one above

[unique cypress]

Another way to think about it is this
$$\sigma_{\alpha}(p^s)=1+p^{\alpha}+...+p^{s \alpha}=\frac{p^{\alpha(s+1)}-1}{p^a-1}$$

[sterile pumice]

DespairΔBullet

[unique cypress]

Take logs?

[normal heart]

take power (so I guess yes, log)

n^d(n)=n^sum...

[unique cypress]

I'm confused now

[normal heart]

$$n^{d(n)}=n^{\sum_{t \mid n} 1}=\prod_{t \mid n} n.$$

[sterile pumice]

cflau_

[unique cypress]

Yep got it thanks

I just need to play around with divisor function I guess

There is also this proof that is bugging me

[normal heart]

what is the function I?

and also which step is troubling you?

[unique cypress]

The upper bound of the inner sum in the first line

What I was thinking is to convert the floor function into the sum of mobius function where d|n

[normal heart]

it's just the fact that $$A=\sum_{k=1}^A 1$$ for $A$ a positive integer, if that is what you're asking

[sterile pumice]

cflau_

[unique cypress]

Oh so A is the floor function here

What about the second step? I can tell there is a switch of summation

[normal heart]

yes, it's just switching the order of summation

[unique cypress]

Yeah but how the bounds changed?

The entire process looks like magic to me

[normal heart]

it takes some time to understand, try writing out the sum with small numbers x and n and it should be clear how they switched the order

Also, note $d \mid (n,k) \iff d \mid n$ and $d \mid k$.

[sterile pumice]

cflau_

[unique cypress]

Yeah

[unique cypress]

So you're implying that $$\sum_{d|n, d|k }$$

[sterile pumice]

DespairΔBullet

[unique cypress]

I do remember seeing some sums getting split into two after doing this

[normal heart]

it just takes some thought gymnastics to establish the olrder of summation interchanges in that way, try expanding the sums with small parameters n and x

[unique cypress]

$$\sum_{d|n}(. )\sum_{d|k }(.)$$

[sterile pumice]

DespairΔBullet

[unique cypress]

Ok I'll take the time to work through some numbers to get the intuition behind it I guess

[craggy cradle]

this implies that any linear combination of n and k with integers divides d such that the number with which you multiply n and k should be integers

[feral roost]

\text{ Idk if this is number theory but can anyone solve $\sum_{x=1}^{\infty} (2x^2)(p(1-p)^{x-1})$? Have been going on circles for an hour now for it}

[sterile pumice]

Lukee

[harsh solstice]

<@&268886789983436800>

[sacred junco]

does anyone know how to tackle this question? specifically part a?

[sleek spire]

well it can't be 0 or 1

[sacred junco]

so do i just use any prime number greater than or equal to 2 that i can think of? and show the prime factorisation of it?

[unkempt void]

a) doesnt need any prime factorisation stuff

[sacred junco]

right, okay thanks

[torn escarp]

no it's not number theory, try calculus or in a question channel #❓how-to-get-help

[unique cypress]

Why this is true?
$$\prod_{d|n}\frac{1}{d^{\varphi(d)}}\prod_{\substack{k=1\ (k,d)=1}}^{d}k=\prod_{d|n}\prod_{\substack{k=1\ (k,d)=1}}^{d}\frac{k}{d}$$

[sterile pumice]

DespairΔBullet

[leaden swan]

There are \phi(d) terms in inner \Pi

[unique cypress]

Sorry I don't quite get it

phi(d) is 1 only if d = 1 or 2

Is the inner product implying this in some way that I still did not notice?

[leaden swan]

How many positive integers below d are coprime to d?

[unique cypress]

That's just phi(d)

[leaden swan]

Well then how many terms will be there in the inner product?

[unique cypress]

[leaden swan]

So you just give one d to each term in product

[unique cypress]

$$\prod_{d|n}\prod_{\substack{k=1\ (k,d)=1}}^{d}\frac{k}{d^{\varphi(d)}}$$

Would that still be correct?

[leaden swan]

No?

[sterile pumice]

DespairΔBullet

[unique cypress]

hmm

[unique cypress]

What's the answer for this one?

[leaden swan]

\phi(d)

[unique cypress]

When doing this are you moving the 1/d^phi(d) function inside the product ?

[leaden swan]

You can't just move a term inside like that

[unique cypress]

I thought you can as long the product is not infinite

@leaden swan Oh I got what you mean now. So the inner product is multiplying d phi(d) times so it is already taking care of the exponent that is outside the inner product

Thanks btw

[leaden swan]

Yes

[sacred junco]

Does anyone have a good method for solving linear diophantine equations with an arbitrary number of variables?

I'm able to find a few online but they all look pretty involved compared to the level of difficulty this class usually has

[normal heart]

For example?

Whats the usual difficulty of your course?

[sacred junco]

As far as raw calculations go the hardest thing I've had to do so far has been some divisibility exercises. One example I can find is show 2^70 + 3^70 is divisible by 13

As for harder things conceptually we had to prove fermat's little theorem using induction as homework

These usually take one or two pages to do for me but the methods I'm finding for solving linear diophantine equations are taking me easily over 4 pages the moment there are 3 variables involved

Maybe I'm just missing something but it seems way over what I'm usually expected to do

[normal heart]

What is an example of a lineat diophantine example ur asked to solve?

And what is your solution that you think is too long?

[sacred junco]

I'm on the bus now but the one was doing at the time was 39x+42y+28z=5

I was using a method that was in a compendium I found but it's a bit long to explain in detail while I'm typing on my phone on the bus x.x

It involved a lot of variable substitutions that led to simplifying the equation down to something obvious and then working your way back to the original variables

What makes it so long is just how many variable substitutions there are

Like for the equation I just posted following the algorithm took me 5 subs deep for each variable

[normal heart]

For each y, can you solve 39x+28z=5-42y in terms of y?

[sacred junco]

Not with the methods I currently have

I can solve that explicitly but not in terms of y

Like if I started with y=1, 2, 3 etc I would do just fine I think

But in terms of y I'd have to do something different from what I've been doing so far

[leaden swan]

Is this about finding a,b such that 39a+28b=1

And then consider x=(5-42y)a and z=(5-42y)b?

That will get you a particular solution

Now you can find all solutions in terms of y

[sacred junco]

I haven't come across this before, I'll give it a closer look when I get home, ty

[leaden swan]

Do you know how to do this?

[sacred junco]

Although I don't really see how that would generalize to more variables

[leaden swan]

Well induction probably

[sacred junco]

Oh yeah no problem

[leaden swan]

Well actually it works in the exact same way ig

[sacred junco]

It's going from the 3 variable equation to what you wrote that I haven't seen before

[leaden swan]

You move everything except 2 variables to right hand side

And then do this

[wide hollow]

Any1 know what quadrant theta would be in if tan theta is > 0 and csc theta is < 0?

[normal heart]

Yeah

[leaden swan]

So if you have $\sum_{i=1}^{n} a_i x_i = c$ this becomes $a_1 x_1 + a_2 x_2 = c-\sum_{i=3}^{n} a_i x_i$

[sterile pumice]

DraK

[normal heart]

Then you can do general y

Same method except u have the variablr y instead

[leaden swan]

Well if you cannot find a pair of coprime integers , this becomes annoying

[sacred junco]

The method I currently use involves converting the equation to a linear congruence equation

And I have no idea how to solve one of those for arbitrary y

Maybe I can and I just don't know it but it def feels a bit odd

I'll give it a closer look when I get home

Thanks for the help anyways

[normal heart]

You should know the general way of solving linear diophantine equations in two variables?

[craggy cradle]

how can n be equal to 2?

1 is not prime

[loud moon]

it doesn’t have to be equal to 2, just needs to be at least 2. it’s unnecessary to consider N = 2 of course but it’s probably written that way to tie that back to “any integer >= 2 has a unique prime factorization” in some lecture notes somewhere

but yeah it’s a bit strange and overkill to invoke a notion of “prime factorization” to show infinitude of primes. basic divisibility arguments are enough. but it’s in the question so

[misty nova]

I'm trying to prove a stronger version of the well-ordering principle for integers: that, for any non-empty set A of integers, every non-empty subset of A has a least element if so does A. my proof depends on a lemma I'm stuck on:

[sterile pumice]

katia

[misty nova]

this sounds like a fairly obvious theorem, but I'm not managing to prove it

so far I've tried proving it by contradiction:

[sterile pumice]

katia

[misty nova]

where should I go from here?

[kind marten]

could i get some help for this question?

[normal heart]

consider x-a0, and compare it to n, noting that a_n>a_{n-1}>...>a0

[loud maple]

If n is composite then n=a×b for some positive integers a and b such that a,b>1

And a ≤ n-1

[loud moon]

the last part would be proving that if n is prime then the factorial actually equals 1 mod n (rather than just nonzero), which is not too difficult to see with the right insight

[dusty dragon]

(3 - 1)! = 2 (mod 3)

I assume they mean -1 (mod n) which is precisely Wilson’s theorem

[loud maple]

It doesn't matter, the given statement is equivalent to the statement "if n is composite, then (n-1)! is not congruent to 1 mod n"

But what you're saying is, in all probability, the intended statement of the problem.

[dusty dragon]

I was more referring to this^

[loud maple]

Ah my bad, apologies.

[loud moon]

yeah it should be -1 of course

[kind marten]

yeah i was looking up factorials with mod n and everywhere said -1

so i was like

maybe its just an error

[misty nova]

I don't follow. what do you mean "compare it to n"?

[normal heart]

Suppose x>a_n for all n. Note a_n-a_0>=n for all n, so what lower bound can we get for x-a_0? And how is this a contradiction if n sufficiently large?

[misty nova]

ok, I see it now. thank you very much

[mossy rampart]

If $a,b\in\mathbb{Z}^{+}$ have exactly 120 common positive divisors, then find how many positive common divisors the numbers: \begin{center}$A=4a+5b$ and $B=3a+4b$ have.\end{center}

[sterile pumice]

Évariste

[silent charm]

Hey all I'm trying to prove the following -
$gcd(ca,cb) = c*gcd(a,b)$ in two different methods, using the Fundamental theorem of arithmetic and without it. I'm not 100% what I am required to show here and how to do so.

[sterile pumice]

meitar5674

[verbal cedar]

so if you have some work written down on paper or digitally you can send a picture, or you can just describe what you've done/tried so far

like if you were able to do it with FToA, and now you're stuck doing it without it for example

[silent charm]

So honestly I'm not 100% sure what am I suppose to prove and I believe this is mostly my issue.

like I could denote d as the gcd of a,b therefore I know both a and b are divisible by d. multiplying by c I get that cd is divisible by the gcd of (ac,ab). Is that even a valid start?

Maybe I'm just afraid doing mistakes cuz its the beginning but honestly feeling kinda lost with it

[verbal cedar]

sure. writing d=gcd(a,b) is really convenient. we know d divides a and b. but that actually implies cd divides ca and cb.

the thing you want to aim for in these kind of proofs is showing that x divides y and y divides x. because then that implies x=y

so you want to prove cd divides gcd(ca,cb) and gcd(ca,cb) divides cd

[silent charm]

Ok let me think about it and see if I can solve it now, I'll tag if success / failure

[sleek spire]

17.9 m^2

[ruby tendon]

how did u get that?

[sleek spire]

thinking hard

[high island]

3x7.5+10x7.5/2

[silent charm]

So for one direction -
cd divides both ca and cb hence by definition cd | gcd(ac,bc)

for the other direction -
im not sure but I know that d' is the gcd of ac,bc therefore lets assume d' > dc so theres no equality.
d' = c*k for some k > d (since we divide both sides by c) which is a contradiction to the minimality of d? is this correct?

[verbal cedar]

wdym by the minimality of d?

[silent charm]

i meant maximality sorry, since its already the gcd, and we get that there is a bigger common diviser

[silent charm]

forgot to tag sorry

[verbal cedar]

i think that works. personally, i used Bezout for the other direction.

[silent charm]

how?

[verbal cedar]

if mx+ny=D, then gcd(m,n) divides D
we know there exist integers x,y such that ax+by=d.

that's the start

[misty nova]

the finished proof, btw:

[sterile pumice]

katia

[misty nova]

now a soft question: has anyone seen this theorem in the literature before?

it came to me but I've personally never seen it before

and I feel like my proof, though original (or at least independently conceived), is a bit longer than necessary

[unkempt void]

Hm I think here it is just easier to note that a subset of Z has a least element if and only if it bounded below

This theorem doesn't generalise to other orders, since for example [0,1] has least element 0 but (0,1) is a subset with no least element

[misty nova]

hmm, true

[misty nova]

ig it doesn't work when the order is dense, since you can always find a smaller element even in an interval (or more generally a set) bounded below

but if it's discrete, as with the integers, then it works

[lunar moat]

Can we always find a real number $s > 0$ such that:

$$
\Sigma_{i=1}^Nr_i^s = 1
$$

where $r_i \in (0,1)$

[sterile pumice]

chedug

[normal heart]

$N=1$ and $r_1=1/2$?

[sterile pumice]

cflau_

[lunar moat]

Hm?

[normal heart]

I mean this disproves your claim right

[lunar moat]

I mean does this number $s$ always exist for any $N$ and for any $r_i \in (0,1)$

[sterile pumice]

chedug

[lunar moat]

Hm, you're right

And N = 2, r1=r2=1/2 also disproves it..

[normal heart]

s=1 works

[lunar moat]

But s can't be 0 or 1. It's a contraction factor, but I didn't mention in for the sake of the channel

[normal heart]

Oh, yeah then no s works

[lunar moat]

Thank you

[cloud patrol]

Hello, I need help solving this.

i tried with the methods shown to us in school but the -13 is messing everything up

[charred mountain]

new fractal

[wooden glen]

I'd write y=9^n to get 3y² + 10y - 13 == 0 (mod 64). Then multiply through by 43 (namely the inverse of 3 modulo 64). Now completing the square yields something very nice ...

(Or even better, multiply through by 3 instead, and complete the square in the form (3y+A)^2 for the appropriate A.)

[cloud patrol]

im sorry, english is not my main language, by multiply through you mean multiply the entire equation, correct?

[wooden glen]

Yes.

[cloud patrol]

alright, much appreciated

[cloud patrol]

i got y1 to be -13/3 and y2 to be 1

[wooden glen]

There shouldn't be any thirds.

What does your equation look like after completing the square?

[cloud patrol]

so just to know we are on the same page, i got 9y^2+30y-39 then I used the formula (-b +- sqrt(b^2-4ac)) / 2a and got those answers for y. is that what Im supposed to do?

[wooden glen]

My suggestion was to complete the square, not to plug into the quadratic formula (which doesn't work well in non-fields).

If (3y+A)² gives 9y²+30y+(some constant) then what must A be?

[cloud patrol]

A=5?

[wooden glen]

Right. Then find the right constant such that (3y+5)² + ??? = 9y²+30y-39.

[cloud patrol]

alright so the ??? needs to be -74

[wooden glen]

Check your arithmetic again.

[cloud patrol]

oof mb i wrote 35 instead of 25

it should be -64

[wooden glen]

So your equation is now (3y+5)² - 64 == 0 (mod 64), which is the same as ...?

[cloud patrol]

(3y + 5)² == 64 (mod 64)

[wooden glen]

It can become simpler yet.

[cloud patrol]

(3y + 5)² == 0 (mod 64) ?

[wooden glen]

Yes. Very nice -- the constant term has disappeared!

Now, which numbers have squares that are multiples of 64?

[cloud patrol]

1,2,4,8

im not sure if i understood the question

[wooden glen]

Uh, 2^2 is 4, which is not a multiple of 64.

Remember that we know that 3y+5 must be a number whose square is a multiple of 64.

[cloud patrol]

oh so y can only be 1 ?

[wooden glen]

y==1 (mod 64) is a solution, but not the only one.

(We're on the right path, but you skipped a few steps and details, and I'm not sure you got to the right point).

[cloud patrol]

i think im missing the point lol, im supposed to find all the solutions, right? i just dont know how i would go about that

[wooden glen]

We're doing that!

But you seems to have skipped ahead from my question: Which numbers have squares that are multiples of 64?

[cloud patrol]

1,4 and 8?

-8, -4, -1, 1, 4, 8?

what exactly does multiples mean, i dont think we are thinking of the same thing

8,16,24,32 etc. are numbers that have squares that are mutiples of 64

i think we are on the same page now 😭

[wooden glen]

Right. The numbers whose squares are multiples of 64 are exactly the multiples of 8.

This means that (3y+5)² == 0 (mod 64) if and only if 3y+5 == 0 (mod 8).

[cloud patrol]

omg i see now

[cloud patrol]

3y == -5 (mod 8)
finding the inverse of this is possible because 3 and -5 are prime in pairs (idk if thats how its said in english)
3 * a == 1 (mod 8)
a = 3
so the inverse is 3.
3y = -5 (mod 8) / * 3
9y = -15 (mod 8)
now because 9 is 1(mod 8) :
y = -15 (mod 8)
so y = - 15 + 8 * l ???

i think y = -15 + 8 * l is the answer

[wooden glen]

Well, recall that -15 == 1 (mod 8), so we can say that a little bit simpler: 3y² + 10y - 13 == 0 (mod 64) <===> y == 1 (mod 8).

Now remember that the variable we were looking for was not y but n, where i had defined y to be 9^n ...

In fact we could plug in y=9^n as soon as we get to 3y+5 == 0 (mod 8), namely getting 3·9^n + 5 == 0 (mod 8).

And, as you've remarked, 9 is the same as 1 when we're working mod 8.

[cloud patrol]

ohhh so that means 8 == 0 (mod 8) ?

[wooden glen]

Yes.

[cloud patrol]

i guess that proves it

youve been of tremendous help, thank you so much for your precious time

i really appreciate it

[wooden glen]

yw

[lilac elk]

does anyone know if this site is legit?
it claims that there is a prize of 120 millions yen to whoever solve the Collatz conjecture it.
https://mathprize.net/posts/collatz-conjecture/

[still flare]

It doesn't seem legit, but it simply does not matter: you're not going to be affected

[verbal cedar]

so there's the theorem that if g is as PR mod p then either g or g+p is a PR mod p^2. for example, 2 is a PR mod 5, so either 2 or 7 is a PR mod 25. but technically 2=7 mod 5. so does that mean that 7 or 12 could be a PR mod 25? and since 7 is definitely not a PR (7^4=1 mod 25), then 12 must be a PR?

[torn escarp]

I think you can show it by supposing you have $x^{p-1}=1\mod p$ then you can expand $$(x+pn)^{p-1}=x^{p-1}+(p-1)pnx^{p-2} \mod p^2$$ notice all the higher terms are killed. This gives you "n" to play with

[sterile pumice]

Merosity

[torn escarp]

then we can reason a bit further from here, but I'll let you work on that for a bit I guess

I'm sort of side-stepping your question by going directly to what the relation is between x vs x+np as being generators

since it's maybe not obvious the next step I'd take is subtract off 1 from the two terms to p-1 powers, then everything is divisible by p and we can simplify it down to write it like this:
$$\frac{(x+pn)^{p-1}-1}{p}=\frac{x^{p-1}-1}{p}-nx^{-1} \mod p$$

[sterile pumice]

Merosity

[torn escarp]

those fermat quotients can only be 0 mod p if they come from a generator mod p^2

[mossy rampart]

We colour the positive Integer numbers from 2 to 1024 with k colours, such that any number has not been coloured by the same colour that any of his multiples have. find the minimum value of k.

[leaden swan]

I guess 11 should work?

[exotic bone]

You can do it with 10 (color a number based on its number of prime factors, counting multiplicities, so all primes are color 1, any product of 2 primes is color 2, etc... Obviously if n|m then n has fewer prime factors than m, so they get different colors). In general the answer is just the ceiling of log_2(n) for 2...n.

[leaden swan]

mb 10 works

[leaden swan]

I don't think it's necessarily ceil. Consider n=5. You can color 1,3,4,5 color 1. 2 color 2

[exotic bone]

Yes and it's provably optimal because all the powers of 2 have to be different colors.

[exotic bone]

That's true actually, this strategy is only optimal when n is a power of 2.

Or sorry only gives ceil(log_2(n))

It's clearly always optimal.

[leaden swan]

I think it should be floor(log_2(n))

Because you clearly need at least that much because the greatest power of 2 in [1,n]

[exotic bone]

Ah that's right.

And Floor(log_2(n)) always has the largest number of prime factors.

Anyway hope this helped.

[mossy rampart]

thanks guys, to be honest, I still do not understand the solution, I even read it from the textbook solution's page and still don't get it...

[errant ridge]

Love the référence in your nickname

[mossy rampart]

thanks!

[leaden swan]

Ok so define a chain as a sequence p_1,p_2...p_n such that p_i is divisible by p_{i+1}

Length of longest chain will be the required color count

[analog portal]

There isn't a quick way to do this right?

I have a method that has success with probability > 1-2^-r after r attempts that involves some maths

[sleek spire]

maybe I'm having a brainfart here, but is there any nice form of $\frac1v \cdot \operatorname{lcm}(q, v^2)$

[loud moon]

what’s your method? you can do this deterministically and in time polynomial in log(N), i.e. “fast”, though depending on how e_j and d_j are defined it can range from trivial to somewhat annoying

[fierce shale]

even with 100-digit prime numbers used to make N?

[exotic bone]

I guess there is an alternative form? But it's not much simpler.. lcm(a, b) = ab/gcd(a, b) so this is qv/gcd(q, v^2) depends on what you want to do with this.

[torn escarp]

lcm(q/v, v) I think also works I guess, idk if that's much nicer or not

[vapid sable]

hi guys, i am i right in my workings here? the solution given did it much more simply but for my understanding could you see if this is correct?

[dusty dragon]

Your proof for l being an integer seems fine but you can jump straight from g | m to m = k_1 * g where k_1 is an integer (same for n). Your proof for m | l seems a bit difficult to follow. I’m not entirely sure what your argument here is since it seems like you assumed that m | l and tried to derive some expression

[vapid sable]

oh i see how ive done the proof of m|l incorrectly let me try again later

i shouldnt have started with that oops

[fervent crest]

Why is t > beta here?

[vapid sable]

thats better right?

[dusty dragon]

Yes, that looks much better!

[vapid sable]

:)

[main stump]

how to prove the hint?

[main stump]

I dont understand...

[lean coral]

don't know if you still need help, but i believe you are meant to use fermat's little theorem here

and then evolve from there

[sacred junco]

Which factorisation of 840 gives us the largest sum?
(Cant use 1 , must be in at least 2 pieces )

With proof

Anyone

[west glade]

consider the function f(x)=x+840/x where x can only be in a relevant interval and then find maximums. that gives you the upper bound for using 2 factors. then with induction you can bound the sum of factors by their product plus some term depending on the number of factors you use

[white lion]

Why is it that when I make 13x congruent 6 mod 23 I get a difference answer than if I were to solve x for 13x congruent -17 mod 23? Surely X should satisfy both so I should have the same answer right?

[dusty dragon]

You should get the same answer, you may have just made a mistake somewhere in your working

,w 13x = 6 mod 23

[sterile pumice]

Results provided by WolframAlpha

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

Requested by opengangs#7348

[dusty dragon]

,w 13x = -17 mod 23

[sterile pumice]

Results provided by WolframAlpha

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

Requested by opengangs#7348

[white lion]

Yeah got it thx @dusty dragon

[languid granite]

also exists for the unit vector

[analog raptor]

Solve in N

any ideas?

[still flare]

N can be any number at all 👍

[torn escarp]

Idk maybe factor the LHS as sum of two cubes

Reduce mod 8 and pray randomly

[leaden swan]

Mod 7 should do the trick

If z>=6 , RHS mod 7 is 5

LHS can be either 1,2 or 0 mod 7

So z < 6

Now like just brute force

@analog raptor

Or you bound z further to get z<=3

[analog raptor]

yeah mod 7 does it

thanks

[onyx granite]

Is there a way to find number of prime numbers up to a natural number n?

[leaden swan]

Well if you want a deterministic way, there is sieve of Eratosthenes

Pretty sure there are a thousand probabilistic/bounding techniques for this

[onyx granite]

sieve of Eratosthenes
NO.

[leaden swan]

Sieve is easy to program tho

[normal heart]

Literally what number theorists have been trying to do for centuries

[stiff rivet]

there are also better sieves

the sieve of Atkin is a modern version

if you just want a reasonable guess, this is answered by the prime number theorem

n/log(n) is a pretty good guess, you can be a bit better but not much

@onyx granite

[errant otter]

Oh? You can?

[onyx granite]

,calc 100/log(100)

[sterile pumice]

Result:

21.714724095163

[onyx granite]

,calc (25-21.714724095163)/(21.714724095163)

[sterile pumice]

Result:

0.151292546497

[onyx granite]

Approx 15% error

[loud maple]

The prime-counting function tends to n/ln(n) as n tends to infinity

For smaller values there may be large percentage errors

[onyx granite]

Hmm

Interesting!

[misty anchor]

Hi! Could someone give me a hand with this?

I’ve tried number 13 but got (n^2)/n-1

Instead of n^2

[gaunt sedge]

how do I prove the homomorphism part of this? (context, this is just before stating the power series trick; it says recall but i dont recall us doing this so im asking here)
for exp, i want to show exp(a+b) = exp(a)*exp(b)
i worked with the power series expansion, but the double summation on the right hand side is hard to simplify

[sleek spire]

I mean, you can use cis for exp lol

but that's not the optimal way

[stiff rivet]

can you share what you have? on the left hand side you use the binomial theorem and if you know what the binomial coefficient looks like you should be already done

i.e. there is no reason to get rid of the double summation if you work from both ends

[tough crown]

How to prove that these do partition n into even and odd prts

[weak rapids]

I'm assuming the question does not want me to use Fermat's Little Theorem. I'm unsure how to proceed, could I get a hint?

[loud moon]

consider the order of a mod each of the three prime factors of n, and think about what that means for the order of a modulo n itself

[wooden glen]

Yeah, it seems fair game to use FLiT for each of the given prime factors and then combine them using CRT.

[weak rapids]

Thanks guys I used these ideas and I think I've got answer

I used that a^(18t) = 1 mod(p) for all the primes p. Then showed that a^(18t) = 1 mod(n) using CRT and the claim follows since 18t divides n-1.

does this seem right?

[wooden glen]

Hmm. If t=1 we have the primes 7, 13, 19. Then 2^18 == 12 (mod 13), rather than 1.

[loud moon]

yes, 18t doesn't quite work, but you are on the right track

[weak rapids]

oh yes damn

ah ok I see

wrong lcm

ty

[unkempt charm]

How can I write $4 - \sqrt{15} \in \mathbb{Q}(\sqrt{15})$ as a sum of squares????

[sterile pumice]

arab arnold

[sacred junco]

Hey there! I have this very simple prime number theory but nobody to discuss it with. I was hoping this community could tear it apart for me. It's not pleasant practising math without anyone to share with. It's very short and straight forward. https://www.reddit.com/r/numbertheory/comments/1348h6y/theory_to_discuss_a_lower_bound_on_the_symmetry/?utm_source=share&utm_medium=web2x&context=3

[torn escarp]

post it on math stackexchange maybe they'll be more willing to tear it apart for you

[sacred junco]

Thanks @torn escarp I was directed here from reddit but that might be the better choice.

[verbal cedar]

say we're looking at the finite field Zp/<x^2-bx-c> (obviously assuming the quadratic is irreducible)
and r is a quadratic nonresidue mod p. when will r be a quadratic residue mod x^2-bx-c, and how can we find its "square root"?
it seems to be true a lot of the time.

[west glade]

well if its not a square mod p, then x^2-r is irreducible and Zp[x]/<x^2-r> gives the same field

which now has the square root

not sure about finding it tho. that would essentially give a field isomorphism between those fields which afaik is a hard thing to find

[torn escarp]

r/discriminant is a QR, so that's basically your answer

I'm on mobile I'll elaborate more later if that doesn't make sense

[verbal cedar]

yeah that's actually where i got the problem. finding a field isomorphism between two quotient fields of Zp by irreducible quadratics
phi: Zp/<x^2-b'x-c'>->Zp/<x^2-bx-c>,
i got that if phi(x)=f(x) in Zp/<x^2-bx-c>, then f would have to satisfy
f(x)^2-b'f(x)-c'=0
but f can't be a constant or else the polynomial is reducible, so we need a square root of r=b'^2+4c' which can't be. a QR mod p, so it must be a QR mod x^2-bx-c

[verbal cedar]

yeah after i sent the message i got that. since r and (discriminant)^-1 are QNRs, then their product must be a QR.
but I'm still curious if there's a way to find a square root. any ideas?

[verbal cedar]

since $\phi(x)^2=f(x)^2=\phi(x^2=b'x+c')=b'\phi(x)+c'=b'f(x)+c'$

[sterile pumice]

nilpotent nix

[verbal cedar]

leading to

$(2f(x)-b')^2\equiv b'^2+4c'\bmod{x^2-bx-c}$

[sterile pumice]

nilpotent nix

[verbal cedar]

or wait i actually got that if $g(x)=m_0+m_1x$, where $g(x)^2\equiv r\bmod{x^2-bx-c}$ then
$$m_0\equiv bm_12^{-1}\bmod{x^2-bx-c}$$
$$m_1^2\equiv 4r(b^2+4c)^{-1}\bmod{x^2-bx-c}$$

so i do just need a square root of r/discriminant

[sterile pumice]

nilpotent nix

[torn escarp]

Well I just turned the problem into finding the sqrt of a QR

I'm other words, the problems are equivalent so if you can do one easily, you can do the other easily

Maybe that's what you just figured out, I didn't read heh

at my computer now, to be explict what my solution is, since we know r/disc is a QR, $\frac{r}{disc}=x^2$ and so $r=x\sqrt{disc}$, which you can rewrite in terms of the root if you wanted

[sterile pumice]

Merosity

[torn escarp]

to be even more explicit say $u$ is one of the roots of $x^2+bx+c$, write it as $u=\frac{-b+\sqrt{disc}}{2}$ so $\sqrt{disc} = 2u+b$ and your solution is $\sqrt{r}=x(2u+b)$

[sterile pumice]

Merosity

[torn escarp]

(I left out sqrt in the previous latex, not gonna edit it and put it out of order now)

[verbal cedar]

but it seems you still need to compute the square root of r/disc and disc in the first place.
though I'm not sure how you compute sqrt(disc) since disc can't be a QR without the poly being reducible

[verbal cedar]

i think these should be mod p actually

but yeah it seems that basically i just need a square root of r/disc mod p and then i have it.
so, are there any tricks for square roots of a product of two nonquadratic residues? i guess that's my only hope lol

[torn escarp]

nah @verbal cedar what I'm saying is this already shows the problem amounts to finding the square root of a QR

if you solve one you necessarily are solving the other problem

[verbal cedar]

okay yeah makes sense

[verbal cedar]

actually we covered something in class that sorta works: cipolla's algorithm. let $a=\frac{r}{disc}$, which is a qr. then choose any $t$ such that $t^2-a$ is a qnr. then
$$\sqrt{a}=\paren{t+\sqrt{t^2-a}}^{\frac{p+1}{2}}$$
it's written in terms of the power of an element in $\mbb{F}_p(\sqrt{t^2-a})$ but the power is in $\mbb{F}_p$.

[sterile pumice]

nilpotent nix

[weak rapids]

I want to find primes p such that (x+y)^13 = x^13 + y^13 mod p. A necessary condition is that 2^13 = 2 mod p -> 2^12 = 1 mod p(except 2). I'm unsure of how to proceed further and would appreciate any hints.

also not sure if the condition is sufficient to guarantee the homomorphism

[torn escarp]

I'd probably look at the binomial theorem

on the plus side, your argument has effectively ruled out all primes larger than 4096, so only a few more to brute force if you wanted... 😛

<@&268886789983436800>

[weak rapids]

why all primes larger than 4096 ?

oh ig you know powers of 2

[torn escarp]

yeah

[leaden swan]

Well you know p is of form 12k+1

So that's atleast 50%

[weak rapids]

not really because 2 works

[leaden swan]

Ok fair

Order of 2 should divide p-1

[weak rapids]

yeah not sure how to find the order of 2 for different primes p though unless i'm just doing trial and error

like 2^3 = 8 = 1mod 7

[torn escarp]

fix y and think of f(x)=(x+y)^13 - x^13 - y^13 as a 12th degree polynomial - since mod p is a field it means for p>13 it has at most 12 roots, but it must have p roots, which is impossible

more explicitly for that f, f(x)=0 mod p for all x in {0,..., p-1} which means it must be a multiple of x^p-x

[leaden swan]

Is (Z/pZ) algebraically closed?

[torn escarp]

no

all algebraically closed fields are infinite

[leaden swan]

So how do you know it will have p roots

[torn escarp]

it's supposedly an identity - that's why it's 0

[leaden swan]

Ah mb

[torn escarp]

f(x)=0 means (x+y)^13 - x^13 - y^13 = 0 yup

so assuming this I derived a contradiction yeah, I could have said that clearer my bad

[weak rapids]

wdym by it must have p roots

[leaden swan]

.

[weak rapids]

ah yes

[sacred junco]

this whole question confuses me but i was wondering if anyone knows how to tackle part a please?

[cunning plinth]

try starting with some specific examples for integers a and x. that should help with the understanding w/ how to approach part (a)

[sacred junco]

sure i’ll try that thanks

[sacred junco]

this is the best i could do but it’s not right i’m sure of it

[cunning plinth]

try prime factoring x as well. what do you see as a result when comparing to what the problem is asking? try also x = 6 and x = 2. what observations can you make then?

[sacred junco]

oh right yeah i forgot to prime factorise x instead of a

ok this is what i’ve changed it to

[cunning plinth]

you want to see the prime factorization of both -- the problem is asking you to establish a relationship between the prime factorization of a and the prime factorization of x

[sacred junco]

okay i’ve prime factorised 60 and 12 and the difference is that 60 has one more prime number than 12. i’m not sure how to express it tho

[cunning plinth]

right! so how is that related to a = qx?

[sacred junco]

right okay i sort of see the connection

i’ve added the last bit but i think it should be changed slightly

[verbal cedar]

so if l divides p-1, then there exists an element of order l mod p. and, i seem to have proved that there are phi(l) such elements. for example, mod 31, there are phi(6)=2 elements of order 6. 3 is a primitive root, so we can write all the elements as
3^(5k)
and so is the idea for it to be a solution, we need k to be coprime to 6=30/5 for it to actually have order 6? or if someone can articulate some intuition more clearly, please let me know.

[tender cedar]

I have an excercise to solve the congruence $4x^{20}+50x+43 \equiv 0 \mod 23$ (without trying bruteforce)

[sterile pumice]

sam

[tender cedar]

But just out of curiosity I tried to bruteforce it with python (and wolframalpha), and there dont seem to be any solutions?

Is there a mistake in the excercise?

def polynomial(x):
    return 4*x**20 + 50*x + 43

for i in range(23):
    if polynomial(i) % 23 == 0:
        print(i)```

This is my code, and it prints nothing

Must be a mistake in the exercise no?

Or do you first have to reduce it or something?

[west glade]

well why should there be a solution? not every polynomial has a solution

[river rapids]

@tender cedar have you tried to use newton's method or something to find x instead?

oh didn't see "mod 23"

[leaden swan]

You can rewrite that as
50 x^3+43 x^2 + 4=0

4x^3+20x^2+4=0

x^3+5x^2+1=0

I guess you can use cardano to find solutions to this

Or well show no real solution exists

[tender cedar]

How did you arrive at the first line?

[leaden swan]

Multiply both sides with x^2

x^22-1=0 for all nonzero x

[sinful shale]

Is anyone here familiar with Diophantine sets?

[weak rapids]

sorry back to this explanation, wouldn't p=13 not work too since we must have 13 roots for mod 13

[leaden swan]

Yea

[torn escarp]

wot

[leaden swan]

0,1,2,3...12 are roots for that,no?

And it's a 12th degree polynomial

[torn escarp]

is it?

what if it's f(x)=0

[leaden swan]

Well f is explicitly defined to be a 12th degree polynomial in x(fixing y) here

I mean it is a formal polynomial that ends up being the 0 function(because of identity imposed)

Like how f(x)=x(x-1) is same as f(x)=0 in Z/2

[torn escarp]

It's not formally 12th degree

This isn't like how x^p-x evaluates to 0, this literally is 0 here

[leaden swan]

So is this wrong? Because by this argument for mod 13 you have 13 roots

Or am I misunderstanding the argument

[torn escarp]

sort of, it might be clearer if you compute what the coefficient is of the x^12 term

that way you see the distinction between when the coefficient is 0 or not

[torn escarp]

here's my hint from earlier

[leaden swan]

Ah

mb

[torn escarp]

yeah it's a bit tricky

I guess the nice thing to know in general is:

$$(x+y)^p - x^p-y^p = \sum_{n=1}^{p-1} \binom{p}{n}x^ny^{p-n} = \sum_{n=1}^{p-1} \frac{p}{n}\binom{p-1}{n-1}x^ny^{p-n} = 0$$
since $p \nmid n$, all those terms are divisible by $p$.

[sterile pumice]

Merosity

[torn escarp]

proving that identity of the binomial coefficients shouldn't be too hard if you expand it out as a factorial

[sacred junco]

You are 100% in my class and I pointed out to the teacher yesterday that this was probably a typo

She amended the problem to 4x^2 etc

[torn escarp]

ah nice

my soln:
||substitute y=2x
y^2+25y+43=0
y^2+2y-3=0
(y+3)(y-1)=0
now y=-3, y=1
so x=-3/2, x=1/2
use euclidean algo to find 2^-1 mod 23 I guess||

[sacred junco]

I'm not getting that but I'm on the bus rn so can't show my work

I think going from the factored version to writing down solutions is not allowed or something

The process we learned involves some form of completing the square

Ah wait

Lines 2 to 3 doesn't work

y^2+25y-3 = 0 mod 23 doesn't imply y^2+2y-3

Afaik

[torn escarp]

everything is mod 23, just didn't write it

25 = 23 + 2 and 43 = 2*23 - 3

[sacred junco]

Yes but the y^2 messes with it

You can check on Wolfram that the answer is different

Also shouldn't the sub be giving you 2y^2

Not just y^2?

Ah nvm I forgor how subs work

[tender cedar]

Yeh I saw this yesterday

[sacred junco]

👍

[unkempt smelt]

How do I prove the following: $0 < b_m < 1,$ $m \geq 1$ and $\sum_{m=1}^{\infty} b_m$ converges implies $\prod_{m=1}^{\infty} (1 - b_m)$ converges to a nonzero number

[sterile pumice]

LeftySam

[unkempt smelt]

I get that if you let $S_M = \sum_{m=1}^{\infty} b_m$ and $P_M = \prod_{m=1}^{\infty} (1 - b_m)$ that $P_M \leq e^{-S_M}$

[sterile pumice]

LeftySam

[unkempt smelt]

Does the result follow from this?

[west glade]

yes

[unkempt smelt]

So since S_M converges, say to a limit S, then e^-S_M converges to e^S and thus P_M is bounded and thus it converges?

[west glade]

well you also need monotonicity

[unkempt smelt]

wdym

[west glade]

wait you want to show that it converges to something nonzero

so no, this is not enough

[unkempt smelt]

So how do I do it?

[west glade]

and an upper bound doesnt actually matter. its clearly smaller than 1

[unkempt smelt]

Yeah I get that

So what should I do instead to prove the result?

[west glade]

for example try finding a lower bound

that is nonzero

also I assume you messed up notation and S_M and P_M are not supposed to be the whole infinite series/product and instead just partial?

[unkempt smelt]

Yeah, I did

[unkempt smelt]

I have no idea

[unkempt smelt]

I think a lower bound of P_M is 1 - S_M but I'm struggling to prove this by induction

[unkempt smelt]

Okay, I've got it. Now how does this help?

I.e. P_M >= 1 - S_M?

[leaden swan]

Yea

It should be the number of iterations, I think

https://archive.lib.msu.edu/crcmath/math/math/a/a057.htm

Well that's usually the right thing,no?

99999999 should take more iterations to reach a fixed point than 9

What are you proposing

Well ig it's not strictly true

But it's like a heuristic

Elaborate

[leaden swan]

Ok, ngl

I don't know wtf cares about additive persistence

Because like none of the integrity stuff I am familiar with uses this

And additive persistence sounds like a very weak thing to use for integrity

For checksum and such, the algorithms you use are way more complicated

Because those algorithms need special properties and hence end up being complicated

Like small change in input should have a significant change in output,etc

So like they aren't meant to be computed by hand by humans

[errant otter]

stop spamming your question everywhere, especially in these channels ._.

[green hill]

How can I prove that the cycle 1,3,9,7,1,3,9,7... doesn't break for 3^n mod(10)?

[wooden glen]

Each number is 3 times the previous, modulo 10.

Since you can compute the next term without knowing how you got where you are or exactly what your n is, there's no way the sequence can't repeat, once you've reached a residue you have seen before.

[green hill]

Cheers!

[opal swift]

If 2 is a primitive root modulo p where p is a prime what is the order of 8 mod p? I think we are looking for the smallest n such that 2^3n = 1 mod p, but I don't know how to use the condition on primitive roots here

[wooden glen]

You'll need to work in the multiplicative group, which (as you should know) is cyclic of order p-1 when p is a prime. You're told that 2 is a generator of the group.

[opal swift]

Yeah 2 generates Z_p in this case

[wooden glen]

The multiplicative group is cyclic of order p-1, not of order p.

[opal swift]

By Z_p I mean the group 0, ... p-1 with multiplication mod p

[wooden glen]

So there is an isomorphism between nonzero elements of Z/p under multiplication to all elements of Z/(p-1) under addition, and in particular you can choose an isomorphism that maps 2 in Z/p to 1 in Z/(p-1).

[wooden glen]

That is not even a group -- 0 doesn't have an inverse.

[opal swift]

ah yes sorry from 1, ... p-1. i think it's denoted actually Z_p^*

[wooden glen]

Yes, and I'm telling you it's easier to think about the isomorphic representation of that group as addition modulo p-1.

[torn escarp]

I'm thinking if 3 divides p-1 then you're closer and need a smaller n, otherwise you just need p-1. In other words, ||n=(p-1)/GCD(3,p-1)||

[verbal cedar]

$\ord(2^i)=\frac{\ord(2)}{\gcd(\ord(2),i)}$

[sterile pumice]

nilpotent nix (nix)

[verbal cedar]

the order formula

[wheat tinsel]

how would you guys solve this one

[loud moon]

I'd probably start by noting that (8x^2 - 6x + 8) is positive for sufficiently large x, and then note that as x grows, there eventually can't be that many perfect cubes between x^3 and x^3 + 8x^2 - 6x + 8, which should be enough to enumerate all possible solutions fairly quickly

[wheat tinsel]

ye

it seems thats the standard thing to do

you can bound that polynomial in x by (x+1)^3<P(x)<(x+3)^3 for x>=0

[loud moon]

yeah I can't think of any simpler way

[fossil fog]

When it comes to hyperoperators, would it be correct to say that $\forall n \in \mathbb{N}, 2[n]2 = 4$ ($H_n(2, 2) = 4$)?\
If I'm not misunderstanding anything,\
$2+2 = 2\cdot 2 = 2^2 = 2↑↑2 = 2↑↑↑2 = ... = 4$\
(pentation, hexation, and so on of 2,2 are all 4, right?)

[sterile pumice]

JJCUBER

[lean gust]

whats a biplane

theres no combinatorics channel but this is close enougj

[loud maple]

#combinatorial-structures

[harsh loom]

Do I need any prerequisites of math to learn this?

Or can I jump straight into it?

[loud maple]

Learn what?

[harsh loom]

Number theory?

[sacred junco]

You don't strictly need anything in particular but you'll probably have a hard time if you don't at least have high school algebra down

[loud maple]

There aren't really any prerequisites for starting with 'elementary' number theory.

[sacred junco]

Also basic proof writing is prob recommended

[loud maple]

Right, what I said was assuming that they are decently comfortable with high school mathematics.

[sacred junco]

Yeah it says he's an undergrad makes sense

[harsh loom]

I see thanks guys!

[opal swift]

Is reduced residue system mod n just the same as Z_n^*?

[verbal cedar]

anyone know what this is supposed to say? it seems like there are some typos and im not sure what it should say to make sense

[fervent grove]

Here is one interpretation: Suppose $n$ is a natural number such that $\varphi(n)\mid(n-1)$, where $\varphi$ denotes the Euler phi function. Prove that $n$ is not divisible by $p^k$, for any prime $p$ and natural number $k\ge2$. (Hint: by contradiction, assume that $n$ is divisible by some such $p^k$ and use the multiplicative property of $\varphi$.)

[sterile pumice]

dfoiler

[verbal cedar]

is that true? also, i'm not sure what "multiplicative property of phi" means when we're just doing phi(p^k) for a single prime p. should we instead suppose for contradiction that p^k divides n for k>=2?

this is my attempt, i'm not sure if it makes sense really.

i wonder if assuming n**=**p^k is actually justified by the multiplicative property of phi. because then the principle should supposedly extend to if n is a product of multiple terms of the form p^k. but i feel like you'd still have to do some justifications that q-1 doesn't make things alright for some other prime q, and this approach to the proof might be more straightforward.

[verbal cedar]

i probably have to do a bit more explaining to conclude the proof but i just wanna make sure this approach actually works

actually i think this does sorta make sense. i think the point is that n will actually have to be just n=p for p some prime.

if p is prime then phi(p) definitely divides p-1, so this exercise appears to have us prove the converse

[leaden swan]

Why does phi(n) | n-1 and p^k | n imply phi(n) | p^k-1?

[verbal cedar]

shit you're right. p^k-1 is still from assuming n=p^k ughhh

[leaden swan]

Do you want the solution?

Hint: ||if p^2|n, Think about prime divisors of gcd(phi(n),n)||

||And think what that implies about gcd(n,n-1) (Using fact phi(n) divides n-1)||

[verbal cedar]

p would have to divide the gcd of phi(n) and n.
and then since p divides phi(n) which divides n-1, then p divides n-1.
so n and n-1 are divisible by p. but then p divides n-(n-1)=1, so p divides 1. contradiction.
is that what you had in mind?

this being the full proof
\begin{proof}
Suppose that $\phi(n)\mid n-1$ and $p^k\mid n$ for $k\geq2$.
Then $p\mid n$, and
[
\phi(n)=p^{k-1}(p-1)\mid \phi(n)\implies p\mid \phi(n)\mid n-1\implies p\mid n-1
]
But then $p\mid n$ and $p\mid n-1$, so
[
p\mid n-(n-1)=1
]
Contradiction. Hence, $p^k$ cannot divide $n$ for $k\geq2$.
\end{proof}

[sterile pumice]

nilpotent nix (nix)

[leaden swan]

Yeah

[verbal cedar]

great thank you so much!

[livid birch]

shouldnt this be an iff statement

[livid birch]

if 2 is a primitive root mod p, how can i use quadratic reciprocity to prove that p \cong 3 or 5 mod 8

[west glade]

the other direction is not true. note that a^((p-1)/2) can only be +-1 cause squaring it gives 1 and for each a coprime to p it is one of them. because mod p gives a field, the polynomials x^((p-1)/2) +-1 have at most (p-1)/2 roots each and because in total they have p-1 roots, they each have (p-1)/2. and now finally notice that there arent (p-1)/2 primitive elements, so there will be elements with a^((p-1)/2=-1 and that arent primitive

[livid birch]

gotcha

[livid birch]

any chance you have a hint on this oone

[normal heart]

if 2 is a primitive root mod p then its a quadratic nonresidue

so you use the property that tells you when 2 is/isnt a quadratic nonresidue

[livid birch]

omfg

i forget basic things

ofc that makes sense, being a primitive root means that it literally cannot be a square mod p

thus forcing it to have legendre = -1

and 2 only has legendre symbol -1 mod p if p = 3 or 5 mod 8

it seems so obvious

[normal heart]

haha, sometimes when you're doing too much advanced stuff you tend to forget some basic properties

It's normal

[livid birch]

yeah very that

i overthink sm

[livid birch]

how can i use extended euclidean algo to find integers a,b such that 8 = 12a + 40b

this is asking for what integers is gcd(12a, 40b) = 8

[charred jasper]

how do I solve these? I used hensel's lemma on the first to show thst x had to be one of {3,4,13,14,22,23} but I'm sure there's a better way to conclude than checking each. And I just have no clue for the latter

[charred jasper]

Oh and if I'm understanding you correctly this is a=2p where p is coprime to 40 and b=q where q is coprime to 12 and p, right?

[livid birch]

wdym

a is any integer

[charred jasper]

you want integers such that gcd(12a,40b)=8,yes?

gcd(12a,40b)=4k no matter what integers a, b you choose, so you just need to add an extra common factor of 2 without adding any other factors in common

[livid birch]

oh i see lmao

[charred jasper]

@manic mortar help.

[manic mortar]

Wha

[charred jasper]

this, im extremely lost

I rembered you were in here

[manic mortar]

i reckon on the first one you might as well just check all 6, its much better than 27

and come on you can do some of them in your head easy as pie

In fact

[charred jasper]

Ok so it's obviously not 4 or 5,but 13,14,22,23 are hard to see

Oh but it can only have two roots, and they have to be symmetric don't they

[manic mortar]

23 is -5, but if -5 were a sln then 5 would be but its not

etc

[charred jasper]

right

Yes

[manic mortar]

so it has to be

[charred jasper]

13,14!

Pogged

[manic mortar]

13, 14

not 14! 😂

😂😂😂

[charred jasper]

fuck you

ok but the second is harder

[manic mortar]

ngl idek what you did for the first one to get ur set

so idk how you can do for thr other one either

[charred jasper]

Hensel's lemma is a trick that lets you lift from lower prime powers to higher