How to solve x^2 is congruent to 1 mod n

[@blackpenredpen]

Which of the following is the way to spell becase? (A) becase (B) becose (C) because (D) becouse (E) becausi

[@OtiumAbscondita]

C

[@lumirina]

Be cos(e)

[@nilaymarathe2271]

The way to spell 'becase' is Option A.

[@merbst]

Some people use spellcheck, you use your fan base to make a math pun!

[@redboy3743]

(C) because

[@Kartik-yi5ki]

Ppl who think that's a becase (4:30) do not understand bprp's genius. That is an a and u at the same time. Optimal spelling.

[@nilaymarathe2271]

Love your work,sir. Best of luck for the marathon. Your 1/(1-x)

[@blackpenredpen]

Nilay Marathe thank you!!!!

[@RyanLucroy]

6:32 brain.exe has stopped working?

[@gaurangagarwal3243]

You know what , before this I did not even know what congruence modulo is . Your videos are encouraging me to do more maths :)

[@mountaindewitt]

These videos are rolling in just as I'm going through modular algebra for my cryptography course

[@alejrandom6592]

How is it going

[@deidara_8598]

Very easy to see by Euler's theorem, as long as the exponent reduces to zero, you have a counter-example.

[@pablofueros]

Hi! I'm stucked in this problem: Show that the int(sin(t)/(t+1)) dt from 0 to x is > 0 for all positive x. Could you try it please? Not only for me, I think it's a nice problem for the rest of the viewers studying Calc. You are awesome!!! Thanks in advance :)

[@si48690]

Good!!Waiting for more advanced quadratic congruences!!

[@wongbob4813]

Please make more number theory videos with proofs!! I'm loving all these so much !

[@CousinoMacul]

This ties in with the fact that Zmodp is a field.

[@stydras3380]

Well, for p prime :D

[@alejrandom6592]

somehow the unedited parts make me like your videos even more

[@zeeshanmehmood4522]

Please do more things like congruence and set theory and rings

[@ianmoseley9910]

Q - if we have a 4 digit pin n1,n2,n3,n4 and we create a new pin using n1+n2 mod 10, n2+n3 mod 10, n3+n4 mod 10 and n4+n1 mod 10; what is the longest non-repeating sequence using this operation multiple times and what is the average sequence length?

[@benjamimapancake6429]

I'm watching this instead of doing my math homework.

[@PMA_ReginaldBoscoG]

Shang Chi and the Legend of Ten Rings math teacher version 😂

[@iurialmeida8979]

Please do a number theory playlist!!!!!

[@TheNinjaDwarfBiker]

Please do more discrete math videos!

[@davidgould9431]

I'm definitely having a "dull day": I don't get the relevance of 6 | 3·4 to showing p has to be prime in p | (x-1)(x+1) because 3·4 isn't (x-1)(x+1) with integer x. I thought: 4 | 8 and 8 = 3² -1 = (3 - 1)(3 + 1), so 4 | (3 +1)(3 - 1) Except we are supposed to be modulo 4, here, so 0 | 0 is trivial or undefined and 0 | (0)(2) is also nonsense, so I guess I need to brush up my modular arithmetic plugin or whatever's dropped out of my brain at this point. Stewing my brain but loving it! Keep up the good work!

[@Locokillazz]

Your channel has helped me so much in my number theory class.

[@avijitdey992]

You're crazy 🤣 Let's solve some inequalities problems 😋

[@Gaark]

those weights are draining your brains man lolol

[@alwysrite]

found it hard to focus on the math - distracted by those wrist bands ! or ... what are they?

[@richardbanh7106]

I have an interesting math problem that I composed during a chemistry lecture. We learned that the pH of an aqueous solution can be calculated with the following equation: pH=-log[H3O+] , where [H3O+] is the hydronium ion concentration. This sparked an idea in my curious head: Can the pH of a substance be equal to the concentration of hydronium ions? In the language of mathematics, is there a value x where x=-log(x)? I've set the equation y = x + log(x) into a graphing calculator and found that x≈0.399. I couldn't settle on this because I wanted to find an exact value for x. I've been at a standstill for days. Can anyone help me out? Much appreciated for those who read all of this. I hope you have a great day :)

