P is a prime number greater than 30. When P is divided by 30, the remainder is x. How many different values of x are possible?
Help! (Ambiguity problem :|)
P is a prime number greater than 30. When P is divided by 30, the remainder is x. How many different values of x are possible?
Help! (Ambiguity problem :|)
The possible values of X are 1,7,11,13,17,19,23,29;
So No. of possible values of X is 8
which can be easily determined by finding the euler totient of 30, which basically represents the number of numbers less than and CO-PRIME to 30
E.T = 30(1-1/2)(1-1/3)(1-1/5) = 8
where 2,3,5 are prime factors of 30
The possible values of X are 1,7,11,13,17,19,23,29;
So No. of possible values of X is 8
which can be easily determined by finding the euler totient of 30, which basically represents the number of numbers less than and CO-PRIME to 30
E.T = 30(1-1/2)(1-1/3)(1-1/5) = 8
where 2,3,5 are prime factors of 30
ye sab to theek h. but when is x=19 (P=49, which is not prime :|)!
correct me what i'm missing. 😞
e(7)=6
203%6=5
51%7=2
2^5%7=4
but bro cannot it b like dis:
51/7=2 remainder i.e. 2 to the power 203..again 2 to the power 3 * 2 to the power 200 which again if divided by 7 i.e. 2 to the power 3 divided by 7 will give remainder 1...so, final answer 1...isnt it a correct ans??...kindly xplain...thnks in advance...
CHEERS!!
The possible values of X are 1,7,11,13,17,19,23,29;
So No. of possible values of X is 8
which can be easily determined by finding the euler totient of 30, which basically represents the number of numbers less than and CO-PRIME to 30
E.T = 30(1-1/2)(1-1/3)(1-1/5) = 8
where 2,3,5 are prime factors of 30
Bro...altho i was able to do this sum my own way....can u elaborate on Euler thing as mentioned by you...may b d formula applicable here....thnks in advance....
CHEERS!!
ye sab to theek h. but when is x=19 (P=49, which is not prime :|)!
correct me what i'm missing. :(
Bro...altho i was able to do this sum my own way....can u elaborate on Euler thing as mentioned by you...may b d formula applicable here....thnks in advance....
CHEERS!!
@godschild: Bro 49 is not prime but there is a 79,109,139.....etc....
@snehans: If you know that list of primes even from 30-60 one can simply check the value of X , but a i explained to godschild one might miss 79,109,139,....
Also eulers remainder theorem / eulers totient is a very useful and easy concept...
i ll update some links soon but for now i learnt the methods from Wikipedia and TOTALGADHA e-book , try those...
A hotel has 50 rooms numbered 2,4,6,..100. All the rooms are initially closed. !st person walks down the corridor & changes the state (i.e. opens all closed doors, and vice versa) of all doors divisible by 1. 2nd person walks down and changes the state of all the doors divisible by 2. And so on upto 50th person. Finally, hpw many doors were left open? Which door was the second last to be closed.?
All rooms numbered having odd number of factors will remain open. So, among all no. 2,4,6,....100 which are perfect squares will remain open.
Perfect squares are 4,16,36,64,100.
Therefore, total 5 doors were left open.
98 was the second last closed door.
What is the remainder when 41^36 + 36^41 is divided by 77?
someone please explain this.
Remainder of ( 7^123 + 9^123 ) / 64 ??
Enceladus Saysyeah the cyclicity method works fine with smaller numbers but what if the question is something like 497^34526 mod 504. Then euler is the best way for it. :)
Yea ur right 😉
(7^123 + 9^123)= (7+9)*(7^122-7^121*9+7^120*9^2-....-7*9^121+9^122)
Cancel the common factor 16 from both numerator & denomenator.
(7^122-7^121*9+7^120*9^2-....-7*9^121+9^122) mod 4= (1+1+....upto 123 times)mod 4
= 123 mod 4= 3
so,Remainder of ( 7^123 + 9^123 ) / 64= 16*3= 48.
What is the remainder when 41^36 + 36^41 is divided by 77?
someone please explain this.
i am getting 0..
successive division of each term by 77 until the power of the term is reduced to 1...
so for 41^36/77.. remainder is 36
similarly for 36^41/77..remainder is 41..
so net remainder is 36+41/77 = 0
What is the remainder when 41^36 + 36^41 is divided by 77?
someone please explain this.
It should be 72.
77 = 11*7
So, we need to find remainders by 11 and 7.
For 41^36:
Remainder by 7:
41^36 => (-1)^36 => 1
Remainder by 11:
41^36 = (-3)^36 = 9^18 = (-2)^18 = 2^18
Now, 2^5 = 32 leaves remainder of -1 by 11.
So, 2^15 will leave -1. And 2^3 will leave 8. So, total = -8 = 3
So, number of form 7x+1 = 11y+3 => 36
Now, for 36^41:
Remainder by 7:
36^41 => (1)^41 => 1
Remainder by 11:
36^41 = 3^41 = 9^20 * 3 = (-2)^20 * 3 = (2^5)^4 * 3 = 1*3 = 3
So, number of form 7x+1 = 11y+3 => 36
So, total remainder of two parts = 36+36 = 72
i am getting 0..
successive division of each term by 77 until the power of the term is reduced to 1...
so for 41^36/77.. remainder is 36
similarly for 36^41/77..remainder is 41..
so net remainder is 36+41/77 = 0
How did you get for 36^41/77..remainder is 41..:shocked:
Here, 36 I am getting as a remainder...
so, ans is 36+36= 72.
this is in the form of (a^b+b^a)/(a+b)
Is there any short-cut to solve question of this form?
Hi everyone!
Find the remainder when 55^190 is divided by 153?
The answer key says 120 but I'm getting 118 as the answer.
Where did I go wrong
Hi everyone!
Find the remainder when 55^190 is divided by 153?
The answer key says 120 but I'm getting 118 as the answer.
Where did I go wrong
It is 118 only, you didn't go wrong:)
Hi everyone!
Find the remainder when 55^190 is divided by 153?
The answer key says 120 but I'm getting 118 as the answer.
Where did I go wrong
153 = 9*17
lets use c.r.t
55^190/9
e(9) = 6
55^4/9 = rem is 1
55^190/17
e(17)=16
55^14/17 = 4^14/17= 16^7/17 = -1
thus
9x+1 = 17y - 1
or 9x+2 = 17y
x=13 and y=7 satisfy
thus rem = 9*13 + 1= 118
Yeah! You didn't go wrong. It's 118 only. 😃
Thanks 