My Math Forum > Math Chinese Remainder!!!!!!!!!!!!

 Math General Math Forum - For general math related discussion and news

 January 29th, 2015, 05:40 PM #1 Member   Joined: Jan 2015 From: Orlando, Florida Posts: 92 Thanks: 10 Chinese Remainder!!!!!!!!!!!! Suppose that m and n are integers with 1 ≤ m ≤ 49 and n ≥ 0 such that m divides n^(n+1) + 1. What is the number of possible values of m? Last edited by skipjack; January 30th, 2015 at 07:16 PM.
 January 29th, 2015, 08:48 PM #2 Global Moderator     Joined: Nov 2006 From: UTC -5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms Well, as a last resort, $n^{n+1}+1\equiv (n+k)^{n+k+1}+1$ when $k$ is a multiple of $n\varphi(n),$ so you could step through each m this way and see which work. I get 29, FWIW. Thanks from USAMO Reaper
 January 30th, 2015, 12:57 PM #3 Senior Member   Joined: Sep 2013 From: Earth Posts: 827 Thanks: 36 I'm a Chinese. I don't even know what's Chinese remainder theorem. Can anyone show me where's the resource to learn this theorem? I feel shameful.
January 30th, 2015, 12:59 PM   #4
Math Team

Joined: Jul 2011
From: Texas

Posts: 3,002
Thanks: 1588

Quote:
 Originally Posted by jiasyuen I'm a Chinese. I don't even know what's Chinese remainder theorem. Can anyone show me where's the resource to learn this theorem? I feel shameful.

 January 30th, 2015, 01:06 PM #5 Senior Member   Joined: Sep 2013 From: Earth Posts: 827 Thanks: 36 I looked out in Wikipedia. But it looks complicated. I don't even know what's mod
January 30th, 2015, 02:20 PM   #6
Math Team

Joined: Jul 2011
From: Texas

Posts: 3,002
Thanks: 1588

Quote:
 Originally Posted by jiasyuen I looked out in Wikipedia. But it looks complicated. I don't even know what's mod.
Google modular arithmetic ... it's not that difficult.

 January 30th, 2015, 02:59 PM #7 Senior Member   Joined: Sep 2013 From: Earth Posts: 827 Thanks: 36 Thanks
January 30th, 2015, 04:30 PM   #8
Member

Joined: Jan 2015
From: Orlando, Florida

Posts: 92
Thanks: 10

Quote:
 Originally Posted by CRGreathouse Well, as a last resort, $n^{n+1}+1\equiv (n+k)^{n+k+1}+1$ when $k$ is a multiple of $n\varphi(n),$ so you could step through each m this way and see which work. I get 29, FWIW.

January 30th, 2015, 06:26 PM   #9
Global Moderator

Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Quote:
 Originally Posted by jiasyuen I'm a Chinese. I don't even know what's Chinese remainder theorem. Can anyone show me where's the resource to learn this theorem? I feel shameful.
Quote:
 Originally Posted by jiasyuen I looked out in Wikipedia. But it looks complicated.
The basic idea is pretty simple: if you have a collection of residues mod different moduli, and the moduli are coprime, then there is a unique residue class mod the product of the moduli which is equal to each of the original residues mod their respective moduli.

So if you have
1 mod 2
2 mod 3
7 mod 11
then the CRT says there is exactly one residue class mod 66 = 2*3*11 which satisfies all three of these, and tells you how to find it.

(If the residues aren't coprime, you take the LCM instead of product, but unless the residues are compatible you won't get any residues that work.)

Quote:
 Originally Posted by jiasyuen I don't even know what's mod
In that case you need more help than I can give.

 Tags chinese, remainder

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post miket Number Theory 9 July 17th, 2014 06:20 AM Herc11 Abstract Algebra 0 February 18th, 2013 03:00 AM Mathsgir10 Number Theory 2 May 19th, 2010 01:00 AM cvcv49 Number Theory 4 April 29th, 2010 08:40 AM cvcv49 Abstract Algebra 2 December 31st, 1969 04:00 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top