Math Is Fun Forum

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Divisibility by 7

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Divisibility by 7

Hi Jane;

There are no solutions:
You only have to try n=0,1,2,3,4,5,6 to get the repetitive cycle
5,3,3,1,3,1,1... mod 7.

Last edited by bobbym (2009-08-09 05:48:14)

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: Divisibility by 7

That’s one way to do it.

But there is an even better solution which does not involve being repetitive.

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

Re: Divisibility by 7

Fermat's Little Theorem could be useful, as it shows that n^6 = 1 for all n ≠ 0 (mod 7).
I'm thinking there's probably a nice way of showing that a^2 = 1 ⇒ a = ± 1 (mod 7), which would then show that n^3 = 1 or 6.
Group theory isn't my best subject though, so I don't know what that nice way is.

---

Why did the vector cross the road?
It wanted to be normal.

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Divisibility by 7

1) 0 is not a solution by inspection.

Using fermat we can prove:

Now for the n^3.

So;

 

So

We needed a modulo of 0 for divisibility and it doesn't exist so the 4n^6 + n^3 +5 is not divisible by 7.

Last edited by bobbym (2009-08-09 08:50:19)

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: Divisibility by 7

Fermat’s little theorem is also an excellent way to solve the problem.

But the very short solution I have in mind doesn’t even need Fermat.

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Divisibility by 7

Hi Jane;

Okay time to look at the hidden text. I'm not following that idea. Can you show your solution?

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: Divisibility by 7

Aw, don’t give up so early.

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Divisibility by 7

Hi Jane;

I did solve it in two ways already but your way remains a mystery to me.

Thanks for the big hint. I worked hard on it. Sorry to wimp out but I was unable to complete the square without getting a rational that I was unable to deal with. I came up with many interesting alternate forms like
4n^6+n^3+5 = (n^3-5)(4n^3+21)+110 which I then could use my method in post #5 on.
I tried to guess what you want but I couldn't. Please provide your method as it will an education for me.

Last edited by bobbym (2009-08-09 18:00:17)

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: Divisibility by 7

Well well, you really are stuck. Well then, have a look at ValentineA’s solution here: http://www.artofproblemsolving.com/Foru … p?t=294059

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Divisibility by 7

Hi Jane;

I got here like she did:

Missed this: Didn't see the factorization. Also if I ever knew anything about
quadratic residues I forgot it.

Thanks Jane. First itiselizabeth and now ValentineA. Some smart girls over there.

Last edited by bobbym (2009-08-09 22:25:54)

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: Divisibility by 7

Also if I ever knew anything about quadratic residues I forgot it.

“Quadratic residues” is just a fanciful way of talking about congruences of perfect squares.

In this problem, you can verify directly that no perfect square can be congruent to −1 mod 7 by checking

individually. In fact it is sufficient to check only

because of the fact that

for any

.

Last edited by JaneFairfax (2009-08-10 01:52:30)

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Divisibility by 7

Hi Jane;

  Thanks for beefing up my quadratic residues a little, so I can forget them again. Thanks  also for providing the third answer because another method is always valuable. I must say though that I like my 2 ways better.

Last edited by bobbym (2009-08-10 17:03:44)

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.