text:
# finding lowest number which solves modulo arithmetic equation

I'm having a some trouble trying to find the best solution.

Given $i,b,m \in \mathbb N$ how do I find the smallest nonnegative integer $n$ that satisfies the equation $$i + bn \equiv 0 \mod m$$

Any help would be appreciated.

• Are you aware of the chinese remainder theorem, or the euclidean algorithm? – flawr Jan 15 '16 at 23:48
• You want $b\times n\equiv i\bmod m$. I think the most efficient solution would be to find solutions modulo each prime power $p^{\alpha}$ with $p^{\alpha}|| m$ and then find all possible solutions via the chinese remainder theorem. – Jorge Fernández-Hidalgo Jan 15 '16 at 23:50

You can solve for $n$ if and only if $gcd(b,m)=1$. In that case you can find $r,s$ such that $1 = rb+sm$ via euclidean algorithm. Then
$$1 \equiv rb \mod m$$ which implies $$b^{-1} \equiv r \mod m$$
Then you can just pick the least positive $n$ satisfying $$n \equiv b^{-1}(-i) \equiv -ri \mod m$$


text:
Search by Topic

Resources tagged with Visualising similar to Loose Change:

Filter by: Content type:
Stage:
Challenge level:

Painting Cubes

Stage: 3 Challenge Level:

Imagine you have six different colours of paint. You paint a cube using a different colour for each of the six faces. How many different cubes can be painted using the same set of six colours?

Ding Dong Bell

Stage: 3, 4 and 5

The reader is invited to investigate changes (or permutations) in the ringing of church bells, illustrated by braid diagrams showing the order in which the bells are rung.

Euromaths

Stage: 3 Challenge Level:

How many ways can you write the word EUROMATHS by starting at the top left hand corner and taking the next letter by stepping one step down or one step to the right in a 5x5 array?

Instant Insanity

Stage: 3, 4 and 5 Challenge Level:

Given the nets of 4 cubes with the faces coloured in 4 colours, build a tower so that on each vertical wall no colour is repeated, that is all 4 colours appear.

Tetrahedra Tester

Stage: 3 Challenge Level:

An irregular tetrahedron is composed of four different triangles. Can such a tetrahedron be constructed where the side lengths are 4, 5, 6, 7, 8 and 9 units of length?

Clocked

Stage: 3 Challenge Level:

Is it possible to rearrange the numbers 1,2......12 around a clock face in such a way that every two numbers in adjacent positions differ by any of 3, 4 or 5 hours?

Penta Colour

Stage: 4 Challenge Level:

In how many different ways can I colour the five edges of a pentagon red, blue and green so that no two adjacent edges are the same colour?

One Out One Under

Stage: 4 Challenge Level:

Imagine a stack of numbered cards with one on top. Discard the top, put the next card to the bottom and repeat continuously. Can you predict the last card?

Paving Paths

Stage: 3 Challenge Level:

How many different ways can I lay 10 paving slabs, each 2 foot by 1 foot, to make a path 2 foot wide and 10 foot long from my back door into my garden, without cutting any of the paving slabs?

How Many Dice?

Stage: 3 Challenge Level:

A standard die has the numbers 1, 2 and 3 are opposite 6, 5 and 4 respectively so that opposite faces add to 7? If you make standard dice by writing 1, 2, 3, 4, 5, 6 on blank cubes you will find. . . .

Cube Paths

Stage: 3 Challenge Level:

