Math Help - Finding prime numbers - problem w/method

1. Originally Posted by Euclid Alexandria
Since 4,753 is a prime number.
$4753\div 7 = 679$

What were you saying

2. Originally Posted by Euclid Alexandria
I was browsing through my subscribed threads for problems that were never completely dealt with. This is one such thread that I'd like to understand. In response to Random's answer (or anyone else reading this), both my book and my previous instructor encouraged the use of calculators for checking answers, but discouraged their use for solving problems. I agree with the idea of not allowing the calculator to do any of my work for me (at this point in time).

By "the pair," I suppose you're referring to $\frac{9,506}{12,222}$

And not $\frac{4,753}{6,111}$

Since 4,753 is a prime number.

Given the restraint of solving by hand, I'm having difficulty determining how I might ascertain the pair's Highest Common Factor... especially if this is the only method available for simplifying this fraction in particular.
Let me show you my way.

It is called the "Euclidean Algorithm" (That is you!) and it appears in the Bible of math, "The Elements".

To begin let me mention some terminology.

The largest common factor is also called the greatest common divisor.
It is abbreviated as $\gcd$

Say you want to find the greatest common factor of 9506 and 12222. A complicated thing to do, since you need to look at all the factors.

So we want to know what $\gcd(9506,12222)=?$

In order to find that, you need to know what a remainder and a quotient is. The quotient is the integer part when you divide. The remainder is what remains.
For example, find quotient and remainder when 25 is divided by 6?
When we divide the integer part that remains is 4. And the remainder is 1.
Here is the most important step when you get the quotient and remainder you can write,
$25=\underbrace{4}_{\mbox{ Quotient }}\times 6+\underbrace{1}_{\mbox{ Remainder }}$
This is called "Division algorithm".

Here is another example, express 333 and 110 in division algorithm form?
$333=3\times 110+3$
---
Now we can talk about Euclidean Algorithm
---
We start of by expressing 12222 and 9506 in division algorithm form.
$12222=1\times 9506+2716$
According to Euclid this problem of find the greatest common divisor is the same as finding the greatest common divisor between the number to the right of quotient and remainder.
But to do that
We need to express 9506 and 2716 in division algorithm form,
$9506=3\times 2716+1358$
Again we find the division algorithm form between number to the right of quotient and remainder,
$2716=2\times 1358+0$
When we reach 0 as remainder this tells us that the number to the right of quotient is the greatest common divisor. So
$\gcd (12222, 9506)=1358$

3. Quick, is there an easy way to determine whether a number is divisible by 7?

PerfectHacker, thank you! That made a lot of sense even at a glance, so it will probably put me at ease this weekend when I look over it in detail. I'm beginning to think this was a really strange problem to appear in my math book. There really are no explanations given for handling its peculiarities.

4. Originally Posted by Euclid Alexandria
Quick, is there an easy way to determine whether a number is divisible by 7?
Yes, there is. I'm not Quick, but I hope I can answer anyway!

Take the last digit and multiply it by 2. So in this case, when you got 2037, the last digit is 7, and multiplied with 2 it's 14. Then you subtract that from "the rest" of the number, which is 203. 203 - 14 = 189. If the new number is divisible by 7, then the original number is as well.

$2037$
$203 - 2\cdot 7 = 189$
$18 - 2\cdot 9 = 0$
0 is divisible by 7, and so is 2037.[/QUOTE]

Here's the derivation:

Consider the number $n$ as a sum of the last digit and the rest of the number, $n = 10\cdot x + y$.
We wanna check if $n\ \equiv\ 0\ (\text{mod 7})$
$10\cdot x + y\ \equiv\ 0\ (\text{mod 7}) \longleftrightarrow$
$-10\cdot x - y\ \equiv\ 0\ (\text{mod 7}) \longleftrightarrow /gcd(2, 7) = 1/ \longleftrightarrow$ (I at least think $gcd(2, 7) = 1$ is a requirement for using the included $\longleftarrow$ sign)
$2\cdot(-10\cdot x - y)\ \equiv\ 0\ (\text{mod 7}) \longleftrightarrow$
$-20\cdot x - 2\cdot y\ \equiv\ 0\ (\text{mod 7}) \longleftrightarrow /-20\ \equiv\ 1\ (\text{mod 7})/ \longleftrightarrow$
$x - 2\cdot y\ \equiv\ 0\ (\text{mod 7})$

5. Originally Posted by TriKri
Take the last digit and multiply it by 2. So in this case, when you got 2037, the last digit is 7, and multiplied with 2 it's 14. Then you subtract that from "the rest" of the number, which is 203. 203 - 14 = 189. If the new number is divisible by 7, then the original number is as well.
Thanks, TriKri, that is a huge help.

6. Your'e so welcome.

Page 2 of 2 First 12