[@RexxSchneider]

The equation x = - log(x) can be solved by using the Lambert W function (also called product logarithm). Writing log for log base 10 and ln for log base e, we have: x = - log(x) x = log(1/x) x = ln(1/x)/ln(10) x * ln(10) = ln(1/x) e^(x*ln10) = 1/x x * e^(x*ln10) = 1 x*ln(10) * e^(x*ln10) = ln(10) Now the LHS is in the right form to use the Lambert W function: x*ln(10) = W(ln(10)) x = W(ln(10)) / ln(10) Put *ProductLog(ln(10)) / ln(10)* into WolframAlpha and you get 0.3990129782602520715964708106240920239962018684549678740721400940 or whatever accuracy you want. Unfortunately, the Lambert W function can't be expressed in elementary functions, so you're not going to get an exact value.

[@davidgould9431]

Love the maths, but the wrist and ankle weights? Muscular development takes 2 to 3 weeks to make any difference: all you are doing a week before the marathon is getting tired. I've run 50 or so marathons and a pile of ultras (up to just over 100 miles) and have just retired from personal training (but, still, could be terribly wrong). I know you've done marathons before, and I totally understand the drive to find a few marginal gains, but the big thing in the three or four weeks before the Big Day is to get the volume of training down while keeping the frequency up: so, same schedule, but shorter. Nothing longer than 10 miles in one go in the 3-4 weeks before. Remember you're doing less: don't eat so much! All this assumes a decent few months of progressive training beforehand. Or you could take the approach I tend to take to marathons nowadays: just rock up and see how it goes. Obviously, it goes less quickly than before, but I'm still trying to keep the stamina up for the stupid long runs and something has to go. That something is speed: after this year's couple of 24 hour events I might focus again on moving a bit quicker. Being 58 probably doesn't help with the speed a great deal :-) I hope the marathon goes well (or, if it was this weekend, has gone well) and look forward to your video, if you've made one this time.

[@gergodenes6360]

And now generalising it to x^2 congruent to n^2 (mod p), we get: x congruent n (mod p) and x congruent -n (mod p)

[@98danielray]

or*

[@gergodenes6360]

​@@98danielray No, actually both are equally valid solutions, not just one of them.

[@98danielray]

@@gergodenes6360 modp goes from 0 to p-1. p-n is not n. unless p =2n

[@98danielray]

@@gergodenes6360 and yes, both are valid solutions. its either one or the other

[@gergodenes6360]

@@98danielrayActually no, congruency is not equality, x can be congruent to many different numbers at the same time (with mod p of course), so not only are they both valid solutions, both are true at the same time here.

[@waishingtseung6930]

Kv:2,3,4,... NvNR:2,3,4,5,... NvWR:?

[@adityaagrawal5946]

Raise your hands 🙋 if you thought the same counter example

[@ליאורו-ט3ו]

I love your channel you very help

[@pacbee]

it works for semiprime .

[@husklyman]

So what is x when: x^2Ξ1 mod(k) while k is NOT prime ?

[@mht5749]

I think a general case, for k a natural number, it's x=k±1 because x^2=k^2±2k+1=k(k±2)+1 and it's easy to see k(k±2)+1≡1 (mod k)

[@angelmendez-rivera351]

Mauricio Huicochea Toledo It can't possibly be k + 1 or k - 1 mod k due to what was shown in the video.

[@TechToppers]

See, he has a video on this...

[@RexxSchneider]

All of the values of x where x ≡ ± 1 (mod k) will be solutions to x^2 ≡ 1 (mod k) whether or not k is prime. Mauricio Huicochea Toledo is correct that x = k±1 will be solutions, as will 2k±1, 3k±1, etc. Of course, x = 0k±1 are solutions as well. Some values of k have extra solutions, such as k=8 has solutions for all odd x. The first few values for k that have extra solutions are: k = 8, 12, 15, 16, 20, 21, 24.

[@dario2886]

The end was the best

[@koenth2359]

