April 11th, 2014, 01:13 AM  #21 
Senior Member Joined: Apr 2014 From: Greater London, England, UK Posts: 320 Thanks: 155 Math Focus: Abstract algebra 
All right, sorry. The problem above was probably over the top; it was naughty of me to set it. Let’s try something more down to earth. Find all integers $n$ such that $\displaystyle \left(n^{10}+9\right)^8+1$ is divisible by $7$. 
April 11th, 2014, 03:58 AM  #22  
Math Team Joined: Jul 2011 From: North America, 42nd parallel Posts: 3,119 Thanks: 151  Quote:
$$ [(n^{10} + 9 )^4]^2 \equiv 1 \ (mod \ 7)$$ So we have $$ k^2 \equiv 6 \ (mod \ 7)$$ Which is impossible since $k^2 \ (mod \ 7) = 0 , 1 , 4 , 2$ Answer: No solution. How would you do the first one you posed? Finding the squares mod 2011 and seeing if any are 2010 seems like a lot of work.  
April 11th, 2014, 05:04 AM  #23 
Senior Member Joined: Apr 2014 From: Greater London, England, UK Posts: 320 Thanks: 155 Math Focus: Abstract algebra 
Nice solution, Agentredlum. The solution to the first problem requires some knowledge of number theory, in particular the theory of quadratic residues. When I posted the original problem, it did not occur to me that some people might not be familiar with this. My apologies. The result I wanted to be used is this: Let $p$ be an odd prime. Then the congruence $x^2+1\equiv0\pmod p$ has an integer solution if and only if $p\equiv1\pmod4$. Equivalently it has no solution if and only if $p\equiv3\pmod4$. This can be proved from Euler’s criterion: $$\left(\frac ap\right)\ \equiv\ a^{\frac{p1}2}\pmod p$$ where $a$ is any integer and the parentheses denote the Legendre symbol. Anyway, enough lecturing from me. Over to you, Agentredlum. 
April 11th, 2014, 05:31 AM  #24 
Math Team Joined: Jul 2011 From: North America, 42nd parallel Posts: 3,119 Thanks: 151 
Thanx , i also appreciate the lecture. I've been trying to get 'comfortable' with quadratic reciprocity for years but there seems to be a mental block somewhere. So let me see if i understand , 1) We can write $k^{2012} = (k^{1006})^2$ 2) We can identify 2011 as $p \equiv 3 \ (mod \ 4)$ 3) Using the result you stated , we conclude there are no solutions. I'm pretty sure other MMF members know how to do the Q.R. , like CRGreathouse , mathbalarka and Hoempa to name a few but they seem to be busy elsewhere. I give the control to CRGreathouse , your question! 
April 11th, 2014, 07:06 AM  #25  
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 931 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Quote:
Edit: This was already solved, twice!, above. I hadn't noticed, I was reading toptobottom.  
April 11th, 2014, 07:44 AM  #26 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 931 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Two sets of integers, A and C, are said to tile the integers if every integer n can be represented uniquely as n = a + c with a in A and c in C. For example, A = {0, 7} and C = the set of even numbers. A set of integers P is called periodic if there is some integer m > 0 and some subset B of {0, 1, ..., m1} such that P is B mod m, that is, P = {b + mn: b in B, n in Z}. You may answer any one of the following questions: 1. (Theory) Prove or disprove: for every tiling (A, C) of the integers, either A or C is periodic. 2. (Computation, easy) The integers mod n can be tiled by some (A, C) exactly when n is of the form $p^a,\ p^aq,\ p^2qr,\ p^2q^2,\ pqr,$ or $pqrs$, where p, q, r, and s are distinct primes and a, b > 0. What is the first n which cannot be so tiled? How many of the first 100 numbers cannot be so tiled? 3. (Theory, easy) See 2. What asymptotic fraction of integers n such that the integers mod n can be tiled? 
April 13th, 2014, 08:31 AM  #27 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 931 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms 
Sigh... The statement in 1 is true (proof omitted). For 2, the first number is 72 and there are no more in the first hundred positive integers. For 3, the fraction is 0 (even though the fraction in the first 100 is 99%). See http://mathworld.wolfram.com/HajosGroup.html and https://oeis.org/A102562 . Control reverts to agent or his designee. Last edited by CRGreathouse; April 14th, 2014 at 06:20 AM. 
April 15th, 2014, 05:42 PM  #28 
Math Team Joined: Jul 2011 From: North America, 42nd parallel Posts: 3,119 Thanks: 151 
Sorry , been away for a few days. I designate MR. TNT! (mathbalarka) or Hoempa as the next inquisitor , whomever posts first. 
April 22nd, 2014, 02:30 AM  #29 
Math Team Joined: Apr 2010 Posts: 2,770 Thanks: 356 
I don't see a proof for 1. Perhaps first try to form two finite sets A' and C such that every n in {0, 1, ..., m1} can be written uniquely as a + c where a in A' and c in C and then extend A' to A such that A and C tile the integers. To proof is that the extension yields a periodic set A. Is this a good approach? For 2, how is b used? 
April 22nd, 2014, 05:08 AM  #30 
Math Team Joined: Apr 2010 Posts: 2,770 Thanks: 356 
And here a new question. A prisoner gets a special offer. He can get released from prison if he can do the following correctly. He gets placed in an open section with cells, each being numbered. In every cell, there is a table with a piece of paper on it, as in the image below. The prisoner has to walk a route through the section. A route must be starting in cell 1, where he is now, and ending in cell 16. He must be in the cell to pick up the piece of paper. He may enter every cell just once. He can enter cells through a door. He could walk through a door in both directions. The prisoner accepts the offer. If he gets to cell 16 with all 16 notes he gets free. Else, he is executed. How many different routes can he walk to freedom? 

Tags 
qanda, revivalmath 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
In what order should I learn math?(Math is daunting)  E01  Academic Guidance  7  February 9th, 2014 09:25 AM 
Math Practising Resources for These Math Goals  z4dok  New Users  0  October 3rd, 2013 08:43 AM 
A book on basic math that explains how math really works  mishaark  Math Books  6  September 8th, 2012 06:19 AM 
Unknown math probelm. math matrice?  s13bob  Linear Algebra  1  May 24th, 2008 07:53 AM 
A book on basic math that explains how math really works  mishaark  Elementary Math  0  January 1st, 1970 12:00 AM 