Np is that for a competition
#elementary-number-theory
stoic bear
@sacred junco I fell asleep lol
I am pretty sure for your problem, you only need to check if the last digit is divisible by 3 as all the other places represent powers of 12, which already has 3 as a factor
ruby egret
After proving that theorem, the author claims this
Without any proof
Is this a corollary?
If it is, I don't really get how it is
wait I think I got it
swift shard
Let's say
a > √n
b > √n
Then
ab > n
Which is real dumb and really stupid
So we can't have the dumb thing, therefore either a or b is less than √n
ruby egret
ya
swift shard
There's nothing wrong with having
a = b = √n
though, if √n is an integer.
ruby egret
I was thinking more along the lines of min(a,b)^2 <= n <= max(a,b)^2
But proof by contradiction always sounds cool
speaking of proofs by contradictions
every uniqueness theorem proofs that I've seen were proof by contradictions
Aren't there other ways to prove uniqueness ?
He says there is nothing in the proof of theorem 1 that implies uniqueness But, isn't the smallest divisor that isn't one always unique?
So that the entire combination of p_1 to p_k should be unique?
Also, what does he mean by consideration of special cases? To check for some numbers?
broken igloo
suppose that we have two ways to factor n, and n is minimal (integers so we can do this). Choose prime of minimal absolute value. If it appears on one side, mod that prime and get contradiction. Otherwise, divide both sides by that
@ruby egret
well, I guess that's a proof by contradiction
I'm guessing if you count proving that Z is a PID
pick an ideal (a, b, c, d, e...), it's equivalent to (gcd(a, b, c, d, e...))
since gcd is well defined we are done
ruby egret
In the first definition of the symbol
Is it for some A, for all A.
A is a positive number, he says later on
Also what does f/phi mean?
ruby egret
hmm
so the second one and the first one mean the same thing?
Or do they mean the same thing only for large As?
quick furnace
no
big O and small o are different
f = O(φ) can be restated as f/φ being bounded
ruby egret
yeah that makes more sense
light flicker
yeah that's just english
light flicker
What A are you talking about
light flicker
Yes, it's possible that the A could be different for all O's
In the summation too, the A's could be different for all n of the O(1)'s
ruby egret
ok, but then I could also write the summation equal to O(1) right?
ruby egret
🤔
light flicker
Why do you think that
ruby egret
before that, the summation is just O(1) added n times all with possible different As right?
or am I reading this wrong?
light flicker
That's right
ruby egret
So if I have A_1 for the first O(1) and so on till A_n for the last O(1), I could construct an A which is A_1 + A_2 + ... + A_n for an O(1) and that would be equal to the sum?
light flicker
Let's say for example that all of your A's are 1
Then what would A_1 + A_2 + .... + A_n be
ruby egret
n?
light flicker
And is that O(1)?
ruby egret
well by the definition I could say that the right hand side O(1)(assuming the sum is on the left hand side) represents a function, f for which f<n.1 while all the left hand side O(1)s repersented functions g<1 , h<1, ...
Since you said A could be different
then the lhs would have g + h+ ...
which would be less than n
where n is the A when I represent it with O(1)
on the rhs
light flicker
what does n.1 mean
ruby egret
n times 1
light flicker
f is a function of n, n is not a constant
Saying that f < n does not mean that f is O(1) where A = n
For example, if you take f(n) = sqrt(n),
Then it's true that f(n) < n for all n
But for any A you choose, f(n) > A for n big enough
ruby egret
like they said f = O(φ) means f<Aφ , so if I say f = O(1), I mean f<A with A=n
w8 I never said f is a function of n
light flicker
Yeah but it is
ruby egret
because of the sum?
light flicker
because of the fact that you're talking about functions being O(n)
ruby egret
ok I might get it if you could give an example of a function thats not O(1) and say, O(34) at the same time
ruby egret
so if a function is O(1) then it's also O(34)?
Then if it's O(n) why isn't it also O(1)?
light flicker
because n is not a constant
If you let g(n) = n
then O(n) is the same as O(g(n))
You're right
That this is kind of ambigious
Because it's not clear whether or not n is just a constant like you're claiming
or if n is the independent variable of all the functions
But since they never talked about n before this, n doesn't have any value, so it's assumed to be the independent variable
Plus, as you note, if n was just a constant, they would write O(1) and not O(n)
ruby egret
Later in the text the author claims that = between O and o is not symmetric, i.e., o(1) = O(1) is always true but O(1) = o(1) is not always true
Is the first one always true because of limits?
I mean if f/φ approaches zero, then there will always exist an A for which |f| < Aφ, right?
But there always existing an A for which | f | < Aφ does not imply that f/φ has a limit that approaches zero?
Is that the reason?
light flicker
Yes that's true
quick furnace
@patent goblet
patent goblet
Hey ty
quick furnace
yes ok so
the whole "10^n - 1 is divisible by 9 for all n" thing
first off
this is not saying ALL numbers divisible by 9 are expressible in this form
and second
ok i guess time to write up a more detailed proof of the divisibility rule
i'd ask you if you're comfortable with sigma notation for summations but it's likely the answer is no
i can do it w/o that it's just gonna be longer
patent goblet
I'll survive with it or get the general idea, but yeah its rough. I really appreciate this.
quick furnace
so consider a positive integer $N = d_0 + 10d_1 + 100d_2 + \cdots + 10^k d_k$, where each $d_i$ is a digit (i.e. an integer between 0 and 9)
sterile pumiceBOT
Ann:
quick furnace
this is just writing the integer in terms of its digits in base 10 since we care about those
patent goblet
Ok got it.
quick furnace
obivously the sum of $N$'s digits is $S(N) = d_0 + d_1 + \cdots + d_k$
sterile pumiceBOT
Ann:
quick furnace
ad-hoc notation, but w/e
patent goblet
ok following still.
quick furnace
so the divisibility rule for 9 says that $N$ is divisible by 9 if and only if $S(N)$ is
sterile pumiceBOT
Ann:
quick furnace
so to prove that, i'm going to consider $N - S(N)$
sterile pumiceBOT
Ann:
quick furnace
what?
no i don't care whether any of the digits were nines
$N - S(N) = d_0 + 10d_1 + 100d_2 + \cdots + 10^k d_k - (d_0 + d_1 + d_2 + \cdots + d_k) \ = 9d_1 + 99d_2 + 999d_3 + \cdots + (10^k - 1)d_k$
sterile pumiceBOT
Ann:
quick furnace
does this make sense
patent goblet
ahh yes
quick furnace
the coefficient on $d_i$ is going to be $10^i - 1$, which is always a multiple of 9
sterile pumiceBOT
Ann:
quick furnace
so $N - S(N)$, being a sum of multiples of 9, is itself a multiple of 9
sterile pumiceBOT
Ann:
patent goblet
sigh im still really struggling to follow along
patent goblet
7362
7000 + 300 + 60 + 2 this was my plan of attack earlier.
quick furnace
uh
patent goblet
i decomposed that into 7 x (999 x 1)
quick furnace
ok wait no like
patent goblet
- 3 x (99 + 1)
patent goblet
im having a really hard time to understand without a concrete example.
quick furnace
you can write 7362 as 7(999+1) + 3(99+1) + 6(9+1) + 2
patent goblet
yeah
quick furnace
which can then be rewritten as 7*999 + 3*99 + 6*9 + (7+3+6+2)
quick furnace
$7362 = \underbrace{7 \cdot 999 + 3 \cdot 99 + 6 \cdot 9}{\text{multiple of 9}} + \underbrace{7+3+6+2}{\text{digit sum}}$
sterile pumiceBOT
Ann:
patent goblet
this is what I needed to see thank you. The rest of the formal definition stuff, I really have no idea whats going on. All i had to work with was their short example, and some definitions I could find online.
I tried something like that
quick furnace
yeah that's uh
patent goblet
so basically, due to the digit sum being divisible by 9 and the multiple of 9 section, we can ascertain if its divisible by 9
sterile pumiceBOT
Koray:
patent goblet
im just trying to understand how that works in respect to the example
Or understand the notation I guess.
quick furnace
if you want to connect that general form to your specific example
k = 3
d_3 = 7
d_2 = 3
d_1 = 6
d_0 = 2
patent goblet
ahh ok.
gah sec
7362 = 7000 + 300 + 60 + 2
N = 7(1000) + 3(100) + 6(10) + 2
N = d_3(1000) + d_2(100) + d_1(10) + d_0(1)
S(N) = d_3 + d_2 + d_1 + d_0
N - S(N) = [d_3(999) + d_3 + d_2(99) + d_2 + d_1(9) + d_1 + d_0 ] - [ d_3 + d_3 + d_1 + d_0]
N - S(N) = [7(999) + 7 + 3(99) + 3 + 6(9) + 6 + 2 ] - [7 + 3 + 6 + 2]
N - S(N) = [7(999) + 3(99) + 6(9) ]
N - S(N) = 9[7(111) + 3(11) + 6(1) ]
N - S(N) = 9[777 + 33 + 6 ]
N - S(N) = 9[2[(17) * 2(12)]
N - S(N) = 9[2(17) * (2^3)(3)]
really sorry for being so slow.
@quick furnace thank you. I really appreciate it, I really needed some guidance there. I know its weird that I need to go through a problem like that, but it really helps me figure out whats going on.
Makes sense now
(10^(n) -1)d_n
patent goblet
So per power 10 instance, (1000) + (100) + (10) + (1)
You are multiplying each power 10 instance by the value of the digit instance, ; d_3(1000) + d_2(100) + d_1(10) + d_0(1)
By converting the power 10 instance into a power (9 + 1) instance, one can ; d_3(999) + d_3 + d_2(99) + d_2 + d_1(9) + d_1 + d_0
create additional respective digit instances.
This results in the creation of several divisible by 9 instance terms. ; 9(7(111) + 3(11) + 6(1)) + 7 + 6 + 3 + 2
Now divisibility solely requires the checking of the separate added digit 9(7(111) + 3(11) + 6(1)) + 18
instances. 9(7(111) + 3(11) + 6(1)) + 9(2)
18 is divisible by 9 9((7(111) + 3(11) + 6(1)) + (2))
light flicker
Try it out
ruby egret
Trying some other theorems first
depending on the answer, it might move up or down the list :3
craggy solstice
use definition of mod to prove
ruby egret
I never said I'm having trouble proving it
ACTUALLY
I can't prove the second one
waaah
w8 don't tell me yet
aright
how do I show ac is congruent to bd(modm) ?
I'm stuck
If use m|(a-b) and m|(c-d) for
m|(a-b)(c-d)
I get two extra junk terms that I can't get rid of
I see no other way to bring an m|(ac-bd)
light flicker
You have more problems than that
because if you multiply it out, you get ac + bd which is not what you want
ruby egret
yes
a generous hint would be appreciated
linear combinations of (a-b)(c-d) isn't working for the same problem
w8 a min
linear combinations of (a-b)(c-d) and (a-b) cancels some terms
meh I got nothing new
light flicker
You have that both m|(a-b) and m|(c-d)
so you don't need to multiply the two together to get something divisible by m
m|a(c-d) for example
plain fable
you can write it, but it might just be wrong
ruby egret
I did not understand the second para
This is from the proof of Euler's theorem
Why can they assume that? Does this have anything to do with least residue theorem?
light flicker
assume what
light flicker
we need more context, what's a
plain fable
I think a just means any of a_1, a_2, ... a_phi(m)
actually nvm
that doesn't make sense
ruby egret
yeah I've been trying
time to plug in numbers
If a is relatively prime to m, then the remainder left when I divide a with m is also relatively prime with m?
And since the remainder is less than m, it must be one of those a_1 , a_2, ... ?
last parcel
hello, how can I prove that the only solution to yx² + y^3 = 2x^3 is x = y ?
for x, y positive integers
torn escarp
lame idea maybe, you could try y=x+z and then try to prove z=0
aha ok I think I got it
by plugging in y=x+z we end up with,
$z(4x^2+3xz+z^2)= 0$
sterile pumiceBOT
Merosity:
torn escarp
either z=0 in which case we have nothing to prove or z!=0
so let's assume z isn't 0 and so we must have that
$4x^2 +3xz+z^2=0$
sterile pumiceBOT
Merosity:
sterile pumiceBOT
Merosity:
torn escarp
since squares are either 0 or 1 mod 3, the only solution is that x and z are divisible by 3
so if we plug in x=3x' and z=3z' we end up with
the exact same equation again
since the 9s factor out entirely
and so it is a case of infinite descent
which is our contradiction and we're done
last parcel
thank you
torn escarp
fun problem thanks
craggy solstice
ok im just starting out but how do i solve things like if x|y find all x satisfying
i am solving a prob
and it reduces down to n+1|2n
=>n+1|n-1
ok it seens like there are no solutions as there seems no possible way thats possible
but how can i be concrete
like in other probs
torn escarp
it sounds a little too broad what you're asking, can you show me some concrete example questions
craggy solstice
i gave an example of find all n such that n+1|2n
it becomes n+1|(n+1)+(n-1)
n+1|n-1
now its impossible for such a thing to happen
but what about other problems like
find all x :-x-3|x³-3
basically asking how to solve these type of problems
@torn escarp
torn escarp
I guess I just kind of play around with them inside of gcd functions in steps until I get it to something that's relatively prime, basically like what you're doing
craggy solstice
hmm
torn escarp
like that n+1 | 2n I would write like,
gcd(n+1, 2n) = gcd(n+1, n-1) = gcd(2, n-1)
seems like n=1 is then a solution
craggy solstice
can you do the second one
torn escarp
is the sign on that correct or is it supposed to be x-3
craggy solstice
well i reduced the second one to
hcf{(x-3),x(x-1)(x+1)}
yea
its just x-3
sorry
torn escarp
both of the things you said were contradictions I'm just tired and confused
torn escarp
I got it I just thought you said you already solved it
torn escarp
how'd you do that
craggy solstice
subtract x-3 from x³-3
torn escarp
I see
I guess I am thinking of subtracting it x^2 times to kill the cube
x^3 -3 - x^2(x-3) = 3x^2-3
repeat again but 3x times
craggy solstice
yea so gcd{(x-3),3(x-1)(x+1)}
torn escarp
3x^2 -3 - 3x(x-3) = 9x-3
craggy solstice
ok wait so gcd(a,b)=gcd(a,b-qa)?
torn escarp
should be, I'm actually like barely conscious at this point I need to go to sleep
torn escarp
I'm gonna brush my teeth and maybe look but good luck
craggy solstice
nah nah
sleep >>>
tomorrow
@torn escarp hey it seems like i got it
i have followed everything you said
and it reduces to gcd((x-3),(23))
now 23's prime
thus x-3=1 and x-3=23
x={4,26}
seems like
it
wait i got another thing
let t=x-3
t|24
after some work
now its done
so i am wrong
ok
amber basin
So i've developed a proof for the first half of a problem, but this second part is really bugging me. Suppose we have $$x\equiv b_1 (mod; m_1) \qquad x\equiv b_2 (mod; m_2)$$ I need to somehow show that, if a solution exists for the system, that it is unique modulo $$lcm(m_1,m_2)$$
This has been my approach, but I don't feel like I'm going anywhere, I noted that we can express all incongruent solutions, for some integer k as $$t_0+\frac{m_2}{(m_1,m_2)}k$$
Then, I plug this solution, assuming it exists, back into the first congruence in the system.
$$x=m_1\cdot t +b_1=m_1\left(t_0+\frac{m_2}{(m_1,m_2)}\right)\equiv $$
sterile pumiceBOT
wazabear_notabear:
obtuse solstice
silver solar
Now do Dirichlet's theorem
light flicker
Now show that there are arbitrarily long sequences of primes in arithmetic progression
craggy solstice
lmao
silver solar
G r e e n - T a o
shadow steeple
is there a name for a number p such that the first n digits of p is a prime number for all n?
torn escarp
sounds like numerology
broken igloo
@shadow steeple https://en.wikipedia.org/wiki/Truncatable_prime
sacred junco
if there is a nice way to find 10^10 then we are done
cause 10^5 is doable
wait nvm
light flicker
The problem is to show that $10^{50} + 1 \equiv 0 \pmod {7019801}$
sterile pumiceBOT
Zopherus:
light flicker
7019801 is prime
sacred junco
yeah
can we conlude something knowing that 10^100 \equiv to 1 mod big number AND 10^100 \equiv 1 mod 101?
light flicker
7019800 factorizes as 2^3 * 5^2 * 35099
So if we can show that the order of 10 is not 35099, that'd help, but that doesn't seem easy
light flicker
@supple furnace help
light flicker
I've never read it, but I've heard some decent things about it
north pendant
what's your recomendation
light flicker
Depends how much abstract algebra you know
north pendant
not a lot
light flicker
It wouldn't be a terrible idea to learn some algebra first
If you plan on doing more number theory stuff, you have to know algebra
north pendant
what do you recommend for that
light flicker
Dummit and Foote is the usual recommendation
There are a lot of algebra books honestly and most of them are fine
north pendant
ok, thanks
supple furnace
@light flicker I sort of doubt that there’s a good approach. One could try to mimic the 641|2^32+1 idea, but I don’t think it’ll translate well.
light flicker
Yeah okay I'm not missing anything then
static sparrow
what if F is infinite? you're not managing infinite subsets in there
and why is this in #elementary-number-theory 
and you're talking about a reunion of elements of F which in general doesn't make sense
when in doubt, you can always ask your question in one of the questions channels
and also, read #❓how-to-get-help
sterile pumiceBOT
Anyone_Someone2018:
sacred junco
Yet i don't know how to prove if it is true for all such set of liars.
Any hint would be nice
sterile pumiceBOT
Anyone_Someone2018:
broken igloo
consider what happens when you multiply two together
@sacred junco
Then from there it's easy to get invertibility
pliant surge
This is an example of a ring, could someone explain the meaning of "pointwise" in this example?
hollow bramble
like addition is defined by (f+g)(x)=f(x)+g(x) kinda thing
pliant surge
so would fg(x) = f(g(x)) be a pointwise operation?
pliant surge
ah i see
pliant surge
ahh thanks a lot 👍
sterile pumiceBOT
Anyone_Someone2018:
velvet meteor
How do you prove that the lcm of 2, 4, 6, ... , 2 *N is at least 2^N ?
If that's the case, which I think is
velvet meteor
Ok but then how do you prove that knowing what you said ?
I'm not studying math, so although it seems intuitive, I can't prove it
Also, it may just be wrong, what I said
sterile pumiceBOT
rudy:
velvet meteor
Well this is trivial, the real question is then to prove that
$lcm(1,2,3,...n) \geq 2^{n-1} $
is true
sterile pumiceBOT
Life Is A Hoax:
sacred junco
Yes. It’s simple enough.
velvet meteor
Really ? Because I don't see how to prove that
I looked online but I can't seem to even find what you just asserted
broken igloo
induction probably doesn't work too well
broken igloo
well my lower bound is n/2*n/3*n/5*n/7*...*n/p where p is the biggest prime < n...
light flicker
Yeah idk about this problem
We can show it just be true asymptotically by showing it's related to prime number theorem
supple furnace
Using the binomial coefficients trick, it’s greater than n((n-1)Cfloor((n-1)/2))>2^(n-1) because there are n terms in the form ((n-1)Ck) and we know that ((n-1)Cfloor((n-1)/2)) is largest.
ruby egret
What does he mean in that last sentence?
"The excess of the actual over the approximate values can be accounted for by the general
theory."
Does he mean that ,for example, the extra .159..... for the first case can be calculated by some theory to be introduced later?
broken igloo
probably
supple furnace
It’s a PNT reference, but note that even PNT isn’t that accurate in the asymptotics of (pi(x)-x/log(x))/pi(x). The Riemann hypothesis would be a huge improvement, getting us within O(1/sqrt(x)) in error.
ruby egret
That last step
How did he get this?
What he did would suggest that 2+4+...+2^N < 2^(N+1) , right?
Right and I can prove that with geometric progressions
smh I'm so slow
ruby egret
What he did there is proof by induction, right?
light flicker
Not really no
ruby egret
But 2.2.1 is true for n=1, he said that "suppose that" 2.2.1 is true for n, he then proved in 2.2.2 that it is true for n+1, so isn't that proof by induction?
I mean it does conclusively prove 2.2.1
light flicker
Ah yeah I guess it is induction
ruby egret
After proving this
The author says this
But if I let q = (2^2).3.5....p + 1 instead in theorem 11
Deosn't that prove that there are infinitely many primes of the form 4n + 1?
ruby egret
ok
So it's not divisible by any of the primes before and including p , but it might be the product of two numbers (4m+1) and (4n+1) where at least one of them is between p and q and is a prime?
ok I got it
light flicker
Well you should understand what they're doing first
ruby egret
It could be a product of numbers of the form 4n + 3
light flicker
Yeah
sacred junco
I don't understand how this implication follows
@light flicker
~~ikik im pinging a specific helper but please help me 
~~
Ah nvm
It followed from a previous statement
ruby egret
How much do I need to know to understand a proof of or to be able to prove Dirichlet's theorem?
light flicker
Well from the proof I know
It's just some basic analysis
And a little group theory I guess
sacred junco
Suppose I have $n=p_1^{\alpha_1}\cdots p_n^{\alpha_n}$ where $p_1,\dots,p_n$ are primes with $p_1<\cdots<p_n$ and $\alpha_1,\dots,\alpha_n$ are all positive integers, how do I write out all the divisors in increasing order?
sterile pumiceBOT
christina:
sacred junco
Is there an easy method that I can do to avoid not including an divisor?
And obviously not trying out all combinations and sort them
torn escarp
interesting question, I'd be curious to see if there's some way to do it without just writing the divisors then sorting them after the fact
sacred junco
Hello flower guy
torn escarp
lol
sacred junco
I asked this because I was solving for integer solutions for an equation with 2 variables, but I forgot to list 9 as a divisor of 36
torn escarp
in that case it's good to know the number of divisors is going to be
sacred junco
ah right
torn escarp
$\prod_{i=1}^n (\alpha_i + 1)$
sterile pumiceBOT
Merosity:
torn escarp
really can't think of anything better than writing out a little table of exponents 0 to alpha and filling it out
so like if I wanted divisors of 12 I'd fill this out:
torn escarp
or if I wanted something like say, divisors of 60 then take those 6 entries and line them along a new axis with 5^0 and 5^1 again
sacred junco
Ohh
So you can just multiply every entry by 5 to get all the other divisors
Right
Also I realized that I used n as the number and the number of prime divisors
torn escarp
yep
grave bough
Is there an integer n so that the sum of its digits is equal to the sum of the digits of n^2, and the latter sum exceeds 2019
light flicker
What have you tried?
grave bough
I don’t get what it’s asking for, I’m assuming you do something modulo 9
light flicker
What don't you get?
light flicker
Yeah
grave bough
Hm okay
light flicker
They just specify one, doesn't really matter though
grave bough
Okay, so n my guess is that n is divisible by 9 because modulo of it would remain the same
That’s all I’ve thought of
So would it just be like 229 9s in a row?
Since that would sum 2025
grave bough
Mod 3?
grave bough
1?
light flicker
yeah
grave bough
Well the question is just asking whether there is an integer or not right? So 229 9s in a row would work right?
Oh wait how do I prove that the sum is still the same
light flicker
Yeah
All you've done is shown that the mod 9 value stays the same
27 has sum 9, but 27^2 has sum 18
grave bough
Mhm, I’m not sure how to prove it but it’s right right? I’ve only tested a few. Give me a sec to think
light flicker
That your answer works?
grave bough
Well how do you prove it?
grave bough
Yes I see the pattern
But how do I ensure that the pattern continues?
Like don’t I need to prove it?
grave bough
Mhm, do I need to use mods?
light flicker
no
grave bough
Mhm I think I get it?
So when you multiply it out you get like x^2-2x+1 so x(x-2)+1. If x is like a power of 10 then the pattern follows
That was a bad explanation uh
grave bough
Thank you, I think I understand
tropic veldt
Hello, I have been stuck on homework problem on Diophantine Equations, and I was wondering if you guys could help
if anyone is interested. I know how to do 1st part, but unsure how to do 2nd
supple furnace
Consider ab-a-b+k with 0<k<ab+1. Take the solution x in {0,...,b-1} to ax=-a+k mod b and the solution y in {0,...,a-1} to by=-b+k mod a (which exist since a,b are invertible by the (a,b)=1 condition). Then ax+by is congruent to -a-b+k mod ab by the Chinese Remainder Theorem and is at most 2ab-a-b. Since k is positive and at most ab, ax+by is either k-a-b or ab-a-b+k. The latter finishes and the former gives a solution as well (take a(x+b)+by). Then if k>ab, we can take a solution (r,s) to ax+by=ab-a-b+k-abfloor(k/ab) and take (r,s+afloor(k/ab)).
patent goblet
Im confused by what they mean here
What are they talking about in regard to involution?
i know the basic definition of a function that is its own inverse, but how does that at all relate to powers and roots?
nevermind im an idiot.
They literally just described it.
Just never heard of it like that.
ruby egret
Suppose I have a= b modn
Is there any specific number x I could always multiply a with so that
ax = (n-b) mod n ?
quick furnace
-1
sacred junco
if n > b, then x= (n-b)/b
if n < b, then x = (n-b mod n)/(b mod n)
x can be anything if a = 0
neat kraken
hey everyone, I was wonderig if I had
$11 \equiv 55 \pmod{13}$ if I could write this at $1 \equiv 5 \pmod{13}$
sterile pumiceBOT
finkbeca:
sterile pumiceBOT
Ann:
quick furnace
so 😬
ruby egret
d = (a,b)
How do they know that d doesn't divide z instead of c?
oh is it because x and y can be chosen so that z = 1?
and I'm guessing d|c implies d<=c which combined with the previous inequality gives c = d?
zzz why can't hardy get a bit more wordy
ruby egret
lmao
it's gh hardy's number theory book
looks pretty old , idk
is this the same number theorist gh hardy who worked with ramanujan 🤔
wild zinc
yes
ruby egret
sooo
I know it seems kind of obvious
but how do I prove this rigorously?
smh
nvm I did it
I'm so dumb
why is h+1 <= h' ?
suppose n = 5, then two consecutive terms are 1/4 and 1/3
but 1 +1 is not less than or equal to 1
light flicker
how are we supposed to know what $\mathfrak{F}_n$ is
sterile pumiceBOT
Zopherus:
ruby egret
h'/k and h/k
dammit
I always miss the little details
I thought he wrote h'/k' and h/k
light flicker
I mean
the fact that the theorem is about fractions with the same denominator should give you a hint
That your thing is not a counterexample
light flicker
\begin{Theorem}
For $p$ prime, the multiplicative group $\mathbb{Z}/p\mathbb{Z}^*$ is cyclic
\end{Theorem}
sterile pumiceBOT
Zopherus:
light flicker
\begin{proof}
Let $\psi(d)$ be the number of elements of order $d$ in the group for $d \mid p -1$. Then, we use the fact that the equation $x^d \equiv 1 \pmod p$ has d solutions to say that $$\sum_{c | d} \psi(c) = d$$
Using the mobius inversion formula tells us that $$\psi(d) = \sum_{c |d} \mu(c)d/c$$
You can check for yourself that the right side of this equation is exactly $\phi(d)$ which means that $\psi(d) = \phi(d)$ and in particular, we have that $\psi(p-1) = \phi(p-1)$
\end{proof}
sterile pumiceBOT
Zopherus:
ruby egret
Okay another question from my same previous proof
How is $\frac{h}{k-1} < \frac{h+1}{k}$
sterile pumiceBOT
Abrar:
ruby egret
nvm
sacred junco
Imagine we have a sequence of integers like
1,2,3,5,3,4
and we take the absolute value of differences f(x+1)-f(x) until we have one digit which is 0,1. Give a formula for the numbers that follow this sequence
unkempt nova
so I've written the general solution for a Diophantine equation, but I've written "for some k ∈ Z," but isn't it supposed to be "for all?"
I'm not sure if I have to fix it or not
Am I making sense?
broken igloo
for some is okay
torn escarp
if you think it sounds ambiguous I'd just change it honestly, "for some" can give a kind of vague impression that it only works for some subset of Z or for some single specific one.
no reason to risk being misunderstood if you yourself don't fully feel confident in it
ruby egret
How does that imply that (r,s) is 1?
light flicker
Think more about it
ruby egret
If (r,s)=d , then d|(sh+rh') => d|h" and similarly d|k" which means d must be 1? @light flicker
light flicker
Yes
ruby egret
I have no idea what they are trying to do here. Can someone help?
w8 lemme give context
x,y,x',y' belong to the fundamental point lattice
Are they trying to denote the denominator with $\Delta$ and saying that it must divide all of a,b,c and d in 3.6.2?
sterile pumiceBOT
Abrar:
ruby egret
Hard to tell whether $\Delta = ad - bc$ is the definition or $\Delta = +- 1$ or both
sterile pumiceBOT
Abrar:
ruby egret
It's probably the denominator
If x',y',x and y all have to be integers, I get how the denominator must divide a,b,c and d, but what does the (1,0) and (0,1) thing have to do with this?
alpine jasper
i break this problem into four cases, does what i'm doing make any sense?
(repost from one of the question channel)
ruby egret
alright I've been thinking about this for the last 30 mins and I can't seem to figure out where the -1 and +1 came from in the denominator of that theorem
magic violet
alright I am not 100% sure if to put it here, in #proofs-and-logic or #advanced-number-theory but I'll give it a shit here
"assume 15 whole, positive numbers, prove that without using each number more than once, using multiplication, subtraction and addition, you can create a number divisable by 1000 with nothing left over
what is the smallest amount of numbers that will satisfy that requirement"
This has to work for every set of 15 numbers, in case that wasn't clear in the translation
not a clue how to even begin to be honest, contemplating proving using a python script but i dont think they would approve of that
stoic bear
So you are trying to prove it possible for Al sets of 15 numbers? What does the smallest amount of numbers part mean?
magic violet
After proving it for 15 numbers, the question wants you to go back and try to work out the smallest N for which it is possible, so sets of 8, sets of 10, etc @stoic bear
light flicker
Are you allowed to use parentheses
light flicker
Hm, I have a way to do it with 11, but I don't think this is optimal
magic violet
@light flicker this is not for the numbers between 1 and 15, if it was it wouldve been easier
with parentheses you can do it with 7, (2)(5)(7+3)(6+4)
without i dont think you can do it with less than 15 because of prime breakdown
however in this question you need to prove it for any 15 numbers
light flicker
I know
magic violet
oh
magic violet
How? and how do i prove it even for 15?
like
this question kinda fell on me out of nowhere, i have no clue how to even start proving that you can do it with 15, let alone with less
light flicker
Once you figure it out for 15, figuring out how to minimize to 11 becomes straightforward
magic violet
🤔
light flicker
The hint is that 1000 = 2^3 * 5^3
magic violet
i thought it had something to do with prime breakdown, but still i have no clue how to start proving that, and especially because of the addition and subtraction
light flicker
First try to get something that's a multiple of 2
then multiply three multiples of 2 together to get 2^3
repeat for 5
magic violet
because for example if i get 15 prime numbers (let's say the first 15 for example) i def cant do it with just multiplication, and to prove it's possible with any 15 numbers is a lot harder and kinda out of my league
getting 3 multiples of 2 is easy
any odd number when adding to an odd number will result in an even number, an odd and even number when multiplied together will result in an even number (by definition) and 2 even you can either multiply or add
but getting multiples of 5 is a lot harder, especially getting 3 of them
magic violet
I need to go by % mathematics, which essentially boils down the question to something like this
(starting with 15 numbers, 6 go towards creating the 2's multiplication)
create with 9 numbers 5^3
which is boiled down to create with 9 numbers between 0-4 5^3
which is boiled down to create with 3 numbers between 0-4 5 (or 0)
problem is i know it's possible, i dont know how to prove it
also im not sure how you did it with 11 if what i did so far is correct, that means you hvae 2 numbers between 0-4 to create 5 which idk how it's possible
light flicker
Are you sure you can't use any of the numbers in the 2's multiplication
magic violet
I am not sure how i can prove i can always use them
light flicker
What does it mean to use them
magic violet
that to break them down to prime factors they contain a multiplication of 5
as i understand it at least
light flicker
That's not quite the right idea
magic violet
🤔
magic violet
I've been working on this question for 3 hours, i have no clue how im supposed to use them except for a prime breakdown containing 5 since that's how you check if a number is divisible by another number
and i cant use the 9 numbers to contain 2 because i dont know just based on the remainder that it's odd or even, so i dont know how to treat them
light flicker
This is not an easy problem, 3 hours is a pretty short time. Just try to formalize your intuitive ideas to work with them
patent oak
magic violet
@light flicker hey, i just continued to work on it for the past 3 hours but i still have no clue how to even actually prove that it can be done with 15
assuming 3 random numbers between 0 and 4 i dont know how to prove they can always create a 5 (or a 0), it makes sense, no idea how to prove it
and even if i managed to do that, i still dont have a clue on how to use the first 6 numbers for another 5
My background in number theory is still super limited
fervent crest
So the chinese remainder theorem asserts that if $n_1,\dots,n_k$ are pairwise coprime positive integers greater than $1$, $a_1,\dots,a_k$ are integers such that $1\leq a_i<n_i$ for any $1\leq i\leq k$, then there is a number $x$ such that $x\equiv a_1\pmod{n_1}$, $\dots$, $x\equiv a_k\pmod{n_k}$ and for any two $x_1$ and $x_2$ satisfying this, we have $x_1\equiv x_2\pmod{n_1\cdots n_k}$. But how do I find this $x$?
sterile pumiceBOT
Whoever:
wild zinc
extended euclidean algorithm
first do it on n1, n2 to replace the two congruences with one mod n1n2
and then repeat until you just have a single congruence left
fervent crest
wait how do you replace two congruence with 1 congruence?
stuck lintel
I thought part of CRT was the method that you can use to combine two congruences
The way I like to think about it is if you have x=a (mod m) and x=b (mod n) where (m,n)=1, you can find some number y such that y is a multiple of n and congruent to a (mod m), then you do the same for the second congruence, and you add the two together
wild zinc
extended euclidean algorithm gives you solutions x,y to xn1 + yn2 = 1, so a2n1 x + a1n2 y = a2 (mod n2) and a1 (mod n1)
ruby egret
How do they know that N does not divide a^m ?
N could be q(p^m) where p and q are primes, in which case p|a and p is not a prime factor of b
Or does that just not matter?
nvm I'm an idiot
stark vapor
Anyone interested in ciphers?
I had what I believed to be a substitution cipher
3 4 1 5 1 4 6 20 13 6 15 12 15 2 18 9 3 11 5 22 15 5 24 26 26 15 21 24 18 3 13 3 22 23 9 22 10 24 3 10 24 12 12 3 11 1 3 22 15 3 18 24 3 14 22 10 9 19 3 15 5 3 9 2 26 15 21 10 24 20 3 5 15 11 3 19 15 3 15 11 1 18 24 22 19 15 11 26 15 21 18 19 21 3 3 3 19 19 9 2 11 15 22 26 15 21 10 24 20 3 2 24 9 12 3 5 6 21 22 26 15 21 23 15 21 12 5 11 15 22 6 3 18 3 24 5 9 11 1 22 10 9 19 13 3 19 19 24 1 3 22 10 3 11 23 15 21 12 5 26 15 21
I converted it to base 26, because otherwise things like frequency analysis would fail with 1
c d a e a d f t m f o l o b r i c k e v o e x z z o u x r c m c v w i v j x c j x l l c k a c v o c r x c n v j i s c o e c i b z o u j x t c e o k c s o c o k a r x v s o k z o u r s u c c c s s i b k o v z o u j x t c b x i l c e f u v z o u w o u l e k o v f c r c x e i k a v j i s m c s s x a c v j c k w o u l e z o u
And playing around with the letters, the closest I can get is:
e c g d g c b v m b o l o f r i e n d t o d a y y o u a r e m e t w i t h a e h a l l e n g e t o e r a e x t h i s e o d e i f y o u h a v e d o n e s o e o n g r a t s o n y o u r s u e e e s s i f n o t y o u h a v e f a i l e d b u t y o u w o u l d n o t b e r e a d i n g t h i s m e s s a g e t h e n w o u l d y o u
Notice how.. with what seems to be the word "success" the e and c are the same .w.
so either my assumption that this is a substitution cipher is wrong and it's a good encryption, or my assumption is right .w. and the guy sucks
<@&286206848099549185> eyyyy, I can ping now 
stoic bear
Looks fun will play around later
shadow steeple
does it being readable mean that it's decrypted, or does it need to be perfect?
north orbit
How many of the first 100 positive integers are divisible by at least 3 distinct primes?
winter bear
hmm
north orbit
Any quick way to solve that in less than 45 seconds?
I see that the greatest prime can only be 13
winter bear
so notice 3* 5* 7>100
actually that doesnt help
so 13 then ur right
so fix the first 2 ig
north orbit
Yeah so there aren't too many cases to consider
winter bear
(2,3) leads to the third being: 5,7,11,13
(2,5) leads to 7
and thats all i think
so thats a total of 5?
north orbit
Answer is 8 apparently
winter bear
so (2,2) leads to 3,5,7,11,13,17,19,23
no way its 8 tho lol
its way more than 8
its 8 with this case alone lol
north orbit
wait distinct primes
winter bear
oh right
north orbit
So squares don't add any then?
north orbit
Alright thanks
Generally how do you check your answer to make sure you included all cases?
winter bear
i mean, just look over the cases and think about if u missed anything ig, its kinda hard to have a general method for that
magic violet
my problem is to prove that you can create a number divided by 1000 with any 15 numbers using multiplication, subtraction and addition
so far i have this
2^3 is easy with 6 numbers, 3 pairs of 2 numbers, odd and odd add them together, odd and even or even and even and multiply them
i also managed to prove that you can create 5^3 with the other 9 numbers, basically do module mathematics and make it 3 triplets and then you have 0-4 which together need to create a 5, if 2 are identical subtract one from the other, if all 3 are different it either has 1 and 4 or 2 and 3 in which case you add them together, that far was fairly easy, however i have no idea how to go less than 15, im guessing that to def make sure that you can a number that is divisible by n you need more than n/2 numbers (that's a guess because i tried to create 4 with 2 numbers and failed)
but the second part of the question is to show that you can do that with with less than 15 numbers
and ive been trying to go under 15 numbers for a few hours now and i have no clue where i can go lower except for one place
instead of the 3 pairs to create 2^3 i can instead do it by just creating an 8 with 5 numbers
which puts me at 14
but i have no idea how i can go lower than that, even though im pretty sure you can go lower
shadow steeple
what constraints are there on those 15 numbers?
magic violet
Any whole positive number, cannot repeat and you cannot use each number more than once @shadow steeple
sacred junco
how can I know for which x, x^(ln2/ln3) is equal to an integer?
light flicker
k^(ln3/ln2) for any integer k
sacred junco
genius! thanks
ruby egret
is this proof correct?
It's an if and only if statement but he doesn't prove it both ways
wild zinc
other way is much simpler
if (n-1)! = -1 (mod n) then n and (n-1)! are coprime, so there are no factors d of n with 1 < d < n so n is prime
which is probably why it was excluded
sterile pumiceBOT
Abrar:
ruby egret
Because it can be broken down into $\sigma(2)$ multiplied n times?
sterile pumiceBOT
Abrar:
light flicker
multiplicative doesn't mean what you think it means
quick furnace
magic violet
Alright so if anyone can make sure my proof is good
problem: figure out the least amount of numbers that you can guarantee a combination of that will be divisible by 1000 with the operations multiplication, subtraction and addition
My solution:
go by 1000 = 10^3, Go with the fact that if any 2 numbers share a last digit (or share the 9-digit) it can be completed together to a multiplication of 10,
if we go by trying to avoid creating any 10's for as long as possible, we'll go like this ( i am just typing the last digit obviously)
1, 2, 3, 4, 5. any additional digit will create a multiplication of 10
we can add two 5's and create only 1 more 10, additional 2 5's, and then we have
1 2 3 4 5 5 5 5 5 and we have 2 10's, any additional digit will create a third 10
QED 10 digits is enough
@light flicker if you can check my proof ill appreciate it a lot
proved by worst case scenario
ruby egret
i didn't get your problem statement. Is that a typo?
coral igloo
What's #elementary-number-theory ?
silver solar
The study of integers and their properties
broken igloo
Elementary number theory; study of the integers, congruences, prime numbers
Channel description
limber rapids
Hello hello, I'm having troubles with a math proof which involves fermat's sum of two squares. The question is: Suppose that p is a prime and p is congruent to 1 (mod 4). Show that it is possible to write p^2 as the sum of two positive squares.
I (think I) understand how to do fermat's sum of two squares in practice, but the theory still deludes me a little bit. I'm not entirely sure how to get started beyond squaring p and trying to go from there. I was directed to come and ask here
broken igloo
ah it has something to do with (u+iv)(u-iv) I guess
tawdry scaffold
This is probably the wrong channel, buuuuuuut...
Someone tell me these roots only somewhat resemble a limacon!
silver solar
What's the polynomial
tawdry scaffold
$x^{17} + x^{16} + x^{15} + x^{14} + x^{13} + x^{12} + x^{11} + x^{10} + x^9 + x^8 + x^7 + x^6 - 63 x^5 + 129 x^4 - 111 x^3 + 49 x^2 - 11 x + 1$
sterile pumiceBOT
Jythro:
silver solar
Interesting, where did this strange polynomial come from?
amber basin
I'm stuck on the following problem. Consider $m,n$ such that $(m,n)=1$, what is the largest integer $m$ such that $n^{12} \equiv 1 (\bmod ; m)$
So I've found that the possible primes in the prime factorization of $m$ must be $2,3,5,7,13$ but now I'm having trouble determining the maximum powers for each.
sterile pumiceBOT
wazabear_notabear:
amber basin
,, \begin{align*}
n^2 &\equiv 1 (\bmod ; 4) \Rightarrow n^{12} \equiv 1 (\bmod ; 4) \
n^4 &\equiv 1 (\bmod ; 8) \Rightarrow n^{12} \equiv 1 (\bmod ; 8) \
n^8 &\equiv 1 (\bmod ; 16) \Rightarrow n^{12} \equiv 1 (\bmod ; 16)
\end{align*}
sterile pumiceBOT
wazabear_notabear:
amber basin
Above is just the example for looking at power of $2$, and my gut tells me that $2^4$ will be the max, but I don't know how I would go about actually proving that, same with the other powers for the primes.
sterile pumiceBOT
wazabear_notabear:
light flicker
Well first, note that the condition that (m,n) = 1 is unnecessary
if (m,n) > 1, then it can never be the case that n^12 = 1 (mod m)
amber basin
hmm, why is that, am I missing something trivial here?
light flicker
Not trivial, think about it for a little
young ginkgo
(m,n)=1 is gcd =1? if n=2,m=3, n^12=4096 and 4095 is a multiple of 3 so n^12 is 1 mod 3
oops i misread
amber basin
Oh so is it just if (m,n) > 1, then n^12 = 0 (mod m)
light flicker
that's not always true
amber basin
oh yeah, but it's true when they are both even though right?
hold up that doesn't seem right
amber basin
i'm noticing that if d=(m,n) then n^12 = dM (mod m) for some M. so the only way for dM=1 would be if d=1 which means m and n must be relatively prime
light flicker
yes
amber basin
So i'm basically now having trouble proving when n^12 = 1 (mod p ) for the different powers of p. But p here is just one of the primes in the prime factorization of m.
light flicker
So maybe I'll just tell you that in general
whole sigil
i scrolled up to see the problem u asked for help with
"for any pair n,m with (m,n) = 1 find m with n^12 = 1 (mod m)
how does this make sense? you already used the letter m
find the largest*
are you asking what the largest possible value of m is in such a pair?
amber basin
yes, it's asking for the maximum value m can take
whole sigil
and zopherus said that for any pair with n^12 = 1, n and m must be coprime anyway
so, taking that as a given, ur just asking what the largest number with 1 as a 12th power residue class is
wait a second
for any m u can pick n = 1
(1, m) = 1
1^12 = 1 mod m
and therefore, in the most boring way possible, there is no largest m
unless im misinterpreting something
whole sigil
oh, so you weren't asking for the largest m in any of those pairs
u were asking for the largest possible m such that all possible pairs with it satisfy the condition
amber basin
yeah
whole sigil
okay, this was highly unclear to me
amber basin
my wording was ambiguous, sorry
light flicker
Yeah I'm confused now too
If you're fixing m, why'd you talk about the largest possible m?
amber basin
oh no i'm just digging my hole deeper
i'm getting the exact wording, one second lol
Find the largest integer m such that n^12 = 1 (mod m) for all integers n relatively prime to m.
light flicker
oh
whole sigil
Basically such that the 12th power residue classes are trivial
maybe we can look at lower powers first
4th power seems relevant
also quadratic and cubic, to see what happens when it's prime
wait i just realized
2^12 = 1 mod m, and so m divides 2^12-1
this reduces it to a finite amount of possibilities
this is the 6th fermat number btw
light flicker
That's assuming that 2 doesn't divide m
whole sigil
oh, wait, i forgot about that condition
yeah, let's think about the odd m's first
clearly since each odd m must divide the 6th fermat number, none is bigger
amber basin
if m is 2, doesn't that mean n would need to be odd?
whole sigil
not fermat number, my bad
mersenne number
yeah, it does mean that, i just forgot about the coprime condition
it's 4095
amber basin
we haven't covered mersenne numbers
whole sigil
mersenne numbers are just of the form 2^n - 1
and they are particularly known for being prime very often
so ull often find the term mersenne prime thrown around a lot
this is around all u need to know for this
amber basin
so if you couldn't use that, how would you go about solving this?
whole sigil
the same exact way
the only way in which i "used that" is by calling it that
i literally just used the name
not any facts about it
amber basin
yes but where did 4095 come from then
have mercy on my poor soul, first time i've taken any math class like this and i'm on a quarter system
whole sigil
@amber basin from the calculator
amber basin
Oh yeah that makes sense. But my professor just got back to me and she wants to see the solution like how I initially tried it (go through each prime and then their powers) and somehow show that m = 2^a, 3^b, 5^c, 7^d, 13^e and then find the maximum values of a,b,c,d,e.
amber basin
yes both
light flicker
you should really think about that here
amber basin
so i started with looking at p=2 and its powers. so for the first iteration I have n^2 = 1 (mod 4) since n is relatively prime to 4, and phi(2^k)=(2^k/2). so this implies that n^12 = 1 mod 4.
do I just keep doing this until that doesn't hold anymore?
light flicker
well
even if phi(q) = 24 for example
if could be possible that n^12 = 1 for all n
Euler's theorem doesn't say anything about this happening
amber basin
but i'm only looking at powers of 2 here, and 24 isn't one of those
light flicker
Sure, sure, but for other numbers, this will be an issue
amber basin
do you have any recommendations on how to tackle this then?
light flicker
this way is fine
amber basin
so I noticed that (still on powers of 2) that anything past a power of 4 will not work...but i don't know why lol
n^12 = 1 (mod 2^4=16)
amber basin
and doing this I get (2^4) *(3^2) * (5^1) * (7^1) * (13^1)=65520
torn escarp
interesting, I think I'm taking the wrong approach on this but just noticing if you pick some large, highly divisible n then
$f(c_n) \equiv 0 \mod d$
sterile pumiceBOT
Merosity:
torn escarp
for all d that divide n
so I guess in some sense we can kind of pick all the c_d = c_n for d|n and we have a kind of continuity or maybe we can take some kind of inverse limit thing, I have no idea how to go about that
probably some much more sane approach, just ignore that lol
silent lantern
hmm @torn escarp we're currently finsihed talking about orders in NT so i assume that it would be something to do with QR
light flicker
Quadratic Reciprocity?
silent lantern
mhm
@light flicker any ideas? ive been cracking at this for like 2-3 hours on and off gonna take a break no
*now
light flicker
thought about it a little a while ago, seems hard, I'll think a bit more
torn escarp
oh I didn't even consider proving b^2-4ac is a perfect square, I slipped out of reality
silent lantern
yeah haha we sometimes just gotta go back to the basics
torn escarp
wait you said you just learned about orders?
like p-adic valuation
this does seem like a kind of case of the hasse-minkowski local global principle
that you can solve this in every completion of the rationals -> implies you can solve it in the rationals
it seems pretty clear to me that we can solve it in every p-adic field since the condition guarantees we can hensel lift, ehhh this seems like still the wrong approach though, there's some simple way of looking at it I want to believe, idk I'm not a ninja highschool number theory whiz
silent lantern
@light flicker i kinda arrived to this step : ax^2+bx+c = 0 mod p is always solvable. So after completing the square you get that (2a+b)^2 = b^2-4ac mod p is always solvable. Now b^2-4ac is constant so what you want to show is that if we have for every prime k = a^2 mod p, then it must imply that k itself is a square
im kinda not sure how to go about showing this tho, because this deals with an infinite number of primes
light flicker
Wait did you miswrite that second part?
(2a+b)^2 = b²-4ac mod p is always solvable?
silent lantern
multiply the thing by 4a and u get 4a^2x^2+4abx+4ac=0 mod p==> (2a+b)^2 - b^2 + 4ac= 0mod p ==> (2a+b)^2 = b^2-4ac mod p
supple furnace
(a/p)=1 for all p implies a is a perfect square by quadratic reciprocity, Dirichlet, and CRT
light flicker
where did the x disappear to
silent lantern
i think dirichilet is a bit too much
light flicker
But yeah I don't think it matters
I mean you wrote it yourself
we have that b^2 - 4ac is a square for every prime
You don't need all those results right tree? Quadratic reciprocity should be enough
supple furnace
You pretty much do
There’s a group theory proof by Elkies
But I’ve actually spent time looking for simple sols to this prob
Remember that you have to decompose into to primes for QR to work (Jacobi symbols aren’t allowed here), which necessitates full Dirichlet for getting the contradiction.
light flicker
hm damn
supple furnace
If you relax it to (a/n)=1 for all n, then it becomes much easier. It’s basically impossible for a to be a QR mod a^2 unless a is perfect square.
You don’t even need reciprocity
supple furnace
@light flicker
supple furnace
That’s equivalent to the original prob
light flicker
No other clever way to do it hm
supple furnace
Did you read above
Select (b^2-4ac)^2
If b^2-4ac isn’t a perfect square
And you get a contradiction
We can assume that (a,b)=1 btw for if d|a,b, d|c and we can divide out by d to get a new quadratic. Similarly, if 2|b, we can analyze b’^2-ac and take (b’^2-ac)^2 instead
So this rigorizes stuff
@light flicker
light flicker
Oh yeah
noble elm
looks to be
noble elm
what are you looking at?
tawdry scaffold
the roots of a polynomial following a particular construction. this one is of degree 30. as you can imagine, wolfram isn't very happy with me adding more roots than this
but it seems to converge to this shape
tawdry scaffold
except im not seeing the inner loop complete itself, nor the outer loop curve inwards near 1+0i
sounds easier than it is
that one root between the inner loop and 1+0i is the solution to a particular problem ive been working on, and im trying to find a way to find that point in situations that aren't as pretty as this one
in a more general case
noble elm
Oh, neato!
tawdry scaffold
im lacking the tools to adequately check whether the complex roots match a limacon, though
partly because most of these roots are of 12th degree polynomials, which i cant solve analytically
and the other part is because im having difficulty converting a limacon into cartesian coordinates
hollow bramble
its probably easier in polar
cobalt sparrow
Is there anyway to solve $\phi(n)=p^{2016}$ for $n$ ?
sterile pumiceBOT
TheXitizen:
craggy solstice
????
cobalt sparrow
I got an answer from a person that is $n=2^2017$ , (I didn't find it ) .
I am having problems as to how to arrive at the answer
sterile pumiceBOT
TheXitizen:
prime pike
I had only learned to count to Quadrillion. Anything above is considered bull sh** to my country
craggy solstice
WTF?