But it isn’t constructive at all
#elementary-number-theory
supple furnace
serene socket
The role of Bézout's is just to compute the multiplicative inverses isn't it
supple furnace
Yes
It says that a modular inverse exists for a mod b if (a,b)=1.
Anyway, establishing injectivity is almost Bezout-hard
It implies (relatively prime) Bezout and (relatively prime) Bezout implies it
So they’re equivalent
sacred junco
Hello guys.
Are there any tricks for solving such equations?
I know that in general case I can reduce the number (28763) modulo N (25), and I can reduce the power (341) modulo phi(N) (this Euler's thing) which is 20 for N = 25 IIRC.
But first of all, can I still reduce the power in that way, if my power is in another power?
So, can I make this equation (13^(1^42))?
If yes - then well, it's easy in this particular case, but what would I do if I haven't got this nice 1 in the power?
If no - then how can I solve it?
(I'd be grateful for pinging)
sacred junco
So, it's not possible to reduce this power in that way?
sacred junco
Could you give me a hint how I would do that?
sacred junco
And I have totally no idea how I can reduce that power...
Like, when there is only one power, I can simply reduce it modulo phi(n), but in order to do that here I'd need to compute 341^42 which is not possible without a calculator.
So I guess I somehow need to simplify the whole power 321^42 (or at least this power's power (42)), but I have no idea how to do that
light flicker
Well you were trying to calculate 28763^power (mod 25)
and you said you could use Euler's theorem to reduce the power
Now you're trying to calculate 341^42 (mod 20)
sacred junco
Well...
If I just have 341^42 (mod 20), I can just simplify the number itself (341) by modulo 20,
and I will get 1^42.
So I don't need to simplify 42 because, well, anyway I will have 1 in the result.
I understand that I'm wrong in my assumptions somewhere, but I can't figure out where exactly am I wrong..
sacred junco
Oh...
So the answer would be just 13?
light flicker
Yeah
sacred junco
Wow...
That was easier than it looked like, thanks =)
And one more question, if it wasn't 341, but something else (something simplifying which I wouldn't have gotten this nice 1), I would just simplify the power's power (42) by modulo phi(20), right?
sacred junco
Wow, this is like waay easier now than I initially thought it was..
Thanks again 🙂
unkempt nova
ugh i hate the euclidean algorithm
Can anyone help me with this?
So far I have:
97=5*19+2
19=2*9+1
I just have no real idea what i'm doing
stoic bear
I have never seen that notation before. What mean?
fathom sierra
inverse of 5 mod 97 i suppose
unkempt nova
yeah
fathom sierra
well first do you understand why euclidean algo could be useful here ?
like
what's finding an inverse mod 97 of a number ?
unkempt nova
i haven't a clue
the number that when multiplied with the original number will be congruent to 1 mod 97
fathom sierra
so yeah you want to find an $x$ such that $5x \equiv 1 \bmod{97}$
sterile pumiceBOT
emeric75:
fathom sierra
in other terms it's like getting one solution to the equation
5x - 97k = 1 for integers x,k
unkempt nova
right
fathom sierra
you have the right to speak zoph
ok so yeah now the euclidean algo
97=5 * 19+2
19=2 * 9+1
ah wait
unkempt nova
that's correct, right?
fathom sierra
you should have divided 5 by 2 not 19 by 2
unkempt nova
huh
fathom sierra
well you're finding gcd(97,5)
what makes euclidean algo work is that gcd(a,b) = gcd(b,a mod b) for any a,b
that's the property you use each time you divide here
i mean here you end up with 1 as gcd also but you're just lucky
dim basalt
Is there a simple way to find the unit digit and tens digit of two products when they are not presented in exponential form? I am familiar with the process of finding them when they are the product of two exponents. Is there a missing link that I am missing? For instance, the unit and tens digit of 725278 * 67066.
(sorry if i was interrupting)
fathom sierra
(well you're interrupting a bit)
dim basalt
apologiessss, please continue :/
fathom sierra
you want gcd(97,5), you divide 97 by 5 and you find that 97 mod 5 is 2
therefore gcd(97,5) = gcd(5,2)
and you continue dividing until you come up to a trivial case (remainder being 1 or 0)
unkempt nova
okay
what did I do wrong in the first place when I was diving?
how do I know what to divide
fathom sierra
the number you divided by at some step becomes the number you divide from at the next step
97 = 5 * 19 + 2
5 = 2 * 2 + 1
unkempt nova
yeah, I get that, but how do I know which number to bring down to the second line? (5)
sorry i'm not very good at this
unkempt nova
yeah, but in general, how do I know which one I should bring down
upbeat wren
For gcd(a,b) where a > b, the first two lines are always:
a = b(x1) + x2
b = x2(x3) + x4
then:
x2 = x4(x5) + x6
unkempt nova
right, thank you
I don't know what to do afterwards though
I know it involves 1 = something
sacred junco
its impossible to have something like k^a * m^a = r^b * q^b where none of them are equal right
by the fundamental theorem of arithmatic
would this be a contradiction?
light flicker
uh take a = 2, b = 4, k = 9, m = 4, r = 3, q = 2
sacred junco
oh ok
thanks
if b^c = p^d * m^d then i can say p | b^c right? or can i only say that p^d | b^c?
i think a^c | b^d => a | b^d right?
sacred junco
oops sorry i just saw this
a^c | b^d so b^d = a^c * k
d^b = a (a^(c-1) * k)
=> a | d^b
i think
light flicker
Yep
sacred junco
thanks
dim basalt
dunno if this is advanced enough to be considered number theory but it regards factoring and I can't get my mind around it.
does anyone know how I might tackle it?
answer options are
B. 24
C. 36
D. 72```LCM of 108 and 24 is 216. which is 2^3 x 3^3, or 6*sqrt(6). not sure what to do with that information in terms of getting a solution
daring ice
Essentially you want to look at the prime factorization of everything, and keep in mind that the powers of primes for a perfect square are all even. Since if $n$ is an integer divisible by $p^\alpha$ then $p^{2\alpha}$ divides $n^2$. So break everything down into its prime factorization and that should tell you the prime powers which must at least divide $n$. This is what you want to use.
sterile pumiceBOT
Token:
daring ice
As an extra hint, if you think you solve it. 2 of your integers definitely work. Edit: I forgot about the start of the question, 2 of the integers won't divide ALL integers, 2 of them will divide all integers.
light flicker
Does that left hand side remind you of anything?
sterile pumiceBOT
Zento:
light flicker
Yes, but how do you get it closer to there
astral fiber
a^p-2 * a congruent to 1 mod p
light flicker
Hm not quite
Think about the left hand side of the equation in the question
And think about how you normally simplify things like that
astral fiber
sigma notation?
astral fiber
Im not sure how id simplify that
light flicker
If I told you to calculate 1 + 3 + 9 + 27 + ... + 3^100
Not mod anything, just normal numbers
How would you calculate it
sterile pumiceBOT
Zento:
light flicker
Yes, now finish your problem
light flicker
Check your work, read your problem again
astral fiber
so (1-a^p-1)/(1-a)
its congruent to a certain xmod p
multiply by a-1
a^p-1 = x(a-1)+1
a^p-1 = ax mod p
only number that satisfies this is 0
wait no
i got it in the end
thanks bro
unkempt nova
finally managed to get the hang of the euclidean algorithm
now the extended euclidean algorithm is eroding my brain cells
sacred junco
does the set of (1^1,...,1^n) union (3^1,...,3^n) union (5^1,...,5^n) etc for n going to infinity contain all natural numbers?
light flicker
6?
sacred junco
right im not putting it correctly, sec
(1*2^0,...,1*2^n) union (3*2^0,...,3*2^n) union etc
so 1,2,4,8... union 3,6,12,24... union 5,10,20... etc
light flicker
Is that list going through all odd numbers? Or all primes?
sacred junco
odd numbers
light flicker
Tell me what the fundamental theorem of arithmetic says
sacred junco
every integer can be written as a product of primes
sacred junco
yeah but say 42 its written as a product of 7 3 and 2
oh right 😄
you're so smart!
thanks a lot
thats why math is so beautiful 😄
bleak musk
@mental spindle think about the integers mod m. For 0, 1, 2, 3... m -1, the values are distinct. As soon as you get to m though, it wraps around to zero and the cycle restarts. This gives you m - 1 congruence classes
mental spindle
@bleak musk is that all it says?
bleak musk
Yep
mental spindle
I was reading this
I don't understand this step
maybe that was the wrong theorem 4.7
I found this one as well
mental spindle
which one?
which 4.7 i mean
i have been trying to understand this proof all day
but I cannot get the phi(n) per row part
bleak musk
What is phi(m) defined as?
mental spindle
phi is euilers totient function
bleak musk
(I know I’m asking this to help you through it)
Right
What does the totient function do
mental spindle
it counts the number of values from 1 -> n
which are coprime to it
like for phi(5) #{1,2,3,4} = 4
bleak musk
What does coprime mean?
bleak musk
Yeah
mental spindle
they share no common divisor
bleak musk
So phi(m) is the number of values r such that gcd(r, m) = 1
bleak musk
Right - so that gives you exactly phi(m) rows
mental spindle
and there are phi(m) of those rows
yup
but how do i prove
that in that row
there are phi(n) elements
mental spindle
np
😅
@bleak musk any idea?
this video kinda explains it
but they take an example
and in the end just outline what we need to prove for this to work
but never show how to prove the things needed to be proved
light flicker
Does anyone know anything about elementary genus theory with relation to quadratic forms?
I've been reading the book primes of the form x²+ny² and am a bit confused
sacred junco
from skimming it seems the genus is a type of quadratic form over the ring of integers
?
light flicker
I'll just put the question here
It shouldn't actually require any knowledge about genus theory of quadratic forms
A quadratic form is a function of the form f(x,y) = ax^2 + bxy + cy^2 where we require that gcd(a,b,c) = 1
a number n is said to be represented by a quadratic form if there exist integers x,y (maybe you need coprimeness here, and maybe you need them to be positive) such that ax^2 + bxy + cy^2 = n
The discriminant of a quadratic form is b^2 - 4ac
Maybe I'm missing something, but it seems that the book assumes that if some number n is represented by a quadratic form
Then any number n (mod D) with D as the discriminant, is also represented
But I'm not quite seeing why this is true
silver solar
ayy I've been reading the same book (only got up to Euler's proof of Fermat's theorem tho)
(wrote a dumbed down version of the proof bc I wanted to have the picture clear to myself)
light flicker
Of the problem I'm having?
serene socket
2 is represented by x^2+y^2 but is 6?
light flicker
Hm true
light flicker
Oh lmao, nah that was pretty confusing for me too
This is a super cool book though
silver solar
ain't nobody got time to learn about quadratic forms 
light flicker
lmao true
Unless you just study NT I guess
@serene socket It seems that they only use this fact for values that are relatively prime to D
Numbers in (Z/DZ)*
upbeat wren
x^2 + y^2 = 2 doesn't mean 6 is represented by a quadratic form. I'm pretty sure the xy term can't have a coefficient of zero.
upbeat wren
Sorry. Fouled that one up.
x^2 + y^2 = 2 doesn't mean 2 is represented by a quadratic form. I'm pretty sure the xy term can't have a coefficient of zero.
light flicker
It can have a coefficient of zero
upbeat wren
Okay. I'd take issue with the definition of a quadratic form. It seems if one of the coefficients are zero then the set of quadratic forms can have odd elements.
light flicker
Uh, what do you mean by odd elements
upbeat wren
elements causing issues / problems
light flicker
What issues or problems do you have in mind
Because there's plenty of nice theory associated with these quadratic forms
upbeat wren
Yeah, but if you restrict it further where no coefficient is zero there may be more interesting properties of the restricted set.
(I'm kinda talking without research but I'm just saying ...)
light flicker
I mean, if you can't name any, then you don't really have an argument
serene socket
Not gonna happen, because you can make the change of variables x -> ax +by and y -> cx + dy where ad - bc = 1 and get a quadratic form with no zero coefficients with exactly the same sets of represented integers
light flicker
Anyways
The relevant theorem in the book is that
m is properly represented by a primitive form of discriminant D if and only if D is a quadratic residue mod m
But unless I'm forgetting some basic quadratic residue facts
I don't see how changing m by multiples of D would preserve this
Since I'm not sure reciprocity tells you this
serene socket
I think it's a deep theorem
light flicker
Seems weird, this book is solid and pretty well-known, seems weird they would skip over this fact without mentioning it at all
serene socket
No,
that fact is part of the statement of the theorem
by quadratic reciprocity
but like
Say we've proven that m is represented iff D is a quadratic residue mod m
then it would follow that representedness only depends on equivalence class mod D
upbeat wren
My beef is the problem should state (1,1,0), (0,1,1) and (1,0,1) are not allowed for (a, b, c).
light flicker
Hm, why is that?
I feel like I'm missing something very obvious here
Because this is a proven theorem in the book, it's not too difficult
serene socket
@upbeat wren Read what I said about change of variables
upbeat wren
This is not going to sound very technical. gcd(a,0,b) where a, b are non-one is 0. The only exception is if a, b are both 1. It's like the "limit" of a special case.
upbeat wren
sigh... sorry yes. My point is it doesn't satisfy the conditions given.
upbeat wren
But the definition says gcd(a,b,c) =1
serene socket
So something like (3,0,4) would satisfy the gcd condition
3x^2 + 4y^2
gcd(3,0,4) = gcd(3,4) = 1
upbeat wren
For b=0, the ONLY case where the definition is satisfied is if a=c=1
upbeat wren
Okay. sorry. I'll shush. But I still think cases where a or b or c =0 can be excluded in the definitions. As stated 0 is odd in gcd.
serene socket
I wasn't asking you to shush
light flicker
Yeah I'm still not seeing it, why if D is a quadratic residue mod m, then does representedness only depend on equivalence class mod D? I could see if it said m is a quadratic residue mod D. But I'm not seeing how to flip it around since reciprocity doesn't finish it
upbeat wren
I was 🙂
serene socket
I was asking you to update your mental definition of gcd when 0 is included
light flicker
0 isn't that odd in gcd
Just like Icy said, something like 3x^2 + 4y^2 satisfies gcd(a,b,c) = 1
serene socket
It's not "You're wrong, get out of here"
It's "You're wrong, and here's why, hopefully you agree now"
upbeat wren
Yeah but I'm guessing the cases where b = 0 have some properties that don't apply when b <> 0 and vice versa.
light flicker
But it's just not true
serene socket
quadratic forms have an SL_2(Z) action
light flicker
As Icy also said, any quadratic form with a zero can be switched to something that has no zero, but represents the exact same numbers
serene socket
given by ([[a b][c d]]Q)(x,y) = Q(ax+by,cx+dy)
light flicker
Oh huh I didn't think about it like that
serene socket
the inverse of [[a b][c d]] in SL_2(Z) is [[d -b][-c a]]
So If Q' = [[a b][c d]]Q
Then Q(x,y) = Q'(dx-by, -cx+ay)
giving a 1-to-1 correspondence between integers represented by Q and integers represented by Q'
light flicker
Besides, I can give concrete examples of things that you would lose if you removed the forms with zero
There's a group structure on the genera of reduced forms, and this is something that wouldn't be as nice if you removed the forms with zero
Or at least, your definition of what "reduced" means, would not be as clean
serene socket
Isn't reduced forms just picking a representative of each SL_2(Z)-equivalence class?
upbeat wren
🙂 I need to study math. if this is still the topic of discussion and I have something to say, I'll say something.
light flicker
Yeah, but there's a nice way to describe them
That makes certain things easy to calculate
If you look at positive definite forms, then it is reduced if |b| \leq a \leq c and b \geq 0 if either |b| = a or a = c
But anyways yeah
I'm still not seeing why that theorem implies that representedness only depends on equivalence class modulo D
serene socket
Also hmm
6 isn't represented by x^2+y^2 and 4 is a quadratic residue mod 6
4 is a quadratic residue mod anything
What is the theorem even saying for this
oh oops
discriminant is -4
not 4
hm yes
is -4 a quadratic residue mod 6
No because that's 2 mod 3
upbeat wren
Well I have two final comments, perhaps the gcd condition should be changed to pairwise and perhaps we should remove the special case where the discriminant=1, -1?
serene socket
I'm not sure why pairwise gcd would make any difference whatsoever
upbeat wren
(again I'm doing so with absolutely no logical backing)
serene socket
$\gcd(a_1,\dots,a_n)$ is defined as the meet of $a_1,\dots,a_n$ in the divisibility poset
which is a lattice too
upbeat wren
gcd(3,0) = 3, gcd(4, 0) = 4.
sterile pumiceBOT
Icy001:
upbeat wren
The restriction of gcd(a,b)=gcd(b,c)=gcd(a,c)=1 might provide a set with more structure.
light flicker
Hard to get more structure than a group structure honestly
than a finite abelian group structure even more
serene socket
I'm pretty sure you can make a SL_2(Z) representative of any equivalence class with gcd(a,b)=gcd(b,c)=gcd(a,c)=1
light flicker
I also think this is true
serene socket
And quadratic forms in the same equivalence class are really the same from every possible point of view
upbeat wren
I'll bow out now. 🙂
upbeat wren
Although a funsies quick question just occurred to me. If A = {x| x = a^2 + b^2 where a, b in Z}, show for all integers d>0, d = a_1 + a_2.
light flicker
This is just lagrange's four square theorem
upbeat wren
it is.
dim basalt
This problem stumped me. How does one approach this type of problem?
function f(100) = the product of all even integers from 2 to 100 inclusive. What is the largest prime factor of f(100)?
the discussion online states that the answer is found by finding the largest prime factor n such that 2n < 100 (therefore 47). Why would it not be the largest prime factor less than 100?
quick furnace
f(100) = 2 * 4 * 6 * ... * 100
= 2^50 * 50!
50! is not divisible by any prime numbers greater than 50
dim basalt
I think i see. Therefore if f(100) were to be the product of all integers from 2 to 100 inclusive, the answer would no longer be 47?
rather, 97?
quick furnace
yes indeed
dim basalt
cool! thank you
fervent crest
How do I prove that $d(n)=O(n^\varepsilon)$ for any $\varepsilon>0$, where $d(n)$ is the number of divisors
sterile pumiceBOT
Whoever:
light flicker
Imagine not just asking me smh
fervent crest
Ok
light flicker
Okay bye
fervent crest
@light flicker I'm sorry help
fervent crest
Big O notation
fervent crest
$f(x)=O(g(x))$ means that there exists a constant $K$ and $m$ such that $x\geq m$ means $f(x)\leq K|g(x)|$
sterile pumiceBOT
Whoever:
supple furnace
Here’s my approach. Fix r>0. We show that d(n)/n^r is bounded. Take the prime factorization of n and let the ith prime be p_i with exponent e_i. Then d(n)/n^r is multiplicative and the p_i component is (e_i+1)/p_i^(re_i). First, if we fix p_i, then the function of e_i is bounded because 1+1/e_i is less than p^r for sufficiently large e_i. Secondly, since e^x>1+x, if p_i>e^(1/r), then (e_i+1)/p_i^(re_i)<1. n can be written in the form r_1s_1, where r_1 is a product of bad prime powers while s_1 is product of good prime powers. We showed that d(r_1)/r_1^r is bounded, so d(n)/n^r is bounded as well.
@fervent crest
supple furnace
I proved that for all sufficiently large p_i, we have (e_i+1)/p_i^(re_i)<1 regardless of e_i.
unkempt nova
How do I find positive solutions to a diophantine equation? I figured out a way to solve them, but I can't get exclusively positive solutions
swift shard
Have an example?
light flicker
The answer, just like for everything else you've been doing, is euclidean algorithm
unkempt nova
Yeah so like
swift shard
Great, finding an answer gets you everywhere. Now, note that if (x,y) is a solution, (x - 5, y + 3) is one too
So you have x = 62 - 5k and y = -31 + 3k
swift shard
3 and 5 are coprime. So you can kinda swap the coefficients and get more solutions
If they weren't coprime then you can divide by the gcd when doing this.
unkempt nova
Yeah, originally the equation was 21x + 35y = 217
swift shard
3x + 6y = 6
If (x,y) is a solution, (x+2, y-1) is one as well
unkempt nova
thanks
So I know that ϕ(ab) where a, b are prime equals ϕ(a)ϕ(b), but what about ϕ(abc) where c is prime as well? (the euler ϕ-function)
swift shard
@unkempt nova
You have a bit more power than that:
φ(ab) = φ(a)φ(b)
If a and b are coprime
unkempt nova
ah! i knew i forgot something, thanks
swift shard
So yes, φ splits three ways if a,b,c are each coprime
unkempt nova
alright, thank youuu
timber blaze
Prove that $$\frac{5n +7}{3n + 4} $$is irreducible for $n \in \mathbb{Z}$
sterile pumiceBOT
Daniel Cann:
timber blaze
I said:
We need to show that the numerator and denominator are coprime. I will apply the division algorithm to find the highest common factor
$$ (5n + 7) = (3n + 4) \times 1 + (2n + 3)$$
$$(3n + 4) = (2n + 3) \times 1 + (n + 1)$$
$$(2n + 3) = (n + 1) \times 2 + (1)$$
$$(n + 1) = (1) \times n + (1)$$
$$n = 1 \times n + 0$$
Hence 1 is the HCF and the numerator and denominator are coprime $\Rightarrow \frac{5n + 7}{3n + 4}$ is irreducible for $n \in \mathbb{Z}$
sterile pumiceBOT
Daniel Cann:
timber blaze
Is this a convincing proof?
I was unsure about my application of the division algorithm here. I could've used Bezout's lemma and tried to find x and y such that the Hcf was 1, but I felt like that was a pretty inefficient approach
timber blaze
Ooo thank you. Would it be necessary to work backwards to find that 3 and -2 would be my coefficients and then state that using Bezout's lemma or is what I did enough?
sacred junco
What you did is enough
timber blaze
Good. I've cut out a ton of proof statements for my number theory classes that I've put in a box and I'm doing one a day to help prepare for an exam and the fact that I got this one is a good sign
EVEN THOUGH this one is a pretty easy one
But I'm perpetually afraid of not providing enough steps
sacred junco
Is this a college class?
timber blaze
Because number theory seems to be the land of not-obvious
No, it's sixth form
And I cannot assume anything since it's the land of not-obvious
Or miss out any steps in my working
Sixth form additional pure
The additional pure module in further maths
sacred junco
Thats interesting
timber blaze
We have to do some topics from number theory from this stuff to stuff like linear congruences, quadratic residues, that type of thing
It's really simple compared to what's out there but it's a different 'form' of mathematics to what I'm used to
elfin lava
I don't have room in my schedule to take elementary number theory in my undergraduate studies, is there a resource yall would recommend for self teaching?
light flicker
How much math do you know?
light flicker
@elfin lava
elfin lava
Multivariable calc, ODE, some PDE, Linear Algebra, Probability and Inference, Set theory, and some misc. applied stuff from special topics courses related to data science.
@light flicker
light flicker
Elementary number theory and its applications by Rosen is nice
If you study some abstract algebra, you could pick up Classical introduction to number theory by Ireland and Rosen instead
swift shard
Number theory via group theory is bae
elfin lava
Thank you. I will be taking my first abstract algebra class next summer at the earliest. Spring semester I am taking Real Analysis and Enumerative Combinatorics, the rest of my immediate schedule is stats and programming, not really relevant.
This the one?
swift shard
Honestly you'll get a pretty good grasp of number theory if you spend enough time in group theory
elfin lava
I am guessing I will be disadvantaged without it?
swift shard
No
light flicker
Yes that's the book
you can definitely learn elementary number theory without knowledge of group theory or algebra
But knowing group theory really allows you to clear up why some things are true
Things like Wilson's theorem or Fermat's Little/Euler's theorem become immediately obvious with knowledge of group theory
And that's how you start thinking about those things
As just applications of the results from group theory
but, regardless, you can still learn number theory without these ideas, and see all the cool ideas
wild zinc
I'm interested to see how you get wilson's theorem from group theory
I don't doubt it can be done (my immediate thoughts are ||looking at symmetric groups||) but it seems less obvious than fermat/euler
anyway I'm off out for a bit now anyway so I'll have a think and if I don't think of it by the time I'm back I'll let you know
oh wait
are you using that ||multiplication forms a cyclic group mod p||?
light flicker
Nope
wild zinc
oh wait nvm
you just
||product of all elements in an abelian group = product of elements of order 2 of a group||
and then the result follows from ||euclid lemma||
but tbh that seems to be the same as the standard number theoretical proof, just with group theory language
anyway I'm satisfied it's doable simply now, so interested to see what your method was
light flicker
Yeah that's the idea
But I usually say it as that you can pair every element up with their inverse
So we just have to look at what is their own inverse
serene socket
TIL Wilson’s theorem is another one of those theorems that are really easy from the point of view of group theory
light flicker
Uh is this sarcasm or
serene socket
no
light flicker
Oh wow
I mean, you're like super knowledgeable so I assumed you would've seen this before
grizzled stump
There’s also a neat proof of Wilson’s theorem via Sylow theory IIRC 
silent lantern
@elfin lava justin stevens gives a really good introductary nt book
problems in elementary number theory is good as well
ruby topaz
i have a really hard time doing exercice related to bijection injection does anyone know a youtuber or a site that explain it well? how to procede to prove that it s bejective etc for example if you have an application f:F -> E and g:E->F if fog: Id how can you prove that f is surjective...? there are many other excercice but i mean in this kind of abstraction not something with numbers
it would also be cool for relations and equivalence classes
sacred junco
@LocalCreeper#1521 his book is aimed at olympiad Nt
wild zinc
tbh there's not that much difference between most elementary number theory and olympiad number theory
sacred junco
Quadratic residues, and so forth arent on there
wild zinc
oh nvm the book is just incomplete
although yeah I haven't really seen a NT book aimed at olympiads that really covers everything
exotic raptor
succ
wild zinc
why
dusky pecan
https://en.wikipedia.org/wiki/Diophantine_equation
Under Linear Diophantine Equations:
"Finally, given two solutions such that ax1 + by1 = ax2 + by2 = c, one deduces that u(x2 − x1) + v(y2 − y1) = 0. As u and v are coprime, Euclid's lemma shows that v divides x2 − x1."
why is it that v divides x2-x1?
Euclid's lemma just states that if a prime p divides ab, then p must divide at least one of a or b. i don't see how thats applicable here though
light flicker
Write it as u(x2-x1) = v(y1-y2)
dusky pecan
still i dont see how theres any talk of any prime number
we only have that u,v are coprime
hang on. according to this version of euclid's lemma http://mathworld.wolfram.com/EuclidsLemma.html, it says that if d divides ab, and d is coprime to a, then d must divide b
so if u(x2-x1) = v(y1-y2), then v divides u(x2-x1), and with v,u being coprime, v must divide (x2-x1)
ah i see. the one on posted on wolfram is generalization of euclids lemma
anyway thanks for ur help @light flicker
light flicker
You should see how that generalization follows
Take some prime p dividing v
p divides v(y1-y2) so it also divides u(x2-x1)
supple furnace
Euclid's Lemma really drew me to NT originally
inner crest
Here's a problem I just came up with: Calculate the last 3 digits of 3↑↑↑3. (You are allowed to use a computer)
stoic bear
I have seen this before in a PROMYS application problem set?
inner crest
wtf lmao
inner crest
yep
inner crest
https://prase.cz/kalva/putnam/putn85.html maybe you're thinking of A4?
winter bear
yeah
upbeat wren
In another more atom-y universe an old couple wins 2 X 10^2020 Dahlars in a lottery. They decide to split it 50/50 (10^2020 each). The husband puts his part in a savings account at X% interest. The wife decides to put her part in a savings account that earns Y% a year. Both X and Y are whole numbers between 1 and 99 and X and Y are 10 apart. What is X and Y if at the start of years 2, 4, 6, 8 ... 2000 the total amount is divisible by 76.
Er edit ... The years with a total divisible by 76 may only be up to 1000.
silent lantern
@inner crest @stoic bear yeah those are really common NT problems
pretty killeable with CRT and Fermat's little theorem but yea
sacred junco
Can someone help with this?
I know that maybe I should do the product of those two divided by the lcm
But I don't know the lcm?
craggy solstice
@sacred junco
what have you tried yet
think of it in this way
if d|b and d |c then d| (b-c)
wild zinc
big hint: ||use euclid's algorithm||
sacred junco
@wild zinc How?
craggy solstice
my thing is shorter
sacred junco
I have that -1
wild zinc
thonk
sacred junco
So I have 2^1998 - 2^1989, now what?
wild zinc
your thing is exactly the same
sacred junco
?
wild zinc
euclid's algorithm uses gcd(a,b) = gcd(a mod b, b) for a <= b
and repeats
which is another way of saying it uses gcd(a,b) = gcd(a-b, b) for a <= b and repeats
sacred junco
So 511
wild zinc
yes, what did you do for that
sacred junco
Why?
sacred junco
..
wild zinc
nvm that does work to show that gcd(2^1998 - 1, 2^1989 - 1) divides 511
sacred junco
Why?
wild zinc
gcd(2^1998 - 1, 2^1989 - 1) = gcd(2^1998 - 2^1989, 2^1989 -1) = gcd(2^1989(2^9 - 1), 2^1989 - 1)
and 2^1989 - 1 is odd
so this is gcd(2^9 - 1, 2^1989 - 1)
sacred junco
And now how can you prove that's lowest form?
wild zinc
you need to prove 2^9 - 1 divides 2^1989 - 1
stuck lintel
Think about how you can factor a^n -1
stuck lintel
Woops didn’t mean to react trash
$\frac{a^n -1}{a-1} = \frac{(a-1)(a^{n-1} + \dots + 1)}{a-1} = a^{n-1} + \dots + 1$
sterile pumiceBOT
Plum:
sacred junco
So what can I do from there?
stuck lintel
So think about what a and n are here
wild zinc
you want to show that 2^9-1 divides 2^1989-1
so select a appropriately that you might get 2^9-1 dividing something
and then see if you can pick n appropriately too
sacred junco
?
sleek cove
worth doing the num theory section in this book before class starts in a couple weeks?
alpine jasper
you just need basic proof skills: direct proof, contradiction, ... etc
if you want to be well prepared for that class i highly recommend reading something about number theory
i'm somewhat familiar with "a friendly introduction to number theory" by silverman, i recommend that, since you're looking for number theory material anyway
sacred junco
Well, anything Springer is good tbh
You might enjoy ENT by Gareth Jones
Also Springer
sleek cove
ok thanks for the suggestions
not really so much worried about being "well prepared" as i am just wanting to get used to the types of basic problems
like if they are induction/logic/etc based or what not
sacred junco
The remainders when two natural numbers are divided by 16 are 11 and 14 respectively. Find the remainder when their sum is divided by 8.
I know how to solve it, but I am confused on by what they do. They do a = 16k_1 + 11 = 2k_1(8) + 8 + 3 = (2k_1 + 1)8 + 3
And b = 16k_2 + 14 = 2k_2(8) + 8 + 6 = (2k_2 + 1)8 + 6
And I am confused on what they did there. They already have 2k_1 and 2k_2, so why is there a 16 there and not an 8?
sacred junco
<@&286206848099549185>
long whale
wdym, k_1 and k_2 are numbers and you just split 16 into 2 * 8
sacred junco
No look
It goes like this:
a = 16k_1 + 11 to a = 2k_1(8) + 8 + 3
Why are they adding 8 to 2k_1(8) if it's 2k already?
craggy solstice
lol
sacred junco
What is the greatest common divisor of 2^1998 - 1 and 2^1989 - 1?
I still don't understand this problem. Where do I get after gcd(2^1998 - 1, 2^1989 - 1) = gcd(2^1998 - 1 - 2^1989 + 1, 2^1989 - 1) = gcd(2^1998 - 2^1989, 2^1989 - 1) = gcd(2^1989(2^9 - 1), 2^1989 -1)
How do I prove that 2^9 - 1 divides 2^1989 - 1?
sacred junco
<@&286206848099549185>
use polynomial division perhaps?
Well that's not very number theory-y
sure it is
set x = 2
and do polynomial division with x-1
There should be some way to prove this otherwise..
or you could do difference of cubes
since 1989 divides 3
Yeah, but that's still not very number theory-y
They don't even do that
theres a formula for this
@sacred junco Where'd you get that?
stack exchange unfortunately
sometimes i forget things
but i can explain it for you if you want
even though its online already lol
essentially if you have two numbers, 2^a-1 and 2^b-1 and a|b then 2^a-1|2^b-1
@sacred junco This doesn't seem very intutiive...
ok ill keep going
assuming that what i just said was true
2^p-1 will divide 2^m-1 and 2^n-1 if p|m and p|n
the greater p is, the greater the divisor will be
so we need to find the gcd(m,n)
and set that equal to p
this gives the largest possible divisor for 2^m-1 and 2^n-1
So is there a way to do this problem without knowing that formula...
idk
here's the link that explains the formula
take a look at it
Yeah, but I'm not really interested in the general case to be honest
More like.. this specific case
It's not even the general case
It's the "general case" when the base is 2
Which is not extremely useful, lol
sterile pumiceBOT
Denial:
sacred junco
Let f(x) = 12x+7 and g(x) = 5x+2 whenever x is a positive integer. Define h(x) to be the greatest common divisor of f(x) and g(x). What is the sum of all possible values of h(x)?
Can someone help?
I used the euclidean algo gcd(12x+7,5x+2) a few times to get to gcd(13,x+8). Now what?
stuck lintel
Well we know that 13 only has 2 factors, 1 and 13, so see if both of those are possible
sacred junco
Hello? <@&286206848099549185> Please...
sacred junco
the gcd of 13 and any number can only be two numbers, 13 and 1
Yes
I know that
But so what?
How am I supposed to use that information?
the question asks for the sum of all possible values of h(x)
the only possible values are 1 and 13
so the sum must be 14
But we still have x+8
Am I supposed to ignore that part?
that doesn't matter because we know that there are only 2 possibilites
if you wanted to prove it, you could find x such that gcd(13,x+8) = 1 and gcd(13,x+8)=13
this is quite simple
but those are the only possible values
The answer isn't correct..
then you did the euclidean algorithm wrong
Can you tell me if I did this correct
"How many perfect cube factors does 3^6 * 5^10 have?"
Basically, 11 possibilities
I'm kind of lazy to list them but, but 3 can be 3^0 or 3^3 or 3^6, and 5 can be 5^0, 5^3, 5^6, 5^9
With the exception of 3^0 and 5^0 of course. I counted 11?
hushed ether
Why exclude 1?
sacred junco
Why would that be a perfect cube..?
hushed ether
Because it's 1 cubed
sacred junco
??????
hushed ether
You're doing it exactly right, but the answer is 12
sacred junco
What does 1 have to do with anything?
sacred junco
So then the answer can be any number. Because 1^30 is also a perfect cube..
I don't agree with what you are saying.
hushed ether
1^30 is a perfect cube
Because it's 1
A perfect cube is an integer that can be obtained by cubing a positive integer
sacred junco
Ok
why not make a table
I agree with you
like a times table but the 3 factors are on the top and 5 factors are on the bottom
you would get a unique number in each square
since the table is 4x3, the number of values is 12
@sacred junco
this is how you would do the euclidean algorithm
so the gcd is either 11 or 1
and so the answer is 12
Yeah
I know
I didn't reply to that sorry, but I did it again and it was 12
Why is this subject so difficult?
sacred junco
Can someone check my solution?
Given that a is a multiple of 1428, find the greatest common divisor of a^2+9a+24 and a+4.
My solution: gcd(a^2+9a+24,a+4)
= gcd(a^2+9a+24 - (a+4)^2,a+4)
= gcd(a^2+9a+24 - a^2-8a-16,a+4)
= gcd(a+8,a+4)
= gcd(4,a+4)
We know that 4 | 1428, therefore, it's 4.
shadow steeple
I got 4 as well
sacred junco
@shadow steeple But is my method correct?
sacred junco
<@&286206848099549185>
silent lantern
@sacred junco that’s fine I think
sacred junco
Is there a short proof of
Given that $a\equiv b\pmod{m}$ and $c\equiv d\pmod{m}$, for $a,b,c,d,m\in\mathbb{Z}$ we have $ac\equiv bd \pmod{m}$?
sterile pumiceBOT
defective:
sacred junco
<@&286206848099549185>
long whale
just like a=km+b for some k, c=lm+d for some l, then (km+b)(ml+d)=km^2l+kmd+lmb+bd, the first 3 terms are divisible by m, so 0modm then bd is left as a remainder
sacred junco
What?
Can someone put it in terms of m?
It's kind of difficult to read that many variables and losing the m altogether..
long whale
i mean i can write k as km and l as lm if that makes it easier
sacred junco
So do you have
Ok
So what happens to the bd?
Wait
I don't think your thing is correct
You have no m^2 anywhere
sacred junco
Why not?
long whale
i mean i could prove that too i guess
swift shard
Sry, I mean
am + b = b (mod m)
long whale
is that not basically the definition of residues
long whale
what about it confused you
sterile pumiceBOT
defective:
long whale
yes
sacred junco
And what about bd?
That's the rhs
Can you use symmetry to do
Well, nevermind
But now what @long whale ?
long whale
i mean now just check the residue of the right side modm
so anything that's an integer times m is going to be 0modm right
so bd is what's left that's not 0modm, and that's just bdmodm
long whale
bdmodm is what you're trying to show ac is congruent to
sacred junco
Are you trying to say bd (mod m)?
long whale
yes
sacred junco
Oh
Okay
So because
$ac = km^2l+kmd+lmb+bd$ in bold are multiples of m, it will equal 0 after the modulo operation
Is that correct?
sterile pumiceBOT
defective:
sacred junco
@long whale
long whale
yeah
sacred junco
@long whale Thanks
Can someone check this proof?
$15 \equiv 3 \pmod{4}$
$15^2 \equiv 3^2 \equiv 9 \equiv 1 \pmod{4}$
$15^3 \equiv 3^3 \equiv 3 \pmod{4}$
$15^4 \equiv 3^4 \equiv 1 \pmod{4}$
Thus, we have:
$15^{15} \equiv 3^{15} \equiv 3 \pmod{4}$
sterile pumiceBOT
defective:
sacred junco
<@&286206848099549185>
sacred junco
15^15 = 3^15 mod 4 = 3^3^5 mod 4 = 3^5 mod 4 = 3^3 x 3^2 mod 4 = 3 mod 4
So yes
Correct @sacred junco
Thanks @sacred junco
steep pebble
How do I self study number theory
obtuse solstice
Read books
swift shard
Do group theory instead
inner crest
join the dark side
inner anchor
Is there an elementary proof of legendres theorem on three squares?
inner anchor
Apparently one exists in Uspensky and Heaslet, Elementary Number Theory (1939), pp. 465-474
If anyone could find a PDF of that i would be grateful
meager cobalt
you can get it on libgen
inner anchor
Thanks a lot!
red saffron
How show a^2 - 2b^2 = 1 has infinite integer solutions using Z[sqrt(2)] and that if N(r)=a^2 - 2b^2 where r=a+bsqrt(2) then N(rs)=N(r)N(s)
light flicker
You're looking for units in Z[sqrt(2)]
red saffron
@light flicker the units are a+bsqrt(2)?
light flicker
uh, I'm not sure what you're asking
red saffron
I know (3, 2) and (0, 0) work and that's it
light flicker
you can show that an element of the ring is a unit if and only if its norm is 1
So the units are exactly those that solve your Pell equation
red saffron
I don't know what norm or unit means @light flicker I haven't done any ring theory
lol
Let me show u full question actually
light flicker
The norm is the N function you wrote down
light flicker
units are those elements with inverses
You should first prove that something is a unit if and only if it has norm 1
light flicker
uh what
red saffron
a+bsqrt2
light flicker
how can a and b be in r then
light flicker
I have no idea what you're trying to say
red saffron
a unit is r such that N(r)=1 where N is norm?
light flicker
where is this problem from
light flicker
Yeah there's probably an elementary solution here
Oh yeah it's dumb
You can figure it out
red saffron
can u give me a hint
light flicker
Focus on the thing they tell you to show
red saffron
i tried substituting N(r)=1 into it
light flicker
No
red saffron
yeah thought so
light flicker
You get that the r in your ring such that N(r) = 1 are exactly the solutions to your pell equation right
red saffron
yeah
light flicker
So you already found one
how do you find more r such that N(r) = 1, if you have one such r
using the fact that N(rs) = N(r)N(s)
red saffron
you're talking about r = 3 + 2sqrt(2) right
light flicker
any such r
light flicker
but how
light flicker
What's s
red saffron
another element of Z{sqrt(2)}
light flicker
Well is the norm of s always one
red saffron
i thought N(r)=1 not N(s)
light flicker
So is the norm of s always one
light flicker
Is it?
light flicker
Yes that's the problem
red saffron
uh ok
torn escarp
hint: you can think about the product property as N(r^m) = N(r)^m
sacred junco
Can someone explain me why this thing works: Want to find 2 last digits of $3^{2016}$, they say $\phi\left(100\right)=40, 2016 = 16\left(40\right) \implies 3^{2016} = 3^{16} \left(100\right)$
sterile pumiceBOT
Godel:
inner anchor
This follows directly from Eulers totient theorem, which is just a generalization of Fermats little theorem
inner anchor
A way to think about eulers totient theorem is looking at the group $\left(\mathbb{Z}/n\mathbb{Z}\right)^{\times}$, with its cardinality being exactly $\phi(n)$. Now choosing some element $a\in\left(\mathbb{Z}/n\mathbb{Z}\right)^{\times}$ and looking at the set $S = {am_1, am_2, \ldots, am_{\phi(n)}}$, where the m:s are the different members of the set. Now you might notice that $S$ is just a permutation of $\left(\mathbb{Z}/n\mathbb{Z}\right)^{\times}$, and so $\prod^{\phi(n)}{i=1} m_i \equiv \prod^{\phi(n)}{i=1} am_i$, which after dividing throughtout by $\prod^{\phi(n)}_{i=1} m_i$ gives us $a^{\phi(n)}=1$
sterile pumiceBOT
Pappa:
inner anchor
But the main idea is that S is just a permutation of the group that we started with
sacred junco
yeah got it, thx
How would I find the last two digits of $3^{3^{3&{\dots}}}$ where 3 shows 2020 times
sterile pumiceBOT
Godel:
Compile Error! Click the 
reaction for details. (You may edit your message)
sacred junco
I've tried few things but Im not sure if what I did was legal, basically if $a = b mod n \implies k^a = k^b mod n$?
sterile pumiceBOT
Godel:
sacred junco
anyways that didnt lead my anywhere after some time
stuck lintel
if a = b mod phi(n) and (k,n)=1 then k^a = k^b mod n by euler totient theorem
sacred junco
ok so I guess if$3^{3^{3}} ={100} 83 \implies 3^{3^{3^{3}}} ={100} 3^{2 \phi \left(100\right) + 3} =_{100} 3^3$ but not sure what next
sterile pumiceBOT
Godel:
sacred junco
with that I got that 3 ^3.. 2020 times is congruent to 1010 times which is congruent to 505 times and stopped there
winter bear
this is a putnam problem iirc
but basically find the order of 3 mod 100 (its not phi(100) in this case) and then things will work out nicely
sacred junco
@winter bear how do I find the order of 3 in Z*_100 tho
stuck lintel
i remember seeing somewhere that 3^3^...^3 with some k number of 3s where k>=3 all have the same remainder mod 100
stuck lintel
well 3^3^3 = 3^3 mod 40
inner anchor
its probably better to first look modulo 4 and then mod 25 and then just crt
because mod 4 is easy in this case
sacred junco
yep
inner anchor
mod 25 is kinda awful tho
inner anchor
I havent really ever used it but maybe hensels lemma could help
sacred junco
this problem showed up on my NT exam I never heard about that shit
I supposed its somehow doable with eulers theorem or sth
but ye maybe its tricky
inner anchor
so the order of 3 mod 100 is 20
sacred junco
how
inner anchor
calculator
sacred junco
oh ok lmao
inner anchor
but theres probably a trick that im missing
well you know that the order of 100 divides phi(100)
which helps out a bit
winter bear
yeah just brute force basically, here its easy
but the fact that 20|100 is really nice
cause if we can show the thing remains invariant mod 100, then it remains invariant mod 20
3^(3^3)%20
,calc 3^(3^3)%20
sterile pumiceBOT
Result:
7
,calc 3^3%20
sterile pumiceBOT
Result:
7
Why do u need 20 divides 100
How does it help
Actually havent tried to work it out yet since I dont have any pen and paper, will try later I guess
But thx boys
winter bear
umm ok yeah il let u figure that out on ur own ig
torn escarp
just tried it, way I did it was kind of lame but works
I just prayed that a_{n+1} = 3^{a_n} would eventually have a fixed point
so the sequence is 3, 27, 87, 87 after that I knew I was stuck
I computed 3^27 as
repeated squaring by writing 27 in base 2, $3^{27} \equiv 3^{2^4}*3^{2^3}*3^{2}*3 \mod 100$
sterile pumiceBOT
Merosity:
torn escarp
mod 100 makes it pretty straightforward
then once you get the final step to confirm, 3^{87} mod 100 you reduce it to 3^7 mod 100 by Euler
sacred junco
yeah so what I did before was getting to 3,27,87 and werent able to calculate the next one xD
torn escarp
that last one is actually the easiest
sacred junco
wait I actually calulcated it wrongy, I remember getting 83
torn escarp
$3^{87} \equiv 3^7 \equiv 33^23^{2^2} \equiv 3981 \equiv 27*81 \equiv 87 \mod 100$
sterile pumiceBOT
Merosity:
sacred junco
ok and how 3^27?
torn escarp
I wrote that one out I thought
sacred junco
cause phi(100)=40 so cant reduce this way
torn escarp
$3^{27} \equiv 3^{2^4}*3^{2^3}*3^{2}*3 \mod 100$
sterile pumiceBOT
Merosity:
sacred junco
Oh
torn escarp
writing 27 in base 2 lets you repeatedly square 3
so I squared like, 4 times mod 100, took a few seconds
winter bear
see ord_100 (3) = 20
torn escarp
then multiplied the results together
winter bear
so u can just 3^7
sacred junco
ok so now I would have to calculate 3^16 3^8 mod 100
winter bear
umm trial and error, i did it months ago lol
sacred junco
right
torn escarp
well, my approach was not by trial and error, didn't want to waste time on that
winter bear
well we dont even need to do order, just suffices to show that 3^(20) = 1 mod 100
torn escarp
that could have taken any amount of time
at this point I've actually spent more time discussing the approach than I took to solve it
so it's not really worth discussing imo lol
if getting the order worked then good though
sacred junco
and like calculating 3^16 did you just multiply and reduce when it got past 100?
light flicker
idk why even talk about mod 100, you only care about mod 25 since mod 4 i easy
sacred junco
mod 25 is not that easy I think
light flicker
well, euler's theorem help you reduce it down to looking at
3^3... mod 20
which again you split up into mod 4 and mod 5
and again mod 4 is easy
now you can apply the exact same idea
euler's theorem or I guess fermat's little in this case tells you that you want to find 3^3.... mod 4
which again is easy
then go back and use CRT to stitch up all the pieces
torn escarp
sounds good, I kind of started doing that at first but I felt like it would just take longer overall personally
if there were more primes to deal with or the number was larger I would probably have done it
light flicker
Yeah I mean, this feels like the intended solutions
how do you translate last digit into a question about mods?
okay so how do you use euler's theorem
what does euler's theorem say
okay so what does it say here for the problem you're working on
yes
think of some exponent rules you might be able to use
thats right
olive remnant
I'm doing 9 rn and I just don't know what to do for ii
this is what i have so far but what i have for ii is definitely wrong
9i. Using $P(n): n = 2k$
\$\exists k \in \mathbb{Z}: P(n)$
\9ii. $\forall k \in \mathbb{Z}: \neg(P(n))$
sterile pumiceBOT
yohst:
craggy solstice
can someone tell if the reasoning is enough for this problem
Let d(n)=no. of divisors of n where n is positive and an integer.Prove that d(n) is odd if n is a square
primes have 0 proper divisors or even divisors. All numbers which arent squares have divisors (d,n/d) thus forming a pair for every divisor d
and d^2 neq n for any d
so for square numbers there is a number d such the pair is (d,d) and we get our result
quick furnace
your reasoning is... really wonky.
well ok like
it's your wording.
you seem to have the right idea, ish? but
sacred junco
Well, let n be a square, so: $ n = p_1^{a_1}p_2^{a_2}\dots p_k^{a_k}$
sterile pumiceBOT
rudy:
sacred junco
@craggy solstice also, your way is fine but its a bit unformal
How many divisors does this have Lionel?
There’s a general formula for this.
quick furnace
uhh
@sacred junco you kinda nuked it
the divisors of $k^2$ can be broken into three groups: those less than $k$, those greater than $k$, and $k$ itself
sterile pumiceBOT
Ann:
quick furnace
the first two groups contain the same number of divisors as they can be put in bijection with one another via the map $d \mapsto k/d$