We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • HackerRank Home

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Hiring developers?
  1. Prepare
  2. Mathematics
  3. Number Theory
  4. Primitive Problem

Primitive Problem

Problem
Submissions
Leaderboard
Discussions
Editorial

We define a primitive root of prime number to be some integer satisfying the property that all values of where are different.

For example: if , we want to look at all values of in the inclusive range from to . For , the powers of (where is in the inclusive range from to ) are as follows:

Note that each of these evaluates to one of the six distinct integers in the range .

Given prime , find and print the following values as two space-separated integers on a new line:

  1. The smallest primitive root of prime .
  2. The total number of primitive roots of prime .

Need Help? Check out a breakdown of this process at Math Stack Exchange.

Input Format

A single prime integer denoting .

Constraints

Output Format

Print two space-separated integers on a new line, where the first value is the smallest primitive root of and the second value is the total number of primitive roots of .

Sample Input 0

7

Sample Output 0

3 2

Explanation 0

The primitive roots of are and , and no other numbers in satisfy our definition of a primitive root. We then print the smallest primitive root () followed by the total number of primitive roots ().

Author

bayleef

Difficulty

Easy

Max Score

20

Submitted By

1979

Need Help?


View discussions
View editorial
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy