My Math Forum  

Go Back   My Math Forum > Math Forums > Math Events

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


Thanks Tree137Thanks
Reply
 
LinkBack Thread Tools Display Modes
April 11th, 2014, 01:13 AM   #21
Senior Member
 
Olinguito's Avatar
 
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$.
Thanks from agentredlum
Olinguito is offline  
 
April 11th, 2014, 03:58 AM   #22
Math Team
 
agentredlum's Avatar
 
Joined: Jul 2011
From: North America, 42nd parallel

Posts: 3,347
Thanks: 227

Quote:
Originally Posted by Olinguito View Post
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$

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.

Thanks from Olinguito
agentredlum is offline  
April 11th, 2014, 05:04 AM   #23
Senior Member
 
Olinguito's Avatar
 
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{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
Olinguito is offline  
April 11th, 2014, 05:31 AM   #24
Math Team
 
agentredlum's Avatar
 
Joined: Jul 2011
From: North America, 42nd parallel

Posts: 3,347
Thanks: 227

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
agentredlum is offline  
April 11th, 2014, 07:06 AM   #25
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 933

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Quote:
Originally Posted by Olinguito View Post
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.

Edit: This was already solved, twice!, above. I hadn't noticed, I was reading top-to-bottom.
Thanks from Olinguito
CRGreathouse is offline  
April 11th, 2014, 07:44 AM   #26
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 933

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Quote:
Originally Posted by agentredlum View Post
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?
Thanks from agentredlum and Olinguito
CRGreathouse is offline  
April 13th, 2014, 08:31 AM   #27
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 933

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.
CRGreathouse is offline  
April 15th, 2014, 05:42 PM   #28
Math Team
 
agentredlum's Avatar
 
Joined: Jul 2011
From: North America, 42nd parallel

Posts: 3,347
Thanks: 227

Sorry , been away for a few days. I designate MR. TNT! (mathbalarka) or Hoempa as the next inquisitor , whomever posts first.

Thanks from Hoempa
agentredlum is offline  
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, ..., 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
Hoempa is offline  
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?
Thanks from agentredlum and mathbalarka
Hoempa is offline  
Reply

  My Math Forum > Math Forums > Math Events

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 08: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 December 31st, 1969 04:00 PM





Copyright © 2017 My Math Forum. All rights reserved.