$\frac{(\mu \star N)(n)}{n} = \sum_{d|n} \frac{\mu(d)}{d} = \prod_{p|n} 1-\frac{1}{p}$
#elementary-number-theory
torn escarp
sterile pumiceBOT
Merosity:
last grove
torn escarp
you're welcome 👍
digital swan
I was playing with prime numbers and manage to find this pattern on the primes, does anyone reconize it? oeis.org doesnt,...
alpine jasper
can you screenshot and talk about it instead?
light flicker
You really should describe what you're doing
There are just random numbers how are we supposed to tell what your pattern is
digital swan
oke i will give some description
alpine jasper
just crunch those numbers!
digital swan
I start with the value:
v = floor(p / 2)
After i keep updating v with the same algorithem until it reach to itself:
v = v^2 mod p
De data in my file is primes and total iterations it takes before it reach itself
light flicker
Alright, and what's the pattern?
alpine jasper
so you keep squaring it until it is congruent to the original number?
digital swan
correct
i use this data to find the upper bound for any n case
like if n is made out of two primes
i can use that data and find out how many iterations it takes for n
basicly i can use this to find small factors really fast with a view iterations with this algorithem
alpine jasper
ok i'm still don't get it, for 11 you got 2, what is the exact procedure?
if i take floor(11/2) (which is the same as (p-1)/2
i get 5, so
5^2, that reduces to 3 modulo 11
square that again gets 9
and again to get 81, reducing to 4
doesn't seem to go back to 5 in 2 steps, what am i doing wrong?
digital swan
@alpine jasper that right, there is a catch
you must imagion at start it can happen your not in the circle yet,.. you need to iterate like 5x before your in the circle
alpine jasper
uhh...
alpine jasper
can you describe the entire thing with math
sleek cove
light flicker
If you've read my blog post, he's talking about preperiodic vs periodic points
I.e., for that number, it's true that f^{m+n}(x) = f^{n}(x)
So you need n steps to get "into the circle"
And then the periodic length is m
alpine jasper
i see
digital swan
@light flicker ow thx, i didnt knew how you would call this,.. where has this formula/pattern been used for?
light flicker
This is a paper my friend wrote
That's basically what you're doing but a lot more general
alpine jasper
so if f(x) = x^2, take x = 5 for p = 11
then f^{7}(x) = f^{1}(x) [mod 11]
so f^{7 + n}(x) = f^{1 + n}(x) [mod 11] for all n
does this make sense?
oh wops i made a mistake
digital swan
ow wauw this is even pretty recent thx 😉 @light flicker ❤️
sleek cove
wait why 7
alpine jasper
oh nvm it shouldn't be
digital swan
by the way, what i discovered today is that those values can be used to find the factors on n
sleek cove
so i get what periodic means here, but i dont get what the period for mod 11 is
light flicker
Okay wait this is the wrong paper
It's vaguely related but it's a different paper I'm thinking anout
I'll find the other paper when I get home
digital swan
n = 31 * 19
[442, 405, 283, 574, 225, 560, 252, 481, 473, 498, 35, 47]
442
- 442 225 217 4 31
- 442 252 190 6 19
- 442 473 31 8 31
405
- 405 560 155 4 31
- 405 481 76 6 19
- 405 498 93 8 31
283
- 283 252 31 4 31
- 283 473 190 6 19
- 283 35 248 8 31
574
- 574 481 93 4 31
- 574 498 76 6 19
- 574 47 527 8 31
225
- 225 442 217 4 31
- 225 473 248 4 31
- 225 35 190 6 19
560
- 560 405 155 4 31
- 560 498 62 4 31
- 560 47 513 6 19
252
- 252 442 190 6 19
- 252 283 31 4 31
- 252 35 217 4 31
481
- 481 405 76 6 19
- 481 574 93 4 31
- 481 47 434 4 31
473
- 473 442 31 8 31
- 473 283 190 6 19
- 473 225 248 4 31
498
- 498 405 93 8 31
- 498 574 76 6 19
- 498 560 62 4 31
35
- 35 283 248 8 31
- 35 225 190 6 19
- 35 252 217 4 31
47
- 47 574 527 8 31
- 47 560 513 6 19
- 47 481 434 4 31
that list are the v = v^2 mod p values
i combine those values with eachother to find the prime factors like this:
v = abs(list[i] - list[j])
p = gcd(v, n)
so i got (all done in modulo 11)
f^1 (5) = 3
f^2 (5) = 9
f^3 (5) = 4
f^4 (5) = 5
f^5 (5) = 3
so f^{4 + n} (5) = f^{n} (5) for all n
am i doing this correct? what does this mean for p = 11 to have "2"?
light flicker
Its just an image from sage
digital swan
@light flicker by experience i know it takes max +- 10 iterations before you reach the circle,.. like i am not sure its related to what you send,... but i like your paper 😉
sleek cove
im confused ab p=5 too,
v_0 = 2, so we get
f^{1} = 2
f^{2} = 4
f^{3} = 1
f^{4} = 1 = f^{k>2}
idgi
halp
digital swan
@sleek cove what your trying?
alpine jasper
sleek cove
how do you get 1 for 5 and 2 for 11
digital swan
oke let me give example for 5 and 11
p = 5
v = floor(5 / 2) = 2
list = [4, 1, 1, 1, 1, .....]
4 is the first iteration
and that value isnt in the circle yet
you skip this value
and go to the next
that becomes 1
and after you see it keep repeating itself
means f(5) = 1
now 11
p = 11
v = floor(11 / 2) = 5
list = [3, 9, 4, 5, 3, 9, ..]
you see 11 start inside the circle with 3
sleek cove
its because iterations is always 2x
i dont get this
i dont see any pattern involving 2 in 3,9,4,5
digital swan
te pattern is 4 right
light flicker
Wait are we squaring or doubling
sleek cove
squaring right
digital swan
squaring
look at the list values 😉
you now what i generate th data again,.. without the 2,... then it will make more sense for you guys
oke patched
digital swan
sorry for mistake. the data looked confusing because i used steps of 2 in my algo that generate this result.
is was a improvement in calculations
sleek cove
oh i see
yeah this makes sense now
have you looked at other functions such as v=v^3 mod p? or even v=v^k mod p? it seems interesting
light flicker
It's described in the paper
sleek cove
actually all of the even powers would just shorten the sequence length in half, like v^4 would just be half of v^2
reading papers are for nerds
light flicker
You can also say things more generally, not just for that specific number
The paper is pretty technical
sleek cove
could i read it
digital swan
no, i did a lot of pattern filtering on ```
a^2 mod n = v
b^2 mod n = v
a always has a twin b that produce same v. except a has a divered of n.No
sleek cove
then dont tell me its in the paper smh
digital swan
and yeah about the power 4 i used to do steps of 2
sleek cove
the first or second one u linked
digital swan
what i realized if you want to optimize x^2^y mod n calclulation is that you need totient (n)
that limit me to get myself into intresting positions to get potential prime factors for big integers n cases
digital swan
Thank you for taking the effort by the way, really appriciate it ❤️
forest mica
I need to find numbers x, y and z such that yz I x^3 -2 and y+z I x^4 -2
Any ideas?
x<100
simple hearth
python?
digital swan
@forest mica
"""
yz I x^3 -2 and y+z I x^4 -2
"""
def f(x, y, z):
if(x == 0):
return 0
else:
return (y * z) // pow(x, 3) - 2
def f2(x, y, z):
if(x == 0):
return 0
else:
return y + z // pow(x, 4) - 2
for x in range(100):
for y in range(100):
for z in range(100):
if f(x, y, z) == f2(x, y, z):
print("{} {} {}".format(x, y, z))
something like this you mean?
timid olive
meh python
light flicker
good?
stoic bear
😳
sleek cove
correct answer
sacred junco
Can someone help me understand this proof?
light flicker
@fervent crest
sacred junco
This is from Hatcher's Topology of Numbers and jsyk I've read all previous chapters and done all exercises up to this point so no need to explain the previous stuff
The language towards the end is very hard for me to interpret visually because it feels vague
My first issue is that I don't understand how the last matrix making up P takes the next-to-last edge to <1/0,0/1>
fervent crest
@light flicker why pinged me
light flicker
because you studied these things
sacred junco
It's gorgeous 😍
stoic bear
What is this
sacred junco
an intro number theory book by Allen Hatcher oriented towards algebraic number theory
ugh so I tried to interpret this as
"the next to last edge" := $\left<(b-a_k a)/(d-a_k c), a/c\right>$
sterile pumiceBOT
zd:
sacred junco
cause when you mediant that a_k times with a/c you get b/d back as expected
so in the strip it would be the next to last edge, the edge superimposed over <0/1, 1/a_1> in the diagram
or maybe it's reversed? $\left<a/c, (b-a_k a)/(d-a_k c)\right>$
sterile pumiceBOT
zd:
sacred junco
Just need something when you multiply it by $\left<1/0,a_k/1\right>$ you get $\left<1/0,0/1\right>$
sterile pumiceBOT
zd:
sacred junco
but it doesn't work lol
hmm or wait
it does but it's what's superimposed over $\left<1/0,0/1\right>$
sterile pumiceBOT
zd:
sacred junco
I think what Hatcher was saying more informally is that $\begin{pmatrix}a & b-a_k a\ c & d-a_k c\end{pmatrix} \begin{pmatrix} 1 & a_k \ 0 & 1 \end{pmatrix} = \begin{pmatrix} a & b \ c & d \end{pmatrix}$
sterile pumiceBOT
zd:
sacred junco
which I think works to justify that step in the proof?
I don't know why the matrices alternate from transposed to not transposed though
sacred junco
im gonna try a thing
sacred junco
still not much closer to understanding this proposition
alpine jasper
let's ping @fervent crest again
fervent crest
Please
sacred junco
LOL
hollow bay
how do I solve n^2+k^2=3737?
digital swan
https://en.wikipedia.org/wiki/Euler's_factorization_method
Basicly you know that the prime factors are 3737 = 101 * 37
https://en.wikipedia.org/wiki/Fermat's_theorem_on_sums_of_two_squares
generate sums of two squares for your two primes
10^2 + 1^2 = 101
6^2 + 1^2 = 37
then you can use those results to finish it with this: https://en.wikipedia.org/wiki/Euler's_factorization_method
n = 3737
k = 1 * 2, h = 10 * 2, l = 1 * 2, m = 6 * 2
(a - c) = kl = 4
(d - b) = km = 24
(a + c) = hm = 240
(d + b) = hl = 40
a^2 - c^2 = d^2 - b^2 = (a - c)(a + c) = (d - b)(d + b)
a = (hm + kl) / 2 = (240 + 4) / 2 = 122
b = (hl - km) / 2 = (40 - 24) / 2 = 8
c = (hm - kl) / 2 = (240 - 4) / 2 = 118
d = (hl + km) / 2 = (40 + 24) / 2 = 32
a^2 + b^2 = c^2 + d^2 = 4n
122^2 + 8^2 = 118^2 + 32^2 = 4n
And there you see the two solutions
3737 = 61^2 + 4^2 = 59^2 + 16^2
Also you can do for negative cases:
n = p * q
= 37 * 101
= (1/4)((p+q)^2 - (p-q)^2)
= (1/4)(138^2 - 64^2)
= 69^2 - 32^2
warped void
Can someone check if this is right?
woeful trellis
This also doesn't belong here
sacred junco
you want y on one side
sleek cove
this is clearly a linear diophantine equation therefore nt smh @woeful trellis
torn escarp
$$a(x) = \sum_{n=0}^{p-1}\frac{x^n}{n!}$$ $$b(x) = \sum_{n=0}^{p-1} n!x^n$$
sterile pumiceBOT
Merosity:
torn escarp
Supposedly if $x \ne 0 \mod p$, $a(x) = -b(-1/x) \mod p$
sterile pumiceBOT
Merosity:
torn escarp
any ideas how to prove this?
simple hearth
oh wow, the sum is up to p-1. I've been staring at this thinking the sum was up to infinity 😛
and was trying to understand how it could possibly converge
torn escarp
heh I made some similar mistake myself
actually just got an idea, maybe a(x+y)=a(x)a(y) mod p and so that can then be shown to be true as an identity with b somehow, but I think I might have to do more, not sure
eh, I don't know if I'm in the mood to walk down that path right now, I feel like something to do with rearranging terms might be more likely
sleek cove
whats this from mero
torn escarp
" Also, it turns out that
a(x) = -b(-1/x) (mod p)
for any prime p and any x not congruent to zero (mod p)"
I went ahead and checked a handful of cases by brute force, but didn't prove the "it turns out that" part
they call b(x) the "companion function" so I don't know if this is part of some broader method, like
$\sum a_n x^n$ and $\sum a_n^{-1} x^n$ are always going to be related in this way or something
sterile pumiceBOT
Merosity:
torn escarp
kind of seems like it'd be more specific to the factorial, like wilson's theorem kind of lurking in the background, I'm not sure
I've brute force checked all values with primes up to 100 and found no counterexample, figured that it's reliable enough
digital swan
n = p * q
a = z^2 mod n
b = z^4 mod n
c = (z + 1)^2 mod n
d = (z + 1)^4 mod n
p = gcd(abs(a - b) + abs(c - d), n)
for any n that is coprime exist a z integer that produce a p prime that is part of n coprime
Anyone a clue what theorems are related to this to explain this relation?
If i change the powers 2, 4 to 4, 8 this also holds true
also for powers:
8, 16
16, 32
32, 64
....
here some example data for n = 4223
torn escarp
@obtuse stream I just worked through what you sent, looks like that's exactly what I needed, thanks
torn escarp
ah I think I see a little more clearly about the congruence now
$\binom{p-1}{n} = \binom{-1}{n} = (-1)^n = (-1)^{p-1-n} \mod p$
sterile pumiceBOT
Merosity:
obtuse stream
this is much much cleaner LOL
torn escarp
kind of looking to take on the mod p^k case, I think it'd be possible to generalize to that from here
as in adding more terms to the a(x) and b(x)
dunno, just seems fun
obtuse stream
does wilson's theorem have any reasonable analog for prime powers or is it just sorta bleh
it looks like the factorial is often 0 mod p^k though like 8! mod 9
torn escarp
yeah, so long as you throw out the terms divisible by p
obtuse stream
OH oh ok
sleek cove
oh yeah, mathpages is a cool site
torn escarp
I think I just came up with a generalization but I'm gonna go check it first before I try to explain it if anyone's interested haha
simple hearth
I'd be interested to see. I spent all of yesterday trying not to work on proving the thing you posted because I had other things I needed to get done, but it was a super cool claim.
silk vine
The case k = 1 can be easily solved by applying SFFT.
We find (4,4), (6,3) and (3,6) as a solution.
But for the case k=2 and general, I'm pretty stuck.
Applying SFFT for the k=2 and beyond wouldn't work properly, since I would be dealing with degree 3 and above multivariable polynomials.
Case k=1 (Solved)
• note
Here, k is the same as p. It's quite messy because I've solved this problem before thinking about the general problem, so I didn't have a standard notation, but you get the idea.
Case k=2 (Stuck)
sacred junco
was -1 a typo?
silk vine
General case (Stuck)
was -1 a typo?
@sacred junco yes, it was. Thanks for spotting it.
fervent crest
Idk what you're trying to do but you can simplify the equation significantly:
\begin{align*}
\sum_{i=1}^k\frac{p_i\cdot180(n_i-1)}{n_i}&=360\
\sum_{i=1}^kp_i\br{1-\frac{1}{n_i}}&=2\
\sum_{i=1}^kp_i-\sum_{i=1}^k\frac{p_i}{n_j}&=2
\end{align*}
sterile pumiceBOT
Whoever:
silk vine
Corrected version.
I am trying to solve the problem of finding all semi-regular tessallations of the euclidean plane.
That's where this diophantine equation comes in.
For a fixed k, basically means that I'm choosing k different regular polygons to make a tessellation of the euclidean plane.
silk vine
Yup
sacred junco
I think the degree of this diophantine equation for k>1 is too filthy for me and I cannot help
hmm
for k=2 there are many many solutions
wait I think I did something wrong
n_k ≥ 3 is an important detail I was not considering
fervent crest
Let’s say a number is a perfect $n$th power modulo $m$ if it’s congruent to a number raised to the $n$th power. What can be said about the number of perfect $n$th power modulo $m$, what about the number of perfect $n$th power in $U_m$?
sterile pumiceBOT
Whoever:
fervent crest
Ok of course if m is prime and n=2 then it’s just the number of quadratic residue, and the answer will be (p-1)/2
Well if you include 0 it will be (p+1)/2
torn escarp
I suppose the problem boils down to solving it for powers of a prime, since knowing the solution there we get the answer by the chinese remainder theorem
eh maybe not, I think I was assuming too quickly counting the solutions modulo each divisor p^a of m, would just allow us to multiply the results together
fervent crest
Well maybe asking this question for any m is a bit ambitious, I guess we can try working the special case of m being a prime power first, or even just m=p
torn escarp
yeah sounds good
I think when p | n we have problems
at least for the power of p case, just thinking to hensel's lemma, but maybe it's ultimately fine
didn't you ask a similar question to this a while back? I feel like we had a similar discussion and you showed me a trick and I sort of vaguely remember but forgot how it went
fervent crest
Well we talked about how to compute the square root explicitly
not the number of roots
*perfect powers
torn escarp
ah right
I guess euler's theorem simplifies in a sense which cases to even consider
might be easier in vc
$\omega^3 = 1$ let's say mod 7,
sterile pumiceBOT
Merosity:
torn escarp
$a^3 = (\omega a)^3 = (\omega^2 a)^3 \mod 7$
sterile pumiceBOT
Merosity:
torn escarp
so there are only 2 (not counting 0)
sleek cove
hour long vid just on that 
simple hearth
and it's only part 1!
sleek cove
how many parts?
simple hearth
two
sleek cove
are you going through different apporaches or like, starting from complete scratch and working your way to the sol
simple hearth
this is the approximation part, the second part is the proof, and Riemann's explicit formula for pi(x)
Well, if you don't know what a Bernoulli polynomial is, talking about Euler-Maclaurin approximation takes a bit
but the goal of this series is to make the Riemann Hypothesis make sense, and make all the stuff around it seem less scary. So I think being super terse hurts that. I'd rather take the time to smell the flowers along the way. But it won't be the style for everyone.
timid olive
fkng linux does not allow me open youtube and like zetamath's video
simple hearth
so after part two of this, my plan is to do an intro to some high pointsi n complex analysis, to understand how one finds the zeroes of a complex function (since you can't use the intermediate value theorem or anything). This will eventually lead to talking about some Fourier stuff which is necessary for motivating and proving the functional equation.
The part I'm currently figuring out how to talk about is integral transforms, which are necessary for proving the prime number theory and digging a little deeper into this. But I'm having trouble making it not seem like a weird trick. I think I have some ideas though.
but basically I want each video to tell a story that isn't just a B line to a proof
sleek cove
ok mr 3b1b
wooden sleet
Is there an example of analytic methods being used for number theory that's simpler than the zeta function
simple hearth
@wooden sleet Yes, there are plenty. The first episode I posted talks about some of them.
sacred junco
@simple hearth I think there is a mistake in the video but im not sure. when you approximate the crescents you write f(0) + f(1) / 2 but isnt f(x)=1/x^2? (so it should be f(1) +f(2))
simple hearth
that's for a generic f(x)
we're going to apply it with f(x) = 1/x^2 later
but everything works nicest if I do all the work for the interval 0 to 1
(even though the interval 0 to 1 isn't even involved in the sum)
sacred junco
Given a positive integer $N$, consider any positive integer $n=p_1^{r_1}p_2^{r_2}\dotsm p_k^{r_k}<N$.
There are at most $(r_1-1)(r_2-1)\dotsm (r_k-1)$ many ways to write $n$ as a totient since that would be a product of primes, which must be powers of the same primes $p_1,p_2,\ldots,p_k$, times a product $(p_{i,1}-1)(p_{i,2}-2)\dotsm (p_{i,t}-1)$ made from them.
Thus there are only finitely many values for which the totient function can take on less than any given positive integer. Therefore the limit of the totient function to infinity equals infinity.
Just making sure, is this valid? Any extra work to do or perhaps I made a bigger conceptual mistake
sterile pumiceBOT
zd:
sacred junco
I think I have the wrong number for the upper limit of how many ways you can write some number as a totient
sleek cove
i think this is good, but i thought if the limit of the function was finite then it would imply that the num of primes was finite as well
sacred junco
Nice! Or even just supposing that the limit isn't positive infinity, i.e. that you can establish an upper bound so that there are an infinite number of totients less than or equal to it. Since there are only finitely many values to take on, there is at least one which is the totient of infinitely many numbers. Insert similar counting argument to my previous one but based about a totient rather than a prime factorization to contradict
And I saw an even more complicated one from a buddy who did a hacky thing that I didn't really get ;-;
sleek cove
yeah that makes sense as well, theres definitely many ways to prove this
runic lynx
0,1,2,3,4....,n-1 forms a complete residue system modulo n and exactly phi(n) numbers are co prime to it.
Also r,m+r,2m+r,....,(n-1)m+r forms a complete residue system modulo n. How do i prove that this complete residue system modulo n also has phi(n) numbers coprime to it. If r=0, then i understand why but if its non zero then how do I prove it?
fervent crest
How would you prove it if r=0
fiery root
Hi guys, I need to find the remainder when 15²²+23²² is divided by 19.
I know the first step is to expand binomially and get (19-4)²²+(19+4)²² and then 19k+2⁴⁵ which would mean the remainder is the same as the remainder when 2⁴⁵ is divided by 19.
Now I don't know how to proceed from here...
I don't see a cyclicity in the remainders when 2^n is divided by 19 and I can't manually count the remainder for 2⁴⁵...
fervent crest
Well you didn't notice because the period is pretty long
fiery root
Ohh
fervent crest
But do you know Fermat's little theorem?
fiery root
No I've not heard of it..
fervent crest
Well, it says that if $p$ is a prime and $a$ is not a multiple of $p$, then $a^{p-1}$ has remainder $1$ when divided by $p$
sterile pumiceBOT
Whoever:
fervent crest
You can test it out
fiery root
Wow what, that is a neat concept!
fervent crest
Indeed
fiery root
Yeah doing it rn, this is amazing!
fiery root
Yes it seems like a concept that could be used in very limited situations, but it is fast as heck
Wait okay I need to work a bit, thanks for the hint man! ♥️
I'll have to use a pen and paper 😅
fervent crest
Well, there is a generalization
It says that if $n$ is a positive number, $a$ doesn't share a common divisor with $n$, then $a^{\varphi(n)}$ has remainder $1$ when divided by $n$, where $\varphi$ is the totient function. This is a generalization of that statement I said above because if $p$ is prime then $\varphi(p)=p-1$
sterile pumiceBOT
Whoever:
fiery root
Ohh so instead of primes we shift to coprimes
fervent crest
Yeah
And in the first statement we required a to not be a multiple of p is the same as saying a is coprime with p
Because p is prime
fiery root
Wait wait I'll solve, give me 2
2¹⁸ gives a remainder 1
I'm taking p as 19 and a as 2
So
2¹⁸-1 is divisible by 19
And therefore 2^n*(2¹⁸-1) should be divisible by 19
2⁴⁵-2²⁷ is divisible by 19
Next we need to find the remainder when 2²⁷ is divided by 19, and since we know 2¹⁸-1 is divisible, we know that 2²⁷-2⁹ is divisible by 19
So I just have to find the remainder when 2⁹ is divided by 19. Should I do this manually?
fiery root
Thanks :D
fervent crest
You've discovered something pretty interesting
Which will simplify your life tremendously
So the theorem is that, if a divided by n has remainder b, and c divided by n has remainder d, then ac divided by n has the same remainder as bd divided by n
I'm pretty impressed that you discovered this on your own
fiery root
Nooo I don't get it, how did you draw that generalization? ._.
fiery root
Yes
fervent crest
So 2^{45} is 2^{18}*2^{27}, and the remainder of the product is the product of the remainder
So the remainder of 2^{18}*2^{27} is just 2^{27}
fiery root
Ohh yes I get it!
sleek cove
So I just have to find the remainder when 2⁹ is divided by 19. Should I do this manually?
what is manually
fiery root
As in, just simply divide 512 by 19 :P
fervent crest
It's not too tedious but
fervent crest
512 is 2*16^2, which has same remainder as 2*(-3)^2, which has same remainder as 2*9, or 18
fiery root
Okay I need to take a break. I've been at this binomial thing for a while now and I can't think straight. It's totally eluding me rn
fervent crest
Haha sorry I've been just throwing a lot of information at you
sleek cove
well alternatively, you could just reduce the components
fervent crest
You seem to be capable of doing these stuff, but you just haven't seen a lot of number theory
fiery root
Reduce the components? 😅
sleek cove
what is 23 = to mod 19
fervent crest
If you're computing remainder of product, you can replace each term in the product with numbers with the same remainder
sleek cove
you're allowed to substitute smaller numbers for larger if they are equal to the same number mod n
so 23 = 4 mod 19, thus we have 15^22 + 4^22
same with 15
fiery root
Wow what
Oh
Yeah that makes sense from the binomial expansion @sleek cove
I'm sorry I haven't studied math after grade 12 so I'm not well versed with the mathy terms
fervent crest
Nah these math terms aren't taught in high school sadly 
fiery root
Haha I can see that, you both are PhDs?
sleek cove
noooo lol
fervent crest
no lmao
sleek cove
whoever is only 11
fervent crest
wooden sleet
Wait what
fiery root
Woaaaah
wooden sleet
Lollllll uhh
sleek cove
sory 21
wooden sleet
Lol 11 years old that would be funny
fervent crest
Sideurk is 5
wooden sleet
Nice
sleek cove
but anyways, we notice that 15 = -4 mod 19, so we have (-4)^22 + 4^22, which is much easier to handle
fiery root
Hahahaha
sleek cove
im a normal 19 yr math major smh
fiery root
Yes I was at that point, 2⁴⁵ divided by 19
fervent crest
Yeah
It's actually quite impressive that he found that out without modular arithmetic
fervent crest
I mean yes
I totally agree
If I wasn't exposed to modular arithmetic I would have never figured that out
fiery root
My dudes, I'm 21. I feel dumb asf in here lmao
wooden sleet
I wish they thought modular arithmetic in high school
sleek cove
and wow zephyr is only 2? what a prodigy
fiery root
21...
sleek cove
2 ones?
wooden sleet
That's insane dude, you're not even in kindergarten thats crazy
wooden sleet
But seriously doe
sleek cove
all jokes aside, whoever is actually 53 lol
fiery root
Bye guys, thanks a lot. I learnt a lot of stuff today ♥️
sleek cove
he just likes trolling
fiery root
Huh?
sleek cove
yeah np
wooden sleet
Bye
fervent crest
...
wooden sleet
Bruh
fiery root
Bye!
sleek cove
it follows a chaotic system
fervent crest
That's still a well defined function tho
sleek cove
im disagreeing with your well defined claim
it is well defined
it is defined based off of what i say it is
fervent crest
fiery root
So the theorem is that, if a divided by n has remainder b, and c divided by n has remainder d, then ac divided by n has the same remainder as bd divided by n
@fervent crest
Okay so I was sleeping and thinking of this, and this is way more useful than I thought it'd be. That's all, good night fellas
Man I love this new theorem lmao
red pewter
The fancy words for your theorem might be something like "multiplication is well defined on congruence classes".
fervent crest
Yeah
runic lynx
is there a way to find solutions for $\phi(n)=k$ where $k$ is given, $\phi(n)$ is the euler totient function
sterile pumiceBOT
Abhi964:
runic lynx
Or only hit and trial works?
runic lynx
I had come across a question where k=8, so I used the inequality root(n)<=phi(n)<=n-1
my search space was from 7 to 64, after this i used phi(n)=n*(1-1/p1)*(1-1/p2)....
Now I made a few observations and then basically did hit and trial, i wanted to know if there is some general method to solving such kind of equations , or is this the only method
sleek cove
do you know a different forumla for phi(n)
it might be easier to work with
try breaking n into its factorization and distributing
(and yes we can be smarter about finding the solutions)
runic lynx
try breaking n into its factorization and distributing
@sleek cove How do i do that when I dont even know n
sleek cove
well how did you get the latter half of the formula involving arbitrary p_k's then?
runic lynx
the subscript k doesnt refer to the k given in the question.
sleek cove
i know
runic lynx
My bad should have used a different symbol
sleek cove
what im saying is, where did the p_i's come from
runic lynx
I just assumed that n had k prime factors
sleek cove
so why cant we substitue those factors in for n
like, if you've already assumed n to have i prime factors, dont we know n's factorization?
and this assumption is always true
for n>0
runic lynx
what if i dont assume that
runic lynx
No i mean lets say we dont know how many distinct prime factors n has,
We know it has to have some , but we dont know how many
sleek cove
....which is why we use p_i
not p_7 as the last p
i is arbitrary
there must be i distinct primes
runic lynx
But to know n's factorisation we must also know the powers of the primes , so just by saying that n has i distinct prime factors where i is arbitrary, i cant possibly know the factorisation of n
sleek cove
But to know n's factorisation we must also know the powers of the primes
so we use another arbitrary number for the exponent
alpha_1, alpha_2, ...., alpha_i
runic lynx
Okay so how do we proceed after this
sleek cove
distribute
runic lynx
distribute what exactly?
sleek cove
have you substituted in for n yet
runic lynx
substituted what ?
runic lynx
Yea
sleek cove
so, why not distribute (p_i)^(a_i) into (1-(1/p_i)) for all i?
runic lynx
Thats exxactly what I did, and i had asked for a general method
Thanks for the help btw
sleek cove
Now I made a few observations and then basically did hit and trial, i wanted to know if there is some general method to solving such kind of equations , or is this the only method
@runic lynx
what you did isnt a method, but this way is
what i am doing will greatly reduce the guesswork
uh yeah, in this case we know n=8, so we only consider p's such that p^a-p^a-1 divides 8
so theres no "guessing"
and we can easily find upper bounds on p and alpha, which helps
i mean, theres still work to do, but its much better than just trial and error
runic lynx
But now I have realised that this approach is right, thx
i mean, theres still work to do, but its much better than just trial and error
@sleek cove those were the observations I was talking about, I should have mentioned them though
torn escarp
try writing out some cases by hand to ground yourself
sleek cove
backwards element symbol 
sacred junco
If it wasnt possible then I think the problem wouldnt be there
fervent crest
Well no
sleek cove
hes talking to merosity
fervent crest
A problem can still be interesting if the answer is that no such n exists
sacred junco
I meant Whoever
fervent crest
Because you'll have to show it
torn escarp
$\bN \ni n$
sterile pumiceBOT
Merosity:
sacred junco
it is not the case that no n exists
sleek cove
smh
torn escarp
shake my hand
sleek cove
sleek cove
what if you do it again
torn escarp
no no I want to solve this problem now
I think starting at the solution is probably the way to go
sleek cove
ill get someone to help you
torn escarp
start with
sleek cove
@fervent crest
fervent crest
k≥10 doesn't quite work
sterile pumiceBOT
Merosity:
fervent crest
So n has to have less than 10 digits
sacred junco
Im not sure where that formula came from
fervent crest
$d_kd_k\dots d_k=d_k(11\dots1)=d_k(10^{k-1}+10^{k-2}+\cdots+1)=d_k\frac{10^k-1}{10-1}$
sterile pumiceBOT
Whoever:
sacred junco
Now I see
sterile pumiceBOT
Merosity:
sterile pumiceBOT
kitchen1112:
torn escarp
nope
that's backwards
write out the digits for k=4 using your formula and my formula and compare, I think that would make it clear why
fervent crest
Notice that kn-n=(k-1)n is a multiple of 10
So k odd or n even
and k-1 is divisible by 5 or n is divisible by 5
n=148148 works
@torn escarp
aside from n being single digit, I think that's the only solution
fervent crest
NO
torn escarp
lol
fervent crest
Sorry caps lock was on
But I notice that if a is the last digit of k, then d_ka=d_k (mod 10)
So I found all the solutions to that equation
And the only one that gave me a solution to the original question was 6*8=8 (mod 10)
torn escarp
ah I see
and then mod 10^2 and so on was the plan eh? 😛
seems familiar can't quite place my finger on it though
fervent crest
Well k can't be greater than 9
Or else kn will have one more digit than n
So I think that's it
sacred junco
fervent crest
Never mind
There's another one
185
Python is taking a long time to verify
As usual
Ok yeah python only gave me 1,2,3,4,5,6,7,8,9,185,148148
@sacred junco @torn escarp pretty convinced that these are the only solutions
fervent crest
Wait he has the solution or not
torn escarp
it's a simple enough problem to brute force
torn escarp
fans?
sacred junco
Yeah
torn escarp
Johnny Depp is into number theory these days or somethin?
sacred junco
Not sure who Johnny is
sacred junco
His followers
fervent crest
Who's he
sacred junco
@fervent crest it was correct
fervent crest
Ok
sleek cove
@fervent crest you are 53
fervent crest
Ok
sleek cove
@fervent crest you are a weeb
fervent crest
Ok
sleek cove
@fervent crest ok
fervent crest
Ok
sacred junco
Im still stuck on the question
sacred junco
It's above
sacred junco
kekW this line of a research summary
I think they're unironically using "box" as a variable
delicate fiber
that looks like what u get when ur browser cant render smth
junior tundra
So I was working on this problem earlier today. I got 604 (the ans being 605) on account of me accidentally counting f_11 (1) as equal to 0 and not 1. But anyways the point is I had a method to solving the problem, but it is nowhere near succinct as the official sol. I would like some help interpreting the official sol terminology.
Official sol: "The definition of $f_p$ is equivalent to the following: "If $n$ has a multiplicative inverse mod $p$, $f_p(n)$ is the member of the set ${0, 1, \ldots, p - 1}$ such that $n \cdot f_p(n) \equiv 1 \pmod p$. Otherwise, $f_p(n) = 0$."
Note that this really gives a well-defined function because that set includes exactly one member from each congruence class modulo $p$, and each invertible element has inverses in only one such class.
From this point onwards, it's clear: as $n$ cycles through $1, 2, \ldots, 10 \pmod{11}$, $f_p(n)$ also cycles through the same values in some order. We cover those values 11 times. Thus the answer is $11 \cdot (1 + 2 + \ldots + 10) = 605$."
sterile pumiceBOT
Doctor How:
junior tundra
What does multiplicative inverse mod p mean?
torn escarp
it means n*y=1 mod p
if there's a y such that n*y=1 mod p, then y is the multiplicative inverse
for instance 11 has no inverse mod 11, since it's congruent to 0
2 has an inverse because 2*6 = 1 mod 11
junior tundra
ah
torn escarp
6 is the inverse of 2
yeah
any other questions about their soln you want me to explain or is that all good now
junior tundra
I think I might have a good idea about what a congruency class might mean, but could you explain it to me?
torn escarp
two integers are in the same congruence class mod p if p divides their difference
so x ~ y iff p | (x-y)
just writing the ~ to show it's an equivalence relation and obeys the three rules
but you'd usually write it like $x-y \equiv 0 \mod p$ or $x \equiv y \mod p$
sterile pumiceBOT
Merosity:
junior tundra
Would 1 and ny be in the same congruence class iff p | 1 - ny
torn escarp
yup
fervent crest
Is there an irreducible polynomial in Z that splits into linear factors modulo every prime?
neat harness
i believe the answer is no for deg>1
hold on i think i have some stackexchange saved on this cause I was looking into this a while ago
"For, take any value of n for which f(n)≠±1. (There must exist such n because f can take the values 1 and −1 only finitely many times.) Consider any prime factor p of f(n). Then f(n)≡0modp, which means that f is reducible in Fp[x]: it is divisible by the polynomial x−n."
found that in my old notes for a simple explanation without too much algebra needed
it's been a long time since i've done this stuff tho so not sure how much I can actually answer about this
sacred junco
finally learned how to find all solutions to Pell's equation 
any cool things I can do with my life now
also the topograph is very cool and epic
upbeat wren
Hmm are you an undergrad? Study for next year's Putnam 🙂
sacred junco
I’m not a huge fan of competition math but maybe haha
I’m also not very well prepared and it takes more than a few months to get good at competition problem solving (I took it in my 2nd year tho, this time is my last chance so I might just for fun)
warped silo
steady nest
whats a good place to learn number theory
for like problem solving and stuff( im a CS/Math guy)
i was doing like a really easy modular arithmetic question and i was so confused with what was going on/the solution
sterile pumiceBOT
Publius:
steady nest
nope
sterile pumiceBOT
Publius:
alpine jasper
this is because $5^n=5\cdot5\cdots5$, and because $5\equiv2(3)$, you change all those $5$s into $2$ and obtain
$5^n\equiv2^n(3)$
sterile pumiceBOT
Publius:
alpine jasper
@steady nest is this clear?
steady nest
eh
the congruence part is what i don't understand
oh wait
5 mod 3 is 2 and 2 mod 3 is 2 so $5 \equiv 2(mod 3) $
sterile pumiceBOT
suck2015:
steady nest
yeah @alpine jasper
alpine jasper
right, since it is mod 3, you only need to try four numbers
alpine jasper
actually, have you heard of fermats little theorem?
or euler's theorem
you can simplify $n^5\equiv n^2\cdot n^2\cdot n=1\cdot1\cdot n$
sterile pumiceBOT
Publius:
alpine jasper
so in reality you only need to find $n$ such that
$2^n\equiv n(3)$
sterile pumiceBOT
Publius:
steady nest
@alpine jasper i've heard of them in name but i've never read about them
sleek cove
useful
sterile pumiceBOT
bean:
winged horizon
wdym localization
idk what the x^2+1 part means D :
i think thats all the context i have 😦
the question also asks for find -1 in that system
and fins 1 in that system
no other context provided tho 😦
torn escarp
@winged horizon what do elements of $Z_3[x]_{x^2+1}$ look like
sterile pumiceBOT
Merosity:
torn escarp
no one can help you with your question if you don't communicate the question to us
fervent crest
Actually nvm
sleek cove
the fuck where is sully
torn escarp
how about read earlier in the book where they explain the notation @winged horizon
fervent crest
What that $\bZ_3[x]_{x^2+1}$ means in this context is $\frac{\bZ/3\bZ}{\brk{x^2+1}}$
sterile pumiceBOT
Whoever:
inner crest
top should be polynomial ring
sterile pumiceBOT
Whoever:
torn escarp
this is still going on?
personally I'd write x as i in this case since i^2+1=0 feels more natural to me
then the question is what are a, b in Z/3Z such that sqrt(i) = a+bi?
square both sides
i=a^2-b^2 + 2abi
this gives us a^2-b^2=0 and 2ab=1
this forces a=1 and b=2 or a=2 and b=1 which gives us 2+i and 1+2i which are negatives of each other as we'd expect there to be two square roots
sacred junco
hi, i would just like sure that this question is asking for | |z| | = |a^2 - 6b^2 | < 10
fervent crest
No the norm should be a^2+6b^2
simple hearth
sqrt(6)*i is painful to look at
ashen musk
crap, wrong channel
sacred junco
How would I show that if pi is an gaussian prime with nonzero imaginary part and m is an integer such that pi | m, then N(pi) | m
sacred junco
There exists another gaussian integer a such that a*pi=m
Ah I think I got it
Thank you
fiery root
Hi, I'm trying to find the HCF of (3¹⁵-1) and (3²⁵-1) and I need some directions please
There's a formula given in the book that k being the factor of 15 and 25, the answer would be (3^k-1) but I'd like to go behind without a formula here
torn escarp
do you know the euclidean algorithm?
@fiery root
effectively, subtract the smallest from the largest, then factor out the power of 3 since 3^k -1 is relatively prime to 3 you can throw it away
this whittles it down
sacred junco
why does $a^n ,\vert, b^n$ imply $a ,\vert, b$?
sterile pumiceBOT
zd:
sacred junco
Obviously it implies a divides b^n but I can't really see further than that
torn escarp
single out one prime factor of a
call it p, so p^n divides a^n, which must mean p^n divides b^n, they're all identical copies so each of the n ps must divide one b each
you can't have something like p^2 | b^2 and then specifically imagine each b separately as p^2 | b while p not divide the other b
sacred junco
ok I see this factoring argument is kinda natural
torn escarp
once you have one prime, divide a/p and b/p and repeat again until you use up all the prime factors of a
sacred junco
nice
I think the rut I fell into was not bringing up the prime factorization interpretation of things
but I also saw an induction proof online so that would be another way, although much less natural
derivations preferred lol
fiery root
Merosity: thanks for the direction, I'll look at it! I'm sorry, due to home issues I've had to disable app notifications so I didn't see your tag. Thank you!
Dang that is one NEAT ALGORITHM!
void widget
another way, b^n/a^n = (b/a)^n is an integer
then show that a fraction to a power can't become an integer
sacred junco
Just look at the highest power of p dividing a
sacred junco
then show that a fraction to a power can't become an integer
@void widget that's basically what this is all about though, that would be circular logic no?
If you showed that independently that would just be an alternative proof on it's own though
void widget
yeah it's an alternative
sterile pumiceBOT
Notchmath:
jovial hemlock
sorry texit is being weird
what I’m trying to say:
Is it known that $p_k#^2 > p_{k+n}#$ if $p_{k-n}# > 2^{(n^2)}$, where $p_k#$ is the product of the first $k$ primes?
sterile pumiceBOT
Notchmath:
jovial hemlock
Relatedly, is it known that the sum of the $n$th triangular number and the $(n-1)$th triangular number is equal to $n^2$?
sterile pumiceBOT
Notchmath:
jovial hemlock
I assume it is, but I can’t find anything about it online
simple hearth
you can make a very beautiful proof by picture of it by arranging the two triangles into a square
jovial hemlock
okay yeah I figured, just couldn’t find anything to indicate it was anything
What about the first one?
supple furnace
As for the other problem, it is enough to show that $p_k#>\frac{p_{n+k}#}{p_k#}$. We are given that $p_k#>2^{n^2}p_{k-n+1}...p_k$, so we can conclude by showing that $\frac{p_{k+i}}{p_{k-n+i}}<2^n$ for each $i$ from $1$ to $n$. This follows directly from Bertrand’s Postulate.
supple furnace
I need to format primorials
jovial hemlock
yeah that’s basically how I got that
just using bertrand
I just want to know if it’s a known result or something I’d need to explain in a thing
sterile pumiceBOT
tree3:
supple furnace
Cool
jovial hemlock
primes and primorials are fun but they grow so quickly
supple furnace
Yeah, primorials are much worse than factorials
The prime number theorem gives a ballpark figure, but nothing too strong (like an asymptotic)
jovial hemlock
yeah
jovial hemlock
What are the upper and lower bounds for the nth prime in terms of n?
I know the nth prime is approximately n log(n), and I can easily determine that the nth prime is above 2n for n>4, but I feel as though there should be a stronger lower bound as n grows arbitrarily large, and some sort of upper bound (n^2?) that I can’t find either
jovial hemlock
If I was given the inequality 2x + 3 < 2n + n’th prime, how would I go about finding the upper bound of the lowest n satisfying the inequality in terms of x?
jovial hemlock
also, how do I learn more about how to do things like this? Primes have always really intrigued me
fervent crest
If you want to find the bound of n in terms of x, you will probably need to use lambert W function
And analytic number theory
jovial hemlock
can I ask what I should know before learning analytic number theory?
I’ve gone through linear algebra, and I assume I should have a little bit of background in abstract algebra, as well as real and complex analysis, right?
carmine delta
wait real tree3 (sorry for off topic)
sleek cove
you're not given
sacred junco
why mod4?
fervent crest
It's just a trick
sacred junco
whats trick
simple hearth
there are 4s in the equation, so 4 is a reasonable modulus to choose
sacred junco
aaa
thanks
a,b,c prime numbers , k ∈ N, whats modulo can i take here , , and why?
Mod 4 again maybe
thanks
And mod 2
why mod 2?
LHS is even
k must be odd
a and b are also odd
right
Try a=2m+1, b=2n+1 and k=2t+1
a,b,k all odd
Yes
supple furnace
Mod 3 is what destroys this problem
sacred junco
but why
jovial hemlock
@sacred junco What exactly is the question asking?
are a, b, and c supposed to be distinct numbers? If so, you can show there is no solution by this:
the RHS must be 1 mod 3. Note that (X^2) is 0 mod 3 if X is 0 mod 3, and 1 mod 3 if X is either 1 or 2 mod 3. The LHS must be 1 mod 3 as well. Because all 3 of a^2, b^2, and 16c^2 are square numbers, the only way for this to be possible is if two of the numbers are 0 mod 3 and one is 1 mod 3. For a prime number to be 0 mod 3 it must be 3, and for 4 times a prime number to be 0 mod 3 that prime number must be 3. Therefore 2 of a, b, and c must be 3, so they cannot all be distinct.
supple furnace
They have to be distinct? Once you get that two of them are 3, there are just three (two distinct by symmetry) cases that lead to all the solutions.
They are (3,3,2,3), (17,3,3,7), (3,17,3,7), (37,3,3,13), (3,37,3,13)
supple furnace
3 is a good mod to take because it annihilates the 9k^2 and is also quite small, leaving not many possibilities. You want to usually take prime power moduli (and maybe combine them after). In this case, 4 isn’t too helpful because can’t conclude that any of the squares are 0 mod 4.
sacred junco
but, here can i take mod 9?
supple furnace
Sure, but it’s much easier to take mod 3 here.
supple furnace
They were not assumed to be distinct prime numbers I assume?
a,b, and c?
@sacred junco
sacred junco
no
supple furnace
Cool
supple furnace
The only way to annihilate the 16k^2 is to take mod a power of two, but there is always a nonzero solution mod 2^r for (a,b,c,k) (in retrospect, that’s obvious given the solution set).
In other words, you can’t conclude that any of a,b,c are necessarily divisible by 2, so it’s not helpful.
jovial hemlock
I'll admit that I struggle to see how, once you have the fact that 2 of (a,b,c) are 3, you are limited to those 5 solutions. For example, if a and b are 3, I can see why 4c must be 1 or 8 mod 9, but I can't put my finger on why c must therefore be 2.
supple furnace
Difference of squares
sacred junco
thanks again
supple furnace
The first case is a=b=3. You get 18+16c^2=9k^2+1, or 17=(3k-4c)(3k+4c), which forces k=3, c=2.
(as 17 is prime)
The second case has more possibilities.
jovial hemlock
because...
supple furnace
WLOG set a=3 and c=3 to get 153+b^2=9k^2+1, giving (3k-b)(3k+b)=152.
jovial hemlock
because increasing only one of k and c results in (3k - 4c) no longer being one
increasing them both makes (3k + 4c) too big
supple furnace
You can solve for k and c immediately
supple furnace
without loss of generality
jovial hemlock
right
supple furnace
Because we could either have a=3, c=3 or b=3, c=3
But they are basically the same thing
So it’s easier to cover them together
jovial hemlock
right no I got that, just didn't have the acronym
supple furnace
Cool
supple furnace
Hi
jovial hemlock
so then (3k-b)(3k+b) = 152
supple furnace
They have to both be even
Because they are of the same parity and multiply to 152
And so they are 76,2 or 38,4
jovial hemlock
oh I thought you meant k and b have to both be even
supple furnace
3k-b=2, 3k+b=76
supple furnace
k=13, b=37
supple furnace
And that’s the whole solution set
jovial hemlock
it's interesting that they didn't put the restriction of k being prime as well
it wouldn't have impacted the solution set at all
supple furnace
Yep
jovial hemlock
huh
torn escarp
try them all
sacred junco
how
for modulo 3 i take ( 3^x mod 3, 2^y mod 3, 7 mod 3 ) ?
or ( 3^x - 2^y mod 3 )
sacred junco
why
torn escarp
for mod 3 neither of what you said is right, you take mod 3 of the entire equation
3^x - 2^y = 7 mod 3
then reduce everything you can, try that now @sacred junco
supple furnace
You can handle the cases of y=1,2 individually and then assume y>2. Taking mod 8 gives 3^x=7 mod 8 (which can never happen).
@sacred junco
sacred junco
thanks !
twin forum
Guys, If I have an equation, which I reduced by a modulo, then can I still add/subtract/multiply stuff to both sides?
twin forum
Nvm
sleek cove
trim gust
yes, but be careful with division of x as you also have to divide the moduli m by the gcd(m,x)
sterile pumiceBOT
suck2015:
steady nest
I understand that the modular multiplicative inverse follows this form : $ a \cdot x \equiv 1 \pmod{m} $
sterile pumiceBOT
suck2015:
steady nest
in this case , $ 201 \cdot x \equiv 1 \pmod{299} $
sterile pumiceBOT
suck2015:
steady nest
they multiplied 201 by 3? but how does that explain the mod 5? ( i do know that 603 mod 299 is 5 but did they just use naive approach?)
bleak musk
@steady nest they wanted some multiple of 201 that was equal to a factor of 300 (since 300 is 1 mod 299). The reason you want a factor of 300 is that then you can do the clever multiplying both sides by 60 thing. To find it, I'm assuming they did the naive approach, although someone who knows more NT than me may be able to give something clever
steady nest
thanks for the answer, i honestly just did naive approach to find 180 (c++ for loop up to 299) so the math explanation was nice
swift shard
Beautiful haha
It's completely general, 3 is any prime
The line format is pretty and well paced
What struck you to do it with lines?
sacred junco
It’s because 3 is prime
Since 3 is prime, 3|a*a implies 3|a or 3|a
What do you mean a=b?
Oh, I see what you mean now
Not the a and b in the proof
I don’t see why you’d write wlog here either
sacred junco
Is there an easy way to calculate a multiplicative inverse?
torn escarp
depends on what you consider easy I guess
what way do you compute the inverse currently
sacred junco
I haven't studied modular arithmetic that much so I just pick random numbers until I get it
sleek cove
if you have ax = b mod n, and you want to find the inverse of a, find the value of a^-1 st a(a^-1) = 1 mod n
but i'm ignorant if theres a better way for much larger moduli/a, such as like 6 digit primes for n and a
trim gust
you can use euclidean algorithm
torn escarp
a few times I've written the exponent I want in base 2 and then got the answer by repeated squaring, but I just use a calculator most of the time
sleek cove
hmm i see
torn escarp
stop posting your problems without also posting what you've tried @sacred junco
sacred junco
i tried modulo 24
sacred junco
mod 2?
torn escarp
there are so few numbers that divide 24
you should try them all to gain the experience to see what it looks like
because if you're hesitating and asking mod 2 you are hesitating way too much
sacred junco
thanks
torn escarp
you're welcome
sacred junco
I don't know how to analyze for modulo n ( example )
torn escarp
how is that possible
sacred junco
..
torn escarp
I thought @supple furnace was teaching you the other day to do much more advanced stuff
stoic bear
?
stoic bear
Do you understand how to mod an equation? I'm surprised you accepted tree's solution if you aren't certain on how to do this
trim gust
im pretty you cant just solve that equation
unless it is like a general form of all solutions, but i still doubt that
torn escarp
you can boil it down to what form n has to be in by throwing mod at it a bunch of times and whittling down the factors of 24
that's at least something not too far out of niuton's skill level to learn how to do probably
slow yew
torn escarp
what have you tried?
sterile pumiceBOT
skymoo:
sacred junco
yes
trim gust
it doesnt make a difference
sacred junco
@stoic bear why do you delete your messages 
vernal widget
ofc it does td
torn escarp
the main thing is not to give @slow yew the answer, they need to say what they've tried first