My Math Forum  

Go Back   My Math Forum > Math Forums > Math

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


Thanks Tree3Thanks
  • 1 Post By CRGreathouse
  • 1 Post By skeeter
  • 1 Post By CRGreathouse
Reply
 
LinkBack Thread Tools Display Modes
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.
USAMO Reaper is offline  
 
January 29th, 2015, 08:48 PM   #2
Global Moderator
 
CRGreathouse's Avatar
 
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
CRGreathouse is offline  
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.
jiasyuen is offline  
January 30th, 2015, 12:59 PM   #4
Math Team
 
skeeter's Avatar
 
Joined: Jul 2011
From: Texas

Posts: 2,922
Thanks: 1518

Quote:
Originally Posted by jiasyuen View Post
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.
Google?
skeeter is offline  
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
jiasyuen is offline  
January 30th, 2015, 02:20 PM   #6
Math Team
 
skeeter's Avatar
 
Joined: Jul 2011
From: Texas

Posts: 2,922
Thanks: 1518

Quote:
Originally Posted by jiasyuen View Post
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.
Thanks from jiasyuen
skeeter is offline  
January 30th, 2015, 02:59 PM   #7
Senior Member
 
Joined: Sep 2013
From: Earth

Posts: 827
Thanks: 36

Thanks
jiasyuen is offline  
January 30th, 2015, 04:30 PM   #8
Member
 
Joined: Jan 2015
From: Orlando, Florida

Posts: 92
Thanks: 10

Quote:
Originally Posted by CRGreathouse View Post
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.
this is the correct answer
USAMO Reaper is offline  
January 30th, 2015, 06:26 PM   #9
Global Moderator
 
CRGreathouse's Avatar
 
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 View Post
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 View Post
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 View Post
I don't even know what's mod
In that case you need more help than I can give.
Thanks from jiasyuen
CRGreathouse is offline  
Reply

  My Math Forum > Math Forums > Math

Tags
chinese, remainder



Thread Tools
Display Modes


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





Copyright © 2019 My Math Forum. All rights reserved.