Given a 2 by 2 by 2 skeletal cube with one route `down' the cube. How many routes are there from A to B?

Fermat's Poser

Stage: 4 Challenge Level:

Find the point whose sum of distances from the vertices (corners) of a given triangle is a minimum.

Cubic Conundrum

Stage: 2, 3 and 4 Challenge Level:

Which of the following cubes can be made from these nets?

There and Back Again

Stage: 3 Challenge Level:

Bilbo goes on an adventure, before arriving back home. Using the information given about his journey, can you work out where Bilbo lives?

Stage: 3 Challenge Level:

Can you mark 4 points on a flat surface so that there are only two different distances between them?

Flight of the Flibbins

Stage: 3 Challenge Level:

Blue Flibbins are so jealous of their red partners that they will not leave them on their own with any other bue Flibbin. What is the quickest way of getting the five pairs of Flibbins safely to. . . .

Building Gnomons

Stage: 4 Challenge Level:

Build gnomons that are related to the Fibonacci sequence and try to explain why this is possible.

Around and Back

Stage: 4 Challenge Level:

A cyclist and a runner start off simultaneously around a race track each going at a constant speed. The cyclist goes all the way around and then catches up with the runner. He then instantly turns. . . .

Sprouts

Stage: 2, 3, 4 and 5 Challenge Level:

A game for 2 people. Take turns joining two dots, until your opponent is unable to move.

LOGO Challenge - Triangles-squares-stars

Stage: 3 and 4 Challenge Level:

Can you recreate these designs? What are the basic units? What movement is required between each unit? Some elegant use of procedures will help - variables not essential.

LOGO Challenge - Circles as Animals

Stage: 3 and 4 Challenge Level:

See if you can anticipate successive 'generations' of the two animals shown here.

Hypotenuse Lattice Points

Stage: 4 Challenge Level:

The triangle OMN has vertices on the axes with whole number co-ordinates. How many points with whole number coordinates are there on the hypotenuse MN?

Yih or Luk Tsut K'i or Three Men's Morris

Stage: 3, 4 and 5 Challenge Level:

Some puzzles requiring no knowledge of knot theory, just a careful inspection of the patterns. A glimpse of the classification of knots and a little about prime knots, crossing numbers and. . . .

You Owe Me Five Farthings, Say the Bells of St Martin's

Stage: 3 Challenge Level:

Use the interactivity to listen to the bells ringing a pattern. Now it's your turn! Play one of the bells yourself. How do you know when it is your turn to ring?

Zooming in on the Squares

Stage: 2 and 3

Start with a large square, join the midpoints of its sides, you'll see four right angled triangles. Remove these triangles, a second square is left. Repeat the operation. What happens?

Sea Defences

Stage: 2 and 3 Challenge Level:

These are pictures of the sea defences at New Brighton. Can you work out what a basic shape might be in both images of the sea wall and work out a way they might fit together?

Isosceles Triangles

Stage: 3 Challenge Level:

Draw some isosceles triangles with an area of $9$cm$^2$ and a vertex at (20,20). If all the vertices must have whole number coordinates, how many is it possible to draw?

Cubes Within Cubes

Stage: 2 and 3 Challenge Level:

We start with one yellow cube and build around it to make a 3x3x3 cube with red cubes. Then we build around that red cube with blue cubes and so on. How many cubes of each colour have we used?

Packing 3D Shapes

Stage: 4 Challenge Level:

What 3D shapes occur in nature. How efficiently can you pack these shapes together?

Clocking Off

Stage: 2, 3 and 4 Challenge Level:

I found these clocks in the Arts Centre at the University of Warwick intriguing - do they really need four clocks and what times would be ambiguous with only two or three of them?

Tilting Triangles

Stage: 4 Challenge Level:

A right-angled isosceles triangle is rotated about the centre point of a square. What can you say about the area of the part of the square covered by the triangle as it rotates?

Square Coordinates

Stage: 3 Challenge Level:

A tilted square is a square with no horizontal sides. Can you devise a general instruction for the construction of a square when you are given just one of its sides?

Efficient Packing

Stage: 4 Challenge Level:

How efficiently can you pack together disks?

The Development of Spatial and Geometric Thinking: 5 to 18

Stage: 1, 2, 3 and 4

This is the first article in a series which aim to provide some insight into the way spatial thinking develops in children, and draw on a range of reported research. The focus of this article is the. . . .

Framed

Stage: 3 Challenge Level:

Seven small rectangular pictures have one inch wide frames. The frames are removed and the pictures are fitted together like a jigsaw to make a rectangle of length 12 inches. Find the dimensions of. . . .

The Spider and the Fly

Stage: 4 Challenge Level:

A spider is sitting in the middle of one of the smallest walls in a room and a fly is resting beside the window. What is the shortest distance the spider would have to crawl to catch the fly?

All Tied Up

Stage: 4 Challenge Level:

A ribbon runs around a box so that it makes a complete loop with two parallel pieces of ribbon on the top. How long will the ribbon be?

Floating in Space

Stage: 4 Challenge Level:

Two angles ABC and PQR are floating in a box so that AB//PQ and BC//QR. Prove that the two angles are equal.

Cubic Net

Stage: 4 and 5 Challenge Level:

This is an interactive net of a Rubik's cube. Twists of the 3D cube become mixes of the squares on the 2D net. Have a play and see how many scrambles you can undo!

Coordinate Patterns

Stage: 3 Challenge Level:

Charlie and Alison have been drawing patterns on coordinate grids. Can you picture where the patterns lead?

Konigsberg Plus

Stage: 3 Challenge Level:

Euler discussed whether or not it was possible to stroll around Koenigsberg crossing each of its seven bridges exactly once. Experiment with different numbers of islands and bridges.

Jam

Stage: 4 Challenge Level:

A game for 2 players

Wari

Stage: 4 Challenge Level:

This is a simple version of an ancient game played all over the world. It is also called Mancala. What tactics will increase your chances of winning?

Square It

Stage: 3 and 4 Challenge Level:

Players take it in turns to choose a dot on the grid. The winner is the first to have four dots that can be joined to form a square.

Khun Phaen Escapes to Freedom

Stage: 3 Challenge Level:

Slide the pieces to move Khun Phaen past all the guards into the position on the right from which he can escape to freedom.

Changing Places

Stage: 4 Challenge Level:

Place a red counter in the top left corner of a 4x4 array, which is covered by 14 other smaller counters, leaving a gap in the bottom right hand corner (HOME). What is the smallest number of moves. . . .

Sliced

Stage: 4 Challenge Level:

An irregular tetrahedron has two opposite sides the same length a and the line joining their midpoints is perpendicular to these two edges and is of length b. What is the volume of the tetrahedron?

Dice, Routes and Pathways

Stage: 1, 2 and 3

This article for teachers discusses examples of problems in which there is no obvious method but in which children can be encouraged to think deeply about the context and extend their ability to. . . .

Inside Out

Stage: 4 Challenge Level:

There are 27 small cubes in a 3 x 3 x 3 cube, 54 faces being visible at any one time. Is it possible to reorganise these cubes so that by dipping the large cube into a pot of paint three times you. . . .

Bands and Bridges: Bringing Topology Back

Stage: 2 and 3

Lyndon Baker describes how the Mobius strip and Euler's law can introduce pupils to the idea of topology.

format: plain