My Math Forum Revival-Math Q&A

 Math Events Math Events, Competitions, Meetups - Local, Regional, State, National, International

 April 11th, 2014, 01:13 AM #21 Senior Member     Joined: Apr 2014 From: Greater London, England, UK Posts: 320 Thanks: 156 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$. Thanks from agentredlum
April 11th, 2014, 03:58 AM   #22
Math Team

Joined: Jul 2011
From: North America, 42nd parallel

Posts: 3,372
Thanks: 233

Quote:
 Originally Posted by Olinguito 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$.
We can write

$$[(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$

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: 156 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{p-1}2}\pmod p$$ where $a$ is any integer and the parentheses denote the Legendre symbol. Anyway, enough lecturing from me. Over to you, Agentredlum. Thanks from agentredlum
 April 11th, 2014, 05:31 AM #24 Math Team     Joined: Jul 2011 From: North America, 42nd parallel Posts: 3,372 Thanks: 233 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! Thanks from Olinguito
April 11th, 2014, 07:06 AM   #25
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 Olinguito Find all integers $n$ such that $\displaystyle \left(n^{2014}+2013\right)^{2012}+1$ is divisible by $2011$.
There are no such integers, as far as I can tell. In fact no numbers of the form $k^{2012}+1$ are divisible by 2011.

April 11th, 2014, 07:44 AM   #26
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 agentredlum I give the control to CRGreathouse , your question!
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, ..., m-1} 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: 938 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. Thanks from agentredlum 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,372 Thanks: 233 Sorry , been away for a few days. I designate MR. TNT! (mathbalarka) or Hoempa as the next inquisitor , whomever posts first. Thanks from Hoempa
 April 22nd, 2014, 02:30 AM #29 Math Team   Joined: Apr 2010 Posts: 2,780 Thanks: 361 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, ..., m-1} 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? Thanks from agentredlum
 April 22nd, 2014, 05:08 AM #30 Math Team   Joined: Apr 2010 Posts: 2,780 Thanks: 361 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? Thanks from agentredlum and mathbalarka

 Tags qanda, revivalmath

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post E01 Academic Guidance 7 February 9th, 2014 08:25 AM z4dok New Users 0 October 3rd, 2013 08:43 AM mishaark Math Books 6 September 8th, 2012 06:19 AM s13bob Linear Algebra 1 May 24th, 2008 07:53 AM mishaark Elementary Math 0 December 31st, 1969 04:00 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top