Great vid. I like rephrasing it: x=1 and x=-1 are always solutions of x²≡1 (mod n), n does not need to be a prime. The proof is trivial. When n is prime, there are no OTHER solutions. Can we use the CRT to show that x²≡1 (mod n) iff for each prime factor p of n we have x²≡1 (mod p)?

[@Gideon_Judges6]

I don't like the convention of the congruence operator. Isn't it more intuitive to write: x^2 (mod n) = 1

[@stydras3380]

Not if you are writing several congruencies in one, like 49 Ξ 42 Ξ 7 Ξ 0 (mod 7). Yours would be quite a bit longer :P

[@Gideon_Judges6]

@@stydras3380 the symbol you used looks like Chinese #3, not congruence operator, which is also overloaded to mean "is defined to be" or "strongly defined" so the notation is ambiguous. Also you could equally say: x mod 7= 0 for x in {0, 7, 42, 49} and you could condense that even more with the right set theory symbols. I just think triple equals or whatever you want to call it, is overloaded in general and uintuitive in these simple cases. I understand it's meaning, I just don't prefer it.

[@RexxSchneider]

Let's also clear up the crap about x^2 ≡ 1 (mod p) where "p has to be prime". No it doesn't. Any integer n will give x ≡ ± 1 (mod n) as solutions to x^2 ≡ 1 (mod n). Here's the proof: If x ≡ ± 1 (mod n), then x can be written as nk ± 1 for some integer k. So x^2 = (nk ± 1)^2 = (nk)^2 ± 2nk + 1. Reducing each side modulo n, noting that (nk)^2 ≡ 0 (mod n) and 2nk ≡ 0 (mod n), we have: x^2 ≡ 0 ± 0 + 1 ≡ 1 (mod n). Q.E.D.

[@gas234567890]

That becase in 4:30

[@merbst]

C) Because

[@bharataaryavrat4067]

16=1(mod5) // 5 is a prime 4²=1(mod 5) 4=1(mod6) ❌ result 4=-1(mod 5)❌ result

[@bharataaryavrat4067]

Can u explain it why this is failed

[@LeBartoshe]

@@bharataaryavrat4067 It isn't "failed" though. 16 == 1 (mod 5) Thus 4 == 1 (mod 5) or 4 == -1 (mod 5) 1) 4 == 1 (mod 5) is not true 2) 4 == -1 (mod 5) is true as 4 == -1 (mod 5) == 4 (mod 5) Second result is true, thus the whole statement is true.

[@maxwellsequation4887]

That's not how it works

[@rodrigoamoedo8523]

love the extra load of weight hahahahaha

[@ssdd9911]

is the proof that a (2^2^n)+1 gon is constructible where (2^2^n)+1 is prime similar?

[@xxxprawn8374]

but why doesn’t it work for other numbers?

[@marcrg529]

At the end you said that you can take the square root "only" if n is prime, but you didn't prove that. You proved that it is sufficient to have the congruence mod n with n prime but not that it is necessary. Am I wrong? Thanks a lot!

[@marcrg529]

I mean, probably there exists, for example with n=2, a particular value for X such that X^2=1 mod 2 implies X=1 (mod 2) or X=-1 (mod 2), and therefore it is not necessary for n to be prime.

[@blackpenredpen]

I agree with you, I actually just wanted to prove the first direction and I am actually not sure if the converse is true, then we must have n being prime. I shouldn’t have said “only”

[@marcrg529]

@@blackpenredpen Thanks for answering, teacher ;) Awesome videos!

[@98danielray]

49=1mod6. 7=1mod6. the reciprocal doesnt apply. you can construct any counterexample by summing or subtracting 1 to/of a number and squaring the result.

[@marcrg529]

@@98danielray You are right! Thanks. Take whatever Natural N. Then N+1=1 (mod N). The square (N+1)^2 = N^2 + 2N + 1 = 1 (mod N) too, so it works for any not prime.

[@MrRyanroberson1]

Is there a proof for why, with coprime n and k, n^(k-1) mod k is always 1? I've worked out how to cut the range down to n between 1 and k: (n+mk)^(k-1) has k in every term except for a term valued n^(k-1), and for n=0, n is not coprime. 1 is counted as coprime and works universally, but I can't really go much farther than that.

