wouldn't the answer be $log_2 64$?
#elementary-number-theory
sacred junco
sterile pumiceBOT
war crime
sacred junco
thanks for helping me
sage fern
so what are the 6 weights, then
sacred junco
1, 2, 4, 8, 16, and 32
sage fern
yep, done
sacred junco
how should i go about this proof?
sacred junco
i want to do it like this but i'm not sure if that's the best way
in case you're wondering, theorem 2-1 is euclid's division lemma which is proved by the basis representation theorem in this book
sleek cove
what if k = 2 
heavy palm
I'd like a hint for the second part. Here's what i've done
$\alpha = ab$ where $a,b \in \bZ[i]$. Then $N(\alpha) = N(a)n(b) = p^2$, then we have two cases. Either $N(a) = p^2$ and $N(b) = 1$ (or vice versa) in which case we are done, since $b$ is a unit, or $N(a) =p = N(b)$. Now if we have the second case then $a,b$ are irreducible, which is kinda funky. So now i need to show that this case can never happen, but i'm struggling to find anything to come up with a contradiction with. I'm sure it has sth to do with being congruent to 3 mod 4
sterile pumiceBOT
uoft
heavy palm
nvm i got it
worn pine
hi! how can i solve
sterile pumiceBOT
richard
worn pine
I was able to show that
sterile pumiceBOT
richard
worn pine
I just really don't know how to move on from there
sacred junco
I think I'd use crt here
worn pine
what's crt? sorry
abstract flax
**richard**
I don't get it. Isn't this basically solved already. x can be any of the elements in the equivalence class of 7^7^7
If you want to find the least positive element of that class
Then just continue as you were
7^7 is 13. Then find 13^7 and reduce
abstract flax
Oh, oops
sacred junco
Np I fell for it too
abstract flax
Haven't seen you in a while
sacred junco
Indeed luna
sleek cove
you can also use wolfram's theorem
sterile pumiceBOT
sterile pumiceBOT
sleek cove
ez
sacred junco
7^7^7 = 1 (mod 3) 7^7^7 = 2^7^7 (mod 5) now phi(5) = 4, 7^7=3^7 mod (4), phi(4) = 2 so 7^7=3^1 = 3 so 7^7^7=2^3 = 3 (mod 5), then you solve the system
inner anchor
You can reduce it directly mod 15 just by noticing that phi(15) = 8
And 7^7 mod 8 = -1 and so you just need the inverse of 7 mod 15
torn escarp
yeah that works
computing 7^7 mod 15 seems kind of annoying though, 7^-1 mod 15 is easier since you can look fairly quickly at 7x+15y=1 and recognize 14 is one less than 15 and so you have 7*(-2)+15=1 and so the answer is -2 = 13 mod 15
upbeat wren
7^(7^7) 2 ^ (7 ^ 7) = (-1) ^ (7 ^ 7) (mod 15)
Note: 2^4 = 1 (mod 15) and 2 has an inverse mod 15.
7^(7^7) 2 ^ (7 ^ 7) = -1 (mod 15)
7^(7^7) 2 ^ (-1) = -1 (mod 15)
7^(7^7) = -2 (mod 15)
spare tangle
Hi, I was trying to solve the congruence: (= symbol is actually congruent)
55 x = 44 mod 121 (0)
=> 5x = 4 mod 11 (1)
Find out inverse by solving 5x = 1 mod 11 (2)
=> x = 4*9 mod 11 = 3 mod 11
Sorry if this is a stupid question
Like, do you have to find the inverse first using the earlier congruence (2), or is there a way to solve that eqn in "one go"?
spare tangle
so you mean 11 solutions?
dusty dragon
Yep
spare tangle
you mean non-equivalent congruence classes, or are you just describing the set of congruences?
dusty dragon
Your solutions are of the form x = 3 + 11k for integers k
These solutions belong to the same congruence class. You just want to find all of the solutions that are less than the original modulo
spare tangle
yup, makes sense
dusty dragon
So you found that 3 was a solution, 14 is also a solution
spare tangle
so why are there gcd (55, 121) number of solutions
dusty dragon
Thatโs just a result of the Euclidean algorithm
spare tangle
ah I see
so you said earlier that this is one method
which is to multiply both sides by the inverse
what is the other method?
dusty dragon
The other method is to perform the Extended Euclidean Algorithm
Your linear congruence can be written in the form: 5x = 3 + 11y or 5x - 11y = 3
spare tangle
yes
I believe the word my lecturer used was a diophine equation or something
not sure what it means ๐
dusty dragon
Then, by the Euclidean algorithm, you find the gcd(5, 11)
dusty dragon
I believe the word my lecturer used was a diophine equation or something
Yep! Thatโs the name of the equation involving the two unknowns x and y
Itโs a polynomial expression where our solutions of interest are integers
spare tangle
ahh I see, so is it therefore specific to number theory (due to the fact that we're only interested in integers?)
dusty dragon
Itโs very much a big part of number theory
spare tangle
Btw, I'd like to thank you
dusty dragon
No worries, happy to help! ๐
spare tangle
I really struggle to understand my lecturer, I'm sure she's great at her research but she goes too fast for my slow brain ๐
dusty dragon
Ahh dw, that happens to me too!
spare tangle
I'll have a look at this extended euclidean algorithm, I'm sure it's up next as I try to cram 1 module in 3 days
10% so far
๐
dusty dragon
Good luck!
spare tangle
Thank you, I will need it!
is it okay if I dm you for a question related to number theory? (Clarification, I mean)
dusty dragon
Sure!
spare tangle
Okay, thanks a lot!
dusty dragon
Try now ๐
upbeat wren
Other helpful shortcuts:
Suppose we have kx = 12 (mod 13) for some integer k. If we can find kx = (any factor of 12) mod 13, then you can just multiply so as to get 12 on the right hand side.
Also if kx = ky (mod m) where k has a multiplicative inverse (mod m), x = y (mod m).
Examples:
2x = 12 (mod 13)
x = 6 (mod 13)
3x = 12 (mod 13)
x = 4 (mod 13)
4x = 12 (mod 13)
x = 3 (mod 13)
5x = 12 (mod 13)
Note: 5(3) = 2 (mod 13)
5(3)(6) = (2)(6) = 12 (mod 13)
x = 18 = 5 (mod 13)
6x = 12 (mod 13)
x = 2 (mod 13)
7x = 12 (mod 13)
Note: 7(2) = 1 (mod 13) So this is equivalent to finding the inverse.
7(2)(12) = (1)(12) (mod 13)
x = 24 = 11 (mod 13)
8x = 12 (mod 13)
Note: 8(2) = 3 (mod 13)
8(2)(4) = (3)(4) (mod 13)
x = 8 (mod 13)
9x = 12 (mod 13)
Note: 9(3) = (-4)(3) = (1) (mod 13)
(-4)(3)(12) = (1)(12) (mod 13)
x = 3(12) = 10 (mod 13)
Also kx = xk here so k = 10 --> x = 9 (as we found when k = 9, x = 10) and k = 11 --> x = 7 (as we found when k = 7, x = 11).
3 more shortcuts.
sleek cove
steady nest
when we say $$a \equiv b (\textrm{mod m})$$ does this mean $$ \exists k \in \mathbb{Z} , a= b + mk$$ or $$\exists k \in \mathbb{Z} , a= b - mk$$
sterile pumiceBOT
suck2015
sleek cove
they are the same
dusty dragon
They are equivalent, k is simply some integer
left sigil
This is most obvious because, if $k\in\mathbb{Z}$, then $-k\in\mathbb{Z}$, so replacing $k$ by $-k$ in one of your definitions gives the other.
sterile pumiceBOT
Bannanachair Monarch
real niche
I already asked in calculus, maybe they will answer here
real niche
i tried all bases from 0 to s-1 from this and it worked
verbal cedar
$3(4m-1)k=-(7m+2)$
sterile pumiceBOT
nix
verbal cedar
how would i go about finding the integer solution for this?
sacred junco
I'd start by || considering cases on gcd(4m-1,7m+2) ||
timid pecan
anyone have any ideas for this one? I've been trying to run induction on it but with no success
fervent grove
anyone have any ideas for this one? I've been trying to run induction on it but ...
have you tried writing (x+y)^n = (x+y) * (x+y)^(n-1)?
timid pecan
my bad I just saw this @fervent grove
I've gotten it down to x^(k+1) + ynx^(k) + yx^k + ny^2x^(k-1) but now I'm stuck, do I use the fact that it's mod y^2 to somehow eliminate the yx^k and ny^2x^(k-1)?
wait I forgot to replace the n with a k LOL
fervent grove
I've gotten it down to `x^(k+1) + ynx^(k) + yx^k + ny^2x^(k-1)` but now I'm stuc...
Yes, modulo y^2 will eliminate ky^2 x^(k-1), and the rest of the terms should rearrange into the conclusion
torn escarp
how would i go about finding the integer solution for this?
since it's a hyperbola with asymptotes parallel to the x and y axes, you can graph it and see the integer points
in particular, y=1/4 is one of the asymptotes, so that means all the points are getting arbitrarily close to this line which is between y=0 and y=1, so definitely can't be any integer points out there
reason similarly for the other asymptote
spark shuttle
how can i find the prime factors of something like 3^20-2^20
without calculating any large powers
torn escarp
there's an identity $x^n-y^n = (x-y)\sum_{k=0}^{n-1}x^k y^{n-1-k}$ you can use
sterile pumiceBOT
Merosity
torn escarp
basically a generalization of difference of squares, you don't have to pick n=20 you can pick n to be any divisor of 20 to break it up
I'd probably start by breaking it up as a difference of squares first since that seems easy
$3^{20}-2^{20} = (3^{10}+2^{10})(3^{10}-2^{10})$ to get started
sterile pumiceBOT
Merosity
spark shuttle
yeah tahts what i did but not sure what to do with the 3^10+2^10
sick estuary
Can I get help with a number theory question I have in this channel?
inner anchor
go for it
so for the first part you need to show that $A = P(M)$ divides $P(M+Ax)$ for all $x$
sterile pumiceBOT
Pappa
inner anchor
for that you can use the general statement that for integers $a, b \in \bZ$ and $p \in \bZ[x]$ we have $a-b|p(a)-p(b)$
sterile pumiceBOT
Pappa
sacred junco
So I showed that (p/5)(p/7)=1
so clearly need (p/5)=(p/7)=-1 or (p/5)=(p/7)=1 to be represented by one of the forms
but how do i show that each case correspond to a specific form
sacred junco
<@&286206848099549185>
fervent grove
That or this can be proven by just using the binomial theorem i think
The binomial theorem is unnecessary here. It suffices for a - b | a^k - b^k for each integer k, but a = b (mod a-b).
sick estuary
for that you can use the general statement that for integers $a, b \in \bZ$ and ...
Thanks, this helped a lot
inner anchor
Np
sick estuary
For part ii of a, I'm not quite sure what the question is asking. Is it asking whether there are collectively infinitely many primes that divide the outputs to the polynomial with positive integer inputs?
fervent grove
For part ii of a, I'm not quite sure what the question is asking. Is it asking w...
Look at all the values P(1), P(2), ..., and prime-factor each. We can build the set of primes which appear in the prime factorization of any of the P(1), P(2), .... Show that this set of primes is infinite.
sick estuary
Look at all the values P(1), P(2), ..., and prime-factor each. We can build the ...
How could we use this previous result to break each one down into primes?
fervent grove
We are "really" talking about the set of primes which divide any element of {P(1), P(2), ...}
How have you learned to prove infinitude of primes?
sick estuary
Typically would start by assuming a finite number of them exist and then forming an expression that is not divisible by any of the finite list of primes, thereby giving us that there exists some other prime that must divide the expression and so a contradiction is reached and the assumption is wrong.
fervent grove
Sounds like a good idea
sick estuary
True, maybe there is a way of applying something similar here
fervent grove
There is, and you will find part (a) helpful for this approach
inner anchor
that result is pretty cool
sick estuary
I'm still unsure about how to go about it. Do you mind giving me a further hint?
fervent grove
Hint 1: ||Use Q instead of P. It suffices. (Why?)||
Hint 2: ||Proceed like Euclid.||
Hint 3: ||Suppose there are only finitely many primes dividing someone in {Q(1), Q(2), ...}. Let their product be N. ...||
sick estuary
Hint 1: ||Use `Q` instead of `P`. It suffices. (Why?)||
Hint 2: ||Proceed like E...
I'm still stuck on how to do this. I'm confused with the form of Q and the significance of M and A in P.
fervent grove
The point of the construction of Q is that Q(0)=1
The key trick in this problem is the following tool: ||for an integer n, a = b (mod n) implies Q(a) = Q(b) (mod n)||
Let me know if you need another hint/want the full solution
sick estuary
Could I get the full solution please if you wouldn't mind? I've been stuck on this for too long.
At what level have you studied maths btw?
fervent grove
Full proof: ||We will show that the set of primes dividing any element of the set of {Q(1), Q(2), ...} is infinite.
Suppose for the sake of contradiction there are finitely many. Let their product be N. Now, look at the sequence Q(N), Q(2N), Q(3N), and so on. We have two observations:
- Because
Qis a nonconstant polynomial, these values grow arbitrary large in absolute value. In particular, someone in the sequence has a prime factor. (This is an annoying technicality, but we must deal with it.) - For any prime factor
pdividingN, we see thatkN = 0 (mod p)impliesQ(kN) = Q(0) = 1 (mod p). In particular, all the primespdividingNdo not divideQ(kN).
Observation 1 means that we get a prime factor from someQ(kN). Observation 2 means that this prime factor does not divideN. This is a contradition!||
fervent grove
At what level have you studied maths btw?
I'd rather avoid this question, if you don't mind
fervent grove
Full proof: ||We will show that the set of primes dividing any element of the se...
Let me know if you want clarification
sick estuary
I'd rather avoid this question, if you don't mind
I understand, np. I was just curious since you seem to have great intuition for these problems.
sick estuary
Let me know if you want clarification
Will do, thanks a lot!
fervent grove
I understand, np. I was just curious since you seem to have great intuition for ...
heh, if I had better intuition, I would be able to motivate the solution better
sick estuary
By "someone in the sequence has a prime factor" did you mean a unique prime factor that is not found in the product N?
In general, this is bound to happen as the magnitude of the numbers gets larger?
fervent grove
The first observation is conjuring any prime factor at all, not caring about N. The second observation is where we show that this prime factor doesn't divide N. And yes, this is bound to happen as soon as |Q(kN)| > 1.
The second observation is the "important" one. The first observation is what you write down when you're trying to rigorize the proof given by the second observation. Importantly, the first observation is the only place where we have used the fact that the polynomial is nonconstant, so this step cannot be removed.
does that make sense?
sick estuary
I finally understand what's happening now! Thanks again.
fervent grove
My pleasure!
strong bluff
torn escarp
well the digit expansion of a rational number is eventually periodic
and this corresponds to the base 2 expansion of a number that isn't periodic
sick estuary
Thank you!
torn escarp
you're welcome
fervent grove
Modding out by 1 is uninteresting because everything is equivalent modulo 1.
Modding out by negative numbers doesn't give you anything "new." If you want mod out by -n where n is a positive integer, then a = b (mod -n) is equivalent to -n | a-b is equivalent to n | a-b is equivalent to a = b (mod n). In particular, modding out by -n is the same as modding out by n.
In short, we can mod out by integers other than those bigger than 1, but it's not super helpful
torn escarp
you can mod out by 1 or other things, if you are thinking about the real numbers, modding by 1 gives you a circle by taking the interval [0,1) and wrapping it around
sacred junco
how is this proof?
torn escarp
hmm I would solve directly, $2^m = (2n+1) + (2n-1) = 4n$ so $n = 2^{m-2}$ and the consecutive odd numbers are $2^{m-1} \pm 1$
sterile pumiceBOT
Merosity
sacred junco
was my proof correct?
torn escarp
funnily enough, 2 is not possible to write as a sum of two consec odd numbers though
sacred junco
oh i forgot to add in the title that it only works for $n>1$
sterile pumiceBOT
war crime
sacred junco
but i did show that with the base case
dusty dragon
second dot point seems rather redundant, you don't really use it anywhere in your proof
also instead of writing 2^{k + 1} all the time, you should probably omit that until the end. It looks a bit clunky
steady nest
i understand how to use the euclidean algo to find multiplicative inverses in some Z/nZ however using it to find the inverse of 2 mod 5 doesn't seem to be working?
granted, we know 2*3 = 6, 6 mod 5 = 1 so 3 is the inverse
in mod 5
sleek cove
what
steady nest
hmm?
torn escarp
show your working
steady nest
sure
sterile pumiceBOT
suck2015
Compile Error! Click the 
reaction for more information.
(You may edit your message to recompile.)
steady nest
$$\begin{align} 2x + 5y = 1 && \text{By definition } \ 1 = 5 - 2(2) && \text{this is where i'm stuck} \end{align}$$
sterile pumiceBOT
suck2015
Compile Error! Click the reaction for more information.
(You may edit your message to recompile.)
torn escarp
good, now you take mod 5 of both sides of the equation
1 = -2*2 mod 5 means -2 is the inverse of 2
you can add 5 to it if you want it to between 0 and 4 to get 3
torn escarp
yeah you're welcome
steady nest
Just to clarify
the first one is cylic because (assuuming addition is the group operation), we can eventually generate all stuff in Z by just add 1 a bunch of times or adding -1 a bunch of times?
steady nest
ok thanks!
why would $(\mathbb{Z}/8\mathbb{Z})^x$ not be cyclic for $x+ 8\mathbb{Z}$? The only elements in it are those with an inverse so ${1,3,5,7}$
sterile pumiceBOT
suck2015
steady nest
is it because it over-generates?
torn escarp
oh side thing for latex you can do $(\bZ/8\bZ)^\times$
sterile pumiceBOT
Meฯฯa
torn escarp
a package thing here yeah, but the \times is what I meant to point out
sterile pumiceBOT
suck2015
torn escarp
the \bZ and \bR etc is just a package for this bot, idk what lol
no it doesn't over-generate, I think I see your problem
what's the group operation here, addition or multiplication?
steady nest
multiplication since this set only contains integers with mutliplicative inverses mod 8?
torn escarp
yeah, well specifically once we decide on multiplication we have to pull elements out of the set {0,1,...,7}
since otherwise you have elements like 2 which have no inverse, meaning it's no longer a group
since you're only doing multiplication, you can't do addition or "over generate" because a group is always closed
like concretely let's pretend 3 is a generator
all we can do is start multiplying it by itself to get all the elements
3*3 = 9 = 1 which is the identity
whoops, we are missing out on 5 and 7 now, so try to work out what 5^2 and 7^2 are
torn escarp
yeah
also a trick to notice too is
5^2 = (-3)^2 = 1
you can do that to make the numbers smaller and easier to compute when it's handy
similar for 7, 7^2 = (-1)^2 =1
so always a good idea to swap around between representatives when it's convenient
that also might make it clear that this group is generated by 2 elements
since 5=-3 and we saw 7=-1
once you have like, 3 and 7, 3*7 = 5 is already here
any two of 3,5,7 will generate the group
torn escarp
yeah you're welcome, happy to help
dusty dragon
If p and p + 2 are both prime, how would I show that 12 is a factor of the sum?
I can see that p + (p + 2) = 2p + 2 = 2(p + 1) so p + 1 must be a multiple of 6 for it to work
but how would I go about showing that claim
torn escarp
show that all primes bigger than 3 are congruent to 1 or 5 mod 6
dusty dragon
ah, so if p is congruent to 1 mod 6, then p + 2 is congruent to 3 mod 6 which is composite
smoky zealot
u can try 6n+ or - 1
dusty dragon
if p is congruent to 5 mod 6, then p + 2 is congruent to 1 mod 6
smoky zealot
coz all primes are of form 6n+/-1
dusty dragon
yep, I think I have an idea now. Thank you! ๐
smoky zealot
np ๐
smoky zealot
Can someone help :
Let a,b,c be integers such that
a^6 +2b^6 = 4c^6
. Show that a = b = c = 0
i tried to put bound by showing tht max(a,b,c) > 0
fervent grove
I think modulo 2 says that a is even
torn escarp
I think you can do an infinite descent argument
smoky zealot
I think you can do an infinite descent argument
umm..what is that
smoky zealot
I think modulo 2 says that a is even
yes !!
fervent grove
Once you know that a is even, can you prove that b is even?
smoky zealot
Once you know that a is even, can you prove that b is even?
how
torn escarp
plug in a = 2a'
smoky zealot
ohh i got it : a b c are even and can be written as 2a' , 2b' , 2c'
fervent grove
Then can you prove that a', b', c' are also even?
smoky zealot
then what 2do
smoky zealot
Then can you prove that a', b', c' are also even?
take mod 2 rite
torn escarp
then you have the same equation all over again but with reduced variables
smoky zealot
then what 2do
fervent grove
All zeroes is the only possible way
smoky zealot
All zeroes is the only possible way
why
fervent grove
[Merra is providing a rigorization]
torn escarp
ohh i got it : a b c are even and can be written as 2a' , 2b' , 2c'
back up to this step
you have to reason through this one step at a time, not all at once, that might make it clearer
I think you're jumping to the conclusion too quickly
smoky zealot
i dont get it...why a b c has to be zero
torn escarp
show what happens when you plug in just a=2a'
what's the new equation that you get
like see how this forces b=2b'
smoky zealot
ohhh
smoky zealot
i dont get it...why a b c has to be zero
but why this
torn escarp
lol
it comes from reasoning through what you're trying to ignore me showing you haha
smoky zealot
it comes from reasoning through what you're trying to ignore me showing you haha
๐ซ
torn escarp
if you don't see why a,b,c get turned into 2a', 2b', 2c' you won't get what happened
a^2+2b^2=4c^2 becomes the equation a'^2+2b'^2=4c'^2 after those steps
which is the exact same equation
smoky zealot
OHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH
torn escarp
except we've made everything 2 times greater
torn escarp
the only way you can get a number that converges by multiplying by 2 infinitely often is 0 yeah
fervent grove
aside: hmm this question is nice in that you get back out exactly the same equation
this approach also works on a^2 + 4b^4 = 6c^6, right?
no wait we need more imbalance
torn escarp
I don't know
possibly, just work it out to see for yourself
if you can't answer this yourself then you haven't understood the process
fervent grove
I mean, my point is that we don't need to get out "exactly" the same equation always
which is kinda cool
torn escarp
are you saying it works or doesn't work
fervent grove
I think it does
torn escarp
I think I see a way to make it work but it requires an alternate method
fervent grove
I think the same method works with a little modification
torn escarp
show your steps, I'll type up my solution too we can compare
fervent grove
(mod 2) ==> a is even; fix a = 2a1, so now 2(a1)^2 + 2b^4 = 3c^6
(mod 2) ==> c is even; fix c = 2c1, so now (a1)^2 + b^4 = 3 * 2^5 c1^6
(mod 4) ==> both a1 and b are even; fix b = 2b1, so now (a1)^2 + 16 b1^4 = 3 * 2^5 c1^6
this process can be repeated now (yes I know I'm not being rigorous)
the last step is easier in later iterations
torn escarp
they could both be odd
torn escarp
oh good point
fervent grove
you don't have to do that in later iterations of the proof, but you do in the beginning
torn escarp
looks like it'll probably cycle back around then
fervent grove
to be rigorous, I think you'd have to write out what's the general equation you get after dividing everything by two, but this should work?
torn escarp
I was noticing similar idea but slightly differently just doing it mod 3
fervent grove
ah that's clever
torn escarp
should work both ways I think just fine though
well
there might be an issue with the mod 2 way now that I'm looking at it
torn escarp
the way the powers move around, seems likely we might end up in a situation where we do get it to look like a^2+b^4 = 6 c^6
yeah
torn escarp
I didn't work it out fully but I think the mod 3 way doesn't have this issue
cool
you're welcome
fervent grove
yeah there isn't quite enough imbalance to make (mod 2) work
torn escarp
fun problem, lucky the one you made up we were able to solve it haha
fervent grove
the way the powers move around, seems likely we might end up in a situation wher...
wait to call (mod 2) "properly dead," does this equation have solutions in the 2-adics? the lifting doesn't look obvious to me
(also oops that might not belong in this channel; yell at me if I should move)
ok sorry for spamming, but the only solutions (mod 8) are all even (checked by Python3), so in fact the descent may continue
torn escarp
it has a ton of solutions in the 2-adics I'm pretty sure
fervent grove
really?
torn escarp
maybe not idk
gonna make some coffee and work it out though
like through plugging in it looks like it eventually comes down to a^2 + b^4 = 6c^6
fervent grove
it's not obvious that all of a,b,c need to be even, but I think (mod 8) says they do
I just had Python3 test all possibilities because lazy
torn escarp
well I walked down the steps but made it easier thinking about the tuple of exponents of 2
like it starts out at (0, 2, 1) then this forces a to be divisible by 2 so 2^2 comes out making (2,2,1)
division subtracts 1 from each (1,1,0)
fervent grove
yes, I see how we end up with a^2 + b^4 = 6c^6
torn escarp
oh ok
fervent grove
I'm saying that even at this point, all of them must be even
fervent grove
ok sorry I'm keeping you from your coffee
torn escarp
yeah, unforgivable lol
ok banged out a proof that it has no solutions
how comfortable are you with the ultrametric inequality @fervent grove
fervent grove
pretty comfortable
torn escarp
ok I'll walk through the steps I guess now
fervent grove
[by the way, the descent argument does work, with care]
torn escarp
oh that might be cleaner then
oh well this way will be fun enough I think so I'll show it anyways
fervent grove
but if you have a proper 2-adic [proof], it's cleaner then my descent, so I want to see it ๐
torn escarp
I rewrite it as $a^2-6c^6 = -b^4$ so that I can take the 2-adic absolute value $|.|$
sterile pumiceBOT
Meฯฯa
torn escarp
first off we have $\max(|a^2|, |6c^6|) = |b^4|$
sterile pumiceBOT
Meฯฯa
torn escarp
the reason it becomes a max is because they can never be equal, one has even and the other has odd power of 2
and the larger one dominates always
smoky zealot
A really cool easy qn :
Is it true that for every natural number n the
quantity n^2 +n+41 is a prime?
fervent grove
A really cool easy qn :
Is it true that for every natural number n the
quantity...
n=41?
[ok sorry for interrupting]
torn escarp
since $b^4$ also has even power, it must be $|a^2|>|6c^6|$
sterile pumiceBOT
Meฯฯa
torn escarp
and so we have $|a^2| = |b^4|$
sterile pumiceBOT
Meฯฯa
torn escarp
so just substitute in for some $|u|=1$ we pick $a = b^2u$
sterile pumiceBOT
Meฯฯa
fervent grove
you might have to extend Q2 to get a square root here, right?
fervent grove
ok sure
torn escarp
ok cool so simplifies to $b^2(u^2+1) = 6c^6$ so now we can reason from the inequality earlier that
sterile pumiceBOT
Meฯฯa
torn escarp
$$1 > | \frac{6c^6}{b^4}| = |1+u^2|$$ so we must have that $|u^2|<1$ so this implies $|u^2+1|=1/2$ ultimately
sterile pumiceBOT
Meฯฯa
torn escarp
I'm kind of skipping fast so maybe I should let you catch up or explain in more detail if I'm too terse
torn escarp
it is mod 8
I really am not doing anything super special except feel a bit more comfortable writing it this way is all tbh
fervent grove
ok I guess reasoning in the 2-adics lets us do all the mods at once :/
fervent grove
ok cool so simplifies to $b^2(u^2+1) = 6c^6$ so now we can reason from the inequ...
what is the "inequality earlier"? weren't there a few of those?
torn escarp
cool so once we have that, then $|b^4(u^2+1)| = |6c^6|$ simplifies to $|b|^4 = |c|^6$ so we just pick an $f$ along with $|m|=|n|=1$ so that $b=f^3m$ and $c=f^2n$ and now the equation simplifies to: $$m^4(u^2+1) = 6n^6$$ which looking mod 8 gives 2=6 mod 8
sterile pumiceBOT
Meฯฯa
torn escarp
oops, let me back up, there was only one inequality I gave
$|a^2| > |6c^6|$ is what I'm referring to
sterile pumiceBOT
Meฯฯa
torn escarp
since $|a^2| = |b^4|$ we just plug that in
sterile pumiceBOT
Meฯฯa
fervent grove
ah ok sorry
torn escarp
it might be clearer if I work it out in real time and stream it if you'd rather see that
fervent grove
I'm almost done reading
torn escarp
but that last bit was the contradiction, sure
fervent grove
"looking mod 8" :/
ok I think I see the argument
thank you
is this kind of argument stylistically preferred to just writing out all possible a^2, b^4, c^6 (mod 8)?
inner anchor
case bash is rarely very illuminating
fervent grove
is the above argument very illuminating? :/
inner anchor
good question
torn escarp
I don't think there was much style to this, just basically stepping through the algebra naturally where my nose led me
inner anchor
A really cool easy qn :
Is it true that for every natural number n the
quantity...
a generalization is to show that there exists no polynomial that takes only prime values
torn escarp
maybe I should have explained it better, we could have just also thrown in a=u2^r, b=v2^s, and c=w2^t with |u|=|v|=|w|=1 and solved
inner anchor
another fun exercise is that there is no linear recurrence that takes only prime values
torn escarp
basically same idea I just found it lazier to reuse the variables already present
smoky zealot
a generalization is to show that there exists no polynomial that takes only prim...
yea
fervent grove
basically same idea I just found it lazier to reuse the variables already presen...
hmm ok. the case bash felt clean to me, but I'm also significantly less accustomed to reasoning with the ultametric inequality, so the dissonance is probably on my end
torn escarp
yeah, it's not too serious lol
smoky zealot
@torn escarp Can you help :
Prove that if n is a natural number, n^5/5+n^4/2+n^3/3-n/30 is always an integer.
torn escarp
ultrametric inequality forcing an equality is pretty strong and kind of weird to get used to
smoky zealot
i found lcm as 30
tht means 6n^5+15n^4+10n^3-n must be divisible by 30
idk what 2 do nxt
torn escarp
there's a nice theorem that if a polynomial is integer for the degree+1 consecutive values, then it is for all values
torn escarp
I'm joking btw
smoky zealot
.......
torn escarp
show that the numerator is 0 mod 2, 3, 5
fervent grove
tht means 6n^5+15n^4+10n^3-n must be divisible by 30
if you want to continue this route, you can show that 6n^5 + 15n^4 + 10n^3 - n is always even by checking values (mod 2), then check (mod 3), then check (mod 5)
smoky zealot
if you want to continue this route, you can show that 6n^5 + 15n^4 + 10n^3 - n i...
are there any more routes to proceed ??
apart from my way
sage fern
are there any more routes to proceed ??
just observe that it's equal to $\sum_{i=1}^{n} i^{4}$
sterile pumiceBOT
Kaisheng21
sage fern
smoky zealot
tysm guys
smoky zealot
,w
Factorise 6n^4+15n^3+10n^2-1
sterile pumiceBOT
sleek cove
hmm this seems like it belongs in #advanced-number-theory @sacred junco
true herald
๐
true herald
I need to verify my proof, so the question asked "prove that for any integer a, if a is odd, then gcd(3a, 3a + 2) = 1"
so basically i said that, since a is composite you can write it in the form 2n + 1
now if you substitute 2n + 1 into a in the gcd you get, 3(2n + 1) and 3(2n + 1) + 2
since 3(2n + 1) is composite and 3(2n + 1) + 2 is prime, the gcd of a prime and composite number is always 1
so the gcd(3a, 3a + 2) = 1
is that how you're supposed to do it?
torn escarp
3(2n+1)+2 is not necessarily prime
torn escarp
not a bad idea but I wouldn't use a=2n+1 right away
I'd simplify gcd(3a, 3a+2) = gcd(3a, 2)
then since 3 and a are not divisible by 2, it must be 1
true herald
wait let me process that for a sec ๐คฃ
why did you take away the 3a
I don't exactly get it
torn escarp
gcd(a,b) is the same as the gcd(a,b-a)
steady nest
A more thought out way might just be to carry it out
3(2n+1) +2 = 3(2n+1) +2
3(2n+1)= (3n + 1)2 + 1
2 = 2(1) + 0
true herald
gcd(a,b) is the same as the gcd(a,b-a)
wow!
I've never seen that property in my textbook
torn escarp
subtracting one from the other will never remove the gcd, that's part of the euclidean algorithm
steady nest
I've never seen that property in my textbook
I think that property is why you can do the Euclidean algorithm in that sequence of decreasing numbers
true herald
ohhhhh yeahh
you mean when you find the linear combination representing the gcd or something
torn escarp
yeah, think of it this way, if a and b are both divisible by g, then a-b is also divisible by g
torn escarp
I guess another way to write it out cleanly is like,
torn escarp
a = mg and b=ng then a-b = mg - ng = (m-n)g
true herald
that's a useful piece of info
steady nest
a = kb + r . Any number that divides a and b must also divide r! , r = a -kb
torn escarp
yup
I guess while we're talking about it, a nice identity to know about is a*b=gcd(a,b)lcm(a,b)
you can think of a*b being a multiple of ab but not the least one cause we're "double counting" the terms they have in common, which is their greatest common divisor
true herald
I guess while we're talking about it, a nice identity to know about is a*b=gcd(a...
i remember that
torn escarp
so when you divide it out, ab/gcd(a,b) = lcm(a,b)
cool
yeah then you're pretty good then
torn escarp
yeahyou're welcome
barren herald
fervent grove
What are the possible values of n^2 (mod 5)?
dusty dragon
1^2 = 1 mod 5
2^2 = 4 mod 5
3^2 = 4 mod 5
4^2 = 1 mod 5
5^2 = 0 mod 5
sleek cove
dfoiler was definitely asking for themselves and not asking happiness, i agree ๐
dusty dragon
Oop I missed the context, apologies
sleek cove
apologies rejected
dusty dragon
I will forever be sad now
sleek cove
as you should
young grotto
does primitive root modulo n and reduced residue modulo n mean the same thing? The former refers to the generator of the multiplicative group of integers mod n, and the latter refers to the elements of that group -- but every element is a generator, so they're the same?
young grotto
right, cause thats Z/2 x Z/2
leaden swan
Yes
young grotto
cool, thanks :D
fervent grove
Even if cyclic, not every element has to be a generator. For example, 4 is not a generator of (Z/7Z)^x because it only generates {1,4,2}
sage fern
yeah, the order of the group has to be prime for every non-identity element to be a generator in a cyclic group
inner anchor
sounds quite false
-1 is never a generator mod any prime
unless im really misunderstanding
sage fern
i mean additively, not multiplicatively
sage fern
well actually it's really because
the order of the multiplicative group mod any prime
where the prime is p
is p - 1
since neither 0 nor p are in it
so if you were doing mod p+1, my guess is it would always be prime cyclic and so every non-identity would be a generator
wait no
0 is in it
well
ok it's in the mod but not in the group
panic over
upbeat wren
Technically -1 generates Z2 and Z3 I think?
leaden swan
Yes
upbeat wren
But yeah. 2 is never a generator for any Mersenne Prime modulo except 3. Fun fact.
torn escarp
fun
shy latch
smoky zealot
Any good introductory book for number theory for self study
CHALLENGES AND THRILLS OF PRE COLLEGE MATHEMATICS
Rly good book
I used it till my INMO level
leaden swan
Any good introductory book for number theory for self study
Edmund Landau (the GOAT)'s ent book - Skips lines between proofs so that is annoying else . the chapter on decompositions is particularly my favourite . Has some ridiculously difficult questions.
Number theory I by Manin - I call this the speedrun book . If you know a bit of NT (or you would like to skip ahead) then this book is for you. It teaches you Fermat's little theorem in page 2 and second chapter is on cryptosystems. Yeah this book doesn't messes around. It covers a LOT of topics quickly covering even very advanced stuff
Equations and Inequalities in nt - Covers topics not seen or found in other books (usually the content that is taken for granted) . Very hard to find online iirc. Some of the proofs are explained a bit too much :P
Irving's book on nt/polynoms - It is a "do it yourself" book. Each theorem is expected to be prooved by you (although you are given a blueprint). Gets seriously difficult to read after ~150 pages. It is more of a introductory nt book for the first 100 pages and then ??? for the later 250 pages.
disquisitiones arithmeticae by Gauss - Fun read , if you plan to stick around in number theory add this to your read list. It is a "historical mathematical" literature so that is fun. This book also serves as a nice support book since it isn't clouded with ridiculous generalizations or plain abstraction. You actually "see" the thing that is being talked about.
G. Hardy's intro to the theory of numbers - Classic book , somewhat like burton . Has a standard textbook style and doesn't fret from showing numbers,,. Nothing much to say except that if you want classical style book that is passed around by tradition , pick this up. It is quite a friendly read!
George Andrews is a very nice read . Clear , concise and has a nice selection (and unique) of topics . The partition chapters and the discussion on selected topics like the gauss problem in circle stand out in this one. Also it is 270 pages and doesn't feel slow at all.
Alan Baker's Comprehensive NT - . Although the name is a misnomer since the book is short like 269 pages , has possibly every topic you would encounter in a standard elementary nt course. Though the discussion is brief but everything is apt and nicely summarised. The Ideals chapter and the chapter touching on some analytic aspects are some that stand out. We used this in my course.
Rosen's (Intro to Modern NT) - Very Very Very Very nice. My personal favourite and covers quite a bit actually. Might be dense since it assumes some math maturity else a solid read. Has good number of questions and the proofs are clear and easy to follow (well sometimes at least )
LeVeque - I used this as a supplement to understand some difficult proofs . The chapter on Gaussian Integers is the stand out here (mainly the chapter i read) . Focusses more on examples etc.
Andreescu's new nt book (not the old "structure .." one ) - Arguably the most comprehensive "question" bank here . You see some questions that blow you right away. This one is very long (700 pages) but touches on most encountered topics you can find. Don't pick this if you cannot spend time on it . But yeah , the main point of this book is questions rather than theory.
Finally , Hua Loo Keng's treatise on nt - Very "unique" proofs and heavy emphasis on building intuition on how to write the proof etc. Touches on a lot of topics but this book is usually known for its discussion on chinese remainder theorem mainly . Might be too dense if you have no previous exposure in the later chapters.
Copy pasta from #book-recommendations
sleek cove
CHALLENGES AND THRILLS OF PRE COLLEGE MATHEMATICS
theres literally 15 pages of nt in this 700 page book lmaoo
smoky zealot
theres literally 15 pages of nt in this 700 page book lmaoo
Lol ur looking at old version lmao
New edition they've added many
Stuff
But I agree , it covers more of geometry (obviously coz it's huge syllabi) than number theory
sacred junco
challenges is shit
old book with no real proper coverage
go with MONT if you even care for olympiads
for some reason indians are fascinated with CATIPCM and Excursion and Burton like bruh
leaden swan
Those people have probably never seen good books
sacred junco
probably
ocean moth
Could someone explain to me why Lagrange theorem is only valid for odd primes and not for all integers
dusk heath
you're speaking about the lagrange theorem on polynomials ? @ocean moth
ocean moth
Yes
dusk heath
The important part of the proof is the structure of $\bZ/p\bZ$, or integers modulo $p$ if you want
sterile pumiceBOT
Shika-Blyat
dusk heath
in particular that polynomials of degree $n$ with coefficients taken modulo $p$ have at most $n$ roots modulo $p$
sterile pumiceBOT
Shika-Blyat
dusk heath
it is true only for primes
ocean moth
I know it's true only for primes , but I wanna know why we can't extend this definition to integers
dusk heath
what definition ? 
you mean why can't we, for any integer n, say that polynomials mod n have of have at most their degree roots ?
ocean moth
Yesss exactly
dusk heath
Right so, first a counter-example:
Consider 2X modulo 4. It has 2 roots mod 4, 0 and 2, which are distinct
And then, to generalize this a bit
assume n is not prime. Then we can factor n = mk with m, k != 1.
Consider the polynomial mX modulo n, it has atleast two roots, 0 and k, and since m != 1, then k isn't equal to n, so k isn't equal to 0 mod n, so the roots are distinct
ocean moth
If we consider proof by induction it seems it could be extended
dusk heath
what does this mean ?
ocean moth
There does not exist x that implies s is less than d
dusk heath
what are s and d ?? and that's not a correct way to write that anyway
ocean moth
Oh sorry
dusk heath
don't use symbols for the sake of using symbols, write this kind of stuff in plain english, it's much clearer
ocean moth
ocean moth
don't use symbols for the sake of using symbols, write this kind of stuff in pla...
No actually I didn't send you the complete proof
d is the degree of f(x)
S is solution
dusk heath
$\not\exists x\implies s < d$ is still not a correct way of saying "There does not exist x that implies s is less than d"
sterile pumiceBOT
Shika-Blyat
ocean moth
Okay......
dusk heath
you're assuming a^-1 exists
that relies on p being prime
2^-1 doesn't exist modulo 4
ocean moth
No I was taking about integer other than primes where a inverse exist
dusk heath
ocean moth
Because the condition for it is to be GCD(a,n) = 1
dusk heath
yes
But I still don't see the point
sure, that solves the case of degree 1 polynomials
ocean moth
Now the general case doesn't really on n being prime
dusk heath
it does, your induction isn't correct either
dusk heath
Idk yet what's wrong I'm struggling understanding your symbols and variables patchwork.
I just know it can't be right because you could make base case correct by starting with constant polynomials, and then your induction would have proven a wrong result, as my counter-example of earlier showed
I still don't get what you're trying to say with case 1
what does "There does not exist x that implies s is less than d" even mean ?
what's s here, and how does it relates to x
ocean moth
I still don't get what you're trying to say with case 1
Don't consider it , it was related to some other proof....
I messed up
Writing stuff
leaden swan
If p were not prime you wouldn't have been able to conclude p|(x-a)g(x) implies p|(x-a) or p|g(x)
dusk heath
thanks drake 
leaden swan
This Lagrange theorem doesn't seem very special
It's literally "A polynomial of degree k in F[x] has a maximum of k roots if F is a field"
Sorry,You don't even need F to be a field. Integral domain is sufficient
dusk heath
It's literally "A polynomial of degree k in F[x] has a maximum of k roots if F i...
(yeah with enough algebra the statement of the theorem is immediate )
sacred junco
If x^2 = y^2*d for integers x,y,d can it be shown that y divides x?
My idea is to use the Fundamental Theorem of Arithmetic and take prime factorisations of x,y and d
inner anchor
you pretty much have to show that if y^2 divides x^2 then y divides x
using the fundamental theorem will work
sacred junco
Ah I got confused cuz the hint said to take prime factorisations of x,y and d and then use uniqueness to show that y divides x
I don't get why they suggested to take the fact of d
sterile pumiceBOT
Merosity
sacred junco
I, personally, went down another road when attempting this question. My notation was setting the prime factorisations as x = p1p2..ps and y = q1q2...qr (without factoring in the powers so as in prime repetition is allowed). Then x^2 dividing y^2 would mean that for some i and j p_i^2 divides q_j^2 but that would mean p_i | q_j (essentially) so x | y
The proof I sent above is easier to read but I wonder if mine isn't sloppy in some sense
$p_i^2 | q_j^2$ is the same as setting $q_j^2 = k \times (p_i)^2 = (kp_i)\times p_i$ so $p_i | p_j^2$ ie $p_i | p_j$
sterile pumiceBOT
Laรฏka
lyric geyser
any advice on how to prove the property $\phi(mn) = \phi(m) \phi(n)$ for relatively prime integers m and n
sterile pumiceBOT
add
prime sparrow
Are you comfortable with modular arithmetic? If so try to prove Z/mnZ is isomorphic to (Z/mZ)x(Z/nZ)
lyric geyser
Are you comfortable with modular arithmetic? If so try to prove Z/mnZ is isomorp...
i know modular arithmetic, but i did not understand the rest of the sentence
prime sparrow
Z/mZ is the collection of integers modulo m, does that part make sense to you?
prime sparrow
Yes basically, we use [a] as the notation instead of a, and [a] is the set of all integers with remainder a after division with m
lyric geyser
hmm ok
prime sparrow
I think this approach to solve the problem will require a lot of new things at once, so let me see if i can rephrase it in an easier way
lyric geyser
sure
fervent grove
For background, what do you know about \phi right now?
lyric geyser
\phi{m} is equal to the number of integers in {1, 2, ... , m} that are relatively prime to m
sacred junco
{1,2,...,m-1}
patent sorrel
How can I find x given, 9^21 is congruent to x mod 23
sterile pumiceBOT
Manan.
patent sorrel
9^3 =16 mod 23
inner anchor
Use fermats little theorem
inner anchor
$(9^3)^7 = 9^{21} = 9^{-1} \cdot 9^{22}$
sterile pumiceBOT
Pappa
inner anchor
using the euclidean algorithm to solve $9a + 23b = 1$
sterile pumiceBOT
Pappa
sleek cove
i prefer guessing and checking 
grave carbon
I'm reviewing some abstract algebra, and I was wondering if someone is able to help me refresh on finding integer solutions to both
$$ x+[2]_7y = [4]_7 \text{,and} $$
$$ [4]_7x + [3]_7y = [4]_7 $$
sterile pumiceBOT
beeswax
fervent grove
What would you do if asked to solve the system
[\begin{cases}x+2y=4, \ 4x+3y=4,\end{cases}]
over (say) the rationals?
sterile pumiceBOT
dfoiler
grave carbon
What would you do if asked to solve the system
\[\begin{cases}x+2y=4, \\ 4x+3y=4...
Either substitute, eliminate, or augmented matrix
It'll just be the same solutions mod 7?
fervent grove
Can you make any of those work in Z/7Z?
yeah, it's worth a try ๐
There is a problem because it's not obvious what "divide by 3" (for example) means, but 1/3 exists (mod 7)
grave carbon
What if I just solved that system and considered the integer solutions mod 7
fervent grove
What if I just solved that system and considered the integer solutions mod 7
Yes, this will work
The manipulations you're used to doing for Q or R or C will also work in Z/7Z except for not being able to divide by 7
So just don't divide by (a multiple of) 7, and it should work
leaden swan
If you want a algebraic justification to why that works,We are considering a ring homomorphism from Q to Z/7Z with phi(a)= a mod 7 for a being integer.
Ring homomorphisms always preserve solutions in a sense
grave carbon
Thank you!
Speaking of rings, may I ask your opinions on rings/groups first approach?
fervent grove
what exactly is the question?
grave carbon
Which approach do you think is optimal?
fervent grove
If you want a algebraic justification to why that works,We are considering a rin...
aside: does this homomorphism exist? where does 1/7 go?
fervent grove
Which approach do you think is optimal?
depends on your mathematical maturity. I would typically recommend doing groups first because there are fewer axioms to keep track of. However, groups are not as "meaningful" as rings because the structures you're used to working with tend look more like rings, with an addition and a multiplication
leaden swan
aside: does this homomorphism exist? where does 1/7 go?
mb
I guess if you exclude 1/7 and such you have an homomorphism
fervent grove
depends on your mathematical maturity. I would typically recommend doing groups ...
I guess in short, if you haven't worked with "sets with structure" before, then I'd recommend doing groups first
gloomy zenith
anyone knows how to calculate the effiency gap of elections?
left sigil
Do you know the properties of $\varphi$? If $\text{gcd}(a,b)=1$, we have $\varphi(ab)=\varphi(a)\varphi(b)$. Also, if $p$ is prime, then $\varphi(p)=p-1$. So, if we let $m=ap$ and $n=bp$ all coprime, we get $\varphi(mn)=\varphi(abp^{2})=\varphi(p^{2})\varphi(a)\varphi(b)$, and $\varphi(m)\varphi(n)=\varphi(p)^{2}\varphi(a)\varphi(b)$. Hopefully this is enough to get you started.
sterile pumiceBOT
Bannanachair Monarch
left sigil
**Bannanachair Monarch**
@patent sorrel
patent sorrel
Okay thanks lemme see what I can do
sacred junco
sorry but arent you assuming p does not divide a?
patent sorrel
How will the gcd(m,n) = p help w the proof ?
fervent grove
sorry but arent you assuming p does not divide a?
gcd(a,b) = gcd(m/p,n/p) = gcd(m,n)/p = 1
sacred junco
it's not that
fervent grove
wait yeah that's a legitamite objection sorry
sacred junco
the step phi(abp^2)=phi(a)phi(b)phi(p^2)
fervent grove
the step phi(abp^2)=phi(a)phi(b)phi(p^2)
the assertion is that this step does not follow. for example, m=8 and n=2 gives p=2 with a=4 and b=1
I think the way out is to get rid of all the powers of p, but someone else might have a cleaner way
sacred junco
perhaps assume a = k*p^a such that p does not divide k
we immediately get that p does not divide b
fervent grove
you need a sentence like "without loss of generality, there are at least as many powers of p dividing a as b"
I think
fervent grove
Iโm still confused
ok what is your approach so far/how much of Bannanachair's argument do you follow?
patent sorrel
I follow it I just donโt know what to do after
fervent grove
ok there's an objection that phi(mn) does not actually (necessarily) equal phi(p^2)phi(a)phi(b) as claimed
do you see why?
patent sorrel
As phi(m)phi(n) also equals that and gcd(m,n) is not 1 so phi(mn) โ phi(m)phi(n)?
fervent grove
what Banannachair is trying to do is say phi(mn) = phi(p^2ab) and then assert that all of p^2, a, b are all coprime, so we can write phi(p^2 a b) = phi(p^2)phi(a)phi(b)
nobody is claiming that m and n are coprime because they are not
patent sorrel
Okay
fervent grove
the issue here is that a and b might still have powers of p. for example, m=8 and n=2 have gcd(m,n)=2, so we let p=2, but then a=4 and b=1. so a is still divisible by 2
in particular, phi(p^2 a b) does not directly imply phi(p^2) phi(a) phi(b) because p^2=4 and a=4 are not coprime
does this make sense?
patent sorrel
Yes
fervent grove
ok, the suggester workaround is to extract all the powers of p from m and n instead of just one
do you think you can continue from this?
fervent grove
let's let m = a*p^x and n = b*p^y where a and b are surely not divisible by p
essentially we factor out all of the ps from m (and n) and get a (and b) left over
sacred junco
either x or y is 1
patent sorrel
Okay so get a expression for a and b in terms of m and n
fervent grove
yes. now we can write phi(mn) = phi(p^(x+y) a b) = phi(p^(x+y)) phi(a) phi(b)
sacred junco
full solution || WLOG let m=ap and n=bp^x, note phi(n)=phi(b)phi(p^x)=phi(b)p^(x-1)(p-1) so phi(b)=phi(n)/(p^(x-1)(p-1)) similar argument for m leads to phi(a)=phi(m)/(p-1). Now phi(mn) = phi(abp^(x+1))=phi(a)phi(b)phi(p^(x+1))=phi(a)phi(b)p^x(p-1) substituting in phi(a) and phi(b) we get phi(mn)=(phi(m)phi(n)p)/(p-1) ||
but that's literally what you guys are doing
fervent grove
umm I guess you can read HoboSas's solution, or I can continue walking you through
[aside: I don't think gcd(m,n)=p is necessary, only gcd(m,n) = p^(positive integer)]
sacred junco
that's what the problem is giving us
fervent grove
umm I guess you can read HoboSas's solution, or I can continue walking you throu...
@patent sorrel just let me know
patent sorrel
Thanks guys I appreciate it ๐
sacred junco
[aside: I don't think gcd(m,n)=p is necessary, only gcd(m,n) = p^(positive integ...
I mean yeah this problem can easily generalized
left sigil
sorry but arent you assuming p does not divide a?
Yeah, you're totally right that I shouldn't have made that assumption. Whoops, my bad, I hadn't had my coffee yet this morning.
quick furnace
for once i have a question of my own
i'm looking to list all positive-integer solutions of the equation 3n^2 - 3n + 1 = k^2, or a way to enumerate all of them (perhaps like a recurrence relation)
i've found (n,k) = (8, 13) through experimentation, but i'm not sure how to establish that this is the smallest solution - and if it is, how i'd go about generating more
for context, the equation arose from practical (ish) interest - determining the possible sizes for a number puzzle where the grid has to contain a perfect-square number of cells but the cells are hexagons arranged in a big hexagonal grid
tho i doubt it'll be all that important
also i have heard of like
pell's equation, and i have some vague understanding of how two solutions can be 'composed' to yield a third
but im not sure if this is possible in my case
(if anyone responds, please ping me)
karmic crest
don't need help with this problem but does anyone have any references with problems of a similar flavour? looking for some
inner anchor
The strategy is as you said i think
Just complete the square to get a pell equation
fervent grove
i'm looking to list all positive-integer solutions of the equation 3n^2 - 3n + 1...
This equation can be written as 3(2n-1)^2 + 1 = (2k)^2, so it suffices to solve 3x^2 + 1 = y^2 where x is odd (say). (The parity condition turns out to not be a huge problem, so we're not going to worry about it.)
The main idea is to write 1 = y^2 - 3x^2 = (y - sqrt(3)x) (y + sqrt(3)x) and then do Pell stuff
inner anchor
Then something something continued fraction stuff to get the minimal solution
fervent grove
I guess the question is how familiar you are with Pell theory
quick furnace
admittedly, not very
fervent grove
It is "obvious" that the smallest solution (say, in terms of x) is (x,y) = (2,1)
Now, (2 - sqrt(3)) (2+sqrt(3)) = 1, but of course we want other solutions
The key observation is that (2 - sqrt(3))^k (2+sqrt(3))^k = 1^k = 1 gives us more to work with. For example (2 + sqrt(3))^2 = 7 + 4sqrt(3), so 7^2 - 3 * 4^2 = 1 as well.
quick furnace
uh huh
fervent grove
It "turns out" that all of the (positive integer) solutions can be generated by the recipe: take successive powers (2 + sqrt(3))^k and expand
quick furnace
okay
fervent grove
The best explanations of this I know are a bit involved
fervent grove
There are some elementary explanations that basically say "if (a,b) is a solution, then we can induce a smaller solution by computing (a+b sqrt(3)) / (2+sqrt(3)) and extracting out the coefficients"
Then you descent downwards to show that all solutions must come from powers of (2+sqrt(3))
It's not very fun, but it's doable
torn escarp
I guess you could connect it back with a formula by writing $(2\pm \sqrt{3})^m = (2k) \pm (2n-1)\sqrt{3}$ if that helps to see
sterile pumiceBOT
Merosity
fervent grove
well they asked for a recurence relation, which is perhaps computationally easier?
quick furnace
im ok with this
fervent grove
[namely, if a_k + b_k sqrt(3) = (2 + sqrt(3))^k, then a_(k+1) + b_(k+1) sqrt(3) = (a_k + b_k sqrt(3)) (2 + sqrt(3)) can be expanded into a recurrence]
ok sorry
torn escarp
I guess semi explicitly we can write something like $k=\frac{(2+\sqrt{3})^m+(2-\sqrt{3})^m}{4}$ and $n=\frac{1}{2}+=\frac{(2+\sqrt{3})^m-(2-\sqrt{3})^m}{4\sqrt{3}}$
sterile pumiceBOT
Merosity
torn escarp
but I didn't actually check if the sign or parity of anything is correct, maybe it's only integers as 2m or 2m+1 or something like that
fervent grove
yeah, I think the parity condition will come down to a modular condition on m
the recurrence shows this: after all, recurrences are periodic (mod 2)
patent sorrel
Does anyone know how to find B such that Bx^12 Congruent mod19 has 6 solutions ?
I know 2 is a primitive root of 19
Iโve made a table of indices for 2
fervent grove
Can you find a C such that x^12 = C (mod 19) has 6 solutions?
patent sorrel
I think so
Working in logs would 12x = c mod 18
Then gcd of (12,18) = 6
So 6 solutions ?
fervent grove
can you provide an explicit C, just for concreteness?
fervent grove
Working in logs would 12x = c mod 18
Continuing from here, we need 12x = c (mod 18) to have 6 solutions. Can you provide a c here which gives 6 solutions?
[for example, c=1 gives no solutions. as does c=2]
patent sorrel
How do you know it has no solutions
fervent grove
12x = 1 (mod 18) is equivalent to 18 | 12x-1. Now, 12x-1 is odd and so cannot be divisible by 18
patent sorrel
Idk how to find that tbh
patent sorrel
No
fervent grove
How about 12x = 4 (mod 18)?
patent sorrel
No
fervent grove
do you want to guess the next c?
fervent grove
Awesome
So 12x = 6 (mod 18) has six solutions. How does this give us a C for which x^12 = C (mod 19) has six solutions?
patent sorrel
C is still 6 ?
fervent grove
I think you took logs somewhere here, so we should exponentiate back
I thought you took log2 because 2 is our primitive root
patent sorrel
Yh Iโm not sure how to go back
fervent grove
Ok, let me formalize these logs
patent sorrel
Thank you
fervent grove
When we write x^12 = C (mod 19), the fact that 2 is our primitive root lets us write x = 2^a and C = 2^c
(we'll ignore zero)
Then we need 2^(12a) = 2^c (mod 19)
The order of 2 is 18, so this requires 12a = c (mod 18)
Does this make sense?
patent sorrel
Whatโs a? Is that just x
fervent grove
x = 2^a
patent sorrel
Okay right
fervent grove
a is another dummy variable, but I want to emphasize that it does not appear out of thin air sorry
patent sorrel
Okay okay i understand
fervent grove
So we found that c=6 gives 12a = 6 (mod 18) with six solutions
How do we transform this back into a C which gives x^12 = C (mod 19) six solutions?
patent sorrel
Exponential
fervent grove
So what is our C?
patent sorrel
2
fervent grove
How did you get that?
patent sorrel
Oh wait
fervent grove
(just checking)
patent sorrel
Tbh I donโt know
fervent grove
well, C=2 is incorrect, so :/
patent sorrel
Take the exponential of 6
fervent grove
So what is C?
patent sorrel
e^6
fervent grove
We don't really have an e in (mod 19) world
fervent grove
When we write `x^12 = C (mod 19)`, the fact that `2` is our primitive root lets ...
recall this
in the formalization, we defined C = 2^c
patent sorrel
Oh is it 12
fervent grove
to be clear, 2 is acting like our e
fervent grove
Oh is it 12
C=12 is also incorrect I think
patent sorrel
6?
fervent grove
regardless, I want to see how you're computing C
fervent grove
there is no e
fervent grove
When we write `x^12 = C (mod 19)`, the fact that `2` is our primitive root lets ...
here we have C = 2^c
so c=6
what is C?
patent sorrel
64
fervent grove
Yes
patent sorrel
God damn
fervent grove
sorry using lower-case and upper-case cs was a mistake :/
patent sorrel
Sorry that mustโve been very annoying
fervent grove
no I should have changed letters
patent sorrel
ahah no worries I was being really slow there
fervent grove
alright, back to the original problem
how do we find a B so that Bx^12 = 12 (mod 19) has six solutions?
fervent grove
sounds like something you should try
patent sorrel
Or I mean multiplicative inverse
fervent grove
7/B = 12; can you solve for B?
patent sorrel
7/12
fervent grove
can you give me an element {0,1,...,18} (mod 19) for B?
patent sorrel
Such that B = 7/12 ?
fervent grove
yes
patent sorrel
How can you do that? I thought thereโs only integers in modulo
patent sorrel
Ah okay 1 sec
fervent grove
[the intuition here is that B = 7/12 is the number such that 12B = 7 (mod 19)]
is 12^(-1)
patent sorrel
1
fervent grove
I don't think 12 * 1 = 7 (mod 19)
patent sorrel
18
fervent grove
๐
18x^12 = 12 (mod 19) should have six solutions
if we've done everything correctly
fervent grove
my pleasure
patent sorrel
where q >= 2
fervent grove
how would you explain what we did above?
how much of this makes sense to you https://en.wikipedia.org/wiki/Legendre_symbol#Definition ?
sacred junco
If I want to look at the values of a^2 and 3b^2 mod 12, is there any easier way to do it than than doing the whole congruence table
torn escarp
well you only have to go halfway at least since (12-x)^2 = (-x)^2 = x^2
warped halo
Find all solutions to the simultaneous congruences
x โก 4 mod 315 x โก 9 mod 715
Give your answer as a single congruence x โก a mod n for an appropriate positive integer n and an appropriate integer a โ {0, . . . , n โ 1}. You may use the fact that 1 = 26ยท143โ59ยท63.
this is the question and i have a solution but i dont understand one line in the solution so if anyone could help me out that'd be great
i can send the solution
why are we able to write "59 +s = 143u" on the second the page?
fringe bear
can someone tell me a good video on youtube about Number Theory
like 1 hour or maybe 5 hour video about Number Theory
frosty bough
k
warped halo
can anyone help me with my question??
sleek cove
what do you mean "why"
warped halo
like what makes that statement true
left sigil
can someone tell me a good video on youtube about Number Theory
Here you go: https://www.youtube.com/watch?v=ihMyW7Z5SAs
sleek cove
scroll up 5 messages laika
sterile pumiceBOT
add
lyric geyser
actually, for when p | a
can i do $(a^p)^{p^p} \equiv 0 \pmod p \implies a^{p^{p+1}} - a \equiv -a \pmod p \implies a^{p^{p+1}} - a \equiv 0 \pmod p \equiv a^{p^{p+1}} \equiv a \pmod p$
sterile pumiceBOT
add
inner anchor
$a^{p^{p+1}} - a \equiv -a \pmod p \implies a^{p^{p+1}} - a \equiv 0$ where does this implication come from
sterile pumiceBOT
Pappa
sterile pumiceBOT
add
lyric geyser
yeah
inner anchor
and 0 = 0 mod p
lyric geyser
then a = 0 mod p
inner anchor
okay can you explain the case p|a to me from scratch
sterile pumiceBOT
add
sterile pumiceBOT
add
inner anchor
and why is that
inner anchor
yes
lyric geyser
then $$a ^ {p^{p + 1}} - a \equiv -a \pmod p$
inner anchor
very cool
sterile pumiceBOT
add
Compile Error! Click the reaction for more information.
(You may edit your message to recompile.)
torn escarp
seems like you're skipping a step
lyric geyser
skipping a step?
torn escarp
$a ^ {p^{p + 1}} \equiv 0^ {p^{p + 1}} \equiv 0 \pmod p$
sterile pumiceBOT
Merosity
torn escarp
it's not clear to me how what you're saying connects to your conclusion
a=0 mod p, so raising 0 to a power mod p is still 0 mod p
lyric geyser
-a = 0 mod p
then i added a to both sides of the congruence after applying transitive
torn escarp
do you understand what I'm saying
fervent grove
Fix a dimension $d$ and $p$ a prime. What is known about the number of vectors $\langle v_1,v_2,\ldots,v_d\rangle\in\mathbb F_p^d$ such that
[v_1^2+v_2^2+\cdots+v_d^2\equiv0\pmod p?]
sterile pumiceBOT
dfoiler
fervent grove
For d odd, I've seen a proof that the number is p^(d-1), but even d seem more chaotic
warped halo
so does noone know why?
left sigil
so does noone know why?
Noone can read your handwriting. Use LaTeX.
torn escarp
Noone can read your handwriting. Use LaTeX.
what are you talking about, this is perfectly readable handwriting
left sigil
I'll be honest, it's been so long since I've had to read any handwriting but my own that I've forgotten how to.
sacred junco
that handwriting is very readable
left sigil
Yeah okay it's a me thing I can't read other people's handwriting at all anymore
fervent grove
why are we able to write "59 +s = 143u" on the second the page?
Here is one way to justify this step: we know that 4 + 315s = x = 9 (mod 715). Thus, 315s = 5 (mod 715), so 63s = 1 (mod 143). Multiplying both sides by -59 implies that s = -59 (mod 143), which is what is required.
More directly, the left-hand side -1 + 63s is equal to (x-9)/5 = 143t and is therefore divisible by 143. So the right-hand side 63(59+s) - 26*143 must also be divisible by 143, so 59+s is divisible by 143.
swift shard
The wording on the original question is off. Based on the proof, it maybe should read "it is not the case that exactly two of the integers ab, ac, bc are odd"
But you might not have control over that part haha
wanton torrent
yeah that's the question ๐
torn escarp
I feel like this is easier to prove going forwards rather than backwards
swift shard
Anyway the proof is good it makes sense to me
wanton torrent
I need to do it either contradiction or contrapositive
swift shard
I would argue that what you've written is a contradiction
You've proven a is not an integer, which contradicts that it is
wanton torrent
But it is correct right? xd
swift shard
Yeah looks good
wanton torrent
nice thanks
swift shard
Like Mer said, there's the much easier proof that oddรodd = odd, ergo all of ab, bc, ac are always odd all the time
lyric geyser
for contradiction, $a + 1 \geq b \geq (a+1) \sqrt 2$ doesnt seem to make sense atl east
sterile pumiceBOT
add
lyric geyser
actually a + 1 >= (a + 1)sqrt 2 for negative a <= -1
but the question asks for postiive real number a...
winter bear
thats now how negation works for this
lyric geyser
thats now how negation works for this
yeah i realized
im stuck on how to prove this
sacred junco
what property of R is used to say that 0.99999... = 1 ?