SIMPLE RNGs, that I was referring to, are usually working like xi+1 = a*xi+b mod m,

LCGs are far from the only "simple [P]RNGs"; see also ICGs (CIGs) for another class of simple PRNG with some interesting properties, but the same max.period == mod(M) limitation.

But there are other, even simpler (addition/subtraction/mod only) classes that do not. Eg. this 8-bit generator (thus M=256) displays near perfect randomness by a variety of measures, but has a periodicity of nearly M²:

#! perl -slw
use strict;
use 5.010;
use Data::Dump qw[ pp ]; $Data::Dump::WIDTH = 2000;
use constant {
    BIGPRIME => 251,
    SMALLPRIME => 241,
};

sub x{
    state $r = BIGPRIME;
    state $t = 0;
    $r += (++$t % SMALLPRIME) == 0 ? BIGPRIME : - SMALLPRIME;
    $r %= 256;
}

my @freqs;
my $bytes = '';
for( 1 .. 1e6 ) {
    my $r = x();
    $bytes .= chr( $r );
    ++$freqs[ $_ ][ $r & ( 2**$_ -1 ) ] for 0 .. 8;
}
pp \@freqs;
print STDERR 'Ones: ',  unpack '%32b*', $bytes;
my $first256 = substr $bytes, 0, 256;
if( my $p = 1 + index $bytes, $first256, 1 ) {
    print STDERR "The first sequence is repeated at position $p";
}

__END__
C:\test>primesQ >log
[
  [1000000],
  [500000, 500000],
  [250000, 250000, 250000, 250000],
  [125000, 125001, 125000, 124999, 125000, 124999, 125000, 125001],
  [62500, 62501, 62500, 62499, 62499, 62499, 62500, 62501, 62500, 6250
+0, 62500, 62500, 62501, 62500, 62500, 62500],
  [31251, 31250, 31251, 31249, 31250, 31249, 31250, 31250, 31250, 3125
+0, 31250, 31251, 31250, 31251, 31249, 31251, 31249, 31251, 31249, 312
+50, 31249, 31250, 31250, 31251, 31250, 31250, 31250, 31249, 31251, 31
+249, 31251, 31249],
  [15625, 15626, 15626, 15623, 15625, 15626, 15625, 15624, 15626, 1562
+6, 15624, 15625, 15626, 15626, 15623, 15625, 15626, 15626, 15623, 156
+25, 15626, 15625, 15624, 15626, 15626, 15624, 15624, 15626, 15626, 15
+623, 15625, 15626, 15626, 15624, 15625, 15626, 15625, 15623, 15625, 1
+5626, 15624, 15624, 15626, 15626, 15624, 15625, 15626, 15626, 15623, 
+15625, 15626, 15625, 15623, 15625, 15626, 15625, 15624, 15626, 15626,
+ 15623, 15625, 15626, 15626, 15623],
  [7814, 7813, 7811, 7812, 7815, 7812, 7811, 7813, 7814, 7811, 7812, 7
+815, 7813, 7811, 7812, 7814, 7812, 7812, 7813, 7814, 7811, 7812, 7814
+, 7813, 7811, 7813, 7814, 7812, 7812, 7813, 7813, 7811, 7813, 7814, 7
+813, 7811, 7813, 7813, 7811, 7812, 7814, 7813, 7811, 7813, 7814, 7812
+, 7811, 7814, 7813, 7812, 7812, 7814, 7812, 7810, 7813, 7815, 7812, 7
+811, 7814, 7813, 7811, 7812, 7815, 7812, 7811, 7813, 7815, 7811, 7810
+, 7814, 7814, 7811, 7812, 7815, 7812, 7810, 7813, 7815, 7811, 7811, 7
+814, 7814, 7810, 7811, 7815, 7813, 7810, 7813, 7815, 7811, 7810, 7814
+, 7814, 7810, 7812, 7815, 7813, 7810, 7812, 7815, 7812, 7810, 7814, 7
+814, 7810, 7811, 7815, 7813, 7810, 7813, 7815, 7812, 7810, 7813, 7814
+, 7811, 7811, 7815, 7813, 7810, 7812, 7815, 7812, 7810, 7814, 7814, 7
+811, 7811],
  [3907, 3907, 3906, 3907, 3908, 3907, 3906, 3906, 3907, 3905, 3905, 3
+907, 3906, 3905, 3906, 3907, 3907, 3907, 3907, 3908, 3906, 3906, 3907
+, 3906, 3905, 3906, 3906, 3906, 3906, 3906, 3907, 3906, 3907, 3908, 3
+907, 3906, 3907, 3906, 3906, 3906, 3906, 3906, 3905, 3906, 3907, 3906
+, 3906, 3908, 3907, 3907, 3907, 3907, 3906, 3905, 3906, 3907, 3905, 3
+905, 3907, 3906, 3906, 3907, 3908, 3907, 3906, 3907, 3908, 3905, 3905
+, 3907, 3906, 3905, 3906, 3907, 3906, 3905, 3907, 3908, 3906, 3906, 3
+908, 3907, 3905, 3906, 3907, 3906, 3904, 3906, 3907, 3905, 3905, 3908
+, 3907, 3906, 3907, 3908, 3907, 3905, 3906, 3907, 3905, 3904, 3907, 3
+906, 3905, 3906, 3908, 3907, 3906, 3907, 3908, 3906, 3905, 3907, 3906
+, 3905, 3905, 3907, 3906, 3905, 3906, 3908, 3906, 3906, 3908, 3907, 3
+906, 3906, 3907, 3906, 3905, 3905, 3907, 3905, 3905, 3907, 3907, 3906
+, 3907, 3908, 3907, 3906, 3906, 3907, 3905, 3905, 3906, 3906, 3905, 3
+906, 3907, 3907, 3906, 3907, 3908, 3906, 3906, 3907, 3906, 3905, 3906
+, 3906, 3906, 3905, 3906, 3907, 3
905, 3906, 3908, 3907, 3906, 3907, 3907, 3906, 3905, 3906, 3906, 3905,
+ 3905, 3907, 3906, 3905, 3907, 3908, 3907, 3906, 3907, 3907, 3905, 39
+05, 3907, 3905, 3905, 3906, 3907, 3906, 3905, 3907, 3908, 3906, 3906,
+ 3908, 3906, 3905, 3906, 3907, 3905, 3905, 3906, 3907, 3905, 3905, 39
+08, 3907, 3906, 3907, 3908, 3906, 3905, 3906, 3907, 3904, 3905, 3907,
+ 3906, 3905, 3906, 3908, 3907, 3906, 3907, 3908, 3905, 3905, 3907, 39
+06, 3904, 3906, 3907, 3906, 3905, 3906, 3908, 3906, 3906, 3908, 3907,
+ 3905, 3906, 3907, 3906, 3904, 3906, 3907, 3905, 3905],
]

Ones: 3999980
The first sequence is repeated at position 61697
[download]