[@TechToppers]

I know... Most probably. This is Fermat's *little* theorem right?

[@TechToppers]

This is actually interesting. Shall I post it in replies?

[@MrRyanroberson1]

@@TechToppers Maybe? i forgot i even commented this! definitely would be interesting to see a video proof, could get maybe... several views... math isn't the biggest category on the internet lol

[@TechToppers]

@@MrRyanroberson1 I know the answer!

[@MrRyanroberson1]

@@TechToppers i found that 2^(24x) mod 24x+1 is not 1 (besides x=0). this is already a counterproof since it shows that 2^(25-1) mod 25, even while 2 and 25 are coprime, is not 1.

[@mysteriousperson0845]

Does this proof work is p = 2?

[@theotang8418]

How to solve sqrt congerence

[@aishad4268]

Hey Ive just come across your channel I love it ! Wanted to ask what if the one was replaced by a prime like 7 what would you do ? (Eg: x^2 congruent to 7 mod 13

[@TechToppers]

You have to solve Diophantine. There is another method which I don't know but you can search this problem on Quora. By the way x²≡7 (mod 13) has no solutions. You can show this easily. Like, you can show that x²≡1 or 0 (mod 3). Proof: All natural numbers are in the form of 3q+1 or 3q+2 or 3q. Then... 3q+1≡1 (mod 3) Square both sides. 9q²+6q+1≡1 (mod 3) 3x+1≡1 (mod 3) where x= you know, right? Btw, x=3q²+2q. Similarly see for others. Use same strategy for modulo 13. q ∈ ℤ.

[@sethgrasse9082]

Question: does x congruent to 1 OR x congruent to -1 imply that x congruent to 1 AND x congruent to -1?

[@badrunna-im]

For any 2 statements that would only true if A is both necessary and sufficient for B, where either one implies the other (and itself, trivially). In other words, does x congruent to 1 imply x is congruent to -1, which is the same as being congruent to n-1, which is easily disproven for n≠2.

[@98danielray]

no and yes, he is writing it in a confusing way. it is or

[@nassershehadeh4661]

I have a suggestion for a problem, not sure if youve done it already, but it "proves" 1=2. You've probably seen it, if not I cant type it out in a comment.

[@blackpenredpen]

ok, show

[@nassershehadeh4661]

@@blackpenredpen Let A=B (Multiply both sides by A) A^2=AB (Subract B^2 from both sides) A^2-B^2=AB-B^2 (Some basic algebra) (A+B)(A-B)=B(A-B) (Divide both sides by (A-B)) A+B=B (Since A=B) A+A=A 2A=A (Divide both sides by A) 2=1 I realize there is probably some really stupid thing I am not seeing but a video on this (from your perspective) would be nice to watch.

[@MagnusSkiptonLLC]

@@nassershehadeh4661 _(Divide both sides by (A-B))_ Since A = B as stated earlier, A-B = 0, which means you're diving by 0, and after than all bets are off.

[@sufficientlyalive555]

Just want to check our maths level......Can you make a video solving indian Jee advanced maths paper.......We get 1 hour for that one.......But a challenge for you to complete in 45 min.....It's consist co ordinate geometry,algebra calculus...........More indian subscribers......By the way t series passed pewdiepie .....Indian channels try it pls.

[@aurithrabarua4698]

1st time I thought, those are Omnitrix. But in both hands??? Then I came to know the explanation 😝😝😝

[@RexxSchneider]

At 0:54 "This right here is not true." You're wrong. It is always true that if x^2 ≡ 1 (mod n) then x ≡ ± 1 (mod n) is a solution to it. Do you really believe that x ≡ 1 (mod 8) isn't a solution to x^2 ≡ 1 (mod 8) or that x ≡ 7 (mod 8) isn't a solution? Try them. 1^2 = 1 and that leaves a remainder of 1 when divided by 8. And 7^2 = 49 which also leaves a remainder of 1 when divided by 8. The fact that any odd number squared leaves a remainder of 1 when divided by 8 doesn't mean it's false to say that x=1 and x=7 are solutions. Your "counter-example" is logical effluent, because showing that x=3 solves x^2 ≡ 1 (mod 8) doesn't mean there can't be other solutions, such as x ≡ ± 1 (mod 8).

[@srpenguinbr]

But if x is congruent to 1, x=1+kn x²=(1+kn)² x²=1+2kn+k²n² x² is congruent to 1 mod n

[@maxhaibara8828]

Is it just "If", or is it also "If and only if"?

[@maxhaibara8828]

Oh wait, it is... And the proof should be pretty easy lol

[@blackpenredpen]

Max Haibara I think you can always square both side. The converse has nothing to do with p being prime.

[@maxhaibara8828]

@@blackpenredpen yeah haha, I commented before I even think about it

[@98danielray]

if

[@trewq398]

does he wear weights?

[@nvapisces7011]

H3 math is hard

[@khemirimoez8661]

n has to be prime

[@willnewman9783]

Challenge: Can anyone describe exactly which for which n we have x^2=1 (mod n) implies x=1 or x=-1?

[@RexxSchneider]

All of them. You'll find that x ≡ ± 1 (mod n) are always solutions for x^2 ≡ 1 (mod n). There may be other solutions, but those two hold for every n.

[@willnewman9783]

@@RexxSchneider I was asking for which n are 1 and -1 the only solutions.

[@RexxSchneider]

@@willnewman9783 Okay, I didn't realise from your original question that you were looking for the cases where x ≡ ± 1 (mod n) were the only solutions for x^2 ≡ 1 (mod n). The answer to that question is the set n = { 2, 4, p^k, 2p^k } where p is an odd prime and k is any integer. That is the same as asking for which values of n do primitive roots exist modulo n.

[@merbst]

Ok, now that you're getting into Number Theory, could you please cover Ramanujan's fun Theta series congruences? It was these that caught the eye of Hardy, (I think?) to reveal that Ramanujan was the real deal! All of Ramanujan's famous notebooks are publically published online! Let me go find you a link. Did I just hear you say you're running in the LA marathon? I didn't know that you were in SoCal! (Southern California for the non-locals) If I heard that correctly, I would love to talk to you about my DandelionLabs Nonprofit Organization plans, which is dedicated to improving international communications & collaborations between America and Asia, by focusing on open source software, especially SageMath.org and MediaWiki.org ! If you want to know more about the amazing Free & Open Source SageMath Computer Algebra System global project, I would be happy to drive up to Los Angeles someday to help you install it + accessories and teach you and anyone else who is interested what it can do better than Mathematica!

[@blackpenredpen]

Hi Matt, thanks for the message! Yes, I am running the LA marathon today, starting in 2 hours!!! I will have to get back to you later. : )

[@Jackorite]

You proposed p|(x-1)(x+1) and then said p must be prime because 6 doesn't divide neither 3 or 4. My question is this: Wouldn't you want to prove it for two numbers which are 2 digits away? ( (x-1)(x+1) for some x ) And secondly, doesn't this only prove that you can't rely on that equality for any n, but it doesn't disprove the possibility that no none prime n exists for some x in n|(x-1)(x+1)?

[@stephenbeck7222]

Counterexample for (x-1)(x+1) and a non-prime n works is exactly the counter he started with: x=3, n=8. 8 divides 2*4 but 8 does not divide 2 or 4. You're right that he did not prove that if n is prime then n must divide (x-1) or (x+1), but that statement is a direct result of Euclid's lemma.

[@98danielray]

only primes validate the implication. primes and not primes can satisfy that

[@scarbotheblacksheep9520]

NO THAT'S B

[@helloitsme7553]

What happened to your wrists?

[@zackmercurys]

you look so tired, don't.

[@blackpenredpen]

Zack Mercury awww thank you!

[@davidgould9431]

I would blame the wrist and ankle weights, but that would be mean of me. I think he's been doing marathon training: it does that to you! And g/l with the marathon, bprp.

[@ستيلوأورقة]

do you do wushu hh

[@redboy3743]

Nice

[@rot6015]

weird flex but ok

[@Akyadav-em1xy]

From rajasthan india

[@MathNerd1729]

"Becase p is prime" should be "Because p is prime"

[@dolevgo8535]

oh come on.