Question

Help!

Answer 1

Two numbers are selected from the set of first 100 natural numbers then find total ways in which \(\large a^2+b^2\) is dividisble by 7.

Answer 2

@ganeshie8 @Psymon @shubhamsrg

Answer 3

Okay, here is one trick you can try...

Answer 4

Consider only the final digit of each number!

Answer 5

wont work..

Answer 6

\[
1,1 \to 1+1=2\\
1,2\to 1+4=5\\
...
\]

Answer 7

Why not?

Answer 8

There are \(^{10}C_2\) combos.

Answer 9

I actually want to understand the original solution..
its like..
Numbers are of form: 7k,7k+1,7k+2,7k+3,7k+4..
and then similarly they computed squares too..can anyone tell me what is happening here?

Answer 10

Ummm, that alone isn't a solution.

Answer 11

yes thats the beginning,which I didnt get either

Answer 12

Okay, so what they are saying is that...

Answer 13

please tell in detail :(
m VERY confused :/

Answer 14

Any number \(n\) divided by \(d\) can be written as:\[
n=qd+r
\]Where \(q\) is the quotient and \(r\) is the remainder.

Answer 15

They're all natural numbers. and \(r<d\)

Answer 16

Well they're all integers at least.

Answer 17

In this case they are dividing by \(7\) so \(d=7\). They also used \(k\) for \(q\).

Answer 18

So what they are doing is listing off all possibilities of \[
7k+r
\]

Answer 19

\(r=0,r=1,...,r=6\)

Answer 20

okay

Answer 21

but that stopped at 7k+4??

Answer 22

\[
(7k+r)^2=7\times7k+2\times 7rk+r^2=7(7k+2rk)+r^2
\]

Answer 23

Now if we square the numbers for \(r \in [0,6]\in\mathbb{N}\)...\[
0\to 0\\
1\to 1\\
2\to 4\\
3\to 9=7+2\\
4\to 16=2\times 7+2\\
5\to 25=3\times 7+4\\
6\to 36=5\times 7+1
\]

Answer 24

So the only remainders here are \(0,1,2,4\)

Answer 25

In other words: \[
(7k+r)^2=7k'+r'
\]

Answer 26

Does that muck make sense to you?

Answer 27

what is that?
0->0 ..

Answer 28

\(0^2=0\)

Answer 29

\[
r^2\to 7n+r'
\]

Answer 30

okay

Answer 31

What does the proof say next?

Answer 32

i only have this much :P its a hint

Answer 33

I honestly don't know where to go from there though.

Answer 34

Oh, I think I have an idea!

Answer 35

Okay so suppose \[
a=7k_1+r_1\\
b=7k_2+r_2
\]

Answer 36

:o

Answer 37

Since both \(5\) are between \(0\) and \(6\), they are like \(7\) sided die.

Answer 38

There are \(49\) possibilities and we can list them out...

Answer 39

\[
0^2+0^2=0
\]

Answer 40

So that is \(1/49\) so far...

Answer 41

hmm..can we do the question to which I have full solution then? same type

Answer 42

then we can come back to this if our method is right

Answer 43

Hold on, we can actually do this relatively quickly.

Answer 44

okay

Answer 45

\(7-0=7\) so no \(0, x\) combo will work other than \(0,0\)

Answer 46

Remember that the squares will only have remainders \(0,1,2,4\)

Answer 47

i lost the track
........
lets do a simple one please :|

Answer 48

Ok.

Answer 49

same ques,a+b divisible by 4

Answer 50

Okay, so \(r\) = \(0,1,2,3\)

Answer 51

There are \(4\times 4=16\) possiblities.

Answer 52

u mean that is the answer?

Answer 53

No, that is total possibilities. We need to find target possibilities now.

Answer 54

there are 16 pos of what?

Answer 55

We have: \[
1+3\\
2+2\\
3+1
\]

Answer 56

okay

Answer 57

Only those add up to \(4\)

Answer 58

But \[
0+0
\]also is dibisible by \(4\)

Answer 59

So \(1/4\) is the probability.

Does that work?

Answer 60

hmm yes

Answer 61

Is the original question solved ?

Answer 62

@wio answer to this question is PRETTY long

Answer 63

answer to the question, a+b|4 ?

Answer 64

answer is integral and a big one

Answer 65

\[\large (25C_1 \times 25C_1) + (25C_1 \times 25C_1)+25C_2\]

Answer 66

+25C2

Answer 67

(a, b ) are natural numbers <= 100
find total # of ways that a+b | 4

is that q we talking about at the moment ?

Answer 68

yes

Answer 69

Solution if anyone can explain/understand :|

Numbers are of form.....4k,4k+1,4k+2,4k+3
a+b arae of form 4k------25C2 ways

a of form 4k+1------
b of form 4k+3------
(25C1 x 25C1) ways

a of form 4K+2-----
b of form 4K+2------
(25C2 ways )

a of form 4k+3-------
b of form 4k+1-------
(25C1 x 25C1) ways

Now add both..

Answer 70

Now add all*

Answer 71

http://jsfiddle.net/2BJDc/1/

Answer 72

http://jsfiddle.net/2BJDc/2/

Answer 73

easy,
when dealing with division wid 4, lets represent all natiral numbers below 100 as multiple of 4

numbers = 4k, 4k+1, 4k+2, 4k+3
k = 0-24

Answer 74

We want a+b to be a multiple of 4,
so, a+b = 4k

Answer 75

http://jsfiddle.net/2BJDc/3/

This will let you do any function.

Answer 76

4 cases :-
case 1 :
when a and b both are multiples of 4,
a = 4k, b = 4k
since k can take values from 0 to 24, you can pick two values (a, b) in 25C2 ways

Answer 77

if above case is clear to you, other cases I dont have to explain u

Answer 78

I sort of was explaining that when I wrote: \[
0+0\\
1+3\\
2+2\\
3+1
\]

Answer 79

these are the four ways of divisible by \(4\) out of the \(4\times 4\) total ways.

Answer 80

exactly, those are the remainders we're interested - 4 cases

Answer 81

why is
0<k<24

Answer 82

cuz u want natural numbers less than 100
we represented all natural numbers using below :-
4k, 4k+1, 4k+2, 4k+3

Answer 83

wats the max value for k ?

Answer 84

u cant put k=25 there, cuz that wud give u 4*25+3 = 103

Answer 85

so always it will go to n-1? i mean if its for 7 then 7k+6?

Answer 86

Prodigious!
You need to pay attention @DLS

Answer 87

\(7k+7=7(k+1)+0\)

Answer 88

7k+7 is same as 7k

Answer 89

hmm..

Answer 90

7k+7 is same as 7k
in the world of multiples of 7 ofcourse; we're touching modular arithmetic now...

Answer 91

your a^2+b^2 |7 problem is much simpler than a+b|4 problem actually

Answer 92

How!?

Answer 93

since 7 is a prime, for it to divide (a^2+b^2), it must divide both a and b

Answer 94

once u see that, it boils down to the problem of finding all ways a+b|7

Answer 95

this is simple, cuz we have oly 1 case here

Answer 96

both a and b must be multiples of 7

Answer 97

Why?