가우스는 변의 개수가 페르마 소수인 정다각형은 눈금 없는 자와 컴퍼스만으로 작도가 가능하다는 것을 증명했다. 가우스는 정수론을 수학의 중요한 분야로 만들었다. 가우스는 모든 자연수는 3개의 삼각수들로 나타날 수 있음을 증명해 보였다.




최소제곱법은 측정한 값을 바탕으로 한 결과의 제곱합이 최소가 되는 값을 구하여, 측정 결과를 처리하는 방법이다. 이 방법의 발견에 대한 선후 논쟁이 가우스와 아드리앵마리 르장드르 사이에서 일어났다. 최초의 발표는 르장드르가 1806년에 한 것이지만, 가우스는 1795년에 그것을 발견했다고 주장했다. 가우스가 이러한 논쟁을 싫어했기 때문에 심각한 학문적 논쟁은 편지들과 사후에 발견된 논문들을 통해서 가우스가 먼저 발견했다는 것이 밝혀졌다.




그의 저서 《산술 연구》(라틴어: Disquisitiones Arithmeticae 디스퀴시티오네스 아리트메티카이[*])는 일반적인 정수론의 용어에 있어서는 혁명적 개선이다. 정수의 나누어떨어지는 개념의 처리를 매우 단순화 시킨 합동 산술과 합동식 등을 만들어 냈다. 그리고 1보다 큰 모든 자연수는 소인수들의 순서를 무시하면 유일한 방법으로 소인수 분해된다는 산술의 기본 정리를 최초로 증명했고, 레온하르트 오일러와 장 르 롱 달랑베르에 의해서 발표되었지만 엄격하게 증명되지 못했던 이차 상호 법칙을 증명하였다. 이러한 성과를 포함하고 있는 가우스의 《산술 연구》는 정수론의 발달에 크게 기여하였다.




1799년 박사 학위 논문으로, "대수방정식의 근의 존재 증명"을 저술하였다. 1변수의 모든 유리정함수(integral rational algebraic function)는 1차 또는 2차의 소인수로 분해된다는 것을 보였다. 요한 카를 프리드리히 가우스는 복소수 범위에서, 상수가 아닌 모든 일변수 다항식은 적어도 하나의 근을 가진다는 대수학의 기본 정리를 증명했다. 장 르 롱 달랑베르를 비롯한 수학자들은 요한 카를 프리드리히 가우스에 앞서 잘못된 증명들을 내놓았는데, 가우스는 논문에서 달랑베르의 증명을 비판하였다. 오늘날의 관점에서는 조르당 곡선 정리를 증명 없이 사용한 가우스의 증명 역시 엄밀하지 못했지만, 요한 카를 프리드리히 가우스는 그 뒤에 세 개의 다른 증명들을 내놓았다. 1849년의 마지막 증명은 오늘날에도 엄밀하게 여겨지며, 가우스의 증명들을 통해서 복소수의 개념이 명확하게 정의되었다.




1801년에는 1798년 완성된 《산술 연구》가 출판되었다. 이 책에서 요한 카를 프리드리히 가우스는 합동 산술에 대하여 서술하였고, 이차 상호 법칙을 최초로 증명하였다. 주세페 피아치가 소행성 세레스를 발견하자, 가우스는 세레스의 궤도를 계산하였고, 가우스가 예측한 지점에서 세레스가 재발견되었다. 이로 인하여 요한 카를 프리드리히 가우스는 과학계에 유명세를 타게 되었다. 가우스는 브라운슈바이크 공작으로부터의 장학금에 의존하였는데, 1807년 괴팅겐 천문학 관측소의 박사 겸 괴팅겐 대학교 천문학과 교수로 임명되어서, 재정적으로는 안전하게 되었다.