mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2012-05-08, 11:32   #1
Lee Yiyuan
 
Feb 2011
Singapore

5×7 Posts
Default Congruence relations

Hi, i am widely unfamiliar with modular arithmetic and i wanted to know (i tried hard at googling but still seemed to fail) :
if n = a (mod b), when does n = b (mod a) ?
Lee Yiyuan is offline   Reply With Quote
Old 2012-05-08, 11:44   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dartmouth NS

2×3×23×61 Posts
Default

Quote:
Originally Posted by Lee Yiyuan View Post
Hi, i am widely unfamiliar with modular arithmetic and i wanted to know (i tried hard at googling but still seemed to fail) :
if n = a (mod b), when does n = b (mod a) ?
I made a modular arithmetic thread before, question can you read a clock ? if so you can do modular (clock) arithmetic basics.
science_man_88 is offline   Reply With Quote
Old 2012-05-08, 11:46   #3
Lee Yiyuan
 
Feb 2011
Singapore

5·7 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
I made a modular arithmetic thread before, question can you read a clock ? if so you can do modular (clock) arithmetic basics.
Yup, i know the basics like a + b = a (mod n) + b (mod n), etc. Saw it, thanks!
Lee Yiyuan is offline   Reply With Quote
Old 2012-05-08, 11:50   #4
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dartmouth NS

2×3×23×61 Posts
Default

Quote:
Originally Posted by Lee Yiyuan View Post
Yup, i know the basics like a + b = a (mod n) + b (mod n), etc. Saw it, thanks!
N=a mod (b)=b(mod a) iff N|b-a and N|a-b .
science_man_88 is offline   Reply With Quote
Old 2012-05-08, 11:54   #5
Lee Yiyuan
 
Feb 2011
Singapore

5·7 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
N=a mod (b)=b(mod a) iff N|b-a and N|a-b .
What about for |a - b| < |n| ?

Last fiddled with by Lee Yiyuan on 2012-05-08 at 11:54
Lee Yiyuan is offline   Reply With Quote
Old 2012-05-08, 12:04   #6
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

2×7×461 Posts
Default

Ignore scienceman, he's got the wrong definition ...

N=a mod b = b mod a means (N-a) is divisible by b and (N-b) divisible by a, there's nothing involving a-b.

There is always (ok, for a,b>2) an infinite number of solutions to N=a mod b and N=b mod a; to find them, do 'chinese(Mod(a,b),Mod(b,a))' in pari.
fivemack is offline   Reply With Quote
Old 2012-05-08, 12:13   #7
Lee Yiyuan
 
Feb 2011
Singapore

5×7 Posts
Default

Quote:
Originally Posted by fivemack View Post
Ignore scienceman, he's got the wrong definition ...

N=a mod b = b mod a means (N-a) is divisible by b and (N-b) divisible by a, there's nothing involving a-b.

There is always (ok, for a,b>2) an infinite number of solutions to N=a mod b and N=b mod a; to find them, do 'chinese(Mod(a,b),Mod(b,a))' in pari.
Thank you.
However pari outputs "inconsistent variables in chinese, b!=a

Edit: please ignore my previous comment, i am still struggling with grasping PARI

Last fiddled with by Lee Yiyuan on 2012-05-08 at 12:20 Reason: en
Lee Yiyuan is offline   Reply With Quote
Old 2012-05-08, 12:55   #8
axn
 
axn's Avatar
 
Jun 2003

10101001111002 Posts
Default

You can do it the hard way, but essentially, the solution boils down to N=kab+a+b.

start with, n = ax+b = by+a

rearranging, a(x-1) = b(y-1)

ratio, (y-1)/(x-1) = a/b = (ka)/(kb)

general solution, y = ka+1, x = kb+1

substituing back, n = kab + a + b
axn is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Linear Congruence order 4 sequence not testing in PFGW? carpetpool Software 14 2017-07-13 19:54
Congruence storm5510 Math 27 2009-09-22 23:14
More relations mean many more relations wanted fivemack Factoring 7 2007-08-04 17:32
Congruence notation meknowsnothing Math 1 2007-05-31 03:32
congruence mod 2^p-1 abiessuunreg Miscellaneous Math 3 2005-03-07 21:03

All times are UTC. The time now is 07:11.


Fri Feb 3 07:11:59 UTC 2023 up 169 days, 4:40, 1 user, load averages: 0.99, 0.87, 0.84

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