For every positive multiple of 3, the function f(n) is defined as the

Question

For every positive multiple of 3, the function f(n) is defined as the product of all multiples of 3 from 3 to n, inclusive.
That is,
f(n) = 3 × 6 × 9 × ... × n
If q is the smallest prime factor of f(99) + 1, then q is:

A. Between 2 and 10
B. Between 10 and 20
C. Between 20 and 30
D. Between 30 and 40
E. Greater than 40

nafuzzz · Answer

Here is the answer explained:

f(99) = 3 × 6 × 9 × ... × 99
= 333 × (1 × 2 × 3 × ... × 33)
= 333 × 33!

So, f(99) + 1 = 333 × 33! + 1

For any prime p ≤ 33, p divides 33!, so f(99) + 1 ≡ 1 (mod p).
Hence, no prime less than or equal to 33 divides f(99) + 1.

Testing the next few primes greater than 33 shows that the smallest prime dividing this expression is 37.

Therefore, the smallest prime factor q is between 30 and 40.

Correct Answer: D. Between 30 and 40

2000AD · Answer

I am confused as to how you were able to factor 333 out of (3 * 6 * 9 * ... * 99) - I realize it doesnt have a bearing on the ultimate answer but that step caught my attention.

Bunuel · Answer

Should be 3^33, not 333. Each of the 33 terms (3, 6, 9, ..., 99) contributes one factor of 3, so factoring out 3 from each term gives 3^33 * (1 * 2 * 3 * ... * 33) = 3^33 * 33!.

okHedwig · Answer

Hi Sir,
I understood why the smallest Prime factor will not be less than 33, so the prime no must be greater than 33, But how are we sure that the prime no lies between 30 and 40, it could be greater than 40 too (what if no prime no between 33 &40 is factor for f(99)+1?)
So how to choose between option D & E - Please help!
Thanks

egmat · Answer

okHedwig  Here's the crucial reasoning:

What's the smallest prime greater than 33?  It's  37 .
 
  Can q be less than 37?  No! We've proven that all primes  \leq 33  divide  f(99) , so none of them can divide  f(99) + 1 . And there are no primes between  33  and  37 .
 
  What does this tell us about q?  Since  f(99) + 1 > 1 , it must have at least one prime factor. The smallest possible value for this prime factor is  37 .
 
  Therefore:   q \geq 37 , and since  30 < 37 < 40 , we know  q  is between  30  and  40 .

Hope this answers your question!

DmitryFarberMPrep · Answer

Hmm, so far no one has proved that 37 works. It's certainly the first candidate we have, since all the lower primes will go into 33!. But I don't see a convincing reason to assume that 37 goes in, and certainly a GMAT problem would not require us to assume this.

Bunuel · Answer

This is not correct. The smallest prime must be greater than 31, but how did you conclude that it is 37? In fact, the smallest prime factor of 3^33 * 33! + 1 is 41. This question is just a weak rewording of the official one here: https://gmatclub.com/forum/for-every-po ... 12521.html

For every positive multiple of 3, the function f(n) is defined as the

Prep Toolkit

Top 5 GMAT Debrief Videos

615 to 715 in 15 Days (Ria's Strategies)

More than Quant/Verbal Abilities: Speed vs. Accuracy

745 with Only Self-Prep and GMAT Club

From 555 to 765: 210-point Improvement

Perfect 805 Score Debrief by Julia

GMAT Problem Solving (PS) Questions

For every positive multiple of 3, the function f(n) is defined as the

Prep Toolkit

615 to 715 in 15 Days (Ria's Strategies)

More than Quant/Verbal Abilities: Speed vs. Accuracy

745 with Only Self-Prep and GMAT Club

From 555 to 765: 210-point Improvement

Perfect 805 Score Debrief by